Sokoban (starter)

import random
import sys
import math
from typing import Tuple, List

DIRECTIONS = {'R': (1, 0), 'U': (0, -1), 'L': (-1, 0), 'D': (0, 1)}


def idebug(*args):
    # return
    print(*args, file=sys.stderr, flush=True)


def debug(*args):
    # return
    print(*args, file=sys.stderr, flush=True)


class Cell(object):
    """ :param pos: Position (x, y) de la cellule sur la grille
        :param wall: est un mur ou pas
        :type pos: bool
        :type wall: bool
        :return: class Cell
        :rtype: object
    """
    pos: Tuple[int, int]
    wall: bool
    outside: bool
    drop_zone: bool
    neighbors: List[object]

    def __init__(self, x: int, y: int, c: str=None):
        self.x, self.y = x, y
        self.pos = (x, y)
        self.wall: bool = c == '#'
        self.outside: bool = True
        # self.box: Box = None
        self.drop_zone: bool = c == '*'
        self.neighbors: List[Cell] = []

    # def clone(self):
    #     cell = Cell(self.x, self.y)
    #     cell.pos = self.pos
    #     cell.wall = self.wall
    #     cell.outside = self.outside
    #     cell.drop_zone = self.drop_zone
    #     cell.neighbors = [c.clone() for c in self.neighbors]
    #     return cell

    def has_box(self, board):
        for box in board.boxes:
            if box.cell == self:
                return True

    def visit(self):
        if not self.outside or self.wall:
            return
        self.outside = False
        for cell in self.neighbors:
            if cell is not None:
                cell.visit()

    def __repr__(self):
        return f'{self.pos} {self.drop_zone}'


class Pusher:
    cell: Cell
    moves: List[str]

    def __init__(self, cell: Cell):
        self.cell = cell

    def clone(self):
        pusher = Pusher(self.cell)
        pusher.moves = self.moves[:]
        return pusher

    def __repr__(self):
        return f'{self.cell}'


class Box:
    cell: Cell

    def __init__(self, cell: Cell):
        self.cell = cell

    def clone(self):
        return Box(self.cell)

    def __repr__(self):
        return f'{self.cell}'


class Board:
    grid: List[Cell]
    pusher: Pusher
    boxes: List[Box]

    def __init__(self, grid: List[Cell]=None):
        self.grid: List[Cell] = grid
        self.pusher: Pusher
        self.boxes: List[Box] = []
        if grid:
            for cell in self.grid:
                for _dir in DIRECTIONS.values():
                    new_pos = move(cell.pos, _dir)
                    new_cell: Cell = self.get_cell(new_pos)
                    if new_cell and not new_cell.wall:
                        cell.neighbors.append(new_cell)
        # self.walls = [c for c in self.grid if c.wall]

    def clone(self):
        board: Board = Board()
        board.grid = self.grid
        board.pusher = self.pusher.clone()
        board.boxes = [b.clone() for b in self.boxes]
        return board

    def score(self):
        return len([b for b in self.boxes if b.cell.drop_zone])

    def get_cell(self, pos: Tuple[int, int]):
        tab = [c for c in self.grid if not c.wall and c.pos == pos]
        return tab[0] if tab else None

    def get_box(self, pos: Tuple[int, int]):
        tab = [b for b in self.boxes if b.cell.pos == pos]
        return tab[0] if tab else None

    def is_box_pushable(self, cell: Cell):
        exit_directions: List[str] = []
        for d, _dir in DIRECTIONS.items():
            new_pos = move(cell.pos, _dir)
            new_cell = self.get_cell(new_pos)
            if new_cell and not new_cell.wall:
                exit_directions.append(d)
        if len(exit_directions) < 2:
            return False
        elif len(exit_directions) == 2:
            if ''.join(set(exit_directions)) in ['LR', 'DU']:
                return True
            else:
                return False
        else:
            return True

    def move_pusher(self, direction: str):
        pos = move(self.pusher.cell.pos, DIRECTIONS[direction])
        dest_cell = self.get_cell(pos)
        self.pusher.cell = dest_cell
        if dest_cell.has_box(self):
            box = self.get_box(pos)
            new_box_pos = move(dest_cell.pos, DIRECTIONS[direction])
            box.cell = self.get_cell(new_box_pos)

    def update(self, boxes_pos: List[Tuple], pusher_pos: Tuple[int, int]):
        self.pusher: Pusher = Pusher(self.get_cell(pusher_pos))
        self.boxes: List[Box] = [Box(self.get_cell(pos)) for pos in boxes_pos]
        self.pusher.moves: List[Tuple] = []
        for d, _dir in DIRECTIONS.items():
            pos = move(pusher_pos, _dir)
            cell = self.get_cell(pos)
            if cell and not cell.wall:
                if cell.has_box(self):
                    new_pos = move(cell.pos, _dir)
                    new_cell = self.get_cell(new_pos)
                    if new_cell and not new_cell.wall and not new_cell.has_box(self) and self.is_box_pushable(new_cell):
                        self.pusher.moves.append(d)
                else:
                    self.pusher.moves.append(d)

    def __repr__(self):
        return f'{self.grid} {self.pusher} {self.boxes}'


# class GameState:
#     def __init__(self, boxes: List[Box], pusher: Tuple[int, int]):
#         self.boxes: List[Box] = boxes
#         self.pusher: Tuple[int, int] = pusher


walls = []
floor = []

line = input()
idebug(line)
WIDTH, HEIGHT, BOX_COUNT = [int(i) for i in line.split()]
grid = []

grid: List[Cell] = []
for i in range(HEIGHT):
    row = input()  # one line of the grid: space " " is floor, pound "#" is wall
    idebug(row)
    for j, c in enumerate(row):
        grid.append(Cell(j, i, c))
debug(f'grid: {grid}')

move = lambda a, b: (a[0] + b[0], a[1] + b[1])

"""TODO: define a graph of actions/Gamestates for simulation (BFS, ...)?"""
# graph = {}
# for pos in floor:
#     graph[pos] = []
#     for move_dir in DIRS.values():
#         new_pos = move(pos, move_dir)
#         if new_pos not in walls:
#             graph[pos].append(new_pos)

board: Board = Board(grid)
# game loop
while True:
    line = input()
    idebug(line)
    pusher_x, pusher_y = [int(i) for i in line.split()]
    boxes_pos = []
    for i in range(BOX_COUNT):
        line = input()
        idebug(line)
        box_x, box_y = [int(j) for j in line.split()]
        boxes_pos.append((box_x, box_y))
    board.update(boxes_pos=boxes_pos, pusher_pos=(pusher_x, pusher_y))

    # Write an action using print
    # To debug: print("Debug messages...", file=sys.stderr, flush=True)
    actions = board.pusher.moves
    debug(actions)
    scores = []
    for move_dir in board.pusher.moves:
        new_board: Board = board.clone()
        new_board.move_pusher(move_dir)
        scores.append((move_dir, new_board.score()))
    best_score = max([score for move_dir, score in scores])
    best_move = random.choice([move_dir for move_dir, score in scores if score == best_score])
    # action = random.choice(actions)
    print(best_move)