SIMULATION_TIME = 300


class Customer:
    TIME_ON_CASE = 2    # Max value of delay on case
    TIME_ON_START = 4    # Max value of delay on case

    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()
        self.start_delay = -1
        self.cash_wait = -1
        self.customer_symbols = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']


    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.start_delay == 0:
            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)
        elif self.start_delay > 0:
            self.start_delay -=1
            print (self.start_delay)
        else:
            import random
            self.start_delay = random.randint(1, self.TIME_ON_START)-1
            print ('user %d have to wait %d steps' %(self.id, self.start_delay+1))

    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':
            if self.cash_wait > 0:
                print('left to wait for Customer #%d steps...%d' % (self.id, self.cash_wait))
                self.cash_wait -=1
            elif self.cash_wait == 0:
                self.purchasing = 'purchased'
                # print('PURCHASED' + str(self.id))
            else:
                import random
                self.cash_wait = random.randint(1, self.TIME_ON_CASE)
                # if self.cash_wait

        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 < len(self.customer_symbols):
            return self.customer_symbols[self.id-1]
        else:

            return self.customer_symbols[(self.id % len(self.customer_symbols))]
            # return self.customer_symbols[self.id % len(self.customer_symbols)]
        # 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')

customer_limit =100
current_time = 0
customer_count = 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_count += 1
    if customer_count <= customer_limit:
        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