#!/usr/bin/env python2.5

# ------ Versio 2 ------

import sys
import os
import os.path
import random
import copy

'''HippaZizzo: An artificial intelligence for playing tag game.

Maps are represented as lists inside lists, which contain letters
'H' (chaser), 'P' (runner), '-' (empty). Inner lists represent rows.
[['H', '-', '-'],
 ['P', '-', '-'],
 ['-', '-', '-']]
'''

###################################
# Utility functions

def mirror_x(field):
    '''Mirror field map by x axis'''
    return [row[::-1] for row in field]

def mirror_y(field):
    '''Mirror field map by y axis'''
    return field[::-1]

# Unit tests
assert (mirror_x([['H', '-', '-'],
                  ['P', '-', '-'],
                  ['-', '-', '-']])
         ==      [['-', '-', 'H'],
                  ['-', '-', 'P'],
                  ['-', '-', '-']])

assert (mirror_y([['H', '-', '-'],
                  ['P', '-', '-'],
                  ['-', '-', '-']])
         ==      [['-', '-', '-'],
                  ['P', '-', '-'],
                  ['H', '-', '-']])

def get_surroundings_index(surroundings):
    '''Get array index for surroundings, where surroundings is a
    sequence of 3 sequences of characters 'H', 'P' and '-'.
    
    Surroundings are mapped to index by converting the 9-digit
    base-3 number. Because of symmetry, there are 4 different numbers
    for each similar situation - the one with the smallest value is chosen.
    
    The array index is always less than or equal to 3**9 - 1 = 19682. This
    isn't very optimal implementation, as usually most of the situations
    do not happen (like map full of chasers). But 19kB for memory is not much.
    
    Returns the number, and a string of axises by which to mirror.
    '''
    
    def map_to_number(surroundings):
        assert len(surroundings) == 3
        result = 0
        multiplier = 1
        for row in surroundings:
            assert len(row) == 3
            for pos in row:
                result += multiplier * {'H': 1, 'P': 2, '-': 0}[pos]
                multiplier *= 3
        return result
    
    return min([(map_to_number(surroundings), ''),
                (map_to_number(mirror_x(surroundings)), 'x'),
                (map_to_number(mirror_y(surroundings)), 'y'),
                (map_to_number(mirror_x(mirror_y(surroundings))), 'xy')],
               key = lambda t: t[0])

# Unit tests
assert (get_surroundings_index([['H', '-', '-'],
                                ['-', 'P', '-'],
                                ['-', '-', '-']])[0]
        ==
        get_surroundings_index([['-', '-', '-'],
                                ['-', 'P', '-'],
                                ['-', '-', 'H']])[0])


assert (get_surroundings_index([['H', '-', '-'],
                                ['-', 'P', '-'],
                                ['-', '-', '-']])[0]
        !=
        get_surroundings_index([['P', '-', '-'],
                                ['-', 'H', '-'],
                                ['-', '-', '-']])[0])

class Memory:
    '''Stores past movements of opponent player. For each move, consider
        the 3x3 surroundings of a player instance and the corresponding
        action:
                      H--
        Surroundings: -P-    Action: -y
                      ---
        
        We assume that
            1) all opponent players use the same logic as long as the memory
               is persisted and
            2) actions are symmetric in x- and y- directions. Rotational
               symmetry is not assumed because even our own heuristics break
               against it.
        
        Surroundings are mapped to array index by get_surroundings_index().
        This index is equal for all maps that are mirrored by either axis.
        
        At the array index, the action of the opponent is stored. Memory is
        initialized to 'U' (unknown). If two different actions in the same
        situation are detected, it is marked as 'C' (complex).
    '''
    
    def __init__(self):
        if os.path.isfile("muisti.dat"):
            self.memfile = open("muisti.dat", "rb+")
        else:
            self.memfile = open("muisti.dat", "wb+")
            self.memfile.write('U' * (3**9 - 1))
    
    def add_situation(self, surroundings, action):
        '''Action should be 'x' (-x), 'y' (-y), 'X' (+x), 'Y' (+y)
        or '-' (no movement).
        '''
        assert action in ('x', 'y', 'X', 'Y', '-')
        
        pos, mirror = get_surroundings_index(surroundings)
        # Handle mirroring
        if action.lower() in mirror.lower():
            action = action.swapcase()
        
        self.memfile.seek(pos)
        old = self.memfile.read(1)
        
        if old == 'C':
            return # Do not update 'complex'
        elif old == 'U':
            self.memfile.seek(pos)
            self.memfile.write(action)
        elif old != action:
            self.memfile.seek(pos)
            self.memfile.write('C')
        
        self.memfile.flush()
    
    def get_action(self, surroundings):
        pos, mirror = get_surroundings_index(surroundings)
        self.memfile.seek(pos)
        raw = self.memfile.read(1)
        
        # Handle mirroring
        if raw.lower() in mirror.lower():
            return raw.swapcase()
        else:
            return raw


class Field:
    '''Field map for analysing the situation'''

    movetypes = {'y': (0, -1), 'x': (-1, 0),
                 'Y': (0, 1), 'X': (1, 0),
                 '-': (0, 0)}

    def __init__(self, players, maxX, maxY):
        '''Initialize the map with a list of players in the form:
            [[t, x, y], ...]
           Each inner list represents the type of the player ('H' or 'P') and
           a coordinate pair.
        '''
        self.players = players
        self.maxX = maxX
        self.maxY = maxY
    
    def clone(self):
        '''Return a clone of this field map'''
        return Field(copy.deepcopy(self.players), self.maxX, self.maxY)
    
    def apply_move(self, index, action):
        '''Apply move for player identified by index'''
        dx, dy = self.movetypes[action] # Position deltas
        
        self.players[index][1] += dx
        self.players[index][2] += dy

    def get_surroundings(self, index):
        '''Get surroundings for player identified by index'''
        cx, cy = self.players[index][1:3] # Player is in the center of surroundings
        
        result = []
        for y in [cy + 1, cy, cy - 1]:
            row = []
            for x in [cx - 1, cx, cx + 1]:
                for player in self.players:
                    if player[1] == x and player[2] == y:
                        row.append(player[0])
                        break # Only one char, even if multiple players in same pos
                else:
                    row.append('-')
            result.append(row)
        
        return result
    
    def get_choices(self, index):
        '''Get move choices for player identified by index'''
        cx, cy = self.players[index][1:3] # Current position
        
        choices = ['-']
        if cx != 1:
            choices.append('x')
        if cx != self.maxX:
            choices.append('X')
        if cy != 1:
            choices.append('y')
        if cy != self.maxY:
            choices.append('Y')
        
        return choices

    def count_catchers(self, direction):
        '''Count catchers in the specific map area:
            upper, lower, left or right half.
        '''
        if direction == '-':
            # Average number of catchers
            return len([t for t, x, y in self.players if t == 'H']) // 2
        
        mx, my = self.maxX + 1, self.maxY + 1
        xr, yr = {'x': (range(1, mx // 2), range(1, my)),
                  'X': (range(mx // 2, mx), range(1, my)),
                  'y': (range(1, mx), range(1, my // 2)),
                  'Y': (range(1, mx), range(my // 2, my))}[direction]
        
        count = 0
        for px in xr:
            for py in yr:
                for t, x, y in self.players:
                    if t == 'H' and x == px and y == py:
                        count += 1
        
        return count

def find_sure_escape(field, index):
    '''Find moves that avoid all possibilities of someone catching me'''
    
    def someone_might_catch_me(field, index):
        mx, my = field.players[index][1:3] # My position
        for move in Field.movetypes:
            for player in field.players:
                px, py = player[1:3]
                dx, dy = Field.movetypes[move]
                if player[0] == 'H' and px + dx == mx and py + dy == my:
                    return True
        return False
    
    result = []
    for move in field.get_choices(index):
        newfield = field.clone()
        newfield.apply_move(index, move)
        if not someone_might_catch_me(newfield, index):
            result.append(move)
    
    return result

def move_heuristics(field, index):
    '''Heuristically select a move for player identified by index.
    
    Heuristics used:
        1) Chasers move towards nearest (Manhattan distance) runner.
        2) If runner is next to a chaser, it moves out of reach of the chaser.
           Otherwise it moves to area with least catchers
    '''
    choices = field.get_choices(index)
    
    mx, my = field.players[index][1:3] # My position
    
    if field.players[index][0] == 'H':
        # I'm a chaser
        distances = [(x, y, abs(x - mx) + abs(y - my))
                     for t, x, y in field.players
                     if t == 'P']
        nx, ny = min(distances, key = lambda t: t[2])[0:2]
        
        if index % 2:
            # Do X first
            if nx < mx and 'x' in choices:
                return 'x'
            elif nx > mx and 'X' in choices:
                return 'X'
            elif ny < my and 'y' in choices:
                return 'y'
            elif ny > my and 'Y' in choices:
                return 'Y'
        else:
            # Do Y first
            if ny < my and 'y' in choices:
                return 'y'
            elif ny > my and 'Y' in choices:
                return 'Y'
            elif nx < mx and 'x' in choices:
                return 'x'
            elif nx > mx and 'X' in choices:
                return 'X'
        
        # Couldn't get anything reasonable
        return choices[random.randint(0, len(choices) - 1)]
    
    else:
        # I'm a runner
        def someone_might_catch_me_with(move):
            for player in field.players:
                px, py = player[1:3]
                dx, dy = Field.movetypes[move]
                if player[0] == 'H' and px + dx == mx and py + dy == my:
                    return True
            return False
        
        catchmoves = []
        for move in Field.movetypes:
            if someone_might_catch_me_with(move):
                return move # Move in the same direction as the catcher
        
        emptiest_area = min(choices,
                            key = lambda t: field.count_catchers(t))
        return emptiest_area
    
    # Catch-all fallback
    return choices[random.randint(0, len(choices) - 1)]

def advanced_logic(memory, field, index):
    '''Advanced move selection. This logic uses memory
    to determine opponent actions when chaser and runner are close to each
    other.'''
    
    mt, mx, my = field.players[index] # My type and position
    
    # Can we catch someone with next move?
    for player in field.players:
        if player[0] == mt:
            continue # Consider only opponents
        
        x, y = player[1:3]
        if abs(x - mx) + abs(y - my) <= 2:
            break # Yes, we can
    else:
        # No, we can't
        return move_heuristics(field, index)
    
    # Simulate the moves of the opponents
    newfield = field.clone()
    for i, player in enumerate(field.players):
        if player[0] == mt:
            continue
        
        move = memory.get_action(field.get_surroundings(i))
        
        if move not in Field.movetypes:
            # Not in memory
            move = move_heuristics(field, i)
        
        newfield.apply_move(i, move)
    
    # Choose our move
    if mt == 'P':
        # Do not even consider dangerous moves if there are safe ones
        choices = find_sure_escape(field, index)
        if choices:
            emptiest_area = min(choices,
                            key = lambda t: field.count_catchers(t))
            return emptiest_area
    
    for choice in field.get_choices(index):
        dx, dy = Field.movetypes[choice]
        
        caught = False
        for player in newfield.players:
            if player[0] == mt:
                continue
            
            x, y = player[1:3]
            if mx + dx == x and my + dy == y:
                caught = True
                break
            
        if mt == 'H' and caught:
            return choice # Yes, we caught someone!
        
        if mt == 'P' and not caught:
            print index, "P"
            return choice # Yes, we weren't caught!
    
    # Couldn't find a good move, fall back to heuristics
    return move_heuristics(field, index)

def test_for_overlap(field, index):
    for i, player in enumerate(field.players):
        if i == index:
            continue
        
        if player == field.players[index]: # Same type and position
            return True
    
    return False

def get_past_moves(oldplayers, newplayers, mytype):
    '''Deduce the moves between two lists of players, considering only
    players with the opponents type.'''
    
    moves = []
    for old, new in zip(oldplayers, newplayers):
        if old[0] != new[0] or old[0] == mytype:
            moves.append(None)
            continue
        
        x_change = new[1] - old[1]
        y_change = new[2] - old[2]
        
        for movetype, (dx, dy) in Field.movetypes.items():
            if x_change == dx and y_change == dy:
                 moves.append(movetype)
                 break
        else:
            raise Exception("No such move found: (%d, %d)" % (x_change, y_change))
    
    return moves

def read_players(file, count):
    '''Reads players from file. File is expected to be open and at correct
    position.'''
    players = []
    for i in range(count):
        line = file.readline()
        t, x, y = line.strip().split(' ')[:3]
        x = int(x)
        y = int(y)
        players.append([t, x, y])
    return players

def make_a_smart_thing():
    '''Reads input file, determines moves and writes output'''
    memory = Memory()
    infile = open('hippa.txt', 'rU')
    
    chaser = infile.readline().strip()
    runner = infile.readline().strip()
    
    if len(sys.argv) == 2:
        # For testing, allows specifying action on command line
        mytype = sys.argv[1].upper()
        assert mytype in ('H', 'P')
    else:
        if chaser.lower() == "hippazizzo":
            mytype = "H"
        elif runner.lower() == "hippazizzo":
            mytype = "P"
        else:
            raise Exception("None of the names is 'HippaZizzo'")
    
    maxX, maxY, count, rounds = map(int, infile.readline().strip().split(' '))
    
    # Add old moves to memory
    if rounds >= 1:
        # Seek to position
        for i in range((rounds - 1) * (count + 1)):
            infile.readline()
        
        assert int(infile.readline().strip()) == rounds - 1
        oldplayers = read_players(infile, count)
        oldfield = Field(oldplayers, maxX, maxY)
        assert int(infile.readline().strip()) == rounds
        newplayers = read_players(infile, count)
        
        moves = get_past_moves(oldplayers, newplayers, mytype)
        for i, move in enumerate(moves):
            if move != None:
                memory.add_situation(oldfield.get_surroundings(i), move)
    else:
        assert int(infile.readline().strip()) == rounds
        newplayers = read_players(infile, count)
    
    field = Field(newplayers, maxX, maxY)
    nextfield = field.clone()
    outfile = open("liike.txt", "w")
    for index, player in enumerate(newplayers):
        if player[0] != mytype:
            continue
        
        move = advanced_logic(memory, field, index)
        
        # If two of our players end up in same position, move one of them
        if mytype == 'H':
            tempfield = nextfield.clone()
            tempfield.apply_move(index, move)
            if test_for_overlap(tempfield, index):
                othermoves = [m for m in field.get_choices(index) if m != move]
                move = othermoves[random.randint(0, len(othermoves) - 1)]
            nextfield.apply_move(index, move)
        
        # Convert move representation
        if move == '-':
            wmove = '0'
        elif move.islower():
            wmove = '-' + move
        elif move.isupper():
            wmove = '+' + move.lower()
        else:
            raise Exception("Invalid move: %s", move)
        
        outfile.write("%d %s\n" % (index + 1, wmove))
    
    outfile.close()

if __name__ == '__main__':
    make_a_smart_thing()