12 Lua

#!/usr/bin/lua

-- parse file into a list of strings
function lines_from(file)
    local lines = {}
    for line in io.lines(file) do
        -- Lua table magic
        lines[#lines + 1] = line
    end
    return lines
end


-- breadth-first search between start and goal
local function bfs(graph, start, goal)
    -- we need to remember already visited nodes
    local visited = {}
    -- we will remember the "depth" of the nodes
    visited[start] = 0
    -- BFS uses queue (first in first out)
    local queue = {start}
    -- while we have something to process
    while #queue do
        -- pop item from queue and
        local node = table.remove(queue, 1)
        -- explore its neighbours
        for n, _ in pairs(graph[node]) do
            -- a new node, remember it and its depth
            if not visited[n] then
                table.insert(queue, n)
                visited[n] = visited[node] + 1
            end
            -- we found the goal, report it and finish
            if node == goal then
                print("Goal:", visited[node])
                return node
            end
        end
    end
    -- in the case there is no path start<->goal
    return false
end


-- convert possible characters to ASCII values
local function c2i(char)
    local c = char
    if char == 'S' then
        c = 'a'
    elseif char == 'E' then
        c = 'z'
    end
    return string.byte(c)
end


-- process lines with characters and build adjacency graph
local function build_graph(lines)
    local graph = {}
    local start = nil
    local goal = nil
    -- process rows from the input file
    for i, row in pairs(lines) do
        -- process columns
        for j = 1, #row do
            -- node name = concatenation of its coordinates
            local node = string.format("%d-%d", i, j)
            -- char at position i, j
            local c = row:sub(j, j)
            -- list of adjacent nodes
            graph[node] = {}
            -- get ASCII value so we can check altitude
            local sb = c2i(c)
            -- treat special symbols in input files
            if c == 'S' then
                start = node
            elseif c == 'E' then
                goal = node
            end
            -- the adjacent node for i-j
            local node2 = ""
            -- node above
            if i > 1 then
                up = c2i(lines[i-1]:sub(j, j))
                node2 = string.format("%d-%d", i-1, j)
                -- altitude must be max +1
                if up - sb < 2 then
                    -- the value on the right is not important
                    graph[node][node2] = 1
                end
            end
            -- node below
            if i < #lines then
                down = c2i(lines[i+1]:sub(j, j))
                node2 = string.format("%d-%d", i+1, j)
                if down - sb < 2 then
                    graph[node][node2] = 1
                end
            end
            -- node on the left
            if j > 1 then
                left = c2i(lines[i]:sub(j-1, j-1))
                node2 = string.format("%d-%d", i, j-1)
                if left - sb < 2 then
                    graph[node][node2] = 1
                end
            end
            -- on the right
            if j < #row then
                right = c2i(lines[i]:sub(j+1, j+1))
                node2 = string.format("%d-%d", i, j+1)
                if right - sb < 2 then
                    graph[node][node2] = 1
                end
            end
        end
    end
    -- return the built graph and the two significant nodes
    return graph, start, goal
end


-- we have everything ready to glue together
local filename = "12.input"
local lines = lines_from(filename)
local graph, start, goal = build_graph(lines)
bfs(graph, start, goal)

#!/usr/bin/lua

-- parse file into a list of strings
function lines_from(file)
    local lines = {}
    for line in io.lines(file) do
        -- Lua table magic
        lines[#lines + 1] = line
    end
    return lines
end


-- breadth-first search between start and goal
local function bfs(graph, start, goal)
    local visited = {}
    visited[start] = 0
    local queue = {}
    table.insert(queue, start)
    while #queue do
        local node = table.remove(queue, 1)
        --print("NODE", node, #queue)
        for n, _ in pairs(graph[node]) do
            if visited[n] == nil then
                table.insert(queue, n)
                --print("  APP", n, visited[node] + 1)
                visited[n] = visited[node] + 1
            end
        end
        if #queue == 0 then
            break
        end
        if node == goal then
            return visited[node]
        end
    end
    return math.huge
end


local function c2i(char)
    local c = char
    if char == 'S' then
        c = 'a'
    elseif char == 'E' then
        c = 'z'
    end
    -- normalize from ASCII to integers
    return string.byte(c) - 96
end


local function build_graph(lines)
    -- store original altitudes for each node
    local graphc = {}
    local graph = {}
    local start = nil
    local goal = nil
    for i, row in pairs(lines) do
        for j = 1, #row do
            local node = string.format("%d-%d", i, j)
            local c = row:sub(j, j)
            graph[node] = {}
            local sb = c2i(c)
            graphc[node] = sb
            if c == 'S' then
                start = node
            elseif c == 'E' then
                goal = node
            end
            local node2 = ""
            if i > 1 then
                up = c2i(lines[i-1]:sub(j, j))
                node2 = string.format("%d-%d", i-1, j)
                if up - sb < 2 then
                    graph[node][node2] = 1
                end
            end
            if i < #lines then
                down = c2i(lines[i+1]:sub(j, j))
                node2 = string.format("%d-%d", i+1, j)
                if down - sb < 2 then
                    graph[node][node2] = 1
                end
            end
            if j > 1 then
                left = c2i(lines[i]:sub(j-1, j-1))
                node2 = string.format("%d-%d", i, j-1)
                if left - sb < 2 then
                    graph[node][node2] = 1
                end
            end
            if j < #row then
                right = c2i(lines[i]:sub(j+1, j+1))
                node2 = string.format("%d-%d", i, j+1)
                if right - sb < 2 then
                    graph[node][node2] = 1
                end
            end
        end
    end
    return graph, graphc, start, goal
end


local filename = "12.input"
local lines = lines_from(filename)
local graph, graphc, start, goal = build_graph(lines)
-- we need to find the minimum distance from any lowest altitude
local mind = math.huge

-- for all positions at the lowest altitude, do BFS
for k, v in pairs(graphc) do
    if v == 1 then
        distance = bfs(graph, k, goal)
        mind = math.min(mind, distance)
    end
end

print("Shortest distance:", mind)