#!/usr/bin/python

#
# toki.py - Brute-force solver for Toki Tori levels with no enemies
#
# Copyright (C) 2008 Christian Bauer <www.cebix.net>
#
# Permission to use, copy, modify, and/or distribute this software for any
# purpose with or without fee is hereby granted, provided that the above
# copyright notice and this permission notice appear in all copies.
#

# Notes:
# - World positions are (x, y) tuples of integer tile coordinates;
#   the x axis points left, the y axis points down.
# - Object positions refer to the upper left tile of the object (eggs and the
#   player are 2x2 tiles large).
# - The move algorithms don't check for the map bounds, so there should be a
#   1-tile impassable border around the left, right and bottom sides of the
#   map).
# - The algorithms are not suitable for dealing with enemies (e.g. different
#   paths to the same destination to avoid enemies are not considered).
# - The program finds one possible solution, but not necessarily the most
#   efficient one.
#
# Level design restrictions:
# - Eggs should not be hovering (they are not collected while falling).
# - Eggs should not overlap impassable areas.
# - The player's start position should not overlap impassable areas.
# - Ladders must have solid ground at the bottom and a 2x2 passable space at
#   the top.
#
# TODO:
# - Prevent the building of bridges and the throwing of rocks on top of eggs.
#   Maybe paint eggs into the map?
#
# Possible optimizations:
# - Avoid duplicate code in Bridge*Action, Warp*Action and Rock*Action
#   classes.
# - Don't waste a warp when you can just walk to the destination.
# - After computing the possible move actions, recompute/optimize the paths,
#   and sort the actions by path length to give preference to shorter paths.


import copy


# Tile types:
# ' ' - empty/passable
# 'X' - impassable (wall/floor/bridge/rock)
# 'H' - ladder
# 'B' - switchable block


# Object representing the current state of the world.
#
# Attributes:
# map - world map as a list of strings; each string represents one
#       row of the map, each character represents one tile of the row
# player - player position
# eggs - set of egg positions
# remainingBridges - remaining number of bridges the player can build
# remainingWarps - remaining number of warps the player can use
# remainingRocks - remaining number of rocks the player can use
# remainingSwitches - remaining number of blocks the player can switch
class World(object):
    def __init__(self):
        self.map = []
        self.player = (0, 0)
        self.eggs = set()
        self.remainingBridges = 0
        self.remainingWarps = 0
        self.remainingRocks = 0
        self.remainingSwitches = 0

    # Print the map with all objects.
    def __str__(self):

        # Copy the map
        map = self.map[:]

        # Paint the player
        paint2x2(map, self.player, 'T')

        # Paint the eggs
        for egg in self.eggs:
            paint2x2(map, egg, 'E')

        # Concatenate the strings
        return '\n'.join(map)


# Paint a 2x1 object on the map.
def paint2x1(map, pos, tile):
    x, y = pos
    map[y] = map[y][:x] + tile + tile + map[y][x+2:]


# Paint a 1xx object on the map.
def paint1x2(map, pos, tile):
    x, y = pos
    map[y] = map[y][:x] + tile + map[y][x+1:]
    map[y+1] = map[y+1][:x] + tile + map[y+1][x+1:]


# Paint a 2x2 object on the map.
def paint2x2(map, pos, tile):
    x, y = pos
    map[y] = map[y][:x] + tile + tile + map[y][x+2:]
    map[y+1] = map[y+1][:x] + tile + tile + map[y+1][x+2:]


# Returns true if a the player can walk through a tile on the map (= the
# tile is empty or a ladder).
def tileWalkable(map, pos):
    tile = map[pos[1]][pos[0]]
    return tile == ' ' or tile == 'H'


# Returns true if a the player can be placed on a position on the map
# (2x2 square).
def positionWalkable(map, pos):
    return tileWalkable(map, pos) and tileWalkable(map, (pos[0]+1, pos[1])) \
       and tileWalkable(map, (pos[0], pos[1]+1)) and tileWalkable(map, (pos[0]+1, pos[1]+1))


