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

Commit54cdb62

Browse files
committed
Added days 2016-11, 2016-12 and a pathfinding library
1 parenta1bc715 commit54cdb62

File tree

3 files changed

+826
-0
lines changed

3 files changed

+826
-0
lines changed
Lines changed: 227 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,227 @@
1+
# -------------------------------- Input data -------------------------------- #
2+
importos,itertools
3+
importpathfinding
4+
5+
test_data= {}
6+
7+
test=1
8+
test_data[test]= {"input":"""""",
9+
"expected": ['Unknown','Unknown'],
10+
}
11+
12+
test+=1
13+
test_data[test]= {"input":"""""",
14+
"expected": ['Unknown','Unknown'],
15+
}
16+
17+
test='real'
18+
test_data[test]= {"input":'11112123333',
19+
"expected": ['31','Unknown'],
20+
}
21+
22+
# -------------------------------- Control program execution -------------------------------- #
23+
24+
case_to_test='real'
25+
part_to_test=2
26+
verbose_level=1
27+
28+
# -------------------------------- Initialize some variables -------------------------------- #
29+
30+
puzzle_input=test_data[case_to_test]['input']
31+
puzzle_expected_result=test_data[case_to_test]['expected'][part_to_test-1]
32+
puzzle_actual_result='Unknown'
33+
34+
35+
36+
37+
# -------------------------------- Actual code execution -------------------------------- #
38+
39+
40+
41+
ifpart_to_test==1:
42+
# -------------------------------- Graph-related functions -------------------------------- #
43+
# Re-implement the heuristic to match this graph
44+
defheuristic (self,current_node,target_node):
45+
returnsum([abs(int(target_node[i])-int(current_node[i]))foriinrange (1,len(current_node))])//2
46+
pathfinding.WeightedGraph.heuristic=heuristic
47+
48+
49+
# How to determine neighbors
50+
defneighbors (self,state):
51+
globalstates
52+
E=int(state[0])
53+
movables= [xforxinrange(1,len(state))ifstate[x]==state[0]]
54+
55+
# Connecting if we move 1 element only
56+
possible_neighbors= []
57+
formovableinmovables:
58+
ifE>1:
59+
neighbor=str(E-1)+state[1:movable]+str(int(state[movable])-1)+state[movable+1:]
60+
possible_neighbors.append(neighbor)
61+
ifE<4:
62+
neighbor=str(E+1)+state[1:movable]+str(int(state[movable])+1)+state[movable+1:]
63+
possible_neighbors.append(neighbor)
64+
65+
iflen(movables)>=2:
66+
formoved_objectsinitertools.combinations(movables,2):
67+
mov1,mov2=moved_objects
68+
# No use to bring 2 items downstairs
69+
# if E > 1:
70+
# neighbor = str(E-1) + state[1:mov1] + str(int(state[mov1])-1) + state[mov1+1:mov2] + str(int(state[mov2])-1) + state[mov2+1:]
71+
# possible_neighbors.append(neighbor)
72+
ifE<4:
73+
neighbor=str(E+1)+state[1:mov1]+str(int(state[mov1])+1)+state[mov1+1:mov2]+str(int(state[mov2])+1)+state[mov2+1:]
74+
possible_neighbors.append(neighbor)
75+
76+
return [xforxinpossible_neighborsifxinstates]
77+
78+
pathfinding.WeightedGraph.neighbors=neighbors
79+
80+
defcost(self,current_node,next_node):
81+
return1
82+
pathfinding.WeightedGraph.cost=cost
83+
84+
85+
# -------------------------------- Graph construction & execution -------------------------------- #
86+
87+
# state = (E, TG, TM, PtG, PtM, SG, SM, PrG, PrM, RG, RM)
88+
# Forbidden states: Any G + M if G for M is absent
89+
# Forbidden transitions: E changes, the rest is identical
90+
91+
states=set([''.join([str(E),str(TG),str(TM),str(PtG),str(PtM),str(SG),str(SM),str(PrG),str(PrM),str(RG),str(RM)])
92+
forEinrange(1,5)
93+
forTGinrange(1,5)
94+
forTMinrange(1,5)
95+
forPtGinrange(1,5)
96+
forPtMinrange(1,5)
97+
forSGinrange(1,5)
98+
forSMinrange(1,5)
99+
forPrGinrange(1,5)
100+
forPrMinrange(1,5)
101+
forRGinrange(1,5)
102+
forRMinrange(1,5)
103+
104+
if (TG==TMorTMnotin (TG,PtG,SG,PrG,RG))
105+
and (PtG==PtMorPtMnotin (TG,PtG,SG,PrG,RG))
106+
and (SG==SMorSMnotin (TG,PtG,SG,PrG,RG))
107+
and (PrG==PrMorPrMnotin (TG,PtG,SG,PrG,RG))
108+
and (RG==RMorRMnotin (TG,PtG,SG,PrG,RG))
109+
])
110+
111+
end='4'*11
112+
113+
print ('number of states',len(states))
114+
115+
graph=pathfinding.WeightedGraph()
116+
came_from,total_cost=graph.a_star_search(puzzle_input,end)
117+
118+
puzzle_actual_result=total_cost[end]
119+
120+
else:
121+
# -------------------------------- Graph-related functions -------------------------------- #
122+
# Part 2 was completely rewritten for performance improvements
123+
124+
defvalid_state (state):
125+
pairs= [(state[x],state[x+1])forxinrange (1,len(state),2)]
126+
generators=state[1::2]
127+
128+
forpairinpairs:
129+
ifpair[0]!=pair[1]:# Microchip is not with generator
130+
ifpair[1]ingenerators:# Microchip is with a generator
131+
returnFalse
132+
133+
returnTrue
134+
135+
defvisited_state(state):
136+
globalvisited_coded_states
137+
138+
pairs= [(state[x],state[x+1])forxinrange (1,len(state),2)]
139+
140+
coded_state= [(state[0],pair)forpairinsorted(pairs)]
141+
142+
ifcoded_stateinvisited_coded_states:
143+
returnTrue
144+
else:
145+
visited_coded_states.append(coded_state)
146+
returnFalse
147+
148+
149+
# -------------------------------- BFS implementation -------------------------------- #
150+
start=list(map(int,puzzle_input))+ [1]*4
151+
end= [4]*15
152+
153+
visited_coded_states= []
154+
frontier= [(start,0)]
155+
156+
forstatusinfrontier:
157+
state,curr_steps=status
158+
159+
# Determine potential states to go to
160+
elev_position=state[0]
161+
# The +1 ignores the elevator
162+
elements_at_level= [item+1foritem,levelinenumerate(state[1:])iflevel==elev_position]
163+
164+
movables=list(itertools.combinations(elements_at_level,2))+elements_at_level
165+
166+
ifelev_position==1:
167+
directions= [1]
168+
elifelev_position==4:
169+
directions= [-1]
170+
else:
171+
directions= [1,-1]
172+
173+
fordirectionindirections:
174+
formovableinmovables:
175+
new_state=state.copy()
176+
177+
new_floor=elev_position+direction
178+
new_state[0]=new_floor
179+
ifisinstance(movable,tuple):
180+
# No point in moving 2 items downwards
181+
ifdirection==-1:
182+
continue
183+
new_state[movable[0]]=new_floor
184+
new_state[movable[1]]=new_floor
185+
else:
186+
new_state[movable]=new_floor
187+
188+
ifvalid_state(new_state):
189+
ifvisited_state(new_state):
190+
continue
191+
else:
192+
frontier.append((new_state,curr_steps+1))
193+
194+
ifnew_state==end:
195+
puzzle_actual_result=curr_steps+1
196+
break
197+
198+
ifpuzzle_actual_result!='Unknown':
199+
break
200+
201+
ifpuzzle_actual_result!='Unknown':
202+
break
203+
204+
205+
206+
207+
208+
209+
210+
puzzle_actual_result=curr_steps+1
211+
212+
213+
214+
215+
216+
217+
218+
# -------------------------------- Outputs / results -------------------------------- #
219+
220+
ifverbose_level>=3:
221+
print ('Input : '+puzzle_input)
222+
print ('Expected result : '+str(puzzle_expected_result))
223+
print ('Actual result : '+str(puzzle_actual_result))
224+
225+
226+
227+

‎2016/12-Leonardo's Monorail.py‎

Lines changed: 96 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,96 @@
1+
# -------------------------------- Input data -------------------------------- #
2+
importos
3+
4+
test_data= {}
5+
6+
test=1
7+
test_data[test]= {"input":"""cpy 41 a
8+
inc a
9+
inc a
10+
dec a
11+
jnz a 2
12+
dec a""",
13+
"expected": ['42','Unknown'],
14+
}
15+
16+
test+=1
17+
test_data[test]= {"input":"""""",
18+
"expected": ['Unknown','Unknown'],
19+
}
20+
21+
test='real'
22+
input_file=os.path.join(os.path.dirname(__file__),'Inputs',os.path.basename(__file__).replace('.py','.txt'))
23+
test_data[test]= {"input":open(input_file,"r+").read().strip(),
24+
"expected": ['318083','9227737'],
25+
}
26+
27+
# -------------------------------- Control program execution -------------------------------- #
28+
29+
case_to_test='real'
30+
part_to_test=2
31+
verbose_level=1
32+
33+
# -------------------------------- Initialize some variables -------------------------------- #
34+
35+
puzzle_input=test_data[case_to_test]['input']
36+
puzzle_expected_result=test_data[case_to_test]['expected'][part_to_test-1]
37+
puzzle_actual_result='Unknown'
38+
39+
40+
# -------------------------------- Actual code execution -------------------------------- #
41+
registers= {'a':0,'b':0,'c':0,'d':0}
42+
ifpart_to_test==2:
43+
registers['c']=1
44+
45+
46+
instructions=puzzle_input.split('\n')
47+
i=0
48+
whileTrue:
49+
instruction=instructions[i]
50+
i+=1
51+
52+
ifinstruction[0:3]=='cpy':
53+
_,val,target=instruction.split(' ')
54+
try:
55+
registers[target]=int(val)
56+
exceptValueError:
57+
registers[target]=registers[val]
58+
59+
elifinstruction[0:3]=='inc':
60+
_,target=instruction.split(' ')
61+
registers[target]+=1
62+
elifinstruction[0:3]=='dec':
63+
_,target=instruction.split(' ')
64+
registers[target]-=1
65+
66+
elifinstruction[0:3]=='jnz':
67+
_,target,jump=instruction.split(' ')
68+
iftarget=='0':
69+
pass
70+
else:
71+
try:
72+
ifint(target):
73+
i=i+int(jump)-1# -1 to compensate for what we added before
74+
exceptValueError:
75+
ifregisters[target]!=0:
76+
i=i+int(jump)-1# -1 to compensate for what we added before
77+
78+
ifi>=len(instructions):
79+
break
80+
81+
puzzle_actual_result=registers['a']
82+
83+
84+
85+
86+
87+
# -------------------------------- Outputs / results -------------------------------- #
88+
89+
ifverbose_level>=3:
90+
print ('Input : '+puzzle_input)
91+
print ('Expected result : '+str(puzzle_expected_result))
92+
print ('Actual result : '+str(puzzle_actual_result))
93+
94+
95+
96+

0 commit comments

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