24
\$\begingroup\$

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)
\$\endgroup\$
3
  • \$\begingroup\$ @DLosc Your understanding is correct, and I edited the first rule to reflect the point. \$\endgroup\$
    – Bubbler
    May 25 at 0:41
  • \$\begingroup\$ @DLosc Yes. A typical Link-a-Pix puzzle instance often has numbers higher than 9, and there's no reason to assume otherwise here. \$\endgroup\$
    – Bubbler
    May 25 at 6:47
  • \$\begingroup\$ Ok. I added some test cases to cover those clarifications. Feel free to change them if you like. \$\endgroup\$
    – DLosc
    May 25 at 18:39

13 Answers 13

10
\$\begingroup\$

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
\$\endgroup\$
1
  • \$\begingroup\$ This is lovely. \$\endgroup\$
    – Jonah
    May 24 at 22:33
7
\$\begingroup\$

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
\$\endgroup\$
6
\$\begingroup\$

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?
\$\endgroup\$
2
  • \$\begingroup\$ First time seeing j. + # in the wild. Really nice! \$\endgroup\$
    – xash
    May 24 at 8:18
  • \$\begingroup\$ I had forgotten about j. + # too. This is the implementation my idea deserves! \$\endgroup\$
    – Jonah
    May 24 at 13:33
5
\$\begingroup\$

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
    
\$\endgroup\$
4
  • \$\begingroup\$ Fails at 0 1 0 4 0 0 3 2 2 0 1 (should be false but returns true) because it does not check the 2nd value of the pair. I think your previous code (2#ing the right side instead of _2{.\ing the left) is correct. \$\endgroup\$
    – Bubbler
    May 24 at 5:52
  • \$\begingroup\$ Scrap the last comment, the 2# solution fails at 2 1 1 2 because it cannot distinguish 2s from 1s. \$\endgroup\$
    – Bubbler
    May 24 at 6:04
  • \$\begingroup\$ Yeah it's just flawed right now. I have one more idea, if that doesn't work I'll need to delete and revisit tomm. \$\endgroup\$
    – Jonah
    May 24 at 6:06
  • \$\begingroup\$ Fixed with an explicit check for "ones in the middle" which is way too long. Will try to get rid of it tomorrow. \$\endgroup\$
    – Jonah
    May 24 at 6:29
4
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
3
\$\begingroup\$

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\$.
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 30 bytes

¹Wθ«≔⊟θι¿›ι¹¿∨Φ⁻ι²∧θ⊟θ¬∧θ⁼ι⊟θ⎚

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.

Wθ«≔⊟θι

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\begingroup\$ Sadly, that nice idea had a bug. It fails on, eg, 2 1 2. So I had to delete it and the fix was not as nice. \$\endgroup\$
    – Jonah
    May 24 at 5:17
  • \$\begingroup\$ The fix was to duplicate the ones like before, but without converting them to twos first, and then update the code that adds 1 to the deltas to only do so for numbers greater than 1. \$\endgroup\$
    – Jonah
    May 24 at 5:19
  • \$\begingroup\$ Ok, turned out to be salvagable -- was able to shave it back down almost as low as before. \$\endgroup\$
    – Jonah
    May 24 at 5:28
  • \$\begingroup\$ @Jonah Ah, I see, that's unfortunate. Well, glad you got it working - I think I'm just going to scrap the port for now and if I feel like it I might try to update it later. \$\endgroup\$
    – hyper-neutrino
    May 24 at 5:31
1
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ I don't understand Retina, but maybe 51 bytes? \$\endgroup\$
    – tsh
    May 24 at 9:50
  • \$\begingroup\$ And maybe (1(1)+)(?<-2>,)+\1,(?(2)^)? (I'm not sure what is going, actually.) \$\endgroup\$
    – tsh
    May 24 at 10:05
  • \$\begingroup\$ @tsh I actually started with something similar to that, but I over-thought it and ended up with the wrong golf. As for the second golf, that's just carelessness on my part, thanks. \$\endgroup\$
    – Neil
    May 24 at 10:51
1
\$\begingroup\$

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!

\$\endgroup\$
1
\$\begingroup\$

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.
\$\endgroup\$
1
\$\begingroup\$

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)
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.