frog.py

#!/usr/bin/python3

"""
Solver for the "Frog Puzzle" Android game.
Does not implement sinkable platforms.
Is not efficient at searching; naively tries all combos of labels.
"""

from collections import namedtuple, defaultdict
import itertools

# Directions
UP=(0,1)
RIGHT=(1,0)
DOWN=(0,-1)
LEFT=(-1,0)
DIRS=(UP,RIGHT,DOWN,LEFT)

# Node (=tile) labels (=types)
WATER='.'
EMPTY='#'
TELEPORTS='ABCDE'
START='s'
FINISH='f'
REWIND3='3'
JUMP='J'
USER_LABELS=EMPTY+'^<>v'+REWIND3+JUMP  # 4 directions, 3-back, jump, empty
FIXED_LABELS=TELEPORTS+START+FINISH+WATER  # teleports, start, finish

# Result of simulation
SUCCESS = 0
SOME_UNVISITED = 1  # reached finish without visiting all nodes
DROWNED = 2
HISTORY_DEPLETED = 3
INFINITE_LOOP = 4
SIMULATION_LIMIT = 5

class Graph:
    def __init__(self, nodes):
        """
        Initialize graph. `nodes` is a mapping from grid coords (x,y) to the label
        """
        self.nodes = nodes  # grid coords -> Node
        self.teleport_pair = {}  # teleport coordinates -> coordinates of the other endpoint
        self.start = (-1, -1)
        self.finish = (-1, -1)
        self.num_to_visit = 0 # number of nodes to visit, excluding the finish node

        # Initialize teleports
        for t in TELEPORTS:
            pair = [xy for (xy,label) in nodes.items() if label==t]
            assert len(pair) in (0,2), ("Teleport %s is not OK" % label)
            if not pair: continue
            self.teleport_pair[pair[0]] = pair[1]
            self.teleport_pair[pair[1]] = pair[0]

        # Initialize special points
        starts = [xy for (xy,label) in nodes.items() if label==START]
        finishes = [xy for (xy,label) in nodes.items() if label==FINISH]
        assert len(starts) == len(finishes) == 1
        self.start = starts[0]
        self.finish = finishes[0]

        # Initialize others
        self.num_to_visit = len([xy for (xy,label) in nodes.items() if label != WATER and label != FINISH])

    @classmethod
    def from_string(cls, s):
        nodes = defaultdict(lambda: WATER)
        grid = [list(line.strip()) for line in s.splitlines() if line.strip()]
        for y_inv, line in enumerate(grid):
            y = len(grid) - 1 - y_inv  # index of row in `grid` is the "inverse y"; our coord system has y=0 at the bottom
            for x, label in enumerate(line):
                nodes[(x,y)] = label
        return cls(nodes)

    def to_string(self):
        ret = ''
        max_x = max(x for ((x,y), label) in self.nodes.items() if label!=WATER)
        max_y = max(y for ((x,y), label) in self.nodes.items() if label!=WATER)
        for y in range(max_y,-1,-1):
            for x in range(max_x + 1):
                ret += self.nodes[(x,y)]
            ret += '\n'
        return ret

    __str__ = to_string

    def simulate(self, max_steps=10000):
        """
        Simulates at most `max_steps` from start. Simulation usually terminates earlier 
        because the method detects death, an infinite loop, or success. Returns a 
        (status, (x,y)) pair describing how and where the simulation ended.
        """
        pos = self.start
        heading = UP
        hist = []
        # Set of visited unique positions (regardless of heading); to track completion
        visited_pos = set()
        # Set of encountered full states; to track infinite loops.
        visited_state = set()
        # True iff the most recent step was a teleport or history rewind. If so,
        # we have to not change the heading in the upcoming step.
        is_heading_frozen = False
    
        for step in range(max_steps):
            if False:  # debug
                print('\n' + str(self))
                print('^^^ Before step %d;  position is %r;  heading is %s;  visited %d/%d;  history is %r' % (step, pos, ('LEFT' if heading==(-1,0) else 'RIGHT' if heading==(1,0) else 'DOWN' if heading==(0,-1) else 'UP' if heading==(0,1) else 'UNKNOWN:%r' % heading), len(visited_pos), self.num_to_visit, hist))

            lbl = self.nodes[pos]

            # Check for stopping condition
            if lbl == FINISH:
                if len(visited_pos) == self.num_to_visit: return SUCCESS, pos
                else: return SOME_UNVISITED, pos
            elif lbl == WATER:
                return DROWNED, pos

            # Log the move
            hist.append(pos)
            visited_pos.add(pos)
            if (pos, heading, len(visited_pos)) in visited_state:
                return INFINITE_LOOP, pos
            visited_state.add((pos, heading, len(visited_pos)))
            
            # Advance
            if lbl == EMPTY or lbl == START or is_heading_frozen:
                pos = (pos[0]+heading[0], pos[1]+heading[1])
                is_heading_frozen = False
            elif lbl in '<>^v':
                heading = (LEFT if lbl=='<' else RIGHT if lbl=='>' else UP if lbl=='^' else DOWN)
                pos = (pos[0]+heading[0], pos[1]+heading[1])
                is_heading_frozen = False
            elif lbl == JUMP:
                pos = (pos[0]+2*heading[0], pos[1]+2*heading[1])
                is_heading_frozen = False
            elif lbl == REWIND3:
                if len(hist) < 4: return HISTORY_DEPLETED, pos
                hist.pop()
                hist.pop()
                hist.pop()
                pos = hist[-1]  # leave direction as-is
                hist.pop()  # the new/old location will be reinserted into hist in next iteration
                is_heading_frozen = True                
            elif lbl in TELEPORTS:
                pos = self.teleport_pair[pos]
                is_heading_frozen = True
            else:
                raise NotImplementedError("Don't know how to handle fields with label "+repr(lbl))


        print('WARNING: Failed to detect infinite loop in graph:\n'+str(self))
        return SIMULATION_LIMIT, pos

    def solve(self):
        '''
        Relabels self.nodes with a solution to the puzzle, and return True.
        If the puzzle is unsolvable, returns False, and labels on nodes might be arbitrary.
        '''
        # Nodes on which the user is able to change the label.
        editable_nodes = [xy for (xy, label) in self.nodes.items() if label==EMPTY]

        for i, labels in enumerate(itertools.product(USER_LABELS, repeat=len(editable_nodes))):
            if i and not i%1000000: print('Tried %d labelings out of %d' % (i, len(USER_LABELS)**len(editable_nodes)))
            for xy, label in zip(editable_nodes, labels):
                self.nodes[xy] = label
            result = self.simulate()
            if result[0] == SUCCESS: return True
        return False

