Advent of Lua

A few notes to self, in case I'm looking for previous stuff to copypaste in some future december or something...

Maybe this mostly just "Lua stuff I think is fun" and not necessarily always that AoC related? Anyway I like Lua, it's smol. When I AoC with Lua I usually make pretty self-contained programs that only depend on the plain and regular Lua implementation and its standard library.

Here's some example code. It does the file stuff that usually needs to be done and the "works in the browser as well" thing.

If not line by line: Possibly f:read("*all") instead of f:lines().

Here's foldl because because:

function foldl(f, acc, list)
  for _, v in ipairs(list) do acc = f(acc, v) end
  return acc
end

Strings, matching, ...

Cataphatically matching on and grabbing what I want is often preferable to apophatically splitting on what I don't want.

If I e.g. have a line of input like "123: 54 34 12" and I need to do one thing with the number before the : and one thing with the rest of the numbers. I typically ignore the : and just gmatch to get the numbers:

local line = "123: 25 34 12"

local nums = line:gmatch("%d+")
local first = tonumber(nums())
local rest = {}
for n in nums do table.insert(rest, tonumber(n)) end

print(foldl(function(a, b) return a + b end, first, rest))
print(foldl(function(a, b) return a - b end, first, rest))

If there had been a varying number of numbers before the : I'd probably match and grab the before and after pieces before doing work on those:

local line = "123 456: 25 34 12"
local before, after = line:match("(.*):(.*)")
print("before:", '"' .. before .. '"')
print("after:", '"' .. after .. '"')