# Returns true if a 2x2 object can be placed on a position on the map.
def positionEmpty(map, pos):
    x, y = pos
    return map[y][x] == ' ' and map[y][x+1] == ' ' and map[y+1][x] == ' ' and map[y+1][x+1] == ' '


# Return the final position of a 1x2 object after possibly falling down
# from the given position.
# (Note: Ladders are passable, but they block a fall.)
def fall1x2(map, pos):
    x, y = pos
    while map[y+2][x] == ' ':
        y += 1
    return (x, y)


# Return the final position of a 2x2 object after possibly falling down
# from the given position.
# (Note: Ladders are passable, but they block a fall.)
def fall2x2(map, pos):
    x, y = pos
    while map[y+2][x] == ' ' and map[y+2][x+1] == ' ':
        y += 1
    return (x, y)


# Return the set of eggs the player can collect at the given position.
def collectedEggs(world, pos):
    x, y = pos
    collect = set()

    for egg in world.eggs:
        if egg[0] >= x-1 and egg[0] <= x+1 and egg[1] >= y-1 and egg[1] <= y+1:
            collect.add(egg)

    return collect


# Action: Move player
#
# Attributes:
# to - target position
# path - string describing the player's path to the target (for reference)
# collect - whether an egg is collected at the target position
class MoveAction(object):
    def __init__(self, to, path, collect):
        self.to = to
        self.path = path
        self.collect = collect

    def __repr__(self):
        return "MoveAction(%r, %r, %r)" % (self.to, self.path, self.collect)

    def __str__(self):
        return "Move to %s, for example by going %s" % (self.to, self.path)

    # Note: There is no possible() method because we never generate
    # impossible movements in the first place.

    # Execute the action in the world
    def execute(self, world):
        world.player = self.to
        if self.collect:
            world.eggs.difference_update(collectedEggs(world, self.to))


# Action: Build bridge to the left
class BridgeLeftAction(object):
    def __repr__(self):
        return "BridgeLeftAction()"

    def __str__(self):
        return "Build bridge to the left"

    # Is the action possible?
    def possible(self, world):
        if world.remainingBridges == 0:
            return False

        x, y = world.player

        if world.map[y+2][x] == ' ' and world.map[y+2][x-1] == ' ':
            return True  # player will partly stand on the bridge
        if world.map[y+2][x-1] == ' ' and world.map[y+2][x-2] == ' ':
            return True  # bridge to the left of the player
        return False

    # Execute the action in the world
    def execute(self, world):
        x, y = world.player

        if world.map[y+2][x] == ' ':
            bridgeX = x-1  # player partly stands on the bridge
        else:
            bridgeX = x-2  # bridge to the left of the player

        paint2x1(world.map, (bridgeX, y+2), 'X')
        world.remainingBridges -= 1


# Action: Build bridge to the right
class BridgeRightAction(object):
    def __repr__(self):
        return "BridgeRightAction()"

    def __str__(self):
        return "Build bridge to the right"

    # Is the action possible?
    def possible(self, world):
        if world.remainingBridges == 0:
            return False

        x, y = world.player

        if world.map[y+2][x+1] == ' ' and world.map[y+2][x+2] == ' ':
            return True  # player will partly stand on the bridge
        if world.map[y+2][x+2] == ' ' and world.map[y+2][x+3] == ' ':
            return True  # bridge to the right of the player
        return False

    # Execute the action in the world
    def execute(self, world):
        x, y = world.player

        if world.map[y+2][x+1] == ' ':
            bridgeX = x+1  # player partly stands on the bridge
        else:
            bridgeX = x+2  # bridge to the right of the player

        paint2x1(world.map, (bridgeX, y+2), 'X')
        world.remainingBridges -= 1


