Advent of Code 2016 Day 13 (Lua)

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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s