R=range
G=lambda:[[0]*4for _ in R(4)]
B=G()

def print_board(B):
 print "\n".join(" ".join(("%4d"%c) if c else '   .' for c in row) for row in B)

#return (is_move,is_combination,new_src,new_dest)
def combine(s,d):
 if s<1or d<1:return (0,0,s or d)
 if s==d:return (1,0,s+d)
 return(0,s,d)


#0=up, 1=right, 2=down, 3=left
#direction -> (dx, dy, startx, xdirection, starty, ydirection)
#Ds=[(-1,0,0,1,0,0),(0,-1,0,0,0,1),(1,0,2,-1,0,0),(0,1,0,0,2,-1)]
#direction -> (dx, dy)
Ds=[(0,-1),(1,0),(0,1),(-1,0)]
#delta -> (iter_start, iter_end, iter_direction, source_direction)
Js=[(0,4,1,0),(2,-1,-1,-1),(1,4,1,1)]
Ss=[0,-1,1]
def move(P,d):
 C=G()
 dx,dy=Ds[d]
 sx,ex,ix,Sx=Js[dx]
 sy,ey,iy,Sy=Js[dy]
 while 1:
  N=[r[:]for r in P]
  for x in R(sx,ex,ix):
   for y in R(sy,ey,iy):
    src=N[y][x]
    q,w=(y-Sy,x-Sx)
    dest=N[q][w]
    is_comb,next_src,next_dst=combine(src, dest)
    if is_comb and(C[y][x]or C[q][w]):continue
    #print "N[%d][%d]=%s,N[%d][%d]=%s --> %s, %s, comb=%s" % (
    #    y, x, src, q, w, dest, next_src, next_dst, is_comb)
    N[y][x]=next_src
    N[q][w]=next_dst
    C[q][w]+=is_comb
  if N==P:break
  P=N
 return N
def fill(N):
 for x in R(4):
  for y in R(4):
   if N[y][x]==0:N[y][x]=2;return N
moves=lambda P:[d for d in R(4)if move(P,d)!=P]
ev=lambda P:sum((256,c)[c>0] for v in P for c in v)+P[3][3]*10+P[3][2]*9
def move_ev(P,d):
 return ev(move(P,d))
def best(P,i):
 if i==0:return(ev(P),-1)
 M=moves(P)
 return max((best(fill(move(P,d)),i-1)[0],d)for d in M)if M else (-9999,-1)

B[0][0]=2
i=0
res = '';go=0
while B:
 if i%1==0:print_board(B)
 if not go and B[3][3]==2048:
     print "Path to 2048:", res
     if not go and raw_input("Continue (y/n)? ")[0]!='y':break
     go=1
 EV,MOVE=best(B,4)
 if i%1==0:print "Best move: %s, with EV=%s" % ("awds"[MOVE], EV)
 B=fill(move(B,MOVE))
 res += `MOVE`
 i+=1

print "Final position:"
print_board(B)
print "Path to final position:", res