1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
require "ext"
local directions = {
right = {0,1},
down = {1,0},
left = {0,-1},
up = {-1,0},
wait = {0,0},
}
local tiles = {
wall = {rep="#"},
lbliz = {rep="<",move=directions.left},
rbliz = {rep=">",move=directions.right},
ubliz = {rep="^",move=directions.up},
dbliz = {rep="v",move=directions.down},
empty = {rep="."}
}
local map = {}
local row,col = 0,0
local start,finish
local function place(map,row,col,ent)
map[row] = map[row] or {}
map[row][col] = map[row][col] or {}
table.insert(map[row][col],ent)
end
for line in io.lines() do
map[#map+1] = {}
row = row + 1
col = 0
for char in line:gmatch("(.)") do
col = col + 1
if char == "." then
if row == 1 then
start = col
else
finish = col
end
end
for name,tile in pairs(tiles) do
if char == tile.rep and name ~= "empty" then
place(map,row,col,{r=row,c=col,t=tile})
break
end
end
end
end
local w,h = col,row
local function print_puzzle(map)
for row = 1,h do
for col = 1,w do
if map[row] and map[row][col] then
local elist = map[row][col]
if #elist == 1 then
io.write(elist[1].t.rep)
else
io.write(#elist)
end
else
io.write(".")
end
end
io.write("\n")
end
end
local h,w = #map, #map[1]
local min_walk = math.abs(finish - start) + h
print_puzzle(map)
local function step_map(map)
local newmap = {}
for row = 1,h do
for col = 1,w do
if map[row] and map[row][col] then
for _, ent in pairs(map[row][col]) do
if ent.t.move then
local dir = ent.t.move
ent.r = ent.r + dir[1]
ent.c = ent.c + dir[2]
--loop
if ent.r == 1 then
ent.r = h-1
elseif ent.r == h then
ent.r = 2
elseif ent.c == 1 then
ent.c = w-1
elseif ent.c == w then
ent.c = 2
end
place(newmap,ent.r,ent.c,ent)
else
place(newmap,ent.r,ent.c,ent)
end
end
end
end
end
return newmap
end
local function could_move(map,row,col)
local ret = (
row >= 1 and
col > 1 and
row <= h and
col < w and
map[row] and
map[row][col] == nil
)
--print(ret)
return ret
end
--map doesn't change, no matter what we do, we can store the blizzard simulation
local map_mem, mapat = {}, {[0] = map}
setmetatable(mapat,{__index=function(self,key)
if map_mem[key] then return map_mem[key] end
map_mem[key] = step_map(mapat[key-1])
return map_mem[key]
end})
local state = {
location = {1,start},
minute = 0,
speculative_goal = min_walk
}
local function copy_state(state)
return {
location = {state.location[1],state.location[2]},
minute = state.minute,
speculative_goal = state.speculative_goal
}
end
local spec_tbl = {
[directions.right] = -1,
[directions.down] = -1,
[directions.left] = 2,
[directions.up] = 2,
[directions.wait] = 0
}
local branches = {state}
local min_path = 147
local nbranches = 0
while #branches > 0 do
--print(#branches)
local tbranch = table.remove(branches)
nbranches = nbranches + 1
if nbranches % 100000 == 0 then
print("Analyzed",nbranches,"branches",#branches,"active")
end
if tbranch.minute > min_path then
goto nextbranch
end
if tbranch.speculative_goal > min_path then
goto nextbranch
end
local nloc = tbranch.location
if nloc[1] == h and nloc[2] == finish then
print("Found a working branch:",tbranch)
print("Branches remaining:",#branches)
if tbranch.minute < min_path then
min_path = tbranch.minute
end
goto nextbranch
end
local ctime = tbranch.minute
local nmap = mapat[ctime + 1]
--print_puzzle(nmap)
for name, direction in pairs(directions) do
local nrow, ncol = nloc[1] + direction[1], nloc[2] + direction[2]
if could_move(nmap,nrow,ncol) then
if nrow == h then
assert(ncol == finish)
end
local sc = copy_state(tbranch)
sc.location = {nrow,ncol}
sc.speculative_goal = sc.speculative_goal + spec_tbl[direction]
if sc.speculative_goal < min_path and sc.minute < min_path then
sc.minute = sc.minute + 1
table.insert(branches,sc)
end
end
end
--[[
--It's actually faster if we don't do this, and all states fit into one memory page
--Once in a while, sort the branhces to prioritize promising paths
if nbranches % 100000 == 0 then
table.sort(branches,function(a,b)
return (a.minute + a.speculative_goal) > (b.minute + b.speculative_goal)
end)
end
]]
::nextbranch::
end
print(nbranches)
print("Out of branches")
print(min_path)
|