# Action: Warp left
# (Note: It is possible to warp onto ladders.)
class WarpLeftAction(object):
    def __repr__(self):
        return "WarpLeftAction()"

    def __str__(self):
        return "Warp to the left"

    # Is the action possible?
    def possible(self, world):
        if world.remainingWarps == 0:
            return False

        x = world.player[0]
        return x >= 4 and positionWalkable(world.map, (x-4, world.player[1]))

    # Execute the action in the world
    def execute(self, world):
        world.player = fall2x2(world.map, (world.player[0] - 4, world.player[1]))
        world.eggs.difference_update(collectedEggs(world, world.player))
        world.remainingWarps -= 1


# Action: Warp right
# (Note: It is possible to warp onto ladders.)
class WarpRightAction(object):
    def __repr__(self):
        return "WarpRightAction()"

    def __str__(self):
        return "Warp to the right"

    # Is the action possible?
    def possible(self, world):
        if world.remainingWarps == 0:
            return False

        x = world.player[0]
        return x <= len(world.map[0])-6 and positionWalkable(world.map, (x+4, world.player[1]))

    # Execute the action in the world
    def execute(self, world):
        world.player = fall2x2(world.map, (world.player[0] + 4, world.player[1]))
        world.eggs.difference_update(collectedEggs(world, world.player))
        world.remainingWarps -= 1


# Action: Warp up
# (Note: It is possible to warp onto ladders.)
class WarpUpAction(object):
    def __repr__(self):
        return "WarpUpAction()"

    def __str__(self):
        return "Warp up"

    # Is the action possible?
    def possible(self, world):
        if world.remainingWarps == 0:
            return False

        y = world.player[1]
        return y >= 4 and positionWalkable(world.map, (world.player[0], y-4))

    # Execute the action in the world
    def execute(self, world):
        world.player = fall2x2(world.map, (world.player[0], world.player[1] - 4))
        world.eggs.difference_update(collectedEggs(world, world.player))
        world.remainingWarps -= 1


# Action: Warp down
# (Note: It is possible to warp onto ladders.)
class WarpDownAction(object):
    def __repr__(self):
        return "WarpDownAction()"

    def __str__(self):
        return "Warp down"

    # Is the action possible?
    def possible(self, world):
        if world.remainingWarps == 0:
            return False

        y = world.player[1]
        return y <= len(world.map)-6 and positionWalkable(world.map, (world.player[0], y+4))

    # Execute the action in the world
    def execute(self, world):
        world.player = fall2x2(world.map, (world.player[0], world.player[1] + 4))
        world.eggs.difference_update(collectedEggs(world, world.player))
        world.remainingWarps -= 1


# Action: Throw a rock to the left
class RockLeftAction(object):
    def __repr__(self):
        return "RockLeftAction()"

    def __str__(self):
        return "Throw rock to the left"

    # Is the action possible?
    def possible(self, world):
        if world.remainingRocks == 0:
            return False

        if world.player[0] < 2:
            return False

        return positionEmpty(world.map, (world.player[0] - 2, world.player[1]))

    # Execute the action in the world
    def execute(self, world):
        final = fall2x2(world.map, (world.player[0] - 2, world.player[1]))
        paint2x2(world.map, final, 'X')
        world.remainingRocks -= 1


# Action: Throw a rock to the right
class RockRightAction(object):
    def __repr__(self):
        return "RockRightAction()"

    def __str__(self):
        return "Throw rock to the right"

    # Is the action possible?
    def possible(self, world):
        if world.remainingRocks == 0:
            return False

        if world.player[0] > len(world.map[0]) - 4:
            return False

        return positionEmpty(world.map, (world.player[0] + 2, world.player[1]))

    # Execute the action in the world
    def execute(self, world):
        final = fall2x2(world.map, (world.player[0] + 2, world.player[1]))
        paint2x2(world.map, final, 'X')
        world.remainingRocks -= 1


