SIMULATION_TIME = 400


class Customer:
    def __init__(self, id, position, supermarket):
        self.id = id
        self.position = position
        self.supermarket = supermarket
        self.purchasing = None

        self.path = []
        for i in self.supermarket.key_points.keys():
            if self.id % i == 0:
                self.path += self.supermarket.key_points[i]
        self.update_path()

    def update_path(self):
        self.path = sorted(
            self.path,
            key=lambda t: ((t[0]-self.position[0])**2 + (t[1]-self.position[1])**2)**0.5,
            )
        # print(self.path)

    def free_to_walk(self, target):
        d_x = target[0] - self.position[0]
        d_y = target[1] - self.position[1]

        x_direction = 0 if d_x == 0 else 1 if d_x > 0 else -1
        y_direction = 0 if d_y == 0 else 1 if d_y > 0 else -1
        new_position = (
            self.position[0] + x_direction,
            self.position[1] + y_direction)
        if self.supermarket.is_cell_free(new_position):
            return new_position
        else:
            possible_new_positions = [
                (self.position[0]-1, self.position[1]),
                (self.position[0]-1, self.position[1]-1),
                (self.position[0], self.position[1]-1),
                (self.position[0]+1, self.position[1]-1),
                (self.position[0]+1, self.position[1]),
                (self.position[0]+1, self.position[1]+1),
                (self.position[0], self.position[1]+1),
                (self.position[0]-1, self.position[1]+1),
            ]
            possible_new_positions = [
                x for x in possible_new_positions
                if self.supermarket.is_cell_free(x)]
            if possible_new_positions:
                new_positions = sorted(
                    possible_new_positions,
                    key=lambda t: ((t[0]-target[0])**2 + (t[1]-target[1])**2)**0.5,
                )
                return new_positions[0]
                # print('::', self.id, new_positions)

    def walk(self):
        if self.position in self.path:
            if self.purchasing == 'go_to_cash':
                self.purchasing = 'cash'
            self.path.remove(self.position)
            self.update_path()

        # print(self.id, self.purchasing, self.path)

        if self.path:
            target = self.path[0]
            new_position = self.free_to_walk(target)
            if new_position:
                self.position = new_position
                # print('customer #%d is trying to go to (%d, %d)' % (
                #     self.id,
                #     self.position[0],
                #     self.position[1],
                #     ))
        elif self.purchasing == 'finished':
            print('customer #%d went out' % self.id)
            self.supermarket.customers.remove(self)
            self.supermarket.customers_out += 1
        elif self.purchasing == 'cash':
            self.purchasing = 'purchased'
        elif self.purchasing == 'purchased':
            new_positions = sorted(
                    self.supermarket.finish_slots,
                    key=lambda t: ((t[0]-self.position[0])**2 + (t[1]-self.position[1])**2)**0.5,
                )
            if new_positions:
                self.position = new_positions[0]
                self.purchasing = 'finished'
                print('customer #%d is going out' % self.id)
        elif self.purchasing != 'go_to_cash':
            import random
            self.path = [random.choice(self.supermarket.cash_registers)]
            new_position = self.free_to_walk(self.path[0])
            if new_position:
                self.position = new_position
                self.purchasing = 'go_to_cash'

    def view(self):
        if self.id % 2 == 0:
            return '@'
        elif self.id % 3 == 0:
            return '&'
        return '*'


class Supermarket:
    WALL = '#'
    CASH = 'C'
    START = 'S'
    FINISH = 'F'

    def __init__(self, file_name):
        from collections import defaultdict

        with open(file_name) as f:
            self.data = [list(x.strip()) for x in f]

        self.height = len(self.data)
        self.width = len(self.data[0])

        self.walls = []
        self.cash_registers = []
        self.start_slots = []
        self.finish_slots = []
        self.key_points = defaultdict(list)

        for y, row in enumerate(self.data):
            for x, ch in enumerate(row):
                if ch == self.WALL:
                    self.walls.append((x, y))
                elif ch == self.CASH:
                    self.cash_registers.append((x, y))
                elif ch == self.START:
                    self.start_slots.append((x, y))
                elif ch == self.FINISH:
                    self.finish_slots.append((x, y))
                elif ch.isdigit():
                    self.key_points[int(ch)].append((x, y))

        self.customers = []
        self.next_customer_id = 1
        self.customers_in = 0
        self.customers_out = 0

    def get_customer_for_cell(self, position):
        for x in self.customers:
            if position == x.position:
                return x

    def is_cell_free(self, position, allow_finish=False):
        if (0 <= position[0] <= self.width - 1) and \
                (0 <= position[1] <= self.height - 1):
            if position not in self.walls and \
                    position not in [x.position for x in self.customers]:
                if position in self.finish_slots and not allow_finish:
                    return False
                return True
        return False

    def add_customer(self):
        entries = [x for x in self.start_slots if self.is_cell_free(x)]
        if entries:
            customer = Customer(
                self.next_customer_id,
                entries[0],
                self)
            self.customers.append(customer)
            self.next_customer_id += 1
            self.customers_in += 1
            return customer

    def move_customers(self):
        for x in self.customers:
            x.walk()

    def draw(self):
        for y, row in enumerate(self.data):
            for x, c in enumerate(row):
                t = self.get_customer_for_cell((x, y))
                print(t.view() if t else c, end='')
            print()

supermarket = Supermarket('input.txt')

current_time = 0
while current_time < SIMULATION_TIME:
    print('Time: %d Customers inside: %d Customers in: %d Customers out: %d' % (
        current_time, len(supermarket.customers),
        supermarket.customers_in,
        supermarket.customers_out))
    supermarket.move_customers()

    customer = supermarket.add_customer()
    if customer:
        print('New customer #%d just came in at (%d, %d)' % (
            customer.id,
            customer.position[0],
            customer.position[1]))
    else:
        print('New customer cannot come into the supermarket.')

    supermarket.draw()
    current_time += 1