Jan-03-2025, 07:30 PM
So, I have a pretty big code. Its a bread-first-search algorythm. Im trying to avoid checking too many cases and going for the permutations instead. But when all the objects are at the same altitudes and there are 8 objects or more, the code gets really big (probably because the order of complexity will be exponential). If you have some time, Im gonna leave my code here and you can write wtv you want. If not, you can just leave some ideas to maybe reduce cases or something
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)<=len(path):
break
#else:
#continue
except PlayGroundError:
break
#print(path)
try:#if pathToWorlds(w,path):
world = pathToWorlds(World(og_world.ground,deepcopy(og_world.state)),path)[-1]
#print(world)
#cookies = possible_cookies(world)
#print(cookies)
#continue
except PlayGroundError:
break
#permutation_number+=1
pick=0
for action in path:
if action.split(' ')[0] == 'P':
pick+=1
if pick + 1 == len(og_world.state):
list_paths.append(path)
length_paths.append(len(path))
#print(list_paths)
#continue
else:
continue
#length_paths: list[int] = []
#for path_i in list_paths:
# length_paths.append(len(path_i))
#print((length_paths))
if list_paths != []:
return list_paths[length_paths.index(min(length_paths))]
else:
raise PlayGroundError('Impossível completar o objetivo')
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
Attached Files