# Action: Switch blocks
class BlockSwitchAction(object):
    def __repr__(self):
        return "BlockSwitchAction()"

    def __str__(self):
        return "Switch block"

    # Is the action possible?
    def possible(self, world):
        if world.remainingSwitches == 0:
            return False

        x, y = world.player

        if world.map[y][x-1] == 'B' and world.map[y+1][x-1] == 'B' and \
           world.map[y][x+2] == ' ' and world.map[y+1][x+2] == ' ':
            return True  # switch left -> right
        if world.map[y][x-1] == ' ' and world.map[y+1][x-1] == ' ' and \
           world.map[y][x+2] == 'B' and world.map[y+1][x+2] == 'B':
            return True  # switch right -> left

        return False

    # Execute the action in the world
    def execute(self, world):
        x, y = world.player

        if world.map[y][x-1] == 'B':
            fromX = x - 1
            toX = x + 2
        else:
            fromX = x + 2
            toX = x - 1

        paint1x2(world.map, (fromX, y), ' ')
        paint1x2(world.map, fall1x2(world.map, (toX, y)), 'B')
        world.remainingSwitches -= 1


# Return the list of move actions possible from the given position.
# Note: The returned paths are possible paths, and not necessarily the
# shortest ones.
#
# world - current world state
# pos - current position of the player
# checkedPositions - set of positions already checked by the algorithm
# lastMove - last executed move action, keeps track of the path
def possibleMoveActions(world, pos, checkedPositions = None, lastMove = None):
    if not checkedPositions:
        checkedPositions = set([pos])  # mutable, so addMove() and deeper recursion levels can update it

    moves = []
    x, y = pos

    def addMove(pos, step):
        # Possibly fall downwards after the step (note: we don't need to
        # check for eggs along the way down because this would mean that
        # eggs were hovering)
        final = fall2x2(world.map, pos)
        if final != pos:
            step = step + '(drop)'

        # Final position already considered via a different path?
        if final not in checkedPositions:

            # No, add it
            collect = len(collectedEggs(world, final)) > 0
            if lastMove:
                # Append step to path
                move = copy.deepcopy(lastMove)
                move.to = final
                move.path = move.path + step
                move.collect = collect
            else:
                # Initial step of path
                move = MoveAction(final, step, collect)

            # Append this move
            moves.append(move)
            checkedPositions.add(final)

            # If we haven't collected an egg, continue searching from the
            # new position
            if not collect:
                moves.extend(possibleMoveActions(world, final, checkedPositions, move))

    # Check whether we can move to the left
    if tileWalkable(world.map, (x-1, y)) and tileWalkable(world.map, (x-1, y+1)):
        addMove((x-1, y), 'L')  # straight
    elif tileWalkable(world.map, (x-1, y-1)) and tileWalkable(world.map, (x-1, y)) and world.map[y+1][x] != 'H':  # avoid side-climbing off ladders
        addMove((x-1, y-1), 'L^')  # climbing up one tile

    # Check whether we can move to the right
    if tileWalkable(world.map, (x+2, y)) and tileWalkable(world.map, (x+2, y+1)):
        addMove((x+1, y), 'R')  # straight
    elif tileWalkable(world.map, (x+2, y-1)) and tileWalkable(world.map, (x+2, y)) and world.map[y+1][x+1] != 'H':  # avoid side-climbing off ladders
        addMove((x+1, y-1), 'R^')  # climbing up one tile

    # Check whether we can move up a ladder
    if world.map[y+1][x] == 'H' and world.map[y+1][x+1] == 'H':  # Note: no check for free space at the top
        addMove((x, y-1), 'U')

    # Check whether we can move down a ladder
    if world.map[y+2][x] == 'H' and world.map[y+2][x+1] == 'H':
        addMove((x, y+1), 'D')

    return moves


class SolutionFound(Exception):
    def __init__(self, solution):
        self.solution = solution


