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

Commit34dbe35

Browse files
committed
Improved performance for days 2018-10 and 2018-22
1 parent89a7947 commit34dbe35

File tree

5 files changed

+390
-73
lines changed

5 files changed

+390
-73
lines changed

‎2018/10-The Stars Align.py

Lines changed: 22 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -71,25 +71,31 @@
7171
stars.append(list(map(int,r)))
7272

7373
star_map=pathfinding.Graph()
74+
stars_init= [star.copy()forstarinstars]
75+
min_galaxy_size=10**15
76+
min_i_galaxy_size=0
7477
foriinrange(2*10**4):
75-
stars= [(x+vx,y+vy,vx,vy)forx,y,vx,vyinstars]
76-
vertices= [x-y*1jforx,y,vx,vyinstars]
77-
78-
# This was solved a bit manually
79-
# I noticed all coordinates would converge around 0 at some point
80-
# That point was around 10300 seconds
81-
# Then made a limit: all coordinates should be within 300 from zero
82-
# (my first test was actually 200, but that was gave no result)
83-
# This gave ~ 20 seconds of interesting time
84-
# At the end it was trial and error to find 10 240
85-
coords= [v.realinrange(-300,300)forvinvertices]+ [
86-
v.imaginrange(-300,300)forvinvertices
87-
]
88-
89-
ifall(coords)andi==10239:
78+
stars= [(x+i*vx,y+i*vy,vx,i*vy)forx,y,vx,vyinstars_init]
79+
80+
# This gives a very rough idea of the galaxy's size
81+
coords=list(zip(*stars))
82+
galaxy_size=max(coords[0])-min(coords[0])+max(coords[1])-max(coords[1])
83+
84+
ifi==0:
85+
min_galaxy_size=galaxy_size
86+
87+
ifgalaxy_size<min_galaxy_size:
88+
min_i_galaxy_size=i
89+
min_galaxy_size=galaxy_size
90+
elifgalaxy_size>min_galaxy_size:
91+
vertices= [
92+
x+vx*min_i_galaxy_size- (y+vy*min_i_galaxy_size)*1j
93+
forx,y,vx,vyinstars_init
94+
]
9095
star_map.vertices=vertices
91-
print(i+1)
96+
puzzle_actual_result=min_i_galaxy_size
9297
print(star_map.vertices_to_grid(wall=" "))
98+
break
9399

94100

95101
# -------------------------------- Outputs / results -------------------------------- #

‎2018/10-The Stars Align.v1.py

Lines changed: 98 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,98 @@
1+
# -------------------------------- Input data -------------------------------- #
2+
importos,parse,pathfinding
3+
4+
test_data= {}
5+
6+
test=1
7+
test_data[test]= {
8+
"input":"""position=< 9, 1> velocity=< 0, 2>
9+
position=< 7, 0> velocity=<-1, 0>
10+
position=< 3, -2> velocity=<-1, 1>
11+
position=< 6, 10> velocity=<-2, -1>
12+
position=< 2, -4> velocity=< 2, 2>
13+
position=<-6, 10> velocity=< 2, -2>
14+
position=< 1, 8> velocity=< 1, -1>
15+
position=< 1, 7> velocity=< 1, 0>
16+
position=<-3, 11> velocity=< 1, -2>
17+
position=< 7, 6> velocity=<-1, -1>
18+
position=<-2, 3> velocity=< 1, 0>
19+
position=<-4, 3> velocity=< 2, 0>
20+
position=<10, -3> velocity=<-1, 1>
21+
position=< 5, 11> velocity=< 1, -2>
22+
position=< 4, 7> velocity=< 0, -1>
23+
position=< 8, -2> velocity=< 0, 1>
24+
position=<15, 0> velocity=<-2, 0>
25+
position=< 1, 6> velocity=< 1, 0>
26+
position=< 8, 9> velocity=< 0, -1>
27+
position=< 3, 3> velocity=<-1, 1>
28+
position=< 0, 5> velocity=< 0, -1>
29+
position=<-2, 2> velocity=< 2, 0>
30+
position=< 5, -2> velocity=< 1, 2>
31+
position=< 1, 4> velocity=< 2, 1>
32+
position=<-2, 7> velocity=< 2, -2>
33+
position=< 3, 6> velocity=<-1, -1>
34+
position=< 5, 0> velocity=< 1, 0>
35+
position=<-6, 0> velocity=< 2, 0>
36+
position=< 5, 9> velocity=< 1, -2>
37+
position=<14, 7> velocity=<-2, 0>
38+
position=<-3, 6> velocity=< 2, -1>""",
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+
}
52+
53+
# -------------------------------- Control program execution -------------------------------- #
54+
55+
case_to_test="real"
56+
part_to_test=1
57+
58+
# -------------------------------- Initialize some variables -------------------------------- #
59+
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"
63+
64+
65+
# -------------------------------- Actual code execution -------------------------------- #
66+
stars= []
67+
forstringinpuzzle_input.split("\n"):
68+
ifstring=="":
69+
continue
70+
r=parse.parse("position=<{:>d},{:>d}> velocity=<{:>d},{:>d}>",string)
71+
stars.append(list(map(int,r)))
72+
73+
star_map=pathfinding.Graph()
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]
77+
78+
# This was solved a bit manually
79+
# I noticed all coordinates would converge around 0 at some point
80+
# That point was around 10300 seconds
81+
# Then made a limit: all coordinates should be within 300 from zero
82+
# (my first test was actually 200, but that was gave no result)
83+
# This gave ~ 20 seconds of interesting time
84+
# At the end it was trial and error to find 10 240
85+
coords= [v.realinrange(-300,300)forvinvertices]+ [
86+
v.imaginrange(-300,300)forvinvertices
87+
]
88+
89+
ifall(coords)andi==10239:
90+
star_map.vertices=vertices
91+
print(i+1)
92+
print(star_map.vertices_to_grid(wall=" "))
93+
94+
95+
# -------------------------------- Outputs / results -------------------------------- #
96+
97+
print("Expected result : "+str(puzzle_expected_result))
98+
print("Actual result : "+str(puzzle_actual_result))

