Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

I'm trying to solve the Reve's puzzle (a variant of the Tower of Hanoi puzzle with four pegs). This is what I've come up with so far:

def solve(disk, source, temppeg1, temppeg2, destination):
    if disk == 1:
        print((source, destination))
    elif disk == 2:
        print((source, temppeg1))
        print((source, destination))
        print((temppeg1, destination))
    else:
        solve(disk - 2, source, temppeg2, destination, temppeg1)
        print((source, temppeg2))
        print((source, destination))
        print((temppeg2, destination))
        solve(disk - 2,  temppeg1, source, temppeg2, destination)

>>> solve(16, 'a', 'b', 'c', 'd')
('a', 'c')
... 763 lines deleted ...
('a', 'd')

While this works fine, I was wondering if there's a better solution (more optimal) than what I have so far. Currently with what I have, I can solve 16 disk in 765 moves.

share|improve this question
1  
one question that comes immediately to mind is "are you trying to actually solve? or just find the minimum number of moves to solve? –  Joran Beasley Feb 22 at 19:08

1 Answer 1

up vote 3 down vote accepted

if you are just trying to find the minimum number of moves and not necessarily a solution you can use the Frame–Stewart algorithm that you linked to earlier

this builds up a solution to the number of moves to achieve a solution.

def FrameStewart(ndisks,npegs):
    if ndisks ==0: #zero disks require zero moves
        return 0
    if  ndisks == 1 and npegs > 1: #if there is only 1 disk it will only take one move
        return 1
    if npegs == 3:#3 pegs is well defined optimal solution of 2^n-1
        return 2**ndisks - 1
    if npegs >= 3 and ndisks > 0:
        potential_solutions = (2*FrameStewart(kdisks,npegs) + FrameStewart(ndisks-kdisks,npegs-1) for kdisks in range(1,ndisks))
        return min(potential_solutions) #the best solution
    #all other cases where there is no solution (namely one peg, or 2 pegs and more than 1 disk)
    return float("inf") 

print FrameStewart(16,4) #prints 161

this tells us that the optimal solution for 16 disks and 4 pegs is 161 moves, note that it does not tell us what those moves are

if you actually need the moves you will have to heavily modify this solution.

start by solving the towersofhanoi with 3 pegs as that is the traditional layout and has well defined algorithms to solve

def towers3(ndisks,start=1,target=3,peg_set=set([1,2,3])):
   if ndisks == 0 or start == target: #if there are no disks, or no move to make
      return [] #no moves
   my_move = "move(%s,%s)"%(start,target) 
   if ndisks == 1: #trivial case if there is only one disk, just move it
      return [my_move]
   helper_peg = peg_set.difference([start,target]).pop()
   moves_to_my_move = towers3(ndisks-1,start,helper_peg)
   moves_after_my_move = towers3(ndisks-1,helper_peg,target)
   return moves_to_my_move + [my_move] + moves_after_my_move

you can easily verify that this is returning optimal solutions by knowing that the optimal solution to the towers of hanoi with 3 pegs is 2ndisks - 1

all thats left is to change FrameStewart to also return moves

def FrameStewartSolution(ndisks,start=1,end=4,pegs=set([1,2,3,4])):
    if ndisks ==0 or start == end: #zero disks require zero moves
        return []
    if  ndisks == 1 and len(pegs) > 1: #if there is only 1 disk it will only take one move
        return ["move(%s,%s)"%(start,end)]  
    if len(pegs) == 3:#3 pegs is well defined optimal solution of 2^n-1
        return towers3(ndisks,start,end,pegs)
    if len(pegs) >= 3 and ndisks > 0:
        best_solution = float("inf")
        best_score = float("inf")
        for kdisks in range(1,ndisks):
            helper_pegs = list(pegs.difference([start,end]))
            LHSMoves = FrameStewartSolution(kdisks,start,helper_pegs[0],pegs)
            pegs_for_my_moves = pegs.difference([helper_pegs[0]]) # cant use the peg our LHS stack is sitting on
            MyMoves = FrameStewartSolution(ndisks-kdisks,start,end,pegs_for_my_moves) #misleading variable name but meh 
            RHSMoves = FrameStewartSolution(kdisks,helper_pegs[0],end,pegs)#move the intermediat stack to 
            if any(move is None for move in [LHSMoves,MyMoves,RHSMoves]):continue #bad path :(
            move_list = LHSMoves + MyMoves + RHSMoves
            if(len(move_list) < best_score):
                best_solution = move_list
                best_score = len(move_list)
        if best_score < float("inf"):       
            return best_solution
    #all other cases where there is no solution (namely one peg, or 2 pegs and more than 1 disk)
    return None

note that this is going to be much slower than the version that does not need to find the actual solution (this being codereview maybe some folks have suggestions to make it run faster) Timings from this experiment

towers3(16)  # 0.09 secs
FrameStewart(16) #0.04 secs
FrameStewartSolution(16) #67.04 secs!!!

really slow as you can see

you can speed it up alot by memoizing it

import json

def fsMemoizer(f): #just a junky quick memoizer
    cx = {}
    def f2(*args):
        try:
            key= json.dumps(args)
        except:
            key =json.dumps(args[:-1] + (sorted(list(args[-1])),))
        if key not in cx:
            cx[key] = f(*args)
        return cx.get(key)
    return f2
@fsMemoizer
def FrameStewartSolution(ndisks,start=1,end=4,pegs=set([1,2,3,4])):
    ...

after memoization the time to calculate became much faster (less than a second)

share|improve this answer
    
Thank you Joran, however now that I know what the minimum number of moves are is there a way to print what the moves are like what I currently have but with your suggested algorithm instead? –  Sc4r Feb 22 at 19:35
1  
thats why I asked in the comment ... and you said you were trying to find the minimum number of moves ... it is certainly possible but its going to be very difficult ... this algorithm is not really designed around finding an actual solution ... –  Joran Beasley Feb 22 at 19:37
    
Thanks for the help Joran! –  Sc4r Feb 22 at 21:37
    
this seems to find the optimal solution ... its not very fast and its not very pretty but it works –  Joran Beasley Feb 22 at 21:58
1  
None is a more natural return value than "NaN". –  200_success Feb 23 at 6:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.