def tests():
    # Test basic parsing
    g = Graph.from_string("""
      ...
      sf.
    """)
    assert g.nodes == {
            (0,0): 's',
            (0,1): '.',
            (1,0): 'f',
            (1,1): '.',
            (2,0): '.',
            (2,1): '.',
    }, "Nodes are %r" % g.nodes
    
    # Test teleports
    g = Graph.from_string("""
      C3f
      #sC
    """)
    assert g.teleport_pair == {
            (0,1): (2,0),
            (2,0): (0,1),
    }, "Teleports are %r" % g.teleport_pair
    
    # Test to_string
    g = Graph.from_string("""
      C3.
      sfC
    """)
    s = g.to_string()
    assert s == 'C3.\nsfC\n', 'str(g) == '+repr(s)
    
    # Test straight linesi and completion criteria
    g = Graph.from_string("f\ns")
    result = g.simulate(max_steps=3)
    assert result == (SUCCESS, (0,1)), 'Unexpected result: ' + repr(result)

    g = Graph.from_string("f\n#\n#\ns")
    result = g.simulate()
    assert result == (SUCCESS, (0,3)), 'Unexpected result: ' + repr(result)


    # Test simple turns
    g = Graph.from_string(">f\ns.")
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)

    g = Graph.from_string("f<\n.s")
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)

    g = Graph.from_string(".f\n>^\ns.")
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)

    g = Graph.from_string("v\ns\nf")
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)


    # Test complex turns
    g = Graph.from_string("""
      >###v
      #...#
      #.f.#
      s.^#<
    """)
    result = g.simulate()
    assert result == (SUCCESS, (2,1)), 'Unexpected result: ' + repr(result)
    
    # Test jumps 
    g = Graph.from_string("f\n.\nJ\ns")
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)
    
    g = Graph.from_string(">Jf<\ns...")
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)
    
    g = Graph.from_string("f\nJ\ns")
    result = g.simulate()
    assert result[0] == DROWNED, 'Unexpected result: ' + repr(result)

    # Test teleports
    g = Graph.from_string(">B.Bf\ns....")
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)
    
    g = Graph.from_string(">ABAB<\ns.f...")
    result = g.simulate()
    assert result[0] == INFINITE_LOOP, 'Unexpected result: ' + repr(result)
    
    g = Graph.from_string("""
        .f...
        >A.Av
        s..^<
    """)
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)
    
    # Test 3back
    g = Graph.from_string("""
        >J.3
        sf..
    """)
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)
    
    g = Graph.from_string("""
        >J.3
        s#3f
    """)
    result = g.simulate()
    assert result[0] == HISTORY_DEPLETED, 'Unexpected result: ' + repr(result)

    g = Graph.from_string("""
        >>3
        s^f
    """)
    result = g.simulate()
    assert result[0] == INFINITE_LOOP, 'Unexpected result: ' + repr(result)
    
    g = Graph.from_string("""
        .f.
        >C3
        sC^
    """)
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)
    
    # Test complex level
    g = Graph.from_string("""
        ..v.
        fAJ.
        v3JA
        #.s.
        33<.
    """)
    result = g.simulate()
    assert result[0] == SUCCESS, 'Unexpected result: ' + repr(result)
    
    # Test autosolve
    g = Graph.from_string("""
        ##
        sf
    """)
    assert g.solve()
    assert str(g) == """
        >v
        sf
    """.replace(' ','').lstrip('\n'), 'Bad solution: ' + str(g)

    g = Graph.from_string("""
        ..#.
        fA#.
        ###A
        #.s.
        ###.
    """)
    assert g.solve()
    assert str(g) == """
        ..v.
        fAJ.
        v3JA
        v.s.
        33<.
    """.replace(' ','').lstrip('\n'), 'Bad solution: ' + str(g)
    
    # Success
    print('All tests pass')
    
def main():
    # Solve a hardcoded puzzle
    g = Graph.from_string("""
        .A##B.
        ..#...
        B###..
        .C#CAf
        ..s...
    """)
    g = Graph.from_string("""
        ###
        A.A
        #.#
        s.#
        ##f
    """)
    g = Graph.from_string("""
        fB###A.
        .......
        #B###A#
        ...s...
    """)
    g = Graph.from_string("""
        DC.BA
        ####E
        ##s##
        C#E#B
        .DfA.
    """)
    if g.solve():
        print(g)
    else:
        print('No solution known')

if __name__=='__main__':
    #tests()
    main()