# A292764 # we encode each configuration by a list of n integers in 0..3: # (i1, ..., in) # i1 gives the tower of disk 1 (the smallest one) # ... # in gives the tower of disk n (the largest one) # 0 corresponds to tower A # 1 corresponds to tower B # 2 corresponds to tower C # 3 corresponds to tower D # each list is then encoded by 0 <= x = i1+4*i2+...+4^(n-1)*in < 4^n # from 0 <= x < 4^n, return a list of 4 lists for A, B, C, D def decode(x,n): L = [[],[],[],[]] l = (4^n+x).digits(4) # we put the smallest elements last for i in range(n-1,-1,-1): t = l[i] L[t].append(i) return L def encode(l): x = 0 for j in [1,2,3]: for i in l[j]: x += j*4^i return x # returns the possible moves # dir=1 to move forward (0->1->2->3->0), dir=-1 backward (0->3->2->1->0) def moves_cyclic(l,dir): L = [] for i in range(4): j = (i+dir) % 4 # can we move from tower i to j? if l[i]<>[] and (l[j] == [] or l[i][-1] < l[j][-1]): l2 = [copy(l[k]) for k in range(4)] l2[i] = l2[i][:-1] l2[j].append(l[i][-1]) L.append(l2) return L # breadth-first search, meet-in-the-middle version # 2,8,18,36,66,120,210,360,618,1052,1790,3040,5162,8756,14854 def A292764(n,verbose=false): start = Set([0]) end = Set([2*(4^n-1)//3]) new_start = start new_end = end steps = 0 finished = false while not finished: steps += 1 new2 = Set([]) for x in new_start: if finished: break l = decode(x,n) for l2 in moves_cyclic(l,1): x2 = encode(l2) if not x2 in start: if x2 in end: finished = true break new2 += Set([x2]) new_start = new2 start += Set(new_start) if verbose: print steps, len(start), len(new_start), len(end), len(new_end) if finished: break steps += 1 new2 = Set([]) for x in new_end: if finished: break l = decode(x,n) for l2 in moves_cyclic(l,-1): x2 = encode(l2) if not x2 in end: if x2 in start: finished = true break new2 += Set([x2]) new_end = new2 end += Set(new_end) if verbose: print steps, len(start), len(new_start), len(end), len(new_end) return steps