Advent of Code 2016 Day 12 (C#)
Advent of Code 2016 Day 11 (Groovy)
Advent of Code 2016 Day 10 (OcaML)
Advent of Code 2016 Day 9 (Factor)
Advent of Code 2016 Day 8 (c++)
Advent of Code 2016 Day 7 (Javascript)
Advent of Code 2016 – Day 6 (Julia)
Advent of Code 2016 – Day 5( Java 8)
Advent of Code 2016 – Day 4 (Perl 6)
Advent of Code 2016 – Day 3 (Clojure)
Advent of Code – Day 2 (Python 3)
Advent Of Code 2016 – Day 1(Haskell)
Day 13
Start: 12/18/2016
Finish 12/19/2016
Language: Lua
SPOILER ALERT: If you have any inkling, any whatsoever, to work on the Advent of Code…. DO NOT READ THIS BLOG POST. DO NOT LOOK AT MY GITHUB PROJECT. It is no fun if you’re not solving it yourself, and you’ll feel so much better about yourself if you can figure it out without looking up an answer. This blog post is not to give away the answer, but instead, is there for people to learn from.
As always, the following code is in my GitHub: https://github.com/pviafore/AdventOfCode2016
The Challenge
This challenge was about finding your way through a maze given open spaces and walls. You only knew the walls based on a mathematical formula, and you had to take the optimal path to a destination.
This sounds like a job for my favorite algorithm -> the A* search algorithm. I could use the number of steps I’ve taken so far in addition to the manhattan distance to my target (which works because I could only move horizontally and diagonally) to look for the shortest path to my destination.
I chose Lua for this problem. At an ADTRAN hackathon I had put Lua into one of our embedded C products, so I had some familiarity. Let’s see how I did.
Part 1
Not very proud of my main loop, but I’m trying to paste my raw original code as soon as I have it done. I should have extracted three or four methods, but I didn’t, so here it is.
favorite_number = 1364
function isOdd(num)
return num % 2 == 1
end
function get_number_of_bits(num, accum)
if num == 0 then return accum end
if isOdd(num) then return get_number_of_bits(bit32.rshift(num,1), accum+1) end
return get_number_of_bits(bit32.rshift(num,1), accum)
end
function compute_is_wall(x,y)
if x < 0 or y < 0 then return true end
local num = x*x + 3*x + 2*x*y + y +y*y
num = num + favorite_number
return isOdd(get_number_of_bits(num, 0))
end
function filter(collection, f)
local new = {}
for k,v in pairs(collection) do
if f(v) then table.insert(new, v) end
end
return new
end
eqmt = {__eq = function (k1, k2) return k1[1] == k2[1] and k1[2] == k2[2] end }
gridmeta = { __index = function(t,k)
for key,val in pairs(t) do
if key == k then return t[key] end
end
t[k] = compute_is_wall(k[1], k[2])
return t[k]
end }
grid = {}
setmetatable(grid, gridmeta)
seen = {}
target = {31,39}
setmetatable(target, eqmt)
function get_manhattan_distance(x,y)
return math.abs(target[1] - x) + math.abs(target[2] - y)
end
function is_seen(pos)
for k,v in pairs(seen) do
if k == pos then return true end
end
return false
end
function get_open_spaces(x,y,steps)
local options = { {x+1, y, steps+1}, {x-1, y, steps+1}, {x, y+1, steps+1}, {x, y-1, steps+1}}
setmetatable(options[1], eqmt)
setmetatable(options[2], eqmt)
setmetatable(options[3], eqmt)
setmetatable(options[4], eqmt)
return filter(options, (function(v) return not grid[v] and not is_seen(v); end))
end
function get_best_option(options)
best = {1,1, 100000000}
for k,v in pairs(options) do
if v[3] + get_manhattan_distance(v[1], v[2]) < best[3] + get_manhattan_distance(best[1], best[2]) then
best = v
end
end
return best
end
function main()
options = {{1,1, 0}}
setmetatable(options[1], eqmt)
while true do
position = get_best_option(options)
if(not is_seen(position)) then
seen[position] = true
end
for k,v in pairs(options) do
if options[k] == position then
options[k] = nil
break
end
end
spaces = get_open_spaces(position[1], position[2], position[3])
for _,space in pairs(spaces) do
if(space == target) then
return space[3]
end
table.insert(options, space)
end
end
end
print(main())
The code to compute is a wall is pretty straight-forward:
function isOdd(num)
return num % 2 == 1
end
function get_number_of_bits(num, accum)
if num == 0 then return accum end
if isOdd(num) then return get_number_of_bits(bit32.rshift(num,1), accum+1) end
return get_number_of_bits(bit32.rshift(num,1), accum)
end
function compute_is_wall(x,y)
if x < 0 or y < 0 then return true end
local num = x*x + 3*x + 2*x*y + y +y*y
num = num + favorite_number
return isOdd(get_number_of_bits(num, 0))
end
The cool thing about Lua is metatables. Since a table is the only data structure in Lua, metatables are what gives Lua a lot of power. I used metatables to compute if the space was a wall or not, and then cache it for later uses (so that I wasn’t doing a bunch of multiplications again and again and again)
gridmeta = { __index = function(t,k)
for key,val in pairs(t) do
if key == k then return t[key] end
end
t[k] = compute_is_wall(k[1], k[2])
return t[k]
end }
grid = {}
setmetatable(grid, gridmeta)
One thing that bit me was the fact that tables aren’t equal just because there keys and values are equal. So I had to define a equality metatable (eqmt) and use it wherever I was representing an X,Y coordinate. I took a long time on this, as it slowed down tracking which I’ve seen last, as well as caching my wall calculations.
eqmt = {__eq = function (k1, k2) return k1[1] == k2[1] and k1[2] == k2[2] end }
For each position I evaluate, I need to figure out what the next open spaces are. I look in the four cardinal directions (making sure that all my tables can be checked for equality) and then run over a custom filter function to make sure its not a wall and it hasn’t been seen already.
function get_open_spaces(x,y,steps)
local options = { {x+1, y, steps+1}, {x-1, y, steps+1}, {x, y+1, steps+1}, {x, y-1, steps+1}}
setmetatable(options[1], eqmt)
setmetatable(options[2], eqmt)
setmetatable(options[3], eqmt)
setmetatable(options[4], eqmt)
return filter(options, (function(v) return not grid[v] and not is_seen(v); end))
end
For the main loop, I run my heuristic to find my best option, figure out my next moves from there, and add it to the option list.
function get_best_option(options)
best = {1,1, 100000000}
for k,v in pairs(options) do
if v[3] + get_manhattan_distance(v[1], v[2]) < best[3] + get_manhattan_distance(best[1], best[2]) then
best = v
end
end
return best
end
function main()
options = {{1,1, 0}}
setmetatable(options[1], eqmt)
while true do
position = get_best_option(options)
if(not is_seen(position)) then
seen[position] = true
end
for k,v in pairs(options) do
if options[k] == position then
options[k] = nil
break
end
end
spaces = get_open_spaces(position[1], position[2], position[3])
for _,space in pairs(spaces) do
if(space == target) then
return space[3]
end
table.insert(options, space)
end
end
end
This ran blazing fast, and it made me think that if I were to get equality on tables right the first time around, a Breadth First Search might have been sufficient.
Part 2
The next part of the code required that I find all unique coordinates within 50 steps. Here a breadth first search was easy, and I just kept a count of positions I had not seen before
count = 0
function main()
options = {{1,1, 0}}
setmetatable(options[1], eqmt)
stopLooping = false
while not stopLooping do
position = options[1]
if(not is_seen(position)) then
count = count+1
seen[position] = true
end
table.remove(options, 1)
if(position[3] <= 49) then
spaces = get_open_spaces(position[1], position[2], position[3])
for _,space in pairs(spaces) do
if(space == target) then
return space[3]
end
table.insert(options, space)
end
end
stopLooping = (#options == 0)
end
end
Wrap-up
It took me a little longer than it should have, as the aforementioned Lua table equality metamethod was missing for a while, which slowed me down. But once I figured that out, I was done with both part 1 and part 2 in an hour.
My final grade for this is a solid B. I got to use metatables and metamethods, and I always love writing an A* search, but I still had hindrances along the way.
For Day 14, looks like I’m back to calculating MD5 hashes, and I’m going to try out Go.
Pat Viafore 
8 thoughts on “Advent of Code 2016 Day 13 (Lua)”