River Fording Puzzle v2

fording_puzzle_v2.py

"""River Fording Puzzle.

3 girls, each with her father, go for a stroll. They come to a small river.
One boat, able to carry 2 persons at a time, is at their disposal.

Crossing would be simple for everyone except the girls. None is willing to be 
in the boat or ashore with 1 or 2 strange fathers, unless her own father is 
present too. How do they all get across?
"""

from itertools import combinations, permutations 
from collections import deque

BOAT_SIZE = 3
GIRLS = frozenset(['G1', 'G2', 'G3', 'G4'])
FATHERS = frozenset(['F1', 'F2', 'F3', 'F4'])
RELATIONS = dict(zip(sorted(GIRLS), sorted(FATHERS)))

# World

def genesis(near):
    """Return tuple representation of initial world."""
    boat, far = set([]), set([])
    boat_near = 1
    return (near, boat, far, boat_near)

def show(world):
    """Return string representation of world."""
    near, boat, far, boat_near = world

    near_str = str.ljust(' '.join(sorted(near)), 24)
    far_str = str.rjust(' '.join(sorted(far)), 24)
    boat_str = ' | ' + str.rjust(' '.join(boat), 8) + ' | '
    empty = ' ' * 14
    river = (boat_str + '~ ~ ~' + empty if boat_near else 
             empty + '~ ~ ~' + boat_str)

    return ' '.join([near_str, river, far_str])

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 'Solution #', ind + 1, 'of', len(solutions), '\n'
        print '\n'.join(show(line) for line in history)

# Validation

def is_complete(world):
    """Return True if world is complete, i.e. near shore and boat are empty."""
    near, boat, _, _ = world
    return near == set([]) and boat == set([]) 

def is_valid(group):
    """Return True if set of ppl is valid, i.e. no girl with strange father."""
    girls = group & GIRLS 
    fathers = group & FATHERS 
    return all(RELATIONS[girl] in group for girl in girls if fathers)

def valid_world(world):
    """Return True if all locations of world are valid."""
    near, boat, far, _ = world
    return is_valid(near) and is_valid(boat) and is_valid(far)

# Core Game Funcs 

def flatten(lists):
    """Flatten list of sublists of iterables into list of iterables."""
    return [item for sublist in lists for item in sublist]

def draw_sublists(loc, max_ppl=2):
    """Draw all valid permtutations of groups of people of size 1 to max_ppl.
    Draw all combinations first, then find permutations of the combinations.
    """
    combos = [ppl for n in xrange(max_ppl) for ppl in combinations(loc, n + 1)
              if is_valid(set(ppl))]
    perms = [permutations(ppl) for ppl in combos]
    return [()] + flatten(perms) 

def apply_delta(world, delta, load_boat):
    """Transfer people between boat and the boat's current shore.
    People are transferred one at a time (recursively).
    Args
        world: tuple of game world
        delta: tuple of people to swap 
        load_boat: boolean, load boat if True, else unload boat
    Returns
        New world with delta applied if world is valid, else empty tuple.
    """

    near, boat, far, boat_near = world
    
    # return null if invalid world or loading an empty boat
    if not valid_world(world): return ()
    if load_boat and boat == set([]) and not delta: return ()
    
    # base case, deltas applied to valid world, move boat and return new world
    if not delta:
        boat_loc = boat_near ^ True if load_boat else boat_near
        return (near, boat, far, boat_loc)
    
    # find appropriate set delta action and apply recursively
    boat_f = boat.union if load_boat else boat.difference
    if boat_near:
        near_f = near.difference if load_boat else near.union
        far_f = lambda x: far
    else:
        near_f = lambda x: near
        far_f = far.difference if load_boat else far.union
    
    d = set([delta[0]])
    next_world = (near_f(d), boat_f(d), far_f(d), boat_near)

    return apply_delta(next_world, delta[1:], load_boat)

