from dataclasses import dataclass from copy import deepcopy from typing import Callable from collections import deque from itertools import permutations #import math @dataclass class Location: #coordenadas xpos:int ypos:int @dataclass class Ground: #mapa name:str #nome do mapa width:int height:int #dimensões do mapa space:list[list[int]]#matriz com o relevo (cada quadradinho é uma entrada) com_wings:list[Location]#lista de localizações em que há alas comuns wormholes:list[tuple[Location]] #lista para guardar os 'wormholes'; estará associado a duas localizações (tuplo). @dataclass class Object: name:str where:Location#posição no ground @dataclass class Agent: name:str where:Location#posição objects:list[Object]#objetos que tem consigo altitude:int#altitude inicial do agente - será constante e serve para saber o número de degraus que pode subir Thing = Agent | Object State = dict[str,Thing]#guarda as coisas do mundo - chave string (nome das coisas), e objetos/agentes @dataclass class World: ground: Ground #constante (alterado apenas no setaltitude) state: State#atualiza em cada 'ação' do agente Path = tuple[str,...] #definir o tipo de variável que será o path class PlayGroundError(Exception):#definir exceção geral do playground pass class NoCookieProblemError(Exception):#definir exceção para cookie monster problems pass class NoGatheringProblemError(Exception):#definir exceção para wizard gatherings pass """"" def cleanUp(agent: Agent)-> Agent: for obj1 in range(len(agent.objects)): for obj2 in range(obj1+1,len(agent.objects)): if agent.objects[obj1] == agent.objects[obj2]: agent.objects.remove(agent.objects[obj1]) return agent """ def validez_do_nome(name:str)->bool: #função auxiliar para validar os nomes invalido=False if name == '': invalido = True else: for caracter in name: if not (caracter.isalnum() or caracter=='_'): invalido=True #verifica se é alfa(beto)/numérico, ou underscores return bool(invalido) def newObject(name:str)->Object: loc = Location(xpos=0,ypos=0)#começar na origem nome_objeto = name if validez_do_nome(name) == True:#validar nome raise PlayGroundError("Nome inválido para o objeto!!") return Object(name = nome_objeto, where=loc) def newAgent(name:str)->Agent: if validez_do_nome(name) == True: raise PlayGroundError("Nome inválido para o agente!!") return Agent(name,Location(0,0),[],0)#começar sem objetos, altitude default(é irrelevante) def newWorld(name:str,width:int,height:int)->World: if validez_do_nome(name) == True:#validar nome raise PlayGroundError("Nome inválido para o mundo!!") if (width <= 0) or (height<=0) : raise PlayGroundError("Dimensões inválidas para o mundo!!") #definição da matriz de altitude matriz = [] for i in range(width): listas = [] for j in range(height): listas.append(0) matriz.append(listas) return World(ground=Ground(name,width,height,matriz,[],[]),state={}) #cria o mundo, sem nada e com o chão com altitude zero e dimensões width e height; sem alas comuns nem wormholes def setAltitude(w:World,loc:Location,width:int,height:int,alt:int)->None: if (width<=0 or height<=0): raise PlayGroundError('O retângulo deve ter dimensões positivas!') if (loc.xpos<0 or loc.ypos<0 or loc.xpos>=w.ground.width or loc.ypos>=w.ground.height): raise PlayGroundError('localização fora do mapa') if (loc.xpos + width > w.ground.width or loc.ypos + height > w.ground.height): raise PlayGroundError('Retângulo inválido!-fora do mundo') for coluna in range(loc.xpos, loc.xpos + width): for linha in range(loc.ypos, loc.ypos + height): w.ground.space[coluna][linha] = alt #altera todos os valores dentro do "retângulo" dado (em loc com width e height) para a altitude dada. #Para o python altera as entradas da matriz que correspondem a este retângulo. return None def putThing(w:World, thing:Thing, loc:Location) -> Thing: if thing.name in w.state: raise PlayGroundError('Thing already exists') if (loc.xpos < 0 or loc.ypos < 0 or loc.xpos >= w.ground.width or loc.ypos >= w.ground.height): raise PlayGroundError('Invalid location') for existing_thing in w.state.values(): if (existing_thing.where.xpos==loc.xpos and existing_thing.where.ypos==loc.ypos): raise PlayGroundError('Localização ocupada!!!!!') if isinstance(thing, Agent): thing.altitude = w.ground.space[loc.xpos][loc.ypos]#define a altitude do agente - apenas para agentes! thing.where = loc #define a localizaçao da thing w.state[thing.name] = thing #adiciona a thing ao dicionário com key respetiva ao seu nome return thing def moveAgent(w:World,ag:Agent,dir:str)-> World|None: directiony = 0#definição das variáveis de direção - para ajudar na compreensão (e na escrita do código) directionx = 0 if dir == 'L': directionx = -1 elif dir == 'R': directionx = 1 elif dir == 'U': directiony = 1 elif dir == 'D': directiony = -1 else: raise PlayGroundError('invalid direction!!') newlocx = ag.where.xpos + directionx newlocy = ag.where.ypos + directiony #definir a localização para onde o agente vai (com a respetiva direção) for wormhole in w.ground.wormholes: #percorre todos os tuplos correspondentes aos wormholes if wormhole[0] == Location(newlocx,newlocy): newlocx = wormhole[1].xpos + directionx newlocy = wormhole[1].ypos + directiony elif wormhole[1] == Location(newlocx,newlocy): newlocx = wormhole[0].xpos + directionx newlocy = wormhole[0].ypos + directiony #localização para onde o agente irá, se for para um wormhole if newlocx < 0 or newlocx >= w.ground.width or newlocy < 0 or newlocy >= w.ground.height: return None elif abs(w.ground.space[newlocx][newlocy] \ - ag.altitude)> len(ag.objects):#altitude na posição a ir comparada com altitude inicial! return None #erros de subir demasiados graus de altitude for thing in w.state.values(): if (thing.where.xpos == newlocx) and (thing.where.ypos == newlocy): if isinstance(thing, Object): return None #se a localização estiver ocupada por um objeto else:#se for agente if not (Location(newlocx,newlocy) in w.ground.com_wings): return None #se a localização de destino tiver um agente e não for uma ala comum new_state:State = deepcopy(w.state) #cópia: com deepcopy para não se alterar o mundo original new_agent:Agent = Agent(ag.name , Location(newlocx,newlocy) , ag.objects , ag.altitude) new_state[ag.name] = new_agent #alterar o agente antigo para ser o novo, no dicionário (com a localização atualizada) return World(w.ground,new_state) def pickObject(w:World,ag:Agent,ob:Object)->World|None: if w.ground.space[ag.where.xpos][ag.where.ypos] == w.ground.space[ob.where.xpos][ob.where.ypos]: if not ((abs(ob.where.xpos - ag.where.xpos) == 1 and ob.where.ypos == ag.where.ypos) \ or (abs(ob.where.ypos - ag.where.ypos) == 1 and ob.where.xpos == ag.where.xpos)): return None #verificar se está a um quadrado de distância else: new_state = deepcopy(w.state) #deepcopy para não alterar o mundo original new_agent = Agent(ag.name,ag.where,ag.objects,ag.altitude) #criar novo agente para não alterar o original new_agent.objects.append(ob) #adicionar objeto à lista de objetos do agente del new_state[ob.name] #apagar objeto apanhado do dicionário new_state[ag.name] = new_agent #atualizar o value do agente para o novo(que já tem o objeto) #if ob in new_state.values(): # del new_state[ob.name] return World(w.ground, new_state) else: return None #se não estiverem na mesma altitude não pode apanhar def pathToWorlds(w:World,path:Path) -> list[World]: worlds = [World(w.ground,deepcopy(w.state))] #se o path for vazio, a função devolverá o mundo inicial(deepcopy para não alterar o estado inicial) for action in path: #procura todas as ações separadas no caminho action_parts = action.split(' ') # Separa a ação em palavras (onde há espaços na string) if action_parts[0] in ['U', 'D', 'L', 'R']: #verificar se ação é movimento dir = action_parts[0] agent_name = action_parts[1] ag = w.state.get(agent_name) #definir as variáveis(para facilitar compreensão) e obter o agente if not ag: #verificar se agente existe no dicionário raise PlayGroundError('Agente não encontrado no mundo!') new_world = moveAgent(w, ag, dir)#devolverá, se possível, o novo mundo com a ação realizada if new_world == None:#verificar se movimento é possível raise PlayGroundError('Movimento impossível para o agente!!!') worlds.append(new_world) #adiciona o mundo que resulta da ação à lista w = World(new_world.ground, deepcopy(new_world.state)) #define a variável w como o mundo alterado para continuar o loop elif action_parts[0] == 'P': #verificar se a ação será um pick para pick object agent_name = action_parts[1] object_name = action_parts[2] ag = w.state.get(agent_name) ob = w.state.get(object_name)#variáveis para facilitar compreensão if not ag:#verificar se agente existe no dicionário raise PlayGroundError('Agente não encontrado no mundo!') if not ob:#verificar se objeto existe no dicionário raise PlayGroundError('Objeto não encontrado no mundo!') new_world = pickObject(w, ag, ob)#devolverá, se possível, o novo mundo com a ação realizada if new_world == None:#verifica se é possível apanhar o objeto raise PlayGroundError('Impossível apanhar o objeto') worlds.append(new_world)#adiciona o mundo que resulta da ação à lista w = World(new_world.ground, deepcopy(new_world.state))#define a variável w como o mundo alterado para continuar o loop else:#ação diferente das possíveis raise PlayGroundError('Ação inválida') return worlds def nextWorlds(w: World) -> list[tuple[str, World]]: possible_worlds = []#inicializar a lista de tuplos for agent in w.state.values(): #percorre todos os valores no dicionário if isinstance(agent, Agent): #verifica se é agente ag = deepcopy(agent) for dir in ['U', 'D', 'L', 'R']: #possíveis movimentos do agente action = f'{dir} {ag.name}'#representa um dos movimentos new_world1 = moveAgent(w, ag, dir)#representa o mundo que corresponde à ação if new_world1 != None: possible_worlds.append((action, new_world1))#adiciona à lista final(de tuplos) o mundo e a ação else: continue for ob in w.state.values(): #percorre novamente os valores ag = deepcopy(agent) if isinstance(ob, Object): #para cada agente, vamos procurar pelos objetos (para apanhar) new_world = pickObject(w, ag, ob)#representa o mundo que corresponde à ação if new_world != None: possible_worlds.append((f'P {ag.name} {ob.name}', new_world)) #else: # continue #se possível, adiciona o tuplo da ação com o mundo depois da ação #else: #continue return possible_worlds def findGoal(w: World, goal: Callable[[State], bool]) -> Path: #callable, bool #para especificar que o parâmetro goal (um state do mundo) é avaliado como verdadeiro ou falso. queue = deque([(w, ())]) #com deque exploramos todas as possibilidades e apagamos o tuplo (mundo,path) explorado state_signature: tuple = () for thing in w.state.values(): state_signature += ((thing.name, thing.where.xpos, thing.where.ypos)) visited_states = set() #conjunto que guardará os estados já visitados #para evitar voltar aos mesmos(porque revisitar estados é redundante e ineficaz) #usamos conjunto para adicionarmos depois os states como hashables while queue: current_world, path = queue.popleft() #começa o loop com o elemento da fila à esquerda #for agent in current_world.state.values(): #if isinstance(agent, Agent): # current_world.state[agent.name] = cleanUp(agent) if goal(current_world.state): #goal é um callable booleano, #ou seja, aqui verificamos se o estado atual satisfaz as condições do estado 'goal' #print(current_world.state['monster']) return path #retorna se o goal já estiver realizado. Por causa do BFS, já garantimos que este será o mais curto state_signature: tuple = () for thing in current_world.state.values(): state_signature += ((thing.name, thing.where.xpos, thing.where.ypos)) #estado em forma de hashable com os valores relevantes(a evitar repetir) if state_signature in visited_states: continue#o continue salta o ciclo para a próxima iteração na fila (se o estado for repetido) visited_states.add(state_signature)#adiciona-se o estado que é agora percorrido à lista de estados visitados #print(visited_states) for action, world in nextWorlds(current_world): next_signature: tuple = () for thing in world.state.values(): next_signature += ((thing.name, thing.where.xpos, thing.where.ypos)) #next_world = World(world.ground, deepcopy(world.state)) #print(action,next_world.state) if next_signature not in visited_states: queue.append((world, path + (action,)))#adiciona todas as possibilidades a partir #do estado testado à fila. path são tuplos, logo adicionamos com '+' e ',' raise PlayGroundError('Impossível de completar o objetivo') #o ciclo while queue só é finalizado se o goal for concluído (é dado return do path) ou se já não houver fila para #testar, indicando que todas as possibilidades futuras foram testadas, logo o erro é levantado e o goal não é alcançável """"" def findGoal(w:World, goal:Callable[[State],bool])->Path: tovisit:Queue[tuple[Path,State,str]] = Queue() visiteds: set[str] = set([]) tovisits: set[str] = set([]) setStartAltitude(w) tovisit.put(((),w.state,key(w.state))) while not tovisit.empty(): (path,stateToVisit,nk) = tovisit.get() tovisits.discard(nk) if goal(stateToVisit): return path visiteds.add(nk) for (act,newWorld) in nextWorlds(World(w.ground,stateToVisit)): nwk = key(newWorld.state) if nwk not in visiteds and nwk not in tovisits: tovisits.add(nwk) tovisit.put((path+(act,),newWorld.state,nwk)) raise PlayGroundError """ def setComWing(w:World,loc:Location,width:int,height:int)->None: if (width<=0 or height<=0): raise PlayGroundError('O retângulo deve ter dimensões positivas!') if (loc.xpos<0 or loc.ypos<0 or loc.xpos>=w.ground.width or loc.ypos>=w.ground.height): raise PlayGroundError('localização fora do mapa') if (loc.xpos + width > w.ground.width or loc.ypos + height > w.ground.height): raise PlayGroundError('Retângulo inválido!-fora do mundo') for coluna in range(loc.xpos, loc.xpos + width): for linha in range(loc.ypos, loc.ypos + height): if Location(coluna,linha) in w.ground.com_wings: continue#evitar adicionar a mesma localização duas vezes else: w.ground.com_wings.append(Location(coluna,linha)) #adicionar o retângulo dado à lista de localizações que corresponderá aos quadrados com alas comuns return None def setWormhole(w:World,loc1:Location,loc2:Location)->None: if (loc1.xpos<0 or loc1.ypos<0 or loc1.xpos>=w.ground.width or loc1.ypos>=w.ground.height): raise PlayGroundError('localização dada fora do mapa') if (loc2.xpos<0 or loc2.ypos<0 or loc2.xpos>=w.ground.width or loc2.ypos>=w.ground.height): raise PlayGroundError('localização dada fora do mapa') for existing_thing in w.state.values(): if ((existing_thing.where.xpos==loc1.xpos and existing_thing.where.ypos==loc1.ypos)\ or (existing_thing.where.xpos==loc2.xpos and existing_thing.where.ypos==loc2.ypos)): raise PlayGroundError('Localização ocupada!!!!!') distance: int = abs(loc1.ypos - loc2.ypos) + abs(loc1.xpos - loc2.xpos) if distance <= 3: raise PlayGroundError('As localizações das bocas são inválidas') w.ground.wormholes.append((loc1,loc2))#adiciona o tuplo das localizações #na lista de wormholes com as localizações sendo as bocas do wormhole return None def findCookies(w:World)->Path: if w.ground.width * w.ground.height > 400: raise NoCookieProblemError('O mundo excede o limite de células para este problema') if w.ground.com_wings != []: raise NoCookieProblemError('Não devem existir alas comuns para problemas CookieMonster') count_agent: int = 0 count_cookie: int = 0 #variáveis para facilitar na verificação dos parâmetros for thing in w.state.values(): if isinstance(thing, Agent): count_agent += 1 else: count_cookie +=1 if ((count_cookie == 0) or (count_cookie > 10) or (count_agent != 1)): raise NoCookieProblemError('Os agentes e objetos do mundo não estão nos parâmetros definidos') for thing in w.state.values(): #percorrer os valores definindo o cookiemonster e a lista de bolachas if isinstance(thing,Agent): cookie_monster : Agent = thing if cookie_monster.objects!=[]: raise NoCookieProblemError('O monstro deve começar sem objetos') original_cookies = list(cookie for cookie in w.state.values() if isinstance(cookie, Object)) og_world = w #print(og_world) list_paths = [] #permutation_number = 0 permuts:list[list[Object]] = cookie_permutation(original_cookies) #visited = list() #print(permuts) length_paths: list[int] = [] while permuts != []: cookies: list[Object] = permuts.pop() world = World(og_world.ground,deepcopy(og_world.state)) if isinstance(possible_solution(og_world,cookies,cookie_monster),int): permuts = cleanup(permuts,possible_solution(og_world,cookies,cookie_monster)[0],\ possible_solution(og_world,cookies,cookie_monster)[1]) #permutation_number+=1 continue #if cookies in visited: # permutation_number+=1 # continue #visited.append(cookies) #print(og_world) #print(world) #for cook_i in cookies: # if not (cook_i in possible_cookies(deepcopy(og_world))): # cookies.remove(cook_i) path = () #world = og_world for cookie in cookies: def goal_cookie(s: State) -> bool: return cookie in s[cookie_monster.name].objects #print(cookie) #print(w) #print(World(w.ground,{cookie_monster.name: cookie_monster, cookie.name: cookie})) #print(w.state[cookie_monster.name].objects) #print(findGoal(World(w.ground,{cookie_monster.name: cookie_monster, cookie.name: cookie}),goal_cookie)) #print(w.state[cookie.name]) try: #if findGoal(World(w.ground,{cookie_monster.name: w.state[cookie_monster.name], cookie.name: cookie}),goal_cookie): path += findGoal(World(w.ground,{cookie_monster.name: world.state[cookie_monster.name],\ cookie.name: cookie}),goal_cookie) if length_paths!=[]: if min(length_paths) tuple: cookie_distances:list[int]=[] monster_distances=[] for cookie1 in range(len(cookies)): for cookie2 in range(cookie1+1,len(cookies)): cookie_distances.append(abs(cookies[cookie1].where.xpos - cookies[cookie2].where.xpos) \ + abs(cookies[cookie1].where.ypos - cookies[cookie2].where.ypos)) for agent in w.state.values(): if isinstance(agent, Agent): for cookie in cookies: monster_distances.append(abs(cookie.where.xpos - agent.where.xpos) \ + abs(cookie.where.ypos - agent.where.ypos)) return tuple(cookie_distances,monster_distances) def possible_cookies(w: World)->list[Object]: possible_cookie=[] for agent in w.state.values(): if isinstance(agent, Agent): cookie_monster = agent for cookie in w.state.values(): if isinstance(cookie,Object): if abs(cookie_monster.altitude - w.ground.space[cookie.where.xpos][cookie.where.ypos])\ <= len(cookie_monster.objects): possible_cookie.append(cookie) return possible_cookie """ def cleanup(permutacoes:list[list[Object]],i:int,cookie:Object)->list[list[Object]]: return [perm for perm in permutacoes if perm[i] != cookie] def possible_solution(w:World,cookies:list[Object],monster: Agent) -> tuple[int]|None: for i in range(len(cookies)): if abs(w.ground.space[cookies[i].where.xpos][cookies[i].where.ypos]-monster.altitude) > i: return (i,cookies[i]) return None def cookie_permutation(og_cookies:list)->list[list]: permuts = [] for p in permutations(og_cookies): permuts.append(p) return permuts #return findcookieGoal(w,goal_cookies) #relembrar que a função findgoal devolve o 'path' mais curto que torna o goal verdadeiro def gatherWizards(w:World):#->Path: if w.ground.width * w.ground.height > 400: raise NoGatheringProblemError('O mundo excede o limite de células para este problema') count_agents: int = 0 count_objects: int = 0 #variáveis para facilitar na verificação dos parâmetros for thing in w.state.values(): if isinstance(thing, Agent): count_agents += 1 else: count_objects +=1 if ((count_objects != 0) or (count_agents > 10) or (count_agents == 0)): raise NoGatheringProblemError('Os agentes e objetos do mundo não estão nos parâmetros definidos') if w.ground.com_wings == []: raise NoGatheringProblemError('Não há alas comuns') if (len(w.ground.com_wings) > 1): wing_x = set() wing_y = set() for loc in w.ground.com_wings: wing_x.add(loc.xpos) wing_y.add(loc.ypos) if (max(wing_x) - min(wing_x) + 1) * (max(wing_y)-min(wing_y) + 1) != len(w.ground.com_wings): raise NoGatheringProblemError('Não há apenas uma ala comum retangular neste mundo!') def goal_wizard(s:State)-> bool: for wiz in s.values(): #s tem apenas um elemento sempre; este algoritmo é de ordem de complexidade O(1) return wiz.where in w.ground.com_wings #booleano será chamado em state com apenas 1 agente, em findGoal list_states: list[State] = [] for agent in w.state.values(): list_states.append({agent.name: agent}) list_paths: list[Path] = [] for state in list_states: list_paths.append(findGoal(World(w.ground,state),goal_wizard)) #print(list_paths) length_paths: list[int] = [] for path_i in list_paths: length_paths.append(len(path_i)) #print((length_paths)) path_final: Path = [] while list_paths != []: min_path = min(length_paths) for i in range(0,len(list_paths)): if len(list_paths[i]) == min_path: path_final += list_paths[i] list_paths.pop(i) length_paths.remove(min_path) break #sair deste for loop, para realizar a próxima iteração do while return path_final """"" # tests!! ---------------------------------------------------------------------------------------------------------------------------------------- w = newWorld("Playground",20,20) wizard1 = newAgent("wizard1") wizard2 = newAgent("wizard2") wizard3 = newAgent("wizard3") wizard4 = newAgent("wizard4") wizard5 = newAgent("wizard5") putThing(w,wizard1,Location(0,0)) putThing(w,wizard2,Location(14,8)) putThing(w,wizard3,Location(0,19)) putThing(w,wizard4,Location(12,18)) putThing(w,wizard5,Location(4,6)) setComWing(w,Location(5,6),2,3) setWormhole(w,Location(0,1),Location(8,9)) setWormhole(w,Location(0,18),Location(5,6)) setWormhole(w,Location(9,6),Location(14,19)) setWormhole(w,Location(1,19),Location(14,9)) print(gatherWizards(w)) w1= newWorld('bruv',20,20) cookie1 = newObject('cookie1') cookie2 = newObject('cookie2') cookie3 = newObject('cookie3') monster = newAgent('monster') cookie4 = newObject('cookie4') cookie5 = newObject('cookie5') cookie6 = newObject('cookie6') #cookie7 = newObject('cookie7') setAltitude(w1,Location(14,7),2,1,3) setAltitude(w1,Location(4,4),3,4,1) setAltitude(w1,Location(0,0),2,1,2) setWormhole(w1,Location(1,11),Location(15,6)) setWormhole(w1,Location(1,3),Location(3,5)) setWormhole(w1,Location(3,12), Location(13,17)) putThing(w1,cookie6,Location(14,7)) putThing(w1,cookie3,Location(1,10)) putThing(w1,cookie1,Location(0,0)) putThing(w1,cookie2,Location(5,6)) putThing(w1,monster,Location(0,1)) putThing(w1,cookie4,Location(12,18)) #putThing(w1,cookie5,Location(18,0)) #print(moveAgent(w1,monster,'R')) #print(pathToWorlds(w1, ('U monster', 'R monster', 'D monster', 'L monster', 'P monster cookie1'))) print(findCookies(w1)) #print(nextWorlds(w1)) def goalw201(ths:State)->bool: for agent in ths.values(): if isinstance(agent, Agent): r:Agent = agent return ((r.where == Location(0,0)) and (len(r.objects) == 2)) w2:World= newWorld("BlackHole",6,6) robot:Agent = newAgent("Batman") putThing(w2,robot,Location(0,0)) box0:Object = newObject("Cube") putThing(w2,box0,Location(5,5)) box1:Object = newObject("Knife") putThing(w2,box1,Location(4,1)) setAltitude(w2,Location(3,4),3,2,2) setAltitude(w2,Location(4,5),2,1,0) setAltitude(w2,Location(2,2),2,2,4) setWormhole(w2,Location(1,1),Location(4,4)) #solution = findGoal(w2,goalw201) #lw = pathToWorlds(w2,solution) #self.assertEqual(len(lw),13) print(findGoal(w2,goalw201)) w = newWorld("Playground",20,20) robot1 = newAgent("CookieMonster") putThing(w,robot1,Location(0,9)) box0 = newObject("box0") putThing(w,box0,Location(1,1)) box1 = newObject("box1") putThing(w,box1,Location(1,3)) box2 = newObject("box2") putThing(w,box2,Location(1,7)) box3 = newObject("box3") putThing(w,box3,Location(1,19)) setAltitude(w,Location(3,0),2,11,9) ## check this setAltitude(w,Location(3,12),2,8,9) ## check this print(findCookies(w))"""