Solver for "Blacksmith Khecho's Ingenuity"

blacksmith.py

"""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()