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

Commit0e9bd66

Browse files
committed
Updated pathfinding to use complex numbers rather than coordinates
1 parent72174b0 commit0e9bd66

File tree

3 files changed

+247
-175
lines changed

3 files changed

+247
-175
lines changed

‎2018/10-The Stars Align.py‎

Lines changed: 32 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,8 @@
44
test_data= {}
55

66
test=1
7-
test_data[test]= {"input":"""position=< 9, 1> velocity=< 0, 2>
7+
test_data[test]= {
8+
"input":"""position=< 9, 1> velocity=< 0, 2>
89
position=< 7, 0> velocity=<-1, 0>
910
position=< 3, -2> velocity=<-1, 1>
1011
position=< 6, 10> velocity=<-2, -1>
@@ -35,40 +36,44 @@
3536
position=< 5, 9> velocity=< 1, -2>
3637
position=<14, 7> velocity=<-2, 0>
3738
position=<-3, 6> velocity=< 2, -1>""",
38-
"expected": ['Unknown','Unknown'],
39-
}
40-
41-
test='real'
42-
input_file=os.path.join(os.path.dirname(__file__),'Inputs',os.path.basename(__file__).replace('.py','.txt'))
43-
test_data[test]= {"input":open(input_file,"r+").read().strip(),
44-
"expected": ['RLEZNRAN','10240'],
45-
}
39+
"expected": ["Unknown","Unknown"],
40+
}
41+
42+
test="real"
43+
input_file=os.path.join(
44+
os.path.dirname(__file__),
45+
"Inputs",
46+
os.path.basename(__file__).replace(".py",".txt"),
47+
)
48+
test_data[test]= {
49+
"input":open(input_file,"r+").read().strip(),
50+
"expected": ["RLEZNRAN","10240"],
51+
}
4652

4753
# -------------------------------- Control program execution -------------------------------- #
4854

49-
case_to_test='real'
55+
case_to_test="real"
5056
part_to_test=1
5157

5258
# -------------------------------- Initialize some variables -------------------------------- #
5359

54-
puzzle_input=test_data[case_to_test]['input']
55-
puzzle_expected_result=test_data[case_to_test]['expected'][part_to_test-1]
56-
puzzle_actual_result='Unknown'
60+
puzzle_input=test_data[case_to_test]["input"]
61+
puzzle_expected_result=test_data[case_to_test]["expected"][part_to_test-1]
62+
puzzle_actual_result="Unknown"
5763

5864

5965
# -------------------------------- Actual code execution -------------------------------- #
6066
stars= []
61-
forstringinpuzzle_input.split('\n'):
62-
ifstring=='':
67+
forstringinpuzzle_input.split("\n"):
68+
ifstring=="":
6369
continue
64-
r=parse.parse('position=<{:>d},{:>d}> velocity=<{:>d},{:>d}>',string)
70+
r=parse.parse("position=<{:>d},{:>d}> velocity=<{:>d},{:>d}>",string)
6571
stars.append(list(map(int,r)))
6672

6773
star_map=pathfinding.Graph()
68-
foriinrange (2*10**4):
69-
stars= [(x+vx,y+vy,vx,vy)forx,y,vx,vyinstars]
70-
vertices= [(x,y)forx,y,vx,vyinstars]
71-
74+
foriinrange(2*10**4):
75+
stars= [(x+vx,y+vy,vx,vy)forx,y,vx,vyinstars]
76+
vertices= [x-y*1jforx,y,vx,vyinstars]
7277

7378
# This was solved a bit manually
7479
# I noticed all coordinates would converge around 0 at some point
@@ -77,21 +82,17 @@
7782
# (my first test was actually 200, but that was gave no result)
7883
# This gave ~ 20 seconds of interesting time
7984
# At the end it was trial and error to find 10 240
80-
coords= [v[0]inrange(-300,300)forvinvertices]+ [v[1]inrange(-300,300)forvinvertices]
85+
coords= [v.realinrange(-300,300)forvinvertices]+ [
86+
v.imaginrange(-300,300)forvinvertices
87+
]
8188

8289
ifall(coords)andi==10239:
8390
star_map.vertices=vertices
84-
print (i+1)
85-
print (star_map.vertices_to_grid(wall=' '))
86-
87-
91+
print(i+1)
92+
print(star_map.vertices_to_grid(wall=" "))
8893

8994

9095
# -------------------------------- Outputs / results -------------------------------- #
9196

92-
print ('Expected result : '+str(puzzle_expected_result))
93-
print ('Actual result : '+str(puzzle_actual_result))
94-
95-
96-
97-
97+
print("Expected result : "+str(puzzle_expected_result))
98+
print("Actual result : "+str(puzzle_actual_result))

‎2018/13-Mine Cart Madness.v1.py‎

Lines changed: 67 additions & 68 deletions
Original file line numberDiff line numberDiff line change
@@ -1,126 +1,133 @@
1-
2-
31
# This v1 works for part 1, not part 2
42
# Since it's also quite slow, I've done a v2 that should be better
53

64

7-
8-
9-
10-
115
# -------------------------------- Input data -------------------------------- #
126
importos,pathfinding,re
137

148
test_data= {}
159

1610
test=1
17-
test_data[test]= {"input":"""/->-\\
11+
test_data[test]= {
12+
"input":"""/->-\\
1813
| | /----\\
1914
| /-+--+-\ |
2015
| | | | v |
2116
\-+-/ \-+--/
2217
\------/ """,
23-
"expected": ['Unknown','Unknown'],
24-
}
18+
"expected": ["Unknown","Unknown"],
19+
}
2520

2621
test+=1
27-
test_data[test]= {"input":r"""/>-<\
22+
test_data[test]= {
23+
"input":r"""/>-<\
2824
| |
2925
| /<+-\
3026
| | | v
3127
\>+</ |
3228
| ^
3329
\<->/""",
34-
"expected": ['Unknown','Unknown'],
35-
}
36-
37-
test='real'
38-
input_file=os.path.join(os.path.dirname(__file__),'Inputs',os.path.basename(__file__).replace('.py','.txt'))
39-
test_data[test]= {"input":open(input_file,"r+").read(),
40-
"expected": ['124,130','99, 96'],
41-
}
30+
"expected": ["Unknown","Unknown"],
31+
}
32+
33+
test="real"
34+
input_file=os.path.join(
35+
os.path.dirname(__file__),
36+
"Inputs",
37+
os.path.basename(__file__).replace(".py",".txt"),
38+
)
39+
test_data[test]= {
40+
"input":open(input_file,"r+").read(),
41+
"expected": ["124,130","99, 96"],
42+
}
4243

4344
# -------------------------------- Control program execution -------------------------------- #
4445

45-
case_to_test='real'
46+
case_to_test="real"
4647
part_to_test=2
4748

4849
# -------------------------------- Initialize some variables -------------------------------- #
4950

50-
puzzle_input=test_data[case_to_test]['input']
51-
puzzle_expected_result=test_data[case_to_test]['expected'][part_to_test-1]
52-
puzzle_actual_result='Unknown'
51+
puzzle_input=test_data[case_to_test]["input"]
52+
puzzle_expected_result=test_data[case_to_test]["expected"][part_to_test-1]
53+
puzzle_actual_result="Unknown"
5354

5455

5556
# -------------------------------- Actual code execution -------------------------------- #
5657

5758

58-
defgrid_to_vertices(self,grid,wall='#'):
59+
defgrid_to_vertices(self,grid,wall="#"):
5960
self.vertices= []
6061
track= {}
6162
y=0
6263

6364
forlineingrid.splitlines():
64-
line=line.replace('^','|').replace('v','|').replace('>','-').replace('<','-')
65+
line= (
66+
line.replace("^","|").replace("v","|").replace(">","-").replace("<","-")
67+
)
6568
forxinrange(len(line)):
6669
ifline[x]!=wall:
6770
self.vertices.append((x,y))
6871
track[(x,y)]=line[x]
6972

7073
y+=1
7174

72-
directions= [(1,0), (-1,0), (0,1), (0,-1)]
73-
right,left,down,up=directions
75+
north=1j
76+
south=-1j
77+
west=-1
78+
east=1
79+
80+
directions= [north,south,west,east]
7481

75-
forcoordsinself.vertices:
82+
forsourceinself.vertices:
7683
fordirectionindirections:
77-
x,y=coords[0]+direction[0],coords[1]+direction[1]
84+
target=source+direction
7885

79-
iftrack[coords]=='-'anddirectionin [up,down]:
86+
iftrack[source]=="-"anddirectionin [north,south]:
8087
continue
81-
iftrack[coords]=='|'anddirectionin [left,right]:
88+
iftrack[source]=="|"anddirectionin [west,east]:
8289
continue
8390

84-
if(x,y)inself.vertices:
85-
iftrack[coords]in ('\\','/'):
86-
iftrack[(x,y)]in ('\\','/'):
91+
iftargetinself.vertices:
92+
iftrack[source]in ("\\","/"):
93+
iftrack[target]in ("\\","/"):
8794
continue
88-
iftrack[(x,y)]=='-'anddirectionin [up,down]:
95+
iftrack[target]=="-"anddirectionin [north,south]:
8996
continue
90-
eliftrack[(x,y)]=='|'anddirectionin [left,right]:
97+
eliftrack[target]=="|"anddirectionin [west,east]:
9198
continue
92-
ifcoordsinself.edges:
93-
self.edges[(coords)].append((x,y))
99+
ifsourceinself.edges:
100+
self.edges[(source)].append(target)
94101
else:
95-
self.edges[(coords)]= [(x,y)]
102+
self.edges[(source)]= [target]
96103

97104
returnTrue
98105

99-
pathfinding.Graph.grid_to_vertices=grid_to_vertices
100106

101-
defturn_left (direction):
102-
return (direction[1],-direction[0])
107+
pathfinding.Graph.grid_to_vertices=grid_to_vertices
103108

104-
defturn_right (direction):
105-
return (-direction[1],direction[0])
106109

110+
defturn_left(direction):
111+
return (direction[1],-direction[0])
107112

108113

114+
defturn_right(direction):
115+
return (-direction[1],direction[0])
109116

110117

111118
# Analyze grid
112119
grid=puzzle_input
113120
graph=pathfinding.Graph()
114-
graph.grid_to_vertices(puzzle_input,' ')
121+
graph.grid_to_vertices(puzzle_input," ")
115122

116-
intersections=graph.grid_search(grid,'+')['+']
123+
intersections=graph.grid_search(grid,"+")["+"]
117124

118-
directions= {'^': (0,-1),'>': (1,0),'<': (-1,0),'v': (0,1)}
119-
dirs= {(0,-1):'^', (1,0):'>', (-1,0):'<', (0,1):'v'}
125+
directions= {"^": (0,-1),">": (1,0),"<": (-1,0),"v": (0,1)}
126+
dirs= {(0,-1):"^", (1,0):">", (-1,0):"<", (0,1):"v"}
120127

121128

122129
# Find carts
123-
list_carts=graph.grid_search(grid, ('^','<','>','v'))
130+
list_carts=graph.grid_search(grid, ("^","<",">","v"))
124131
carts= []
125132
cart_positions= []
126133
fordirectioninlist_carts:
@@ -143,15 +150,16 @@ def turn_right (direction):
143150
pos,dir,choice=cart
144151
new_pos= (pos[0]+dir[0],pos[1]+dir[1])
145152

146-
print (pos,choice,dirs[dir])
147-
153+
print(pos,choice,dirs[dir])
148154

149155
# We need to turn
150156
ifnew_posnotingraph.edges[pos]:
151-
options= [((pos[0]+x[0],pos[1]+x[1]),x)
152-
forxindirections.values()
153-
ifx!= (-dir[0],-dir[1])
154-
and (pos[0]+x[0],pos[1]+x[1])ingraph.edges[pos]]
157+
options= [
158+
((pos[0]+x[0],pos[1]+x[1]),x)
159+
forxindirections.values()
160+
ifx!= (-dir[0],-dir[1])
161+
and (pos[0]+x[0],pos[1]+x[1])ingraph.edges[pos]
162+
]
155163
new_pos,dir=options[0]
156164

157165
# Intersection
@@ -165,25 +173,20 @@ def turn_right (direction):
165173

166174
new_cart= (new_pos,dir,choice)
167175

168-
169-
170-
171-
172176
# Check collisions
173177
ifnew_cart[0]incart_positions:
174178
ifpart_to_test==1:
175179
puzzle_actual_result=new_cart[0]
176180
break
177181
else:
178-
print ('collision',new_cart[0])
182+
print("collision",new_cart[0])
179183
collision+=1
180184
carts= [cforcincartsifc[0]!=new_cart[0]]
181185
cart_positions= [c[0]forcincarts]
182186
else:
183187
carts.append(new_cart)
184188
cart_positions.append(new_cart[0])
185189

186-
187190
# Count ticks + sort carts
188191
subtick+=1
189192
ifsubtick==nb_carts-collision:
@@ -194,18 +197,14 @@ def turn_right (direction):
194197
carts=sorted(carts,key=lambdax: (x[0][1],x[0][0]))
195198
cart_positions= [c[0]forcincarts]
196199

197-
print ('End of tick',tick,' - Remaining',len(carts))
200+
print("End of tick",tick," - Remaining",len(carts))
198201
iflen(carts)==1:
199202
break
200203

201204
ifpart_to_test==2:
202205
puzzle_actual_result=carts
203-
#99, 96
206+
#99, 96
204207
# -------------------------------- Outputs / results -------------------------------- #
205208

206-
print ('Expected result : '+str(puzzle_expected_result))
207-
print ('Actual result : '+str(puzzle_actual_result))
208-
209-
210-
211-
209+
print("Expected result : "+str(puzzle_expected_result))
210+
print("Actual result : "+str(puzzle_actual_result))

0 commit comments

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