return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('llpeg.lpegrex', function() return require [[Module:User:Cscott/lpegrex]] end)
register('day4', function(myrequire)
--[[ DAY 4 ]]--
local lpegrex = myrequire('llpeg.lpegrex')
--[[ PARSING ]]--
local patt = lpegrex.compile([[
Lines <-- {| nl* Card (nl+ Card)* nl* |}
Card <== `Card` {:id: Number :} `:` {:winning: NumberList :} SKIP `|` {:have: NumberList :} SKIP
NumberList <-- {| (Number SKIP)* |}
Number <-- %d+ -> tonumber
nl <-- %nl
SKIP <-- [ ]*
NAME_SUFFIX <-- [_%w]+
]])
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))
return ast
end
--[[ PART 1 ]]--
function winning_numbers(card)
-- in place sort
table.sort(card.have)
table.sort(card.winning)
local my_winning = {}
local i,j = 1,1
while i <= #card.have and j <= #card.winning do
if card.have[i] == card.winning[j] then
table.insert(my_winning, card.have[i])
i = i + 1
elseif card.have[i] < card.winning[j] then
i = i + 1
else
j = j + 1
end
end
--print(card.id, inspect(my_winning))
return my_winning
end
function score_card(card)
local w = winning_numbers(card)
if #w == 0 then return 0 end
local score = 1
for i=2,#w do
score = score * 2
end
return score
end
function sum_points(source)
local cards = parse(source)
local sum = 0
for _,v in pairs(cards) do
sum = sum + score_card(v)
end
return sum
end
--[[ PART 2 ]]--
function naive(source)
local cards = parse(source)
-- preprocess the winning numbers & create initial to-do list
local winning = {}
local todo = {}
for _,v in pairs(cards) do
local id = v.id
table.insert(todo, id)
winning[id] = {}
local next_id = id + 1
for _,_ in pairs(winning_numbers(v)) do
table.insert(winning[id], next_id)
next_id = next_id + 1
end
end
-- okay, naively take stuff off the to-do list and process it.
local i = 1
while i <= #todo do
local id = todo[i]
print("Looking at", id)
for _,v in pairs(winning[id]) do
table.insert(todo, v)
end
i = i + 1
end
--print(inspect(todo))
return #todo
end
function smarter(source)
local cards = parse(source)
-- preprocess the winning numbers & create initial to-do list
local winning = {}
local copies = {}
for _,v in pairs(cards) do
copies[v.id] = 1
end
-- process in order
for _,v in pairs(cards) do
local id = v.id
local next_id = id + 1
for _,_ in pairs(winning_numbers(v)) do -- ignore the actual values
copies[next_id] = copies[next_id] + copies[id]
next_id = next_id + 1
end
end
-- okay, sum up all the copies
--print(inspect(copies))
local sum = 0
for _,v in pairs(copies) do
sum = sum + v
end
return sum
end
--[[ CLI start ] ]--
local source = io.input("day4.input"):read("a")
print("Sum:", sum_points(source))
print("Total:", smarter(source))
--[ [ CLI end ]]--
return {
part1 = function(frame)
local s = mw.title.new(frame.args[1]):getContent()
return sum_points(s)
end,
part2 = function(frame)
local s = mw.title.new(frame.args[1]):getContent()
return smarter(s)
end,
}
end)
local modules = {}
modules['table'] = require('table')
modules['string'] = require('string')
modules['strict'] = {}
local function myrequire(name)
if modules[name] == nil then
modules[name] = true
modules[name] = (builders[name])(myrequire)
end
return modules[name]
end
return myrequire('day4')
end)()
