Module:User:Cscott/Advent Of Code 2023/Day 8 Explained

return (functionlocal builders = local function register(name, f) builders[name] = fendregister('llpeg', function return require end)

register('day8', function(myrequire)--DAY 8 --local l = myrequire('llpeg')--local inspect = require 'inspect'

--PARSING --

local SKIP = l.P" " ^ 0local nl = l.P"\n"function tok(s) return l.P(s) * SKIP end

function record(graph, name, node) node.name = name graph[name] = node if graph._nodes

nil then graph._nodes = end table.insert(graph._nodes, name) return graphend

local patt = l.P

function parse(source) --print(inspect(source)) local ast, errlabel, pos = patt:match(source) if not ast then local lineno, colno, line = lpegrex.calcline(source, pos) local colhelp = string.rep(' ', colno-1)..'^' error('syntax error: '..lineno..':'..colno..': '..errlabel.. '\n'..line..'\n'..colhelp) end --print('Parsed with success!') --print(inspect(ast)) ast.nodes = ast.graph._nodes ast.graph._nodes = nil return astend

--PART 1 --

function part1(source) local input = parse(source) local steps = 0 local location = "AAA" local i = 1 while location ~= "ZZZ" do steps = steps + 1 local dir = input.instrs[i] location = input.graph[location][dir] i = i + 1 if i > #input.instrs then i = 1 end end return stepsend

--Part 2 --

function find_cycle(input, location) local start = location local stops = local steps = 0 local i = 1 local seen = local path = repeat seen[location .. "-" .. i] = steps table.insert(path, location) local node = input.graph[location] if node.stop then table.insert(stops, steps) end local dir = input.instrs[i] --table.insert(path, dir) location = node[dir] steps = steps + 1 i = i + 1 if i > #input.instrs then i = 1 end until seen[location.."-"..i] ~= nil table.insert(path,location)

-- after 'inital' steps we start the cycle local initial = seen[location.."-"..i] -- after 'initial + n*cyclelength' steps we are at the same place local cyclelength = steps - initial -- path[s+1] is where we are at after step `s` (silly 1-based language) assert(path[1+initial]

path[1+initial+cyclelength]) -- subtract the initial portion from the stops -- after 'n*cyclelength + stop' steps we are at a stop; note that the -- 'initial' portion is already included in the 'stop' amount assert(string.sub(path[1+stops[1]], -1)

"Z") return cyclelength, stopsend

function gcd(a,b) -- good ol' euclid while a ~= b do if a > b then a = a - b else b = b - a end end return aend

function lcm(nums) local partial = for i=1,#nums do partial[i] = nums[i] end local prod = 1 for i=1,#nums do -- remove common factors of i from the rest of the list for j=i+1,#nums do partial[j] = math.floor(partial[j] / gcd(partial[i], partial[j])) end prod = prod * partial[i] end return prodend

function part2(source) local input = parse(source) -- post process! local location = for _,name in ipairs(input.nodes) do local node = input.graph[name] local lastchar = string.sub(name, -1) if lastchar

"A" then node.start = true table.insert(location, name) -- collect starting locations elseif lastchar

"Z" then node.stop = true end end -- print(inspect(input)) -- find cycles for each starting location local nums = for i=1,#location do local cyclelen,stops = find_cycle(input, location[i]) -- luckily there's only one stop per cycle! assert(#stops

1) -- not guaranteed! -- luckily the stop position is exactly the same as the cyclelength assert(cyclelen

stops[1]) -- not guaranteed! -- solve simultaneous equations: -- a*cycle1 + stop1 = b*cycle2 + stop2 = c*cycle3 + stop3 = ... -- because we're so lucky, this is just -- a*cycle1 = b*cycle2 = c*cycle3 = .. -- which is just the least common multiple of cycle1..etc -- if we were *really* lucky these would all be primes, but alas. --print(cyclelen,inspect(stops)) table.insert(nums, cyclelen) end return lcm(nums)end

-- CLI version----

return

end)

local modules = modules['table'] = require('table')modules['string'] = require('string')modules['strict'] = local function myrequire(name) if modules[name]