Skip to content

Instantly share code, notes, and snippets.

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

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 =  * 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 = (, Balance(), PEOPLE + ) assert is_completed(world), "World should be complete" + str(world) world = (, Balance(), ) 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, ), {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, ), {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), int(sys.argv)) else: main()
to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.