1D monochrome Link-a-Pix solvability

Question

Background

Link-a-Pix is a puzzle on a rectangular grid, where the objective is to reveal the hidden pixel art by the following rules:

• Connect two cells with number N with a line spanning N cells, so that the two cells are at the two ends of the line.
• The number 1 is considered connected to itself (which makes it an exception to the rule of "connect two cells").
• Two different lines are not allowed to overlap.
• The puzzle is solved when all the given numbers on the grid are connected by the above rules. There may be some unused cells after the puzzle is solved.

The following is an example puzzle and its unique solution.

(Source: The NP completeness of some lesser known logic puzzles, 2019)

A Link-a-Pix puzzle often involves colors and reveals a colorful picture when solved, but we will ignore them for simplicity, and focus on "monochrome" puzzles.

Task

In this challenge, the puzzle is limited to one dimension, or equivalently, a grid of height 1.

Given a 1D Link-a-Pix puzzle instance, check if it has a solution or not. A puzzle instance is given as a sequence of non-negative integers, where each cell with a given number contains that number and the others contain 0.

For output, you can choose to

1. output truthy/falsy using your language's convention (swapping is allowed), or
2. use two distinct, fixed values to represent true (affirmative) or false (negative) respectively.

Test cases

Truthy
[0, 1, 0, 4, 0, 0, 4, 2, 2, 0, 1]
[0, 0, 0, 0] (the puzzle is solved vacuously)
[12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 12] (multi-digit numbers must be supported)
[2, 2, 0, 2, 2, 2, 2, 1, 2, 2] (suggested by tsh)

Falsy
[0, 4, 0, 3, 4, 3, 0] (two lines cannot overlap)
[3, 0, 3, 0, 3, 1, 3, 0, 3, 0, 3]
[1, 0, 2, 2, 2, 2, 2, 0, 1] (one of 2s have nowhere to connect)
[3, 3, 3, 3] (suggested by tsh)
[3, 3, 3]
[0, 0, 4, 4] (the 4s must begin and end the 4-cell line)
[12, 2] (multi-digit numbers must not be treated as multiple single-digit numbers)

Answer 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)

Try it online!

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

Answer 2

Jelly, 15 bytes

Ṁ1;Ṭ×Ʋ€ṚœṣF¥ƒ⁸Ẹ

Try it online!

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Ẹ

Try it online!

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Ẹ

Try it online!

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

Answer 3

J, 33 bytes

0(-.~-:2#_2-~/\I.@:<)1&(1+=j.<)#]

Try it online!

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?

Answer 4

J, 53 bytes

([:*/2|[:+/@:*;.1,~&1)*[:(-.&0-:1+2#_2-~/\I.@:*)]*1&<

Try it online!

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 0
  

• I.@:* Signum and find indexes (ie, indexes of everything non-zero):

  3 6 7 8
  

• _2-~/\ Deltas of consecutive (non-overlapping) pairs:

  3 1
  

• 1+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 no 1s between any of the pairs?

  _1 1 _1 3 _1 _1 3 1 1 _1 1
  

Answer 5

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

Try it online!

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 drop and take can 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

Answer 6

JavaScript (V8), 45 bytes

a=>a.some(v=>c?a*!--c-v:(c=a=v)&&0*--c,c=0)|c

Try it online!

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

Answer 7

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\$.

Answer 8

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.

Answer 9

Jelly, 37 bytes

’ȯ€Ø1F‘µTịĖs2ạ;2ị$$}¥/€‘1¦€2ị$ÐḟUƑƇ$Ƒ

Try it online!

Uses Jonah's trick to replace 1 with 2, 2; credit for that to him here.

Answer 10

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.

Answer 11

Pip, 38 37 bytes

!qR` [01]\b|( \d+)( 0)*\1`{(sNa)-b|x}

Regex solution. Takes input from stdin as a space-separated list of integers with a single leading space. Try it here! Alternately, here's a 39-byte version in Pip Classic: Try it online!

If the numbers were single-digit only, this could be 25 bytes:

!qR`0|1|(\d)0*\1`{#a-b|x}

Try it online!

Explanation

!qR` [01]\b|( \d+)( 0)*\1`{(sNa)-b|x}
 q                                     Read a line of stdin
  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:
                            sNa         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 [falsey], or the second
                                        branch was taken and the length is correct,
                                        in which case the expression is 0 [falsey],
                                        or the length is incorrect, in which case
                                        the expression is nonzero [truthy])
                                  |     OR
                                   x    empty string
                                       (The effect is to remove correctly formatted lines
                                       from the input; incorrectly formatted lines are
                                       either left unchanged or replaced with 1's)
!                                      Return 1 if the resulting string is empty, else 0

---

Here's a non-regex solution in 40 bytes that takes the list as command-line arguments and outputs via stderr (error message = falsey, no error = truthy):

W#Y@g2>y?POg#g>=y=g@Dy=$+g@\,y?g@>:@g;Vk

Try it online!

Answer 12

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.

Answer 13

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)

Answer 14

sed -E, 50 bytes

My sed is rusty and I’m not totally happy with this, but c’est la vie. Takes input on stdin with a trailing space, prints T or F.

s/\b1 /&&/g
s/([0-9]+ )(0 )*\1//g
/[^0 ]/{cF
n}
cT

Attempt This Online!