return (function()
local builders = {}
local function register(name, f)
builders[name] = f
end
register('llpeg', function() return require [[Module:User:Cscott/llpeg]] end)
register('day12', function(myrequire)
--[[ DAY 12 ]]--
local l = myrequire('llpeg')
--[[ PARSING ]]--
local SKIP = l.P" " ^ 0
local nl = l.P"\n"
local patt = l.P{
l.Ct( l.V"SpringLine" * (nl^1 * l.V"SpringLine")^0 * nl^0) * -1,
SpringLine = l.Ct( l.Cg( l.Ct( l.V"Spring" ^ 1 ), "springs" )
* l.P" " * SKIP *
l.Cg( l.Ct( l.V"NumberList" ), "condlist" ) ),
Spring = l.C( l.S"?.#" ),
NumberList = l.V"Number" * SKIP * (l.P"," * SKIP * l.V"Number" * SKIP)^0,
Number = ((l.P"-" ^ -1) * (l.R"09"^1)) / tonumber,
}
function parse(source)
--print(inspect(source))
local ast, errlabel, pos = patt:match(source)
if not ast then
error(string.format("Error at pos %s label '%s'", pos, errlabel))
end
--print('Parsed with success!')
--print(inspect(ast))
return ast
end
--[[ Part 1 ]]--
local State = {}
State.__index = State
function State:new()
return setmetatable({
count = 1, -- how many instances of this state?
in_group = false,
spring_index = 1,
cond_index = 1,
group_size = 0,
}, State)
end
function State:update(props)
for k,v in pairs(self) do
if props[k] == nil then
props[k] = v
end
end
return setmetatable(props, State)
end
function State:key()
local i = 0
if self.in_group then i = 1 end
return string.format("%d %d %d %d", self.spring_index, self.cond_index, i, self.group_size)
end
function State:__tostring()
local group_status = ""
if self.in_group then
group_status = string.format(" in group of size %d", self.group_size)
end
return string.format("%d spring=%d condition=%d%s", self.count, self.spring_index, self.cond_index, group_status)
end
function State:operational(condlist)
if self.in_group then
-- going to leave group
if self.group_size ~= condlist[self.cond_index] then
return nil -- this doesn't work
end
return self:update{
in_group = false,
spring_index = self.spring_index + 1,
cond_index = self.cond_index + 1,
group_size = 0,
}
else
return self:update{
spring_index = self.spring_index + 1,
}
end
end
function State:damaged(condlist)
if self.in_group then
local new_group_size = self.group_size + 1
if new_group_size > condlist[self.cond_index] then
return nil -- this doesn't work
end
return self:update{
spring_index = self.spring_index + 1,
group_size = new_group_size,
}
else
if self.cond_index > #condlist then
return nil -- this doesn't work
end
return self:update{
in_group = true,
group_size = 1,
spring_index = self.spring_index + 1,
}
end
end
function State:done(springs)
return self.spring_index > #springs
end
function State:finalize(condlist)
--print("Finalizing",self)
local cond_index = self.cond_index
if self.in_group then
if self.group_size ~= condlist[cond_index] then
return 0 -- this doesn't work
end
cond_index = cond_index + 1
end
if cond_index ~= (#condlist + 1) then
return 0 -- not enough groups
end
return self.count -- how many ways to make this state
end
function count_ways(springs, condlist)
local state = State:new()
local seen = { [state:key()] = state, }
local todo = { state }
local function insert_new_state(nstate)
if nstate ~= nil then
local nkey = nstate:key()
if seen[nkey] == nil then
seen[nkey] = nstate
table.insert(todo, nstate)
else
seen[nkey].count = seen[nkey].count + nstate.count
end
end
end
local sum = 0
local todo_idx = 1
while todo_idx <= #todo do
state = todo[todo_idx]
todo_idx = todo_idx + 1
if state:done(springs) then
sum = sum + state:finalize(condlist)
else
local spring = springs[state.spring_index]
--print("Examining",state,spring)
if spring == "." or spring == "?" then
insert_new_state(state:operational(condlist))
end
if spring == "#" or spring == "?" then
insert_new_state(state:damaged(condlist))
end
end
end
return sum
end
function part1(source)
local lines = parse(source)
local sum = 0
-- print(inspect(lines))
for i=1,#lines do
local ways = count_ways(lines[i].springs, lines[i].condlist)
--print(i, ways)
sum = sum + ways
end
return sum
end
--[[ Part 2 ]]--
function expand(line)
local nsprings = {}
local ncond = {}
for i = 1,5 do
for _,v in ipairs(line.springs) do
table.insert(nsprings, v)
end
if i < 5 then
table.insert(nsprings, "?")
end
for _,v in ipairs(line.condlist) do
table.insert(ncond, v)
end
end
return { springs=nsprings, condlist=ncond }
end
function part2(source)
local lines = parse(source)
local sum = 0
for i,line in ipairs(lines) do
line = expand(line)
-- print(inspect(line))
local ways = count_ways(line.springs, line.condlist)
--print(i, ways)
sum = sum + ways
end
return sum
end
--[[ CLI ] ]--
local source = io.input("day12.input"):read("a")
print("Part 1 sum:", part1(source))
print("Part 2 sum:", part2(source))
--[ [ END CLI ]]--
return {
part1 = function(frame)
local s = frame:expandTemplate{ title = frame.args[1] }
return part1(s)
end,
part2 = function(frame)
local s = frame:expandTemplate{ title = frame.args[1] }
return part2(s, tonumber(frame.args[2]))
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('day12')
end)()
