29
\$\begingroup\$

I recently found this game and have been enjoying it. Basically, there is a grid of colored tiles and you act by clicking on empty spaces. When you click an empty space, the first tile (if any) in each of the four axis-aligned directions is selected. If any color appears more than once, all tiles of that color are destroyed (and if it hits two of one color and two of another, all four are destroyed).

See the following example:

. . R . .      . . . . .      . . . . .
R---x G .      . . . G .      . . . . .
. . | . .  =>  . . . | .  =>  . . . . .
. G | . R      . G---x R      . . . . R
. . R . .      . . . . .      . . . . .

The game is played on a time limit and clicking a space that does nothing will incur a time penalty, but for this challenge, I am just interested in one thing: can I clear the entire grid?

For example, in this grid, two clicks are enough to clear the grid:

. R . .
. B . B
. R . .

Clicking between the Bs opens a space between the Rs that can be clicked to finish it.

On the other hand, in this grid, there is no way to eliminate all tiles:

G . G . G

If you click between the right two Gs, then you can't eliminate the left one, and same for the other direction.


Given a grid represented as any reasonable format (for example, a matrix of non-negative integers where spaces are 0 is what I predict will be most common), output whether or not the grid can be cleared (refer to the consensus for output format).

You may assume there will be no more than 9 colors; this is so that input can be taken as a list of strings of digits.


Here are some example test cases. The following are all clearable:

. R . G
B . B .
. R . G

[[0, 1, 0, 2], [3, 0, 3, 0], [0, 1, 0, 2]]

. R G .
R . . G
. R G .

[[0, 1, 2, 0], [1, 0, 0, 2], [0, 1, 2, 0]]

. R . G
R . G R
. R . .

[[0, 1, 0, 2], [1, 0, 2, 1], [0, 1, 0, 0]]


R G . G
G R . .
. . R G
G . G R

[[1, 2, 0, 2], [2, 1, 0, 0], [0, 0, 1, 2], [2, 0, 2, 1]]

The following are not:

. R G .
G . . R
G . . R
. R G .

[[0, 1, 2, 0], [2, 0, 0, 1], [2, 0, 0, 1], [0, 1, 2, 0]]

R . R . R

[[1, 0, 1, 0, 1]]

R . .
. . R
. R .

[[1, 0, 0], [0, 0, 1], [0, 1, 0]]

R G R G
[[1, 2, 1, 2]]

. R B .
R . G R
. G B .
[[0, 1, 3, 0], [1, 0, 2, 1], [0, 2, 3, 0]]

You may assume that the board contains at least one cell, but either [[0]] or [[1]] are valid test cases.


This is a challenge, so the shortest submission (in bytes) for each language is the winner!

\$\endgroup\$
4
  • 6
    \$\begingroup\$ Nice challenge idea. \$\endgroup\$
    – Jonah
    Mar 19 at 19:52
  • \$\begingroup\$ Suggested test case: [[0, 1, 3, 0], [1, 0, 2, 1], [0, 2, 3, 0]] -> False \$\endgroup\$
    – Jitse
    Mar 20 at 15:48
  • \$\begingroup\$ Test cases with more than two colors would be helpful. \$\endgroup\$ Mar 20 at 16:44
  • 1
    \$\begingroup\$ @JonathanAllan Hmm, I'll allow you to assume that the board is non-empty but not that there is a space cell. \$\endgroup\$
    – hyper-neutrino
    Mar 23 at 1:26

5 Answers 5

6
\$\begingroup\$

JavaScript (ES11), 185 bytes

-3 thanks to l4m2

Expects a matrix of digits (with 0 for empty) and returns a Boolean value.

f=m=>m.some(z=(r,y)=>r.some((k,x)=>k?z=0:(h=M=>[-1,0,1,2].map(g=d=>(v=m[Y=y+d%2*++k]?.[X=x+~-d%2*k])<1?g(d):k=M?h[v]?M[Y][X]=0:0:![h[v]|=h[v]+v]))()|h(M=m.map(r=>[...r]))|M<m&&f(M)))!=z

Attempt This Online!

Method

For each empty cell in the input matrix, we call a helper function h twice:

  • once with no argument to count the colors of the closest non-empty cells in the 4 directions
  • once with a new copy M of the matrix to remove from M the cells whose color appears at least twice; if some deletions occur, it triggers a recursive call to the main function with the updated matrix

