Tile stacking with ■ and □

Question

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 code-golf 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

Answer 1

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.

Answer 2

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.

Answer 3

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)