# Recursively find a solution (= list of actions) for the given world.
# Raises a SolutionFound exception if successful.
#
# world - world state
# actions - tracks the previous actions
def solve(world, actions = []):
#    print actions

    # A solution is found if all eggs have been collected
    if len(world.eggs) == 0:
        raise SolutionFound(actions)

    lastAction = None
    if len(actions) > 0:
        lastAction = actions[-1]

    def performAction(action):
        # Perform an action and continue the search
        newWorld = copy.deepcopy(world)
        action.execute(newWorld)
        solve(newWorld, actions + [action])

    # Try special actions
    tryActions = [BridgeLeftAction(), BridgeRightAction(),
                  WarpLeftAction(), WarpRightAction(), WarpUpAction(), WarpDownAction(),
                  RockLeftAction(), RockRightAction()]
    if not isinstance(lastAction, BlockSwitchAction):
        tryActions.append(BlockSwitchAction())  # switching two times in a row is always pointless

    for action in tryActions:
        if action.possible(world):
            performAction(action)

    # Try to move (only if the last action wasn't a move that collected
    # no eggs; because then a single move would suffice)
    if not isinstance(lastAction, MoveAction) or isinstance(lastAction, MoveAction) and lastAction.collect:
        moves = possibleMoveActions(world, world.player)
        for move in moves:
            performAction(move)


# Solve a world and print the solution.
def run(world):
    print world
    print
    try:
        solve(world)
        print "No solution found!"
    except SolutionFound, e:
        print "Solution found (%d steps):" % len(e.solution)
        for action in e.solution:
            print
            print action
            print
            action.execute(world)
            print world


# Test world
test = World()
test.map = [ "X B         X",
             "X B         X",
             "XXXHHXHH  XXX",
             "X  HH HH    X",
             "X  HH HHX   X",
             "XXXXXXXXXXXXX" ]
test.player = (1, 3)
test.eggs = set([(10, 0)])
test.remainingBridges = 0
test.remainingWarps = 0
test.remainingRocks = 0
test.remainingSwitches = 2


