Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit8c275b9

Browse files
committed
Added first iterations on day 2021-23
1 parent2ad007e commit8c275b9

File tree

5 files changed

+7137
-0
lines changed

5 files changed

+7137
-0
lines changed

‎2021/23-Amphipod.v1.py

Lines changed: 368 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,368 @@
1+
# -------------------------------- Input data ---------------------------------------- #
2+
importos,grid,graph,dot,assembly,re,itertools,copy,functools
3+
fromcollectionsimportCounter,deque,defaultdict
4+
fromfunctoolsimportreduce
5+
importheapq
6+
7+
fromcompassimport*
8+
9+
10+
# This functions come from https://github.com/mcpower/adventofcode - Thanks!
11+
deflmap(func,*iterables):
12+
returnlist(map(func,*iterables))
13+
14+
15+
defints(s:str):
16+
returnlmap(int,re.findall(r"-?\d+",s))# thanks mserrano!
17+
18+
19+
defpositive_ints(s:str):
20+
returnlmap(int,re.findall(r"\d+",s))# thanks mserrano!
21+
22+
23+
deffloats(s:str):
24+
returnlmap(float,re.findall(r"-?\d+(?:\.\d+)?",s))
25+
26+
27+
defpositive_floats(s:str):
28+
returnlmap(float,re.findall(r"\d+(?:\.\d+)?",s))
29+
30+
31+
defwords(s:str):
32+
returnre.findall(r"[a-zA-Z]+",s)
33+
34+
35+
test_data= {}
36+
37+
test=1
38+
test_data[test]= {
39+
"input":"""#############
40+
#...........#
41+
###B#C#B#D###
42+
#A#D#C#A#
43+
#########""",
44+
"expected": ["12521","Unknown"],
45+
}
46+
47+
test="real"
48+
input_file=os.path.join(
49+
os.path.dirname(__file__),
50+
"Inputs",
51+
os.path.basename(__file__).replace(".py",".txt"),
52+
)
53+
test_data[test]= {
54+
"input":open(input_file,"r+").read(),
55+
"expected": ["Unknown","Unknown"],
56+
}
57+
58+
59+
# -------------------------------- Control program execution ------------------------- #
60+
61+
case_to_test=1
62+
part_to_test=1
63+
64+
# -------------------------------- Initialize some variables ------------------------- #
65+
66+
puzzle_input=test_data[case_to_test]["input"]
67+
puzzle_expected_result=test_data[case_to_test]["expected"][part_to_test-1]
68+
puzzle_actual_result="Unknown"
69+
70+
71+
# This was the very first attempt to solve it
72+
# It tries to parse the input, the run A* on it to find possible movements
73+
# Basically it's wayyy too slow and buggy
74+
75+
76+
# -------------------------------- Actual code execution ----------------------------- #
77+
78+
dot.Dot.sort_value=dot.Dot.sorting_map["xy"]
79+
80+
81+
classNewGrid(grid.Grid):
82+
deftext_to_dots(self,text,ignore_terrain="",convert_to_int=False):
83+
self.dots= {}
84+
85+
y=0
86+
self.amphipods= {}
87+
self.position_to_rooms= []
88+
nb_amphipods= []
89+
forlineintext.splitlines():
90+
forxinrange(len(line)):
91+
ifline[x]notinignore_terrain:
92+
value=line[x]
93+
position=x-y*1j
94+
95+
ifvalue==" ":
96+
continue
97+
98+
ifvaluein"ABCD":
99+
self.position_to_rooms.append(position)
100+
ifvalueinnb_amphipods:
101+
UUID=value+"2"
102+
else:
103+
UUID=value+"1"
104+
nb_amphipods.append(value)
105+
self.amphipods[UUID]=dot.Dot(self,position,value)
106+
107+
value="."
108+
109+
self.dots[position]=dot.Dot(self,position,value)
110+
# self.dots[position].sort_value = self.dots[position].sorting_map['xy']
111+
ifvalue==".":
112+
self.dots[position].is_waypoint=True
113+
y+=1
114+
115+
116+
classStateGraph(graph.WeightedGraph):
117+
amphipod_state= ["A1","A2","B1","B2","C1","C2","D1","D2"]
118+
119+
defa_star_search(self,start,end=None):
120+
"""
121+
Performs a A* search
122+
123+
This algorithm is appropriate for "One source, multiple targets"
124+
It takes into account positive weigths / costs of travelling.
125+
Negative weights will make the algorithm fail.
126+
127+
The exploration path is a mix of Dijkstra and Greedy BFS
128+
It uses the current cost + estimated cost to determine the next element to consider
129+
130+
Some cases to consider:
131+
- If Estimated cost to complete = 0, A* = Dijkstra
132+
- If Estimated cost to complete <= actual cost to complete, it is exact
133+
- If Estimated cost to complete > actual cost to complete, it is inexact
134+
- If Estimated cost to complete = infinity, A* = Greedy BFS
135+
The higher Estimated cost to complete, the faster it goes
136+
137+
:param Any start: The start vertex to consider
138+
:param Any end: The target/end vertex to consider
139+
:return: True when the end vertex is found, False otherwise
140+
"""
141+
current_distance=0
142+
frontier= [(0,start,0)]
143+
heapq.heapify(frontier)
144+
self.distance_from_start= {start:0}
145+
self.came_from= {start:None}
146+
self.visited= [tuple(dot.positionfordotinstart)]
147+
148+
i=0
149+
whilefrontier:# and i < 5:
150+
i+=1
151+
priority,vertex,current_distance=heapq.heappop(frontier)
152+
print(len(frontier),priority,current_distance)
153+
154+
neighbors=self.neighbors(vertex)
155+
ifnotneighbors:
156+
continue
157+
158+
forneighbor,weightinneighbors.items():
159+
# We've already checked that node, and it's not better now
160+
ifneighborinself.distance_from_startandself.distance_from_start[
161+
neighbor
162+
]<= (current_distance+weight):
163+
continue
164+
165+
ifany(
166+
equivalent_positioninself.visited
167+
forequivalent_positioninself.equivalent_positions(neighbor)
168+
):
169+
continue
170+
171+
# Adding for future examination
172+
priority=current_distance+self.estimate_to_complete(neighbor,end)
173+
# print (vertex, neighbor, current_distance, priority)
174+
heapq.heappush(
175+
frontier, (priority,neighbor,current_distance+weight)
176+
)
177+
178+
# Adding for final search
179+
self.distance_from_start[neighbor]=current_distance+weight
180+
self.came_from[neighbor]=vertex
181+
self.visited.append(tuple(dot.positionfordotinneighbor))
182+
183+
ifself.state_is_final(neighbor):
184+
returnself.distance_from_start[neighbor]
185+
186+
# print (len(frontier))
187+
188+
returnendinself.distance_from_start
189+
190+
defneighbors(self,state):
191+
ifself.state_is_final(state):
192+
returnNone
193+
194+
neighbors= {}
195+
fori,current_dotinenumerate(state):
196+
amphipod_code=self.amphipod_state[i]
197+
dots=self.area_graph.edges[current_dot]
198+
fordot,costindots.items():
199+
new_state=list(state)
200+
new_state[i]=dot
201+
new_state=tuple(new_state)
202+
# print ('Checking', amphipod_code, 'moved from', state[i], 'to', new_state[i])
203+
ifself.state_is_valid(state,new_state,i):
204+
neighbors[new_state]= (
205+
cost*self.amphipods[amphipod_code].movement_cost
206+
)
207+
# print ('Movement costs', cost * self.amphipods[amphipod_code].movement_cost)
208+
209+
returnneighbors
210+
211+
defstate_is_final(self,state):
212+
fori,positioninenumerate(state):
213+
amphipod_code=self.amphipod_state[i]
214+
amphipod=self.amphipods[amphipod_code]
215+
216+
ifnotpositioninself.room_to_positions[amphipod.terrain]:
217+
returnFalse
218+
returnTrue
219+
220+
defstate_is_valid(self,state,new_state,changed):
221+
# Duplicate = 2 amphipods in the same place
222+
iflen(set(new_state))!=len(new_state):
223+
# print ('Duplicate amphipod', new_state[changed])
224+
returnFalse
225+
226+
# Check amphipod is not in wrong room
227+
ifnew_state[i].positioninself.position_to_rooms:
228+
room=self.position_to_rooms[new_state[i].position]
229+
# print ('Amphipod may be in wrong place', new_state)
230+
amphipod=self.amphipod_state[i]
231+
ifroom==self.amphipods[amphipod].initial_room:
232+
returnTrue
233+
else:
234+
# print ('Amphipod is in wrong place', new_state)
235+
returnFalse
236+
237+
returnTrue
238+
239+
defestimate_to_complete(self,state,target_vertex):
240+
distance=0
241+
fori,dotinenumerate(state):
242+
amphipod_code=self.amphipod_state[i]
243+
amphipod=self.amphipods[amphipod_code]
244+
245+
ifnotdot.positioninself.room_to_positions[amphipod.terrain]:
246+
room_positions=self.room_to_positions[amphipod.terrain]
247+
targets= [self.dots[position]forpositioninroom_positions]
248+
distance+= (
249+
min(
250+
self.area_graph.all_edges[dot][target]
251+
iftargetinself.area_graph.all_edges[dot]
252+
else10**6
253+
fortargetintargets
254+
)
255+
*amphipod.movement_cost
256+
)
257+
258+
returndistance
259+
260+
defequivalent_positions(self,state):
261+
state_positions= [dot.positionfordotinstate]
262+
positions= [
263+
tuple([state_positions[1]]+ [state_positions[0]]+state_positions[2:]),
264+
tuple(
265+
state_positions[0:2]
266+
+ [state_positions[3]]
267+
+ [state_positions[2]]
268+
+state_positions[4:]
269+
),
270+
tuple(
271+
state_positions[0:4]
272+
+ [state_positions[5]]
273+
+ [state_positions[4]]
274+
+state_positions[6:]
275+
),
276+
tuple(state_positions[0:6]+ [state_positions[7]]+ [state_positions[6]]),
277+
]
278+
279+
foriinrange(4):
280+
position=tuple(
281+
state_positions[:i]
282+
+state_positions[i+1 :i]
283+
+state_positions[i+2 :]
284+
)
285+
positions.append(position)
286+
287+
returnpositions
288+
289+
290+
ifpart_to_test==1:
291+
area_map=NewGrid()
292+
area_map.text_to_dots(puzzle_input)
293+
294+
position_to_rooms=defaultdict(list)
295+
room_to_positions=defaultdict(list)
296+
area_map.position_to_rooms=sorted(
297+
area_map.position_to_rooms,key=lambdaa: (a.real,a.imag)
298+
)
299+
foriinrange(4):
300+
position_to_rooms[area_map.position_to_rooms[2*i]]="ABCD"[i]
301+
position_to_rooms[area_map.position_to_rooms[2*i+1]]="ABCD"[i]
302+
room_to_positions["ABCD"[i]].append(area_map.position_to_rooms[2*i])
303+
room_to_positions["ABCD"[i]].append(area_map.position_to_rooms[2*i+1])
304+
# Forbid to use the dot right outside the room
305+
area_map.dots[area_map.position_to_rooms[2*i+1]+1j].is_waypoint=False
306+
area_map.position_to_rooms=position_to_rooms
307+
area_map.room_to_positions=room_to_positions
308+
309+
# print (list(dot for dot in area_map.dots if area_map.dots[dot].is_waypoint))
310+
311+
foramphipodinarea_map.amphipods:
312+
area_map.amphipods[amphipod].initial_room=area_map.position_to_rooms[
313+
area_map.amphipods[amphipod].position
314+
]
315+
area_map.amphipods[amphipod].movement_cost=10** (
316+
ord(area_map.amphipods[amphipod].terrain)-ord("A")
317+
)
318+
319+
area_graph=area_map.convert_to_graph()
320+
area_graph.all_edges=area_graph.edges
321+
area_graph.edges= {
322+
dot: {
323+
neighbor:distance
324+
forneighbor,distanceinarea_graph.edges[dot].items()
325+
ifdistance<=2
326+
}
327+
fordotinarea_graph.vertices
328+
}
329+
print(len(area_graph.all_edges))
330+
331+
# print (area_graph.vertices)
332+
# print (area_graph.edges)
333+
334+
state_graph=StateGraph()
335+
state_graph.area_graph=area_graph
336+
state_graph.amphipods=area_map.amphipods
337+
state_graph.position_to_rooms=area_map.position_to_rooms
338+
state_graph.room_to_positions=area_map.room_to_positions
339+
state_graph.dots=area_map.dots
340+
341+
state=tuple(
342+
area_map.dots[area_map.amphipods[amphipod].position]
343+
foramphipodinsorted(area_map.amphipods.keys())
344+
)
345+
# print ('area_map.amphipods', area_map.amphipods)
346+
347+
print("state",state)
348+
# print ('equivalent', state_graph.equivalent_positions(state))
349+
print("estimate",state_graph.estimate_to_complete(state,None))
350+
351+
print(state_graph.a_star_search(state))
352+
353+
# In the example, A is already in the right place
354+
# In all other cases, 1 anphipod per group has to go to the bottom, so 1 move per amphipod
355+
356+
357+
else:
358+
forstringinpuzzle_input.split("\n"):
359+
ifstring=="":
360+
continue
361+
362+
363+
# -------------------------------- Outputs / results --------------------------------- #
364+
365+
print("Case :",case_to_test,"- Part",part_to_test)
366+
print("Expected result : "+str(puzzle_expected_result))
367+
print("Actual result : "+str(puzzle_actual_result))
368+
# Date created: 2021-12-23 08:11:43.693421

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp