10
\$\begingroup\$

In this challenge you will receive as input a list of binary lists. The list represents a game board with each element representing a location on the board. The list at each location represents the tiles on the board, with a 0 being a white tile (□) and a 1 being a black tile (■). Each place can have any number of tiles and the order they appear in the list indicates how they are stacked, with the first element being the tile on the top of the stack and the last being on the bottom of the stack.

For example here's a input list and a graphical representation of the game board:

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

□
□   ■     ■
■   ■ ■   □
-+-+-+-+-+-

On a turn of this game the player can move by choosing any one place on the board and picking up all the tiles from that place, without disrupting their order. Then the player must choose a direction, either left or right. Then starting from the place they chose to pick from, until they have no tiles left in their hand they repeatedly choose to either:

  • Drop the tile at the bottom of the held stack at their current place.
  • Move to the adjacent place in their chosen direction.

The player is not permitted drop any tiles out of bounds of the game board.

Here's an example turn:

□ □
■ ■ ■   ■ ■
■ □ □   □ ■
-+-+-+-+-+-

Pick up two tiles from the second place from the left and move to the right:

  □
  ■
  □ 

□
■   ■   ■ ■
■   □   □ ■
-+-+-+-+-+-

Drop 1 tile from the bottom back where it was picked up and move to the right:

    □
    ■


□
■   ■   ■ ■
■ □ □   □ ■
-+-+-+-+-+-

Drop no tiles and move to the right

      □
      ■


□
■   ■   ■ ■
■ □ □   □ ■
-+-+-+-+-+-

Drop two tiles and end.

□
■   ■ □ ■ ■
■ □ □ ■ □ ■
-+-+-+-+-+-

With that the goal of this game is simple. Using as few moves as possible arrange the board so that in every place the top tile is black.

Here is an example game:

□ □ □ □ □
■ ■ ■ ■ ■
-+-+-+-+-

  ■ □
  □ □ □ □
  ■ ■ ■ ■
-+-+-+-+-

  ■ □
  □ □ □
□ ■ ■ ■ ■
-+-+-+-+-


  ■ □
□ □ □
□ ■ ■ ■ ■
-+-+-+-+-

□
□ ■
□ □
□ ■ ■ ■ ■
-+-+-+-+-

■
□
□
□
□
□ ■ ■ ■ ■
-+-+-+-+-

Your task is take the starting board as input and determine the number of moves required to win.

You can assume that the board is at least 2 places wide (the outer list contains at least two lists) and that there are enough black tiles to cover every space on the board (i.e. it is possible to solve)

There are two arbitrary choices I have made. You may swap either, both or neither for the opposite choice:

  • 0 is white. You may instead assume 0 is black and 1 is white.
  • The first element is the tile on the top. You may instead assume the first element is the tile on the bottom and the last element is the tile on the top.

You may also use suitable substitutions for 0 and 1 such as True and False, 1 and -1, etc.

This is so the goal is to minimize the size of your source code as measured in bytes.

Brute force is fine, but I encourage you to try golf faster algorithms. Good golfs under self imposed constraints on time are always worth an upvote.

Test cases

[[0,1],[0,1]] -> 3
[[0,1],[0,1],[0,1]] -> 3
[[1,1,1],[],[]] -> 1
[[1,0],[1],[1,1]] -> 0
[[0,1,0,1,0,1],[],[]] -> 2
\$\endgroup\$
8
  • \$\begingroup\$ Is "moves" in "determine the number of moves required to win" have same meaning with "turn" in "on a turn of this game", or "move" in "move their hand 1 place in the direction they chose"? A assume the first one. If so, I would suggest edit "moves" into "turns". \$\endgroup\$
    – tsh
    Jul 21 at 5:41
  • 1
    \$\begingroup\$ Maybe I misread the question? Is [[0,1],[0,1]] -> [[0],[1,0,1]] -> [[1,0],[1,0]] 2 turns? \$\endgroup\$
    – tsh
    Jul 21 at 6:46
  • \$\begingroup\$ @tsh That first move is not valid. I'm not sure exactly what your misconception is though. Either you are dropping them in the correct order and you are backtracking after you dropped the first or you are dropping them in the incorrect order. You need to drop the tiles from the bottom of the picked up stack. \$\endgroup\$
    – Wheat Wizard
    Jul 21 at 8:08
  • 1
    \$\begingroup\$ Ah, got it. I misunderstood that you can change the direction in the loop. \$\endgroup\$
    – tsh
    Jul 21 at 8:33
  • 1
    \$\begingroup\$ Just come up with a question: if whenever you chose a column and a direction, you can only do "pick up all - move - place 1 - move - place 1 - ..." (move will be wrapped when ending reached). Will the game be still solvable for any game boards currently solvable? \$\endgroup\$
    – tsh
    Jul 21 at 11:12

3 Answers 3

5
\$\begingroup\$

Python 3, 237 bytes

g=lambda a,b,i,j:b and[*g(a[:i]+[[b[-1]]+a[i]]+a[i+1:],b[:-1],i,j),*g(a,b,i+j,j)]or[a]if-1<i<len(a)else[]
f=lambda*b:+all(min(a)<[1]for a in b)and-~f(*sum([g(a[:i]+[[]]+a[i+1:],c,i,j)for a in b for i,c in enumerate(a)for j in[1,-1]],[]))

Try it online!

Brute force answer.

\$\endgroup\$
3
\$\begingroup\$

Python3, 714 bytes:

E=enumerate
def F(b):
 for i,a in E(b):
  for I,j in E(a):
   if j:yield(i,I,1)
   if 0==any(a[:I])and a[I]:yield(i,I,0)
S=lambda b:sum(i!=[]and i[0]for i in b)
def U(b,c,s,x,y,X,q,Q,h,R):
 B=eval(str(b));B[X]=B[x][:y]+B[X];B[x]=B[x][y:]
 if 0==h:c+=1;h=(X,y,X-x>=0)
 elif h[0]!=x or h[1]<y or(X-x>=0)!=h[2]:h=(X,y,X-x>=0);c+=1
 else:h=[X,h[1]-y,h[2]]
 if(R==[]or c<min(R))and(B,c)not in Q:
  if S(B)>s:q.insert(0,(B,c,h))
  else:q.append((B,c,h))
  Q.append((B,c))
def f(b):
 q,Q=[(b,0,0)],[(b,0)]
 R=[]
 while q:
  B,c,h=q.pop(0)
  if(s:=S(B))==len(B):R+=[c]
  for x,y,r in F(B):
   for X,Y in E(B):
    if x!=X and(Y==[]or Y[0]==0): 
     U(B,c,s,x,y,X,q,Q,h,R)
     if r:U(B,c,s,x,y+1,X,q,Q,h,R)
 return min(R)

Try it online!

A little longer than it could be, but contains some optimizations.

\$\endgroup\$
2
  • \$\begingroup\$ I don't fully understand this, but I think I got it down to 593? It depends if the yields are mutually exclusive. If they are not, then 617. \$\endgroup\$ Jul 21 at 0:57
  • \$\begingroup\$ It appears those links don't work: 593, 639 \$\endgroup\$ Jul 21 at 3:12
2
\$\begingroup\$

JavaScript (ES6), 198 bytes

f=(a,n=0)=>(F=(a,k)=>a.every(v=>v[0])|a.some((b,i,[...B],g)=>(B[i]=[],g=(d,q=b,x=i,A=B)=>q+q?A[x]&&g(d,q,x+d,A)|g(d,c=[...q],x,A.map(v=>x--?v:[c.pop(),...v])):k&&F(A,k-1))(1)|g(-1)))(a,n)?n:f(a,n+1)

Try it online!

Commented

// outer recursive function with n = maximum number of moves
f = (a, n = 0) => (
  // inner recursive function with k = remaining number of moves
  F = (a, k) =>
    // success if all leading terms are 1
    a.every(v => v[0]) |
    // for each b[] at position i in a[]
    a.some((b, i, [...B], g) =>
      // let B[] be a copy of a[] with the i-th term set to []
      ( B[i] = [],
        // g is yet another recursive function taking:
        //   a direction d
        //   a vector q[], initially set to b[]
        //   a position x, initially set to i
        //   an array A[], initially set to B[]
        g = (d, q = b, x = i, A = B) =>
          // if q[] is not empty
          q + q ?
            // if A[x] is defined (i.e. we're not out of bounds)
            A[x] &&
            // do a recursive call where the position is updated
            g(d, q, x + d, A) |
            // do a recursive call where the position is unchanged and
            // the last element of q[] is added at the beginning of A[x]
            g(d, c = [...q], x, A.map(v => x-- ? v : [ c.pop(), ...v ]))
          // if q[] is empty
          :
            // if k is not equal to 0, process the next move
            k && F(A, k - 1)
      )
      // invoke g with d = 1 (moving to the right)
      (1) |
      // invoke g with d = -1 (moving to the left)
      g(-1)
    )
// initial call to F
// return n if successful, or try again with n + 1
)(a, n) ? n : f(a, n + 1)
\$\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.