# Forest, Level 1
w1l1 = World()
w1l1.map = [ "XX                         XXXXX",
             "XX                         XXXXX",
             "XX               HHXXX       XXX",
             "XX               HHXXXXX     XXX",
             "XXXXXXXXXXX      HHXXXXXXX     X",
             "XXXXXXXXX        HHXXXXXXX     X",
             "XXXXXXXXX      XXXXXXXXXXX     X",
             "XX  XXXXXXXXXXXXXXXXXXXXXX    XX",
             "X      XXXXXXXXXXXXXXXX       XX",
             "X        XXXXXXXXXXX          XX",
             "XX                            XX",
             "XX                        XXXXXX",
             "XX                     XXXXXXXXX",
             "XX     XXXXXXXXXXXXXXXXXXXXXXXXX",
             "XXX  XXXXXXXXXXXXXXXXXXXXXXXXXXX",
             "XXX  XXXXXXXXXXXXXXXXXXXXXXXXXXX",
             "XXX    XXXXXXXXXXXXXXXXXX     XX",
             "XX      XX                    XX",
             "XXX     XX                    XX",
             "XXX         XXXXXXXXXXXXXXHHXXXX",
             "XXXXX       XXXXX     XXXXHHXXXX",
             "XXXXX                     HH  XX",
             "XXXXX                     HH  XX",
             "XXXXXXX                   HH  XX",
             "XXXXXXX         XXXXXXX   HH  XX",
             "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ]
w1l1.player = (3, 2)
w1l1.eggs = set([(15, 4), (26, 9), (15, 11), (5, 12), (5, 21), (14, 23), (24, 23), (26, 17), (14, 17)])


# Forest, Object 1 (Bridge)
w1o1 = World()
w1o1.map = [ "XXXXXXXXXXXXXXXXXXXXXXXXXX",
             "XXXXXXXXXXXXXXXXXXXX    XX",
             "XXXXXXXXXXXX   XXXX      X",
             "XXXXX          XX        X",
             "XXX                  HHXXX",
             "XXX                  HHXXX",
             "XXX            XX  XXHHXXX",
             "XX             XX  XXHHXXX",
             "XX     XX  XXHHXX  XXHHXXX",
             "XX     XX  XXHHXX    HH XX",
             "XX     XX    HHXX    HH XX",
             "XX     XX    HHXXHHXXXXXXX",
             "X      XXXXXXXXXXHH  XXXXX",
             "X        XXXXXXXXHH    XXX",
             "X X              HH    XXX",
             "XXXXXXX          HH   XXXX",
             "XXXXXXXXXXX    XXXXXXXXXXX",
             "XXXXXXXXXXX    XXXXXXXXXXX",
             "XXXXXXXXXXXXXXXXXXXXXXXXXX" ]
w1o1.player = (9, 10)
w1o1.eggs = set([(15, 4), (23, 2)])
w1o1.remainingBridges = 4


# Forest, Level 2
w1l2 = World()
w1l2.map = [ "XX                              X",
             "XX                              X",
             "XX   X     XXXXXXXXXXXXXXHHXX   X",
             "XXXXXX     XXXXXXXXXXXXXXHHXX   X",
             "XXXXXX                   HH     X",
             "XXXXXX                   HH     X",
             "XXXX     HHXXXXX  XXXXXXXXX  XXXX",
             "XX       HHXX        XXXXXX    XX",
             "X        HHXX        XXXXXX    XX",
             "XX       HHXXXX    XXXX  XX     X",
             "XXX     XXXXXXXX  XXXXX  XX     X",
             "XXXHHXXXXXXXXXXX  XXXXX  XX     X",
             "XXXHHXXXXXXXX        XX  XX    XX",
             "XXXHHXXXXXXXX        XX        XX",
             "XXXHHXXXXX      XX   XX      XXXX",
             "XXXHHXXXXX     XXXXXXXX    XXXXXX",
             "XXXHH       XXXXXXXXXXX    XXXXXX",
             "XXXHH       XXXXXXXXXXXHHXXXXXXXX",
             "XXXHH       XXXXXXXXXXXHHXXXXXXXX",
             "XXXHH       XXXXXXXXXXXHHXXXXXXXX",
             "XXXXXXXXXXHH           HHXXXXXXXX",
             "XXXXXXXXXXHH           HHXXXXXXXX",
             "XXXXXXXXXXXXXXXXXXHHXXXXXXXXXXXXX",
             "XXX      XXXXXXXXXHHXXXXXXXXXXXXX",
             "XXX       XX      HHXX  XX  XXXXX",
             "XXX       XX      HHXX  XXX XXXXX",
             "XXX       XXXXXXXXXXXXXXXXXXXXXXX",
             "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX" ]
w1l2.player = (18, 13)
w1l2.eggs = set([(11, 0), (22, 4), (5, 9), (27, 13), (25, 15), (12, 24)])
w1l2.remainingBridges = 1


# Castle, Hard 6
w2h6 = World()
w2h6.map = [ "X              XXX",
             "X              XXX",
             "X   XX         XXX",
             "X              XXX",
             "X              XXX",
             "X    B         XXX",
             "X    B         XXX",
             "XHHXXXX          X",
             "XHH      XX      X",
             "XHH      XX    XXX",
             "XHH            XXX",
             "XHH            XXX",
             "XXXXXXXX       XXX",
             "XXXXXXXX       XXX",
             "XXXXXXXX       XXX",
             "XXXXXXXXXXXXXXXXXX" ]
w2h6.player = (4, 10)
w2h6.eggs = set([(4, 0), (15, 7)])
w2h6.remainingBridges = 5
w2h6.remainingWarps = 2
w2h6.remainingSwitches = 4


# Sewer, Hard 6
w3h6 = World()
w3h6.map = [ "X     XXXXX",
             "X         X",
             "XXX       X",
             "XX      XXX",
             "X         X",
             "X         X",
             "X       XXX",
             "X         X",
             "XXXXXX    X",
             "XXXXXXXXXXX" ]
w3h6.player = (1, 0)
w3h6.eggs = set([(8, 1), (8, 4)])
w3h6.remainingBridges = 1
w3h6.remainingWarps = 2
w3h6.remainingRocks = 2


run(w3h6)