def boat_transfer(world, visited, load_boat):
    """Load or unload boat.
    Args
        world: tuple of game world
        visited: list of tuples of (world, load_boat)
        load_boat: boolean, load boat if True, else unload boat
    Returns
        (list of next game worlds, updated list of visited game worlds)
    """
    near, boat, far, boat_near = world

    if load_boat:
        loc, size = near if boat_near else far, BOAT_SIZE - len(boat)
    else:
        loc, size = boat, len(boat)
        
    deltas = draw_sublists(loc, size)
    next_worlds = []
    for delta in deltas:
        next_world = apply_delta(world, delta, load_boat)

        if next_world and (next_world, load_boat) not in visited:
            # exclude completed worlds so multiple solutions can be found
            if not is_complete(next_world):
                visited.append((next_world, load_boat))
            next_worlds.append(next_world)

    return next_worlds, visited

# Tests

def test_is_valid():
    """Test group validation logic, false positives and negatives..."""
    false_groups = ({'G1', 'G3', 'F2'}, {'G1', 'F3'}) 
    for g in false_groups:
        assert is_valid(g) is False, 'group should be invalid: ' + str(g)

    true_groups = ({'G1', 'G2'}, {'G1', 'F1'}, {'F1', 'F1'},
                   {'G2'}, {'F3'})
    for g in true_groups:
        assert is_valid(g) is True, 'group should be valid: ' + str(g)
    
    return True

def test_draw_sublists():
    """Test draw subslists."""
    sets = ([], 
            [(1,), (2,), (3,)],
            [(1,), (2,), (3,), (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3, 2)])
    group = {1, 2, 3}
    for n in xrange(3):
        comp = [()] + sets[n]
        assert draw_sublists(group, n) == comp, 'bad sublist: ' + str(group)
    
    return True

def test_apply_delta():
    """Test apply_deltas."""
    # loading one person at a time means this should yield empty list of worlds 
    world = ({'F1', 'F2', 'G1', 'G2'}, set([]), set([]), 1)
    deltas = ('F1', 'F2')
    load_boat = 1
    test = apply_delta(world, deltas, load_boat)
    assert test == (), 'delta: case should fail: ' + str(world) + str(deltas)
    
    deltas = ('G1', 'G2')
    load_boat = 1
    test = apply_delta(world, deltas, load_boat)
    new = ({'F1', 'F2'}, {'G1', 'G2'}, set([]), 0)
    assert test == new, 'delta: case should pass: ' + str(world) + str(new)

    return True

def test_valid_world():
    """Test valid_world."""
    world = ({'F1', 'F2', 'G1', 'G2'}, set([]), set([]), 1)
    assert valid_world(world), 'World is valid' + str(world)

    world = ({'F1', 'G1', 'G2'}, set([]), set([]), 1)
    assert not valid_world(world), 'World is invalid' + str(world)

    world = ({'F1', 'G1'}, set(['G2', 'F3']), set([]), 1)
    assert not valid_world(world), 'World is invalid' + str(world)

    world = ({'F1', 'G1'}, set(['G2']), set(['F2', 'G3']), 1)
    assert not valid_world(world), 'World is invalid' + str(world)
    
    return True

def unit_tests():
    """Run unit tests."""
    return all([test_is_valid(), test_draw_sublists(), test_apply_delta(),
                test_valid_world()])

# Main Solver

def find_solutions(start, mode):
    """Search through game space.
    Args
        start: starting world
        mode: string, BFS or DFS 
    Returns
        List of lists of world states leading to completion.
    """

    completed = []
    visited = [(start, True)]

    if mode == 'BFS':
        gen_history, pop_next = deque, deque.popleft
    else:
        gen_history, pop_next = list, list.pop
    histories = gen_history([([start], visited)])

    while histories:
        history, visited = pop_next(histories)

        # load boat
        on_worlds, visited = boat_transfer(history[-1], visited, True)
        
        # cross shore, offload boats
        for on_world in on_worlds:
            off_worlds, visited = boat_transfer(on_world, visited, False)

            # update history, add to completed list or enqueue for next iter
            for off_world in off_worlds:
                updates = [on_world, off_world]
                if is_complete(off_world):
                    completed.append(history + updates)
                else:
                    histories.append((history + updates, visited))

    return completed

def main(mode='BFS'):
    """Call solver and print top solutions."""

    nears = [set(['G1', 'G2', 'G3', 'G4', 'F1', 'F2', 'F3', 'F4'])]

    for near in nears:
        start = genesis(near) 
        solutions = find_solutions(start, mode)

        print '\nStart\t', str(near)
        print_solutions(solutions)

    return len(solutions)

if __name__ == '__main__':
    unit_tests()
    main()