Can I Clear The Grid?

Question

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 code-golf challenge, so the shortest submission (in bytes) for each language is the winner!

• Jonah: Nice challenge idea.
• Jitse: Suggested test case: [[0, 1, 3, 0], [1, 0, 2, 1], [0, 2, 3, 0]] -> False
• Greg Martin: Test cases with more than two colors would be helpful.
• hyperneutrino: @JonathanAllan Hmm, I'll allow you to assume that the board is non-empty but not that there is a space cell.

Answer 1

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

• l4m2: 192 bytes: f=m=>m.some(z=(r,y)=>r.some((c,x)=>c?z=0:(h=M=>[1,1,1,1].map(g=(k,d)=>(v=m[Y=y+~-d%2*k]?.[X=x+(d-2)%2*k])<1?g(k+1,d):M?h[v]?M[Y][X]=0:0:h[v]=h[v]+v/v|0))()|h(M=m.map(r=>[...r]))|M<m&&f(M)))!=z
• l4m2: h[v]+v/v|0 => h[v]+v|0 as we don't care what number is added
• Arnauld: @l4m2 Nice catch. We can save another byte with h[v]|=h[v]+v.

Answer 2

Charcoal, 109 bytes

WS⊞υ−ι ≔⟦υ⟧υFυFLιF⌕A§ικ.«ιJλκ≔E4KDL+ι⌊ι✳⊗μθ≔EθΦ−⪫μω.¬πηFΦ4∧§ημ⊖Noη§ημ§≔§θμ⌕§θμ§ημ.≔⪪⪫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 ..

≔E4KDL+ι⌊ι✳⊗μθ

Peek in all four orthogonal directions.

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

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

FΦ4∧§ημ⊖Noη§ημ

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.

• Kevin Cruijssen: 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.
• Neil: @KevinCruijssen Sure but this way made it easier to paste in the test cases.
• Neil: (Also, in case you missed it, codegolf.stackexchange.com/a/271912)
• Kevin Cruijssen: 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. 🤔
• Neil: @KevinCruijssen That's because it had an error. I've updated it so you've got five more days in which to crack it.

Answer 3

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!

Answer 4

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.

Answer 5

Jelly, 45 bytes

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

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 ç@€−Ƈ8߀.}

How?

œị1ƙ8ḊƇŒṬ€S¬a - Link 1 (Remove equal colours): ColourCoordinates, Board
œị1ƙ8 - 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ÞḢ$ƙ$+ç8 - 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
 ç8 - call Link 1 - f(that, Board)
¬sŒṪȦ?ç@€−Ƈ8߀ - 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
 −Ƈ8 - keep only those which have changed
 ߀ - call this (Main) Link for each