Commented

f = m =>                          // f is a recursive function taking a matrix m[]
m.some(z = (r, y) =>              // for each row r[] at index y in m[]:
  r.some((k, x) =>                //   for each value k at index x in r[]:
    k ?                           //     if k is not zero:
      z = 0                       //       at least 1 non-empty cell -> clear z
    :                             //     else:
      ( h = M =>                  //       h is a helper function taking M
        [-1, 0, 1, 2]             //       we have 4 directions to test
        .map(g = d =>             //       for each direction d:
          ( v = m[                //         load in v the value of the cell at:
              Y = y + d % 2 * ++k //           Y = y + dy * k (where k is pre-
            ]?.[                  //           incremented)
              X = x + ~-d % 2 *k  //           X = x + dx * k
            ]                     //
          ) < 1 ?                 //         if this cell is defined and empty:
            g(d)                  //           move further in the same direction
          :                       //         else:
            k =                   //           reset k to 0 in all cases
            M ?                   //           if M is defined:
              h[v] ?              //             if h[v] is greater than 0:
                M[Y][X] = 0       //               clear M[Y][X]
              :                   //             else:
                0                 //               do nothing
            :                     //           else:
              ![ h[v] |=          //             set h[v] = 0 if h[v] is undefined
                   h[v] + v       //             or h[v] > 0 if h[v] = 0 and v is
              ]                   //             defined
        )                         //       end of map()
      )() |                       //     1st call to h with M undefined
      h(M = m.map(r => [...r])) | //     2nd call to h with M = copy of m[]
      M < m && f(M)               //     do a recursive call if M was modified
  )                               //   end of some()
) != z                            // end of some() / success if z was not cleared
\$\endgroup\$
3
4
\$\begingroup\$

Charcoal, 109 bytes

WS⊞υ⁻ι ≔⟦υ⟧υFυFLιF⌕A§ικ.«ιJλκ≔E⁴KDL⁺ι⌊ι✳⊗μθ≔EθΦ⁻⪫μω.¬πηFΦ⁴∧§ημ⊖№η§ημ§≔§θμ⌕§θμ§ημ.≔⪪⪫KAωL⌊ιεF¬⁼ει⊞υε⎚»⊙υ⬤ι¬⁻λ.

Try it online! Link is to verbose version of code. Takes input as in the diagrams in the question but any character other than . and space may be used as a colour. Explanation:

WS⊞υ⁻ι ≔⟦υ⟧υFυ

Input the board and start a breadth-first search with that position.

FLιF⌕A§ικ.«

Loop over all of the indices of .s in the current position.

ιJλκ

Temporarily draw the position to the canvas and jump to the current ..

≔E⁴KDL⁺ι⌊ι✳⊗μθ

Peek in all four orthogonal directions.

≔EθΦ⁻⪫μω.¬πη

Get the first non-. character (if any) in each direction.

FΦ⁴∧§ημ⊖№η§ημ

Loop over those characters that appear more than once.

§≔§θμ⌕§θμ§ημ.

Replace the character with a .

≔⪪⪫KAωL⌊ιε

Read the position back from the canvas.

F¬⁼ει⊞υε

If this was a new position (i.e. at least two letters were replaced) then add it to the list of positions to search.

Clear the canvas ready for the next iteration.

»⊙υ⬤ι¬⁻λ.

See if any position has no letters left.

\$\endgroup\$
5
  • \$\begingroup\$ I'm pretty sure you can just take the input without spaces, so you can replace the Minus(i, " ")/⁻ι with i/ι to save 2 bytes. \$\endgroup\$ Mar 20 at 12:34
  • \$\begingroup\$ @KevinCruijssen Sure but this way made it easier to paste in the test cases. \$\endgroup\$
    – Neil
    Mar 20 at 13:21
  • \$\begingroup\$ (Also, in case you missed it, codegolf.stackexchange.com/a/271912) \$\endgroup\$
    – Neil
    Mar 20 at 13:24
  • \$\begingroup\$ I did miss it indeed, but I'm afraid I'd first have to investigate how to calculate the atan2 manually in the first place.. Based on the \u, I see there are six escape characters and four regular characters among the remaining digits/letters. Seem rather short. 🤔 \$\endgroup\$ Mar 20 at 14:09
  • \$\begingroup\$ @KevinCruijssen That's because it had an error. I've updated it so you've got five more days in which to crack it. \$\endgroup\$
    – Neil
    Apr 5 at 16:37
