Skip to content

Instantly share code, notes, and snippets.

@tkuriyama tkuriyama/blacksmith.py
Last active Sep 19, 2015

Embed
What would you like to do?
Solver for "Blacksmith Khecho's Ingenuity"
"""Blacksmith Khecho's Ingenuity
[...]
Khecho, calmly looking around, climbed the steps to the tower's upper
part and glanced out the window. He realized it would be impossible to
jump out and survive. But he saw a rope, forgotten by the masons, hanging
near the window. The rope was thrown over a rusty tackle fastned to the
tower wall above the window. Empty baskets were tied to each end of the
rope. Those baskets had been used by the masons to lift bricks and lower
rubble. Khecho knew that if one load was 10 pounds more than the other,
the heavier basket would descend smoothly to the ground while the other
rose to the window.
Looking at the two girls, Khecho guessed Daridjan's weight at 100 pounds
and the servant's at 80. He himself weighed nearly 180. In the tower he
found 13 separated pieces of chain, each weighing 10 pounds. Now all
three prisoners suceeded in reaching the ground. At no time did a
descending basket weigh over 10 pounds more than the ascending basket.
How did they escape?
Dover Publications
The Moscow Puzzles: 359 Mathematical Recreations, 31-32.
"""
import sys
from copy import deepcopy
from collections import deque
PEOPLE = [80, 100, 180]
WEIGHTS = [10] * 13
class Balance:
"""Balance object.
Methods
move: add of subtract weight from left or right
switch: switch up/down status of left and right
check: check if balance is still intact
show: print balance
"""
def __init__(self):
self.left = []
self.left_up = True
self.right = []
self.right_up = False
self.intact = True
def move(self, add, to_left, weight):
"""
Args
add: boolean, add weight if True, else subtract weight
to_left: boolean, apply weight func to left if True, else to right
weight: int, weight to add or subtract
"""
f = list.append if add else list.remove
if to_left:
f(self.left, weight)
else:
f(self.right, weight)
if self.right_up and sum(self.right) > sum(self.left):
self.switch()
elif self.left_up and sum(self.left) > sum(self.right):
self.switch()
def switch(self):
"""Switch position of left and right; check balance remains valid."""
self.left_up = True if self.right_up else False
self.right_up = self.left_up ^ True
self.intact = self.check()
def check(self):
"""Return True if balance diff is at most 10."""
return False if abs(sum(self.left) - sum(self.right)) > 10 else True
def show(self):
"""Print balance."""
print 'L ', str(self.left), '\t', ('*' if self.left_up else '')
print 'R ', str(self.right), '\t', ('*' if self.right_up else '')
print 'Intact:\t', self.intact, '\n'
def ret_str(self):
"""Return string representation of balance."""
return ' '.join(['|', '*' if self.left_up else '',
str(sorted(self.left)),
'---',
str(sorted(self.right)),
'*' if self.right_up else '', '|'])
# Helper Functions
def is_completed(world):
"""Return True if world is completed, i.e. all poeple are on ground."""
_, _, ground = world
return set(PEOPLE).issubset(set(ground))
def is_valid(world):
"""Return True if world is valid, i.e. balance constraint not violated."""
_, balance, _ = world
return balance.intact
def hash_world(world, string=True):
"""Hash world into string, or list of strings."""
tower, balance, ground = world
world_list = [str(sorted(tower)), balance.ret_str(), str(sorted(ground))]
return ''.join(world_list) if string else world_list
def show(world):
"""Return string representation of world."""
return ' '.join(hash_world(world, False))
def print_solutions(solutions, n=5):
"""Take list of solutions and print top 5."""
by_length = sorted(solutions, key=lambda x: len(x))
for ind, history in enumerate(by_length[:n]):
print '\nSolution #', ind + 1, 'of', len(solutions), '\n'
print '\n'.join(show(line) for line in history)
# Solver
def gen_change_combos(world, people):
"""Group world into logical combinations of changes.
Each world generates a set of 4 changes: {add, remove} x {tower, ground}
Args
world: tuple of puzzle world
people: set of ints representing valid people
Returns
List of tuples (set of ints of location's weights, bool apply_tower,
bool add_balance, bool apply_left)
"""
tower, balance, ground = world
up = balance.left if balance.left_up else balance.right
down = balance.right if balance.left_up else balance.left
combos = []
if people & set(tower) or people & set(up) and up:
combos += [(set(tower), True, True, balance.left_up),
(set(up), True, False, balance.left_up)]
if people & set(ground) or people & set(down) and down:
combos += [(set(ground), False, True, balance.right_up),
(set(down), False, False, balance.right_up)]
return combos
def gen_changes(world, people):
"""Generate individual changes to be appled to world.
Args
world: tuple of puzzle world
people: set of ints representing valid people
Returns
List of tuples
(bool apply_tower, bool add_balance, bool apply_left, int weight)
"""
combos = gen_change_combos(world, people)
return [(apply_tower, add_balance, apply_left, weight)
for place, apply_tower, add_balance, apply_left in combos
for weight in place]
def move(place, add_balance, weight):
"""Add or remove weight from list of ints place.
Args
place: list of ints (representing tower or ground)
add_balance: bool, add to balance (opposite action for place)
weight: int of weight
"""
if add_balance:
place.remove(weight)
else:
place.append(weight)
return place
def apply_change(world, change):
"""Apply change to world.
Create deepcopy to avoid side effects to original world.
Args
world: tuple of world
change: tuple (bool apply_tower, bool add_balance, bool apply_left,
int weight)
Returns
tuple of (new) world, sorted locations as permutations are unncessary
"""
new_world = deepcopy(world)
tower, balance, ground = new_world
apply_tower, add_balance, apply_left, weight = change
if apply_tower:
tower = move(tower, add_balance, weight)
else:
ground = move(ground, add_balance, weight)
balance.move(add_balance, apply_left, weight)
return sorted(tower), balance, sorted(ground)
def gen_next(world, visited):
"""Generate list of valid next worlds.
Permit people to jump off and balance to crash if last move of game.
Args
world: tuple of world
visited: dict of hashes of tuples of worlds visited
Returns
next_worlds: list of tuples of worlds
visited: list of tuples of worlds
"""
changes = gen_changes(world, set(PEOPLE))
next_worlds = []
for change in changes:
next_world = apply_change(world, change)
if is_completed(next_world):
next_worlds.append(next_world)
elif is_valid(next_world) and hash_world(next_world) not in visited:
next_worlds.append(next_world)
visited[hash_world(next_world)] = 1
return next_worlds, visited
def find_solutions(start, just_one, bfs):
"""Search for solutions.
Args
start: tuple of starting world
just_one: boolean, if True return first solution found
BFS: boolean, BFS if True, else DFS
"""
completed = []
visited = {hash_world(start): 1}
histories = deque([([start], visited)])
pop_item = deque.popleft if bfs else deque.pop
while histories:
history, visited = pop_item(histories)
next_worlds, visited = gen_next(history[-1], visited)
for world in next_worlds:
if is_completed(world):
completed.append(history + [world])
else:
histories.append((history + [world], visited))
if just_one and completed: break
return completed
# Test
def test_balance():
"""Test Balance object methods."""
debug = 0
b = Balance()
add, remove = True, False
left, right = True, False
b.move(add, right, 10)
assert b.intact, 'Balance should be intact.'
assert b.left_up, 'Left should be up'
if debug: b.show()
b.move(add, left, 20)
assert b.intact, 'Balance should be intact.'
assert b.right_up, 'Right should be up'
assert not b.left_up, 'Right should be up'
if debug: b.show()
b.move(remove, left, 20)
assert b.intact, 'Balance should be intact.'
assert b.left_up, 'Left should be up'
assert not b.right_up, 'Left should be up'
if debug: b.show()
b.move(add, left, 100)
assert not b.intact, 'Balance should not be intact.'
assert b.right_up, 'Right should be up'
assert not b.left_up, 'Right should be up'
if debug: b.show()
return True
def test_completed():
"""Test world is_completed() function."""
world = ([10], Balance(), PEOPLE + [10])
assert is_completed(world), "World should be complete" + str(world)
world = ([180], Balance(), [10])
assert not is_completed(world), "World should be incomplete" + str(world)
return True
def test_gen_change_combos():
"""Test gen_change_combos()."""
b = Balance()
b.move(True, True, 10)
output = [({20, 10}, True, True, False),
(set(), True, False, False)]
assert gen_change_combos(([20, 10], b, [10]), {20}) == output
return True
def test_gen_changes():
"""Test gen_changes()."""
b = Balance()
b.move(True, True, 10)
output = [(True, True, False, 10),
(True, True, False, 20)]
assert gen_changes(([20, 10], b, [10]), {20}) == output
return True
def test_move():
"""Test adding or removing weight from place."""
tests = (([100, 70, 10, 10], True, 10, [100, 70, 10]),
([100, 10, 180, 10], False, 10, [100, 10, 180, 10, 10]))
for before, add, weight, after in tests:
assert move(before, add, weight) == after, 'Move failed'
return True
def unit_tests():
"""Run unit tests."""
return all([test_balance(), test_completed(), test_gen_change_combos(),
test_gen_changes(), test_move()])
# Main
def main(just_one=False, bfs=True):
"""Call solver and print solutions."""
tower = PEOPLE + WEIGHTS
ground = []
balance = Balance()
world = (tower, balance, ground)
solutions = find_solutions(world, just_one, bfs)
print_solutions(solutions, 3)
return len(solutions)
if __name__ == '__main__':
unit_tests()
if len(sys.argv) == 3:
main(int(sys.argv[1]), int(sys.argv[2]))
else:
main()
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.