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
|
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,flood)
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("* ")
end
else
if flood and flood[row] and flood[row][col] then
io.write(string.format("%-2d",flood[row][col]))
else
io.write(" ")
end
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] == nil or
map[row][col] == nil or
map[row][col].t ~= tiles.wall)
)
--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 flood = {}
for row = 1,h do
flood[row] = {}
end
flood[1][2] = 0
local min = 0
while flood[h][w-1] == nil do
min = min + 1
print("Min",min)
local nmap = mapat[min-1]
local toins = {}
--[[
print("Before flooding 1:")
print_puzzle(nmap,flood)
]]
--flood outward
for rn,row in pairs(flood) do
for cn,col in pairs(row) do
if flood[rn][cn] then
for name, direction in pairs(directions) do
--print("Flooding",rn,cn,name)
local trow = rn + direction[1]
local tcol = cn + direction[2]
if could_move(nmap,trow,tcol) and flood[trow][tcol] == nil then
table.insert(toins,{trow,tcol})
end
end
end
end
end
for _,v in pairs(toins) do
flood[v[1]][v[2]] = min
end
--[[
print("After flooding 1:")
print_puzzle(nmap,flood)
]]
nmap = mapat[min]
--clean up where blizzards pass
for rn,row in pairs(nmap) do
for cn, col in pairs(row) do
flood[rn][cn] = nil
end
end
print("After cleaning:")
print_puzzle(nmap,flood)
end
print(flood[h][w-1])
|