(The match function and the iterator function you get from gmatch return multiple values when patterns with multiple captures match something. It's nice.)

string.find, it returns start position and stop index if it finds. Sometimes I wanna keep finding from the stop index + 1. The values returned for empty capture groups are also positions, so I guess I don't really need find? Certainly not if I'm mostly interested in the stop + 1 thing:

local text = "beep boop pling bap"

local _, stop, found = text:find("(p%a*g)")
print(found, stop + 1)

local found, stop = text:match("(p%a*g)()")
print(found, stop)

This area of the Lua manual is sometimes handy.

2D maps and vectors

If I want to e.g. use x,y-positions as keys in a table, for each unique x,y-value there should be only one table. "Constructing" the same position twice gives me two references to the same table, and not two tables with equal x and y values:

vecs = setmetatable({}, { __mode = "v" })
Vec = {}

function vec(x, y)
  local key = x .. "," .. y
  local found = vecs[key]
  if found then return found end
  local v = setmetatable({ x = x, y = y}, Vec)
  vecs[key] = v
  return v
end

See also: Programming in Lua: 17.1 – Memoize Functions.

The "weak" stuff (__mode = "v") is not usually important particularly important for AoC stuff.

I typically use vectors for positions and also for directions. Som stuf:

function Vec.__add(a, b) return vec(a.x + b.x, a.y + b.y) end
function Vec.__tostring(a) return a.x .. "," .. a.y end

N, E, S, W = vec(0, -1), vec(1, 0), vec(0, 1), vec(-1, 0)
N.name = "N" ; E.name = "E" ; S.name = "S" ; W.name = "W"
dirs = { N, E, S, W }

N.right = E ; E.right = S ; S.right = W ; W.right = N
N.left = W ; W.left = S ; S.left = E ; E.left = N


NW, NE, SE, SW = N + W, N + E, S + E, S + W
NW.name = "NW" ; NE.name = "NE" ; SE.name = "SE" ; SW.name = "SW"
dirs = { NW, N, NE, E, SE, S, SW, W }

And then things like these might happen:

function mappy(lines)
  local map = {}
  local w = 1
  local y = 0
  for line in lines do
    y = y + 1
    local x = 0
    for c in line:gmatch(".") do
      x = x + 1
      map[vec(x, y)] = c
    end
    w = math.max(w, x)
  end
  map.size = vec(w, y)
  return map
end

function printmap(map)
  print(map.size)
  for y = 1, map.size.y do
    for x = 1, map.size.x do
      io.write(map[vec(x, y)] or " ")
    end
    io.write("\n")
  end
end
local example = [[
+--------+
|        |
+--------+
]]

local map = mappy(example:gmatch("[^\n]+"))
print(map[vec(1,1)], map[vec(1,2)], map[vec(2,1)])
printmap(map)

Data structures

{}. That's it, that's the data structures.

Sets are tables where we only care about the keys (and just set the values to true or something).

You can use the same table as a list and a dictionary and a set if you'd like. Unless you can't because the keys are clashing or something. Or maybe don't want. But like. Some times.

Popping a thing from a set

There's a next function:

local table = { x = 1, y = 3, z = 5 }
print(next(table))

You can use it to get a first key and value from a table, and also a next key and value given a previous key:

local t = { x = 1, y = 3, z = 5 }
local k, v = next(t)
while k do
  print(k, v)
  k, v = next(t, k)
end

(I think that when we use the pairs function to get an iterator, next is used under the hood.)

Sometimes there's stuff like: I have this set of "candidates" and I wanna pick one and do something with it andalso the doing generates more candidates and I don't wanna pick the same thing multiple times. next is useful. Since it's a set I'll ignore the second return value from next and just use the key:

local set = { [1] = true, [3] = true, [5] = true }
local closed = {}

local function add(n)
  if n < 1000 and not closed[n] then set[n] = true end
end

local n = next(set)
while n do
  set[n] = nil
  closed[n] = true
  print(n)
  add(n + n + n)
  add(n * n)
  n = next(set)
end

Memo

Helper function if I need to do the cachy memoization thing with more than one type of data structure. I typically want to pass in a "key" function and a constructor function:

function memo(key, new)
  local all = setmetatable({}, { __mode = "v" })
  return function(...)
    local k = key(...)
    local found = all[k]
    if found then return found end
    local v = new(...)
    all[k] = v
    return v
  end
end

Person = {}
person = memo(
  function(pos, dir) return tostring(pos) .. " " .. dir.name end,
  function(pos, dir) return setmetatable({ pos = pos, dir = dir }, Person) end)

Person.__index = Person
function Person.__tostring(p) return tostring(p.pos) .. " " .. p.dir.name end
function Person.step(p) return person(p.pos + p.dir, p.dir) end
local a, b = person(vec(3, 4), N), person(vec(3, 5), N)
print(a, b, b:step())
print("", a == b, a == b:step())

print()

local c = person(vec(3, 3), S)
print(a, c, c:step())
print("", a == c, a == c:step())
print(a.pos == c:step().pos)

Metastuff

Metatables and Metamethods in the manual`.

Most of the metamethods enables syntax like the +/__add above:

print(vec(5, 5) + vec(2, 4))
Dog = {}
function dog(name)
  return setmetatable({ name = name }, Dog)
end
function Dog.__tostring(d) return "a dog called " .. d.name  end
function Dog.__add(a, b) return tostring(a) .. " PLUS " .. tostring(b) end
function Dog.bark(d) print(d.name .. ": Woof") end
deg = dog("Tähti")
print(deg)

Note that the first argument of a binary operation like __add might not be the one with the metatable with that __add function. While the first operand of the + expression takes precedence, the _add of the second operand can get called:

print(deg + "a string")
print("a string" + deg)

Related: Greater than (or equal to) expressions are rewritten to less than (or equal to) expressions before things get to __lt (or __le).

"Methods"

Also the metatable is generally only reached through the metamethods and not more directly. If I want something kind of like "methods defined by a class" then I probably wanna go through __index. This works:

Dog.__index = Dog
deg:bark()

This doesn't:

Dog.__index = nil
deg:bark()

For functionmethodstuff, some things are pretty equivalent:

Dog.__index = Dog

function Dog.bark(d) print(d.name .. ": Woof") end
deg:bark()
deg.bark(deg)

function Dog:bark() print(self.name .. ": Woof") end
deg:bark()
deg.bark(deg)

Dog.bark = function(d) print(d.name .. ": Woof") end
deg:bark()
deg.bark(deg)

Default values

__index is also sometimes nice for stuff like initializing default values in a table when needed:

Foo = {}
function foo() return setmetatable({}, Foo) end
function Foo.__index(t, k)
  local res = foo()
  t[k] = res
  return res
end
local foo = foo()
foo.bar = "blep"
foo.beep.boop = "bap"
print(foo.bar)
print(foo.beep.boop)

(__newindex(t, k, v) is also a thing. Haven't used it much. I'm a bit uncertain about it and the "key must not already be present in table" condition.)

Writing over, not overwriting

I usually use fairly pure and functional data structures for smol things like vectors, but not for larger things like 2D maps. The immutable stuff is easiest to deal with when trying different alternatives and backtracking and stuff like that: I have a value. I try one thing. I try another thing. The value didn't change in-between. (Also, if I'm doing the cachy memoization stuff where I'm always using the same table for the same x,y-value, things will very break if I start changing the x,y-values of vectors after constructing them.)

With mutable stuff things are more awkward and I might need to "undo" changes instead. For small changes I can probably just do that kind of ad hoc. But if I wanna do a bunch of changes and then be able to throw those changes away, __index might be useful: I can keep an original table unchanged while "inheriting" its values through __index.

When I'm using the over table below, writes modify over and reads read from original if the key is not present in over:

local example = [[
+--------+
|        |
+--------+
]]

local original = mappy(example:gmatch("[^\n]+"))
print("original, before:")
printmap(original)

local over = setmetatable({}, { __index = original })
print("over, before:")
printmap(over)

over[vec(2, 2)] = "#"
print("\nover, after:")
printmap(over)
print("original, after:")
printmap(original)

if/else, and/or

if-then-else is statement stuff. For expression stuff, and and or is nice.

for n = 1, 100 do
print(
  (n % 3 == 0 and n % 5 == 0 and "fizzbuzz")
  or (n % 3 == 0 and "fizz")
  or (n % 5 == 0 and "buzz")
  or n)
end

Oh kay.