'''
This is a program that solves a 'plus 7 times 10' puzzle, which is when you have a 4 digit counter that needs to equal a particular number and which can only be modified by either adding 7 or multiplying by 10.
It was used to solve a puzzle in a point and click game (http://neutralxe.net/esc/r2.html).
'''
import queue
import sys
value = input('Enter the number you want the counter to reach: ')
while True:
if not value.isdigit() or len(value) > 4:
value = input('Invalid input! Please supply a number that is less than 4 digits long: ')
else:
break
goal = int(value)
#throwable object containing moves history to reach goal
class ReachedGoal(Exception):
def __init__(self, history):
super().__init__()
self.history = history
#perform breath first search on tree of moves and stop as soon as the goal number is reached
#this will give the shortest path from 0000 (the root of the tree) to the goal number
curr_num = 0
visited = { curr_num }
q = queue.Queue()
q.put((curr_num, [])) #(current grid, moves history)
try:
while not q.empty():
(curr_num, history) = q.get()
#try performing both x10 and +7 to the current number
for (op, new_num) in [
('x10', (curr_num*10)%10000),
('+7', (curr_num + 7)%10000),
]:
new_history = history + [ (op, new_num) ] #add the operation performed and the resulting number to the move history
if new_num in visited:
continue
#goal has been reached
if new_num == goal:
raise ReachedGoal(new_history)
visited.add(new_num)
q.put((new_num, new_history))
except ReachedGoal as e:
#display history of moves performed in order to reach goal number from 0000
for (step, (op, num)) in enumerate(e.history):
print('Step {: >2}: {: <3} ({:0>4})'.format(step+1, op, num))