Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
#!python3
"""Solves Howard's goblins puzzle using backtracking. https://www.facebook.com/howard.dale.3/posts/10152106759878462?stream_ref=5 """
from collections import deque
class Game:
def __init__(self):
self.goblins = [0]*7
self.history = deque()
def time(self):
return len(self.history)
def move(self, x):
for i in range(len(self.goblins)):
if (self.time()+1) % (i+1) == 0:
self.goblins[i] += x
self.history.append(x)
def undo(self):
last_move = self.history.pop()
for i in range(len(self.goblins)):
if (self.time()+1) % (i+1) == 0:
self.goblins[i] -= last_move
def pretty_history(self):
return ''.join('+' if x==1 else '-' for x in self.history)
def pretty_goblins(self):
return ','.join(str(x).rjust(2) for x in self.goblins)
# unit test
def unit_test():
G = Game()
assert G.goblins == [0,0,0,0,0,0,0]
G.move(1)
assert G.goblins == [1,0,0,0,0,0,0]
G.move(1)
assert G.goblins == [2,1,0,0,0,0,0]
G.move(-1)
assert G.goblins == [1,1,-1,0,0,0,0]
G.undo()
assert G.goblins == [2,1,0,0,0,0,0]
G.undo()
assert G.goblins == [1,0,0,0,0,0,0]
G.undo()
assert G.goblins == [0,0,0,0,0,0,0]
unit_test()
if __name__ == "__main__":
G = Game()
while True:
if any(abs(position) > 1 for position in G.goblins):
# dead. backtrack.
print("{0} {1} {2}".format(G.pretty_goblins(), G.pretty_history(), "BUST"))
while G.history[-1] == -1:
G.undo()
G.undo()
G.move(-1)
else:
print("{0} {1}".format(G.pretty_goblins(), G.pretty_history()))
G.move(1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.