| Bytes | Lang | Time | Link |
|---|---|---|---|
| 033 | Pip | 210525T053435Z | DLosc |
| 021 | 05AB1E | 210727T133627Z | Kevin Cr |
| 131 | SWIProlog | 210526T174345Z | Marijn |
| 015 | Jelly | 210524T083001Z | Nick Ken |
| 018 | Brachylog | 210525T032027Z | DLosc |
| 053 | J | 210524T040540Z | Jonah |
| 041 | JavaScript ES6 | 210524T160842Z | Arnauld |
| 061 | Haskell | 210524T180920Z | AZTECCO |
| 045 | Retina 0.8.2 | 210524T090553Z | Neil |
| 030 | Charcoal | 210524T093034Z | Neil |
| 033 | J | 210524T073851Z | Bubbler |
| 037 | Jelly | 210524T012408Z | hyperneu |
| 045 | JavaScript V8 | 210524T012410Z | tsh |
Pip, 38 37 33 bytes
!aR` [01]\b|( \d+)( 0)*\1`(sN_)-B
Regex solution. Takes input from the command line as a space-separated list of integers with a single leading space (must be quoted so it's treated as a single argument). Attempt This Online!
If the numbers were single-digit only, this could be 21 bytes (taking input with no separator):
!aR`0|1|(\d)0*\1`#_-B
Explanation
!aR` [01]\b|( \d+)( 0)*\1`(sN_)-B
a Command-line argument
R` ` Find all non-overlapping matches of this regex:
[01]\b A single 0 or 1
| or
( \d+) Any other number
( 0)* followed by zero or more 0's
\1 followed by the same number again
Replace each match with this function:
sN_ The number of spaces in the match
( )-B minus the value of the first capture group
(Either the first branch was taken, in which
case the capture group is unused and the
expression is nil, or the second
branch was taken and the length is correct,
in which case the expression is 0,
or the length is incorrect, in which case
the expression is nonzero)
The effect is to replace correctly formatted
lines from the input with either 0 or empty
string; incorrectly formatted lines are either
left unchanged or replaced with nonzero numbers
! Return 1 if the resulting string is falsey
(either empty or consists entirely of 0s);
or if truthy, return 0
05AB1E, 21 bytes
.œεεćsOyθyg)Ëy2‹P~]Pà
Can probably be shorted, but this will do for now.
Try it online or verify all test cases.
Explanation:
.œ # Get all partitions of the (implicit) input-list:
ε # Map over each partition:
ε # Map over each inner part-list:
ć # Check if the first item of the list,
sO # the sum of the list minus its first item,
yθ # the last item of the list,
yg # and the length of the list,
)Ë # are all four equal to each other
~ # Or
y P # Check if all items in the list
2‹ # are either 0 and/or 1
] # Close both maps
P # Check if all parts in a partition were truthy (product)
à # Check if any partition is truthy (max)
# (after which the result is output implicitly)
SWI-Prolog, 131 bytes
t([]). t(L):-append(Q,W,L),g(Q),t(W). g([0]). g([1]). g(W):-append([H|L],Q,W),append(L,[H],Q),sum_list(L,0),length(L,X),X is H/2-1.
Prolog is hard to golf but it is ideal for this kind of problem.
Explanation:
% recursion stop condition
t([]).
% a testcase succeeds if the first part Q of the list is good
% and the second part W recursively also succeeds
t(L):-append(Q,W,L),g(Q),t(W).
% base cases: 0 and 1 are both good
g([0]).
g([1]).
% a longer list is good if it consists of the pattern HLLH
g(W):-append([H|L],Q,W),
append(L,[H],Q),
% and L consists of zeros
sum_list(L,0),
% and the length of L is half the border value minus 1
length(L,X),
X is H/2-1.
Jelly, 15 bytes
Ṁ1;Ṭ×Ʋ€ṚœṣF¥ƒ⁸Ẹ
A monadic link taking a list of integers and returning 0 for those that have a solution and 1 for those that don’t.
Explanation
Ṁ | Max
Ʋ€ | For each integer z from 1 to this:
1; | - Prepend 1
Ṭ | - Untruthy (so [1, 4] becomes [1, 0, 0, 1]
× | - Multiply by z
Ṛ | Reverse (so that the largest lists come first)
¥ƒ⁸ | Reduce using the original list as the starting point and the following two links as a dyad:
œṣ | - Split at matching substrings
F | - Flatten
Ẹ | Finally check if any non-zero values remain
Second approach
Jelly, 19 bytes
Ị¬Ts2r/€ịµF^Ø.¦L)FẸ
Explanation
Ị | Insignificant (<= 1)
¬ | Not
T | Truthy indices
s2 | Split into pairs
r/€ | For each, make a range between the two values (returns asingle value if there isn’t a pair, which will knly be seen if no solution
ị | Index into original input
µ | Start a new monadic chain
) | For each:
F | - Flatten (handles situation with single value)
^Ø.¦ | - Xor the first and last values with:
L | The length of that set
F | Flatten
Ẹ | Any
Original approach
Jelly, 23 bytes
ṣḊLḂȯm2;Ẉ+2nʋ¥ɗʋɗⱮỊÐḟFẸ
In brief, tries splitting the list at every occurrence of each integer >=2 and then tests the following for each of those splits:
- The length is odd (I.e. there was an even number of that value originally)
- There are no non-zero integers in between the pairs of that integer
- The lengths of each run of zeros is equal to the integer minus 2
If any test fails for any split then the puzzle is not-solvable.
Explanation
ɗⱮỊÐḟ | Use each of the input except 0s and 1s as the right argument y of the following (with the original argument x as the left argument):
ṣ | - Split x at y (-> z)
ʋ | - Following as a dyad using arguments z and y:
Ḋ | - Remove first element
L | - Length
Ḃ | - Odd
ȯ ɗ | - Or the following as a dyad with arguments z and y:
m2 | - Take every other sublist starting at the first (-> w)
¥ | - Following as a dyad using arguments (w, y)
; ʋ | - Concatenate to the following using arguments (w, y)
Ẉ | - Lengths of w
+2 | - Add 2 (vectorises)
n | - Not equal to y
F | Finally, flatten all lists
Ẹ | Check whether any are non-zero
Brachylog, 19 18 bytes
~c{+<2|h.~l?↔?b+}ᵐ
Try it online! (Times out for falsey test cases longer than seven elements.)
Explanation
Checks every possible partition of the list until it finds a valid solution.
~c Construct a list of lists whose concatenation is the input list
{ }ᵐ The following predicate must succeed for each sublist:
Either:
+ The sum of the sublist
<2 is less than 2
(in which case it's a bunch of 0's and at most one 1)
| Or:
h The first element of the sublist
. (which will be the output of this predicate)
~l? is the length of the sublist
↔ and the sublist reversed
? is the same as itself
b and the sublist with first element removed
+ summed
equals the output of this predicate (previously declared
to be the first element of the sublist)
The second branch succeeds iff the sublist is a valid would-be line of the form \$[N, 0, \cdots, 0, N]\$:
- The head of the sublist is \$N\$.
- Its length is also \$N\$, so it can be filled in to form a line of \$N\$ numbers.
- It is a palindrome, which means its tail is also \$N\$.
- The sum of everything but the head is \$N\$. Since the tail is \$N\$ and all the numbers are nonnegative, all the numbers in the middle must be \$0\$.
J, 53 bytes
([:*/2|[:+/@:*;.1,~&1)*[:(-.&0-:1+2#_2-~/\I.@:*)]*1&<
This is the idea for the approach Bubbler's answer improves and refines. I consider that answer the "final draft" J answer. Aside from making use of some nice J tricks, it also eliminates the need for doing a separate check for "ones in the middle". Previous versions of this answer had similar ideas, but each of them failed on some test cases, whereas Bubbler's solution irons out all the problems.
Consider 0 1 0 4 0 0 4 2 2 0 1:
]*1&<Convert ones to zeros:0 0 0 0 4 0 0 4 2 2 0 0 0I.@:*Signum and find indexes (ie, indexes of everything non-zero):3 6 7 8_2-~/\Deltas of consecutive (non-overlapping) pairs:3 11+2#Duplicate in place and add 1:4 4 2 2-.&0- Does that equal the original input without zeroes or ones? (yes, in this case)4 4 2 2([:*/2|[:+/@:*;.1,~&1)*Are there also no1s between any of the pairs?_1 1 _1 3 _1 _1 3 1 1 _1 1
JavaScript (ES6), 41 bytes
Returns false for valid or true for invalid.
a=>a.some(p=(x,i)=>--p>0?x:a[i+x-1]^=p=x)
Commented
a => // a[] = input
a.some(p = // start with p NaN'ish
(x, i) => // for each value x at position i in a[]:
--p > 0 ? // decrement p; if it's positive:
x // make sure that we have x = 0
// (because we're currently over a connection 'line')
: // else:
a[ // XOR the entry at ...
i + x - 1 // ... i + x - 1 ...
] //
^= p = x // ... with x; and set p = x
// this must give 0 if the puzzle is valid
) // end of some()
The trickiest case is when a \$0\$ is reached at position \$i\$ and we're currently outside a connection (i.e. \$p\le0\$), which causes the entry at \$i-1\$ to be XOR'ed with \$0\$. If the puzzle is valid, this will always result in \$0\$ as expected because:
- if \$i=0\$, we do
undefined ^ 0 - if \$i>0\$, the entry at \$i-1\$ either was already set to \$0\$ or was cleared by the previous XOR
Haskell, 64 61 bytes
f[]=1>0
f(h:t)|r<-drop(h-1)t=[a`div`h*h|a<-[2..h]]++r==t&&f r
f[]=1>0 - if we reach end is solvable: output True
f(h:t)= - head : tail
[a`div`h*h|a<-[2..h]]
- we build the tail of h-block we expect
==take(h-1)t
- and compare with the actual one
&&(f$drop(h-1)t) - then continue
- abusing the fact that
dropandtakecan take negative amount (behaving like 0) on tail to handle both 0 and 1 - edit : concatenaing expected with rest of list and compared to rest of list
Retina 0.8.2, 52 45 bytes
$
,
\d+
$*
1?,|(1(1)+)(?<-2>,)+\1,(?(2)^)
^$
Try it online! Link includes test cases. Edit: Saved 7 bytes thanks to @tsh. Explanation:
$
,
Add a trailing comma so that all numbers are followed by commas.
\d+
$*
Convert the numbers to unary.
1?,|(1(1)+)(?<-2>,)+\1,(?(2)^)
Match all cases of either 0 or 1 followed by a comma, or a number n+1 repeated twice with n commas between (which represents n-1 empty cells) and one following. A .NET balancing group is used to ensure the relationship between the numbers and the number of commas.
^$
Check to see whether everything was matched.
Charcoal, 30 bytes
¹Ｗθ«≔⊟θι¿›ι¹¿∨Φ⁻ι²∧θ⊟θ¬∧θ⁼ι⊟θ⎚
Try it online! Link is to verbose version of code. Outputs a Charcoal boolean i.e. - for affirmative, nothing for negative. Explanation:
¹
Assume a solution exists.
Ｗθ«≔⊟θι
Loop over the cells (in reverse order, not that it matters here).
¿›ι¹
If the last cell n was greater than 1, then...
¿∨Φ⁻ι²∧θ⊟θ¬∧θ⁼ι⊟θ
... if any of the next n-2 cells is nonzero, or the following cell is not n or does not exist, then...
⎚
... clear the canvas, because there is no solution.
J, 33 bytes
0(-.~-:2#_2-~/\I.@:<)1&(1+=j.<)#]
A large part is reused from Jonah's solution, but this solution adds an idea and a J-specific black magic of combining j. with #.
A high-level view of the algorithm
Example input: 0 1 0 4 0 0 4 2 2 0 1
Insert a 1 after ones, and a 0 after other nonzeros (call it X):
0 1 1 0 4 0 0 0 4 0 2 0 2 0 0 1 1
1) Nonzero indices of X:
1 2 4 8 10 12 15 16
Non-overlapping pairwise difference:
(2-1),(8-4),(12-10),(16-15) = 1 4 2 1
Duplicate each number (call it Y):
1 1 4 4 2 2 1 1
2) Remove zeros from X (call it Z):
1 1 4 4 2 2 1 1
Do Y and Z agree? Yes.
Why this works
First, note that Z, which is simply X without zeros, should agree with something duplicated. This means the paired non-zero numbers in X should have the same value (and X cannot have any unpaired value at the end). This holds iff the nonzeros in the original input can be paired in the Link-a-Pix way, ignoring the distances.
Then look at Y, which is generated from the paired distances between nonzero numbers. Y = Z means that the numbers forming a pair must be equal to the distance between them. The process of computing X precisely makes the distance between two n's equal to n (by duplicating the ones and adding a distance of 1 for the others).
How the code works
When given a complex number a+bi as the left arg of #, the corresponding item is replicated a times and then b fill elements are inserted. It is like APL's / and \ combined, and as far as I'm aware, it is at least not very straightforward to do the same in other languages (APL-like or not).
0(-.~-:2#_2-~/\I.@:<)1&(1+=j.<)#] NB. Input: vector of integers
1&(1+=j.<)#] NB. Construct X:
1&( = ) NB. For each item, 1 if equal to 1, 0 otherwise
1&( <) NB. For each item, 1 if greater than 1, 0 otherwise
1+ j. NB. Compute complex numbers (a, b) -> (a+1) + bi
#] NB. As left arg of #, duplicate 1s and insert a 0 after >1s
0(-.~-:2#_2-~/\I.@:<) NB. Test if Y = Z:
0( 2#_2-~/\I.@:<) NB. Construct Y:
0( I.@:<) NB. Indices of nonzero items of X
_2-~/\ NB. Non-overlapping pairwise differences
2# NB. Duplicate each number
0(-.~ ) NB. Construct Z: Remove zeros from X
-: NB. Do Y and Z agree?
Jelly, 37 bytes
’ȯ€Ø1F‘µTịĖs2ạ;2ị$$}¥/€‘1¦€2ị$ÐḟUƑƇ$Ƒ
Uses Jonah's trick to replace 1 with 2, 2; credit for that to him here.
JavaScript (V8), 45 bytes
a=>a.some(v=>c?a*!--c-v:(c=a=v)&&0*--c,c=0)|c
Output falsy if solutions exist.
a=> // `a` is the given input array
a.some( // try to find out some value violate spec
v=> // `v` is current value
c? // `c` is count down since last non-zero
a*!--c-v: // if c=1, we need to close the segment
// with value equals to previous `a`
// if c>1, we need the value to be 0
// if `v` is not what we want, `some` returns true
// also count down `c`
(c=a=v)&& // if c=0 and v=0, ignore current value
// if c=0 and v>0, assign `v` to `a` and `c`
0*--c, // count down c
// also return something falsy
c=0) // count down is initialized to 0
|c // test if there is an unmatched number left