4
\$\begingroup\$

Python3, 368 bytes

E=enumerate
def f(b):
 q=[{(x,y):v for x,r in E(b)for y,v in E(r)}]
 for d in q:
  if sum(d.values())==0:return 1
  for i in d:
   if 0==d[i]:
    D={}
    for X,Y in[(1,0),(-1,0),(0,1),(0,-1)]:
     j,k=i
     while(c:=(j+X,k+Y))in d:
      if d[c]:D[d[c]]=D.get(d[c],[])+[c];break
      j,k=c
    if(U:={**d,**{I:0 for J in D for I in D[J]if len(D[J])>1}})!=d:q+=[U]

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Python 3, 260 bytes

def f(a,w,h):
 if~-any(a):return 1
 for x in range(w*h):
  n=a[:];c=[];[c:=c+[(v,x+i*s)for i,v in enumerate(a[x::s][:t])if v][:1]for s,t in((-w,h),(w,h),(-1,x%w+1),(1,w-x%w))]
  for v,i in c:n[i]*=v not in[u for u,j in c if i-j]
  if n!=a and f(n,w,h):return 1

Try it online!

Takes input as a 1d array of integers a where 0 is an empty cell, and grid dimensions w,h. Outputs 1 for true and None for false.

The function works by trying every move and for each move that removes any tiles it makes a recursive call.

\$\endgroup\$
2
\$\begingroup\$

Jelly, 45 bytes

œị¹ƙ⁸ḊƇŒṬ€S¬a
ŒṪ_ẠÐḟṠAÞḢ$ƙ$+ç⁸
¬sŒṪȦ?ç@€⁻Ƈ⁸߀

A full program that accepts a list of non-empty* lists of non-negative integers where 0 is a space, outputting via its exit code - 1 when possible, 0 otherwise.

Try it online! Or see the test-suite (uses a zsh wrapper to catch the exit code).

* Would identify [[]] as impossible if given, can be handled for +1 byte by inserting 0 between ¬sŒṪȦ? and ç@€⁻Ƈ⁸߀.

How?

œị¹ƙ⁸ḊƇŒṬ€S¬a - Link 1 (Remove equal colours): ColourCoordinates, Board
œị¹ƙ⁸         - Group the ColourCoordinates by their colours on the Board
     ḊƇ       - keep those groups with length greater than one
       ŒṬ€    - covert each into a 2d array with ones at the given coordinates
          S   - sum them to a single mask
           ¬  - logical NOT (vectorises)
            a - logical AND {Board} (vectorises)
                  -> a copy of Board with identified equal colours set to zero

ŒṪ_ẠÐḟṠAÞḢ$ƙ$+ç⁸ - Link 2 (Try pressing): Board, SpaceCoordinate
ŒṪ               - truthy coordinates {Board} -> all ColourCoordinates
  _              - {those} subtract {SpaceCoordinate} (vectorises) -> Offsets
   ẠÐḟ           - {Offsets} discard if all
                     -> those Offsets for colours in SpaceCoordinate's row or column
            $    - last two links as a monad - f(Offsets):
      Ṡ          -   sign (vectorises) (e.g. [0, -3] -> [0, -1] or [4, 0] -> [1, 0])
           ƙ     -   apply to groups of {Offsets} with equal {Sign}s:
          $      -     last two links as a monad - f(Offsets):
       AÞ        -        sort by absolute value
         Ḣ       -        head -> closest Offset in the direction of {Sign}
             +   - add {SpaceCoordinate} -> back from Offsets to coordinates
              ç⁸ - call Link 1 - f(that, Board)

¬sŒṪȦ?ç@€⁻Ƈ⁸߀ - Main Link: list of lists of non-negative integers, Board
¬              - logical NOT {Board} (vectorises) -> 1s at spaces, 0s at colours
     ?         - if...
    Ȧ          - ...condition: any and all? -> 1 if all spaces else 0
 s             - ...then: split {that} into chunks of length {Board} (vectorises)
                            -> error! (can't split into chunks of length zero)
  ŒṪ           - ...else: truthy coordinates -> SpaceIndices
      ç@€      - call Link 2 with swapped arguments for each
         ⁻Ƈ⁸   - keep only those which have changed
            ߀ - call this (Main) Link for each
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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