BFS d'Halloween :-) (FC2020 reloaded)

import math
import random
import sys
import time
from copy import copy
from typing import Tuple, List, Optional
from collections import deque
from numpy import array, where


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


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


class Potion:
    def __init__(self, potion_id, delta, price):
        self.potion_id = potion_id
        self.delta = delta
        self.price = price

    def __repr__(self):
        return f'{self.potion_id} {str(self.delta)} {self.price}'


class Spell:
    def __init__(self, cast_id, delta, castable):
        self.cast_id = cast_id
        self.delta = delta
        self.castable = castable

    def __copy__(self):
        return Spell(self.cast_id, self.delta.copy(), self.castable)

    def __hash__(self):
        return hash((str(self.delta), self.castable))

    def __repr__(self):
        return f'{self.cast_id} {str(self.delta)} {self.castable}'


class Action:
    def __init__(self, action_type, action_id=None, delta=None):
        self.action_type = action_type
        self.action_id = action_id
        self.delta = delta

    def __hash__(self):
        # return hash((self.action_type, self.action_id, tuple(map(tuple, self.delta))))
        return hash((self.action_type, self.action_id))

    def __repr__(self):
        if self.action_type == 'CAST':
            return f'CAST {self.action_id}'
        elif self.action_type == 'BREW':
            return f'BREW {self.action_id}'
        else:
            return 'REST'


def bfs_paths(witch_id: int, potion: Potion):
    if witch_id == 0:
        inv: array = my_inv.copy()
        spells: List = [copy(s) for s in my_spells]
    else:
        inv: array = op_inv.copy()
        spells: List = [copy(s) for s in op_spells]
    depth = 0
    queue = deque([(spells, inv, depth, [])])
    nodes_count = 0
    new_start = time.time()
    visited_states = []
    while queue:
        spells, inv, depth, path = queue.popleft()
        actions = [Action('CAST', s.cast_id, s.delta) for s in spells if s.castable and all((s.delta + inv >= 0))]
        actions.append(Action('REST'))
        # la petite fourmi se deplace pour chercher son chemin
        for action in actions:
            new_spells: List = [copy(s) for s in spells]
            if action.action_type == 'CAST':
                # if inventory is not full after cast, add new recipe, and set castable flag to False
                new_inv: array = inv + action.delta
                if sum(new_inv) > 10:
                    continue
                for s in new_spells:
                    if action.action_id == s.cast_id:
                        s.castable = False
            else:   # action.action_type == REST
                new_inv = inv
                for s in new_spells:
                    s.castable = True
            if all((new_inv + potion.delta >= 0)):
                debug(f'BFS player {witch_id} - nodes_count = {nodes_count} - elapsed_time = {round((time.time() - new_start) * 1000, 2)} ms')
                brew_action = Action('BREW', potion.potion_id)
                yield path + [action, brew_action]
            else:
                gamestate = (new_spells, new_inv, depth + 1)
                # if gamestate not in visited_states:
                node = (*gamestate, path + [action])
                queue.append(node)
                visited_states.append(gamestate)
                # debug(f'node = {node}')
                # debug(f'game state = {gamestate}')
                nodes_count += 1
    debug(f'witch {witch_id} = no solution found!')


def shortest_path(witch_id: int, potion: Potion):
    try:
        return next(bfs_paths(witch_id, potion))
    except StopIteration:
        return None

# somme = lambda a, b: [[sum(x) for x in list(zip(a, b))]]

last_turn_brewed = False

# game loop
while True:
    action_count = int(input())  # the number of spells and recipes in play
    start = time.time()
    idebug(action_count)
    my_spells, op_spells = [], []
    my_inv, op_inv = [], []
    potions = []
    for i in range(action_count):
        line = input()
        idebug(line)
        inputs = line.split()
        action_id = int(inputs[0])  # the unique ID of this spell or recipe
        action_type = inputs[1]  # in the first league: BREW; later: CAST, OPPONENT_CAST, LEARN, BREW
        delta = array([int(inputs[2]), int(inputs[3]), int(inputs[4]), int(inputs[5])])
        price = int(inputs[6])  # the price in rupees if this is a potion
        tome_index = int(inputs[7])  # in the first two leagues: always 0; later: the index in the tome if this is a tome spell, equal to the read-ahead tax; For brews, this is the value of the current urgency bonus
        tax_count = int(inputs[8])  # in the first two leagues: always 0; later: the amount of taxed tier-0 ingredients you gain from learning this spell; For brews, this is how many times you can still gain an urgency bonus
        castable = inputs[9] != "0"  # in the first league: always 0; later: 1 if this is a castable player spell
        repeatable = inputs[10] != "0"  # for the first two leagues: always 0; later: 1 if this is a repeatable player spell
        if action_type == 'CAST':
            my_spells.append(Spell(action_id, delta, castable))
        elif action_type == 'OPPONENT_CAST':
            op_spells.append(Spell(action_id, delta, castable))
        elif action_type == 'BREW':
            potions.append(Potion(action_id, delta, price))
    for i in range(2):
        # inv_0: tier-0 ingredients in inventory
        # score: amount of rupees
        line = input()
        idebug(line)
        inv_0, inv_1, inv_2, inv_3, score = [int(j) for j in line.split()]
        if i == 0:
            my_inv, my_score = array([inv_0, inv_1, inv_2, inv_3]), score
        else:
            op_inv, op_score = array([inv_0, inv_1, inv_2, inv_3]), score

    # debug(f'my spells = {my_spells}')

    # in the first league: BREW <id> | WAIT; later: BREW <id> | CAST <id> [<times>] | LEARN <id> | REST | WAIT
    # potion_to_brew = random.choice(potions)
    potion_to_brew = min(potions, key=lambda p: p.price)
    debug(f'potion to brew: {potion_to_brew}')

    if all((my_inv + potion_to_brew.delta >= 0)):
        action = f'BREW {potion_to_brew.potion_id}'
        last_turn_brewed = True
    elif last_turn_brewed:
        action = 'REST'
        last_turn_brewed = False
    else:
        actions = shortest_path(witch_id=0, potion=potion_to_brew)
        action = actions[0]
        debug(f'path to potion {potion_to_brew} = {actions}')
    print(action)
    debug(f'elapsed time = {round((time.time() - start) * 1000)} ms')