PMTOK Solver

'''
Puzzle solver for Paper Mario: The Origami King
'''

from queue import PriorityQueue

'''
Define possible movements
'''
def rotate(board, row, amount):
    # amount is capped at 12!
    #if amount >= 12 or row >= 4:
    #    raise Exception(f'Invalid move: R({row},{amount})')

    # make a new board, we want to keep the old one (and discard manually later)
    new_board = [[x for x in brow] for brow in board]
    new_board[row] = new_board[row][amount:] + new_board[row][:amount]
    return new_board

# it's ugly but works..
def slide(board, column, amount):
    # 0 <= column < 6
    # 0 <= amount < 8

    # make a new board, we want to keep the old one (and discard manually later)
    new_board = [[x for x in brow] for brow in board]
    # get column
    ncolumn = [row[column] for row in new_board] + list(reversed([row[(column + 6) % 12] for row in new_board]))
    # move the column
    ncolumn = ncolumn[amount:] + ncolumn[:amount]
    for i, item in enumerate(ncolumn[:4] + list(reversed(ncolumn[4:]))):
        if i < 4:
            new_board[i][column] = item
        else:
            new_board[i-4][(column + 6) % 12] = item
    return new_board

'''
define a heuristic for the priority queue.
'''
def unbound_enemies(board):
    # copy the board
    nboard = [[x for x in row] for row in board]

    # slide over all columns to see if the column is JUMP solved
    for column in range(12):
        # if they're all enemies, set them to 0, we don't care about them anymore
        if sum([nboard[row][column] for row in range(4)]) == 4:
            # set all to 0
            for row in range(4):
                nboard[row][column] = 0

    # slide over the nearest two rows to see if they're HAMMER solved
    for column in range(12):
        if nboard[0][column] + nboard[1][column] + nboard[0][(column+1)%12] + nboard[1][(column+1)%12] == 4:
            nboard[0][column] = 0
            nboard[1][column] = 0
            nboard[0][(column+1)%12] = 0
            nboard[1][(column+1)%12] = 0

    return sum([enemy for row in nboard for enemy in row])

def lonely_enemies(board):
    total_loneliness = 0
    for row in range(4):
        for column in range(12):
            if board[row][column] == 0:
                continue

            if row > 0:
                total_loneliness += board[row-1][column]
            if row < 3:
                total_loneliness += board[row+1][column]

            total_loneliness += board[row][(column+1)%12]
            total_loneliness += board[row][(column-1)%12]

    return -total_loneliness

def heuristic(board):
    return unbound_enemies(board) + lonely_enemies(board)

def solve(board, moves=3, progress=True):
    pq = PriorityQueue()
    pq.put((-1, 0, [], board))

    tested_fields = 0

    while not pq.empty():
        heu, used_moves, path, cboard = pq.get()
        tested_fields += 1

        # comment this out if needed, just shows some progress
        if progress and not tested_fields % 25000:
            print(f'Tested {tested_fields} fields...')
        # check if the board is the solution
        # todo!
        if unbound_enemies(cboard) == 0:
            yield (used_moves, path, tested_fields, cboard)

        if used_moves >= moves:
            continue
        # otherwise add all possible moves
        # rotating
        for row in range(4):
            for amount in range(1,12):
                nboard = rotate(cboard, row, amount)
                # evaluate and put..
                npath = path + [('rotate', row, amount)]
                pq.put((heuristic(nboard), used_moves+1, npath, nboard))

        # sliding
        for column in range(6):
            for amount in range(1,8):

                nboard = slide(cboard, column, amount)
                # evaluate and put..
                npath = path + [('slide', row, amount)]
                pq.put((heuristic(nboard), used_moves+1, npath, nboard))

'''
Represents the following battle:
https://cdn.discordapp.com/attachments/619995837828694016/734457814939992114/unknown.png

You only need to modify these 3 fields!
'''
battle_field = [
    [0,1,1,0,0,0,0,1,1,0,0,0],
    [1,0,1,0,0,0,1,0,1,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0],
    [0,0,0,0,0,0,0,0,0,0,0,0]
]

moves = 3

for (moves, path, tested, board) in solve(battle_field, moves=moves, progress=False):
    print(*path)