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
|
require "ext"
local map = {}
local row, col = 0,0
local function fmt_location(row, col)
return string.format("%d,%d",row,col)
end
for line in io.lines() do
row = row + 1
col = 0
for char in line:gmatch("(.)") do
col = col + 1
local locf = fmt_location(row,col)
if char == "#" then
map[locf] = true
end
end
end
local directions = {
N = {-1,0},
S = {1,0},
E = {0,1},
W = {0,-1},
NE = {-1,1},
NW = {-1,-1},
SE = {1,1},
SW = {1,-1}
}
local dir_order = {
{"N","NE","NW"},
{"S","SE","SW"},
{"W","NW","SW"},
{"E","NE","SE"}
}
print(map)
local function parse_location(location)
local trow,tcol = location:match("([%d-]+),([%d-]+)")
return tonumber(trow), tonumber(tcol)
end
local function round(map, order_dir)
--print("Directions:",order_dir)
--first half, propose
local propositions = {}
for location, elf in pairs(map) do
local elf_nearby = false
local trow, tcol = parse_location(location)
for _, dir in pairs(directions) do
local nrow, ncol = trow + dir[1], tcol + dir[2]
local nloc = fmt_location(nrow,ncol)
if map[nloc] then
elf_nearby = true
break
end
end
if not elf_nearby then
propositions[location] = {location}
goto nextelf
end
assert(elf_nearby)
for _,dset in ipairs(dir_order) do
local dir_empty = true
for _,d in ipairs(dset) do
local dir = directions[d]
local nrow, ncol = trow + dir[1], tcol + dir[2]
local nloc = fmt_location(nrow,ncol)
if map[nloc] then
dir_empty = false
break
end
end
if dir_empty then
local dir = directions[dset[1]]
local nrow, ncol = trow + dir[1], tcol + dir[2]
local nloc = fmt_location(nrow,ncol)
if not propositions[nloc] then
propositions[nloc] = {location}
else
table.insert(propositions[nloc],location)
end
goto nextelf
end
end
-- no new location proposed, sit tight
propositions[location] = {location}
::nextelf::
end
--print("Propositions:",propositions)
--second half, move if we were the only ones that want to go there
local any_moved = false
for location, elftbl in pairs(propositions) do
if #elftbl == 1 and elftbl[1] ~= location then
any_moved = true
end
end
if not any_moved then
os.exit(0)
end
local newmap = {}
for location, elftbl in pairs(propositions) do
if #elftbl == 1 then
newmap[location] = true
else
for _,oloc in pairs(elftbl) do
newmap[oloc] = true
end
end
end
return newmap
end
local function aabb(map)
local minrow,mincol,maxrow,maxcol= math.huge, math.huge, -math.huge, -math.huge
for location,_ in pairs(map) do
local row,col = parse_location(location)
minrow = math.min(minrow,row)
maxrow = math.max(maxrow,row)
mincol = math.min(mincol,col)
maxcol = math.max(maxcol,col)
end
return minrow, mincol, maxrow, maxcol
end
local function print_puzzle(map)
local minrow, mincol, maxrow, maxcol = aabb(map)
io.write(" ")
for col = mincol - 1, maxcol + 1 do
io.write(col)
end
io.write("\n")
for row = minrow - 1, maxrow + 1 do
io.write(string.format("%3d|",row))
for col = mincol - 1,maxcol + 1 do
local loc = fmt_location(row,col)
if map[loc] then
io.write("#")
else
io.write(".")
end
end
io.write("\n")
end
end
local function emptyaabb(map)
local minrow, mincol, maxrow, maxcol = aabb(map)
local count = 0
for row = minrow, maxrow do
for col = mincol ,maxcol do
local loc = fmt_location(row,col)
if not map[loc] then
count = count + 1
end
end
end
return count
end
print_puzzle(map)
print("==========")
local i = 0
while true do
i = i + 1
print(i)
map = round(map,dir_order)
table.insert(dir_order,table.remove(dir_order,1))
--print_puzzle(map)
--print("==========")
end
print(emptyaabb(map))
|
