I am trying to write a code to solve the ToH problem by using UCS and A* algorithms and then compare the results. So, the first thing I should do is representing the possible movements as a tree, then the UCS and A* algorithms can go through the tree easily.
Suppose we have 3 stacks and 5 disks, so the initial state will be:
# The Num of stacks is the number of elements in the list.
# The Num of disks is the length of each element in the list.
key = ["12345","00000","00000"]
# A B C
What I need is to build a function that predicts the possible next movements, so the next step could be:
["12340","00005","00000"] or ["12340","00000","00005"]
# so these states will saved as:
dic ={}
x= repr(key)
dic[x] = ["12340","00005","00000"]
# the result:
# ["12345","00000","00000"] : ["12340","00005","00000"]
I tried this naive code:
# there are bugs but I am still working on it
for indx, block in enumerate(key):
for i, char in enumerate(reversed(block)):
if char != "0":
for indx2, block2 in enumerate(key):
if indx2 == indx: pass
for ii, char2 in enumerate(reversed(block2)):
if char2 == "0":
temp=block[i]
block[i]= block2[ii]
block2[ii]=temp
print(key)
Is there any pseudocode or ideas that could help?
For solving the Towers of Hanoi problem there is no need to build the graph of states, as there is a mathematical formula to determine which next move to make.
Still, if you are going to make the graph, then I would suggest to shorten the key to a this format: 12345||. The pipes separate the piles. So if you would move the 5 to the middle stack, its key would be 1234|5|. If then you move the 4 to the last stack: 123|5|4, ...etc.
During the creation of the graph, you could switch to a list of lists, like [["1","2","3"], [], []], so it is easier to manipulate. Your idea to use a dictionary is fine, however, there can be several valid moves from one state, so you would need a list of states.
Nodes in a graph are often implemented with a Node class, so I would suggest this code:
class Node:
def __init__(self, key):
self.key = key
self.children = []
def create_tree(stacks, tree=None):
if not tree:
tree = {}
key = "|".join(["".join(discs) for discs in stacks])
if key in tree: # this node was already created
return tree[key]
tree[key] = node = Node(key)
for source in stacks:
if source:
disc = source[-1]
for target in stacks:
if not target or disc > target[-1]:
# perform the move:
target.append(source.pop())
# recursion
node.children.append(create_tree(stacks, tree))
# undo the move
source.append(target.pop())
return node
root = create_tree([["1","2","3","4","5"], [], []])
After running this, root will be a Node instance with two nodes in its children property. Each of those children will have three children, including a back reference to the root, representing the inverse move.
I kept the dictionary (called tree) hidden in the implementation. If you feel you need access to it, then you could of course make it a non-local variable, or pass it as argument.