‎2018/22-Mode Maze.py

Lines changed: 76 additions & 49 deletions
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,12 @@
11
# -------------------------------- Input data ---------------------------------------- #
22
importos,pathfinding
33

4+
fromcomplex_utilsimport*
5+
6+
7+
j=SuperComplex(1j)
8+
9+
410
test_data= {}
511

612
test=1
@@ -18,7 +24,7 @@
1824
)
1925
test_data[test]= {
2026
"input":open(input_file,"r+").read().strip(),
21-
"expected": ["6256","Unknown"],
27+
"expected": ["6256","973"],
2228
}
2329

2430
# -------------------------------- Control program execution ------------------------- #
@@ -40,23 +46,23 @@
4046

4147
depth=int(depth)
4248
max_x,max_y=map(int,target.split(","))
43-
target=max_x-1j*max_y
49+
target=max_x-j*max_y
4450

4551
geological= {0:0}
4652
erosion= {0:0}
4753
forxinrange(max_x+1):
4854
geological[x]=x*16807
4955
erosion[x]= (geological[x]+depth)%20183
5056
foryinrange(max_y+1):
51-
geological[-1j*y]=y*48271
52-
erosion[-1j*y]= (geological[-1j*y]+depth)%20183
57+
geological[-j*y]=y*48271
58+
erosion[-j*y]= (geological[-j*y]+depth)%20183
5359

5460
forxinrange(1,max_x+1):
5561
foryinrange(1,max_y+1):
56-
geological[x-1j*y]= (
57-
erosion[x-1-1j*y]*erosion[x-1j* (y-1)]
62+
geological[x-j*y]= (
63+
erosion[x-1-j*y]*erosion[x-j* (y-1)]
5864
)%20183
59-
erosion[x-1j*y]= (geological[x-1j*y]+depth)%20183
65+
erosion[x-j*y]= (geological[x-j*y]+depth)%20183
6066

6167
geological[target]=0
6268
erosion[target]=0
@@ -70,65 +76,86 @@
7076
neither,climbing,torch=0,1,2
7177
rocky,wet,narrow=0,1,2
7278

73-
# Override the neighbors function
74-
defneighbors(self,vertex):
75-
north= (0,1)
76-
south= (0,-1)
77-
west= (-1,0)
78-
east= (1,0)
79-
directions_straight= [north,south,west,east]
80-
81-
neighbors= {}
82-
fordirindirections_straight:
83-
target= (vertex[0]+dir[0],vertex[1]+dir[1],vertex[2])
84-
iftargetinself.vertices:
85-
neighbors[target]=1
86-
fortoolin (neither,climbing,torch):
87-
target= (vertex[0],vertex[1],tool)
88-
iftargetinself.verticesandtool!=vertex[1]:
89-
neighbors[target]=7
90-
91-
returnneighbors
79+
allowed= {
80+
rocky: [torch,climbing],
81+
wet: [neither,climbing],
82+
narrow: [torch,neither],
83+
}
9284

9385
# Add some coordinates around the target
9486
padding=10ifcase_to_test==1else50
9587
forxinrange(max_x,max_x+padding):
9688
geological[x]=x*16807
9789
erosion[x]= (geological[x]+depth)%20183
9890
foryinrange(max_y,max_y+padding):
99-
geological[-1j*y]=y*48271
100-
erosion[-1j*y]= (geological[-1j*y]+depth)%20183
91+
geological[-j*y]=y*48271
92+
erosion[-j*y]= (geological[-j*y]+depth)%20183
10193
forxinrange(1,max_x+padding):
10294
foryinrange(1,max_y+padding):
103-
ifx-1j*yingeological:
95+
ifx-j*yingeological:
10496
continue
105-
geological[x-1j*y]= (
106-
erosion[x-1-1j*y]*erosion[x-1j* (y-1)]
97+
geological[x-j*y]= (
98+
erosion[x-1-j*y]*erosion[x-j* (y-1)]
10799
)%20183
108-
erosion[x-1j*y]= (geological[x-1j*y]+depth)%20183
100+
erosion[x-j*y]= (geological[x-j*y]+depth)%20183
109101

110102
terrain= {x:erosion[x]%3forxinerosion}
103+
111104
delerosion
112105
delgeological
113106

114-
# Then run pathfinding algo
107+
# Prepare pathfinding algorithm
108+
109+
# Override the neighbors function
110+
defneighbors(self,vertex):
111+
north=j
112+
south=-j
113+
west=-1
114+
east=1
115+
directions_straight= [north,south,west,east]
116+
117+
neighbors= {}
118+
fordirindirections_straight:
119+
target= (vertex[0]+dir,vertex[1])
120+
ifself.is_valid(target):
121+
neighbors[target]=1
122+
fortoolin (neither,climbing,torch):
123+
target= (vertex[0],tool)
124+
ifself.is_valid(target):
125+
neighbors[target]=7
126+
127+
returnneighbors
128+
129+
# Define what is a valid spot
130+
defis_valid(self,vertex):
131+
ifvertex[0].real<0orvertex[0].imag>0:
132+
returnFalse
133+
ifvertex[0].real>=max_x+paddingorvertex[0].imag<=-(max_y+padding):
134+
returnFalse
135+
ifvertex[1]inallowed[terrain[vertex[0]]]:
136+
returnTrue
137+
returnFalse
138+
139+
# Heuristics function for A* search
140+
defestimate_to_complete(self,start,target):
141+
distance=0
142+
foriinrange(len(start)-1):
143+
distance+=abs(start[i]-target[i])
144+
distance+=7ifstart[-1]!=target[-1]else0
145+
returndistance
146+
147+
# Run pathfinding algorithm
115148
pathfinding.WeightedGraph.neighbors=neighbors
116-
vertices= [
117-
(x.real,x.imag,neither)forxinterrainifterrain[x]in (wet,narrow)
118-
]
119-
vertices+= [
120-
(x.real,x.imag,climbing)forxinterrainifterrain[x]in (rocky,wet)
121-
]
122-
vertices+= [
123-
(x.real,x.imag,torch)forxinterrainifterrain[x]in (rocky,narrow)
124-
]
125-
graph=pathfinding.WeightedGraph(vertices)
126-
127-
graph.dijkstra((0,0,torch), (max_x,-max_y,torch))
128-
129-
puzzle_actual_result=graph.distance_from_start[(max_x,-max_y,torch)]
130-
131-
# 979 is too high
149+
pathfinding.WeightedGraph.is_valid=is_valid
150+
pathfinding.Graph.estimate_to_complete=estimate_to_complete
151+
152+
graph=pathfinding.WeightedGraph()
153+
154+
graph.a_star_search(
155+
(SuperComplex(0),torch), (SuperComplex(max_x-j*max_y),torch)
156+
)
157+
158+
puzzle_actual_result=graph.distance_from_start[(max_x-j*max_y,torch)]
132159

133160

134161
# -------------------------------- Outputs / results --------------------------------- #

0 commit comments

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