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('day5', function(myrequire)
--[[ DAY 5 ]]--
local lpegrex = myrequire('llpeg.lpegrex')
--[[ PARSING ]]--
local patt = lpegrex.compile([[
Start <== {:seeds: Seeds :} nl nl {:maps: {| Map (nl nl Map)* |} :} nl* !.
Seeds <-- `seeds:` NumberList
MapTitle <- {:source: %w+ :} `-` `to` `-`{:dest: %w+ :} SKIP `map:`
Map <-- {| MapTitle nl {:ranges: {| Range (nl Range)* |} :} |}
Range <-- {| SKIP {:destStart: Number :} SKIP {:sourceStart: Number :} SKIP {:rangeLength: Number :} SKIP &(nl/!.) |}
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))
-- Post process maps
local maps = {}
for _,m in ipairs(ast.maps) do
maps[m.source] = m
-- add 'sourceEnd' for convenience
for _,r in ipairs(m.ranges) do
r.sourceEnd = r.sourceStart + r.rangeLength - 1
end
-- sort ranges
table.sort(m.ranges, function(a,b)
return a.sourceStart < b.sourceStart
end)
end
return ast.seeds, maps
end
--[[ PART 1 ]]--
function map_one(ranges, val)
for _,r in ipairs(ranges) do
if r.sourceStart <= val and val < (r.sourceStart + r.rangeLength) then
return (val - r.sourceStart) + r.destStart
end
end
return val -- not mapped => unchanged
end
function get_location(seed, maps)
local have = "seed"
local want = "location"
local val = seed
while have ~= want do
m = maps[have]
val = map_one(m.ranges, val)
have = m.dest
end
return val
end
function get_first_location_part1(source)
seeds, maps = parse(source)
local locations = {}
for _,seed in ipairs(seeds) do
table.insert(locations, get_location(seed, maps))
end
table.sort(locations)
return locations[1]
end
--[[ PART 2 ]]--
function addTo(table1, table2)
for _,v in ipairs(table2) do
table.insert(table1, v)
end
end
local RangeMT = {}
function RangeMT:__tostring()
return self.start .. "-" .. self["end"]
end
function new_range(start, len)
return setmetatable(
{ start = start, len = len, ["end"] = start + len - 1 },
RangeMT
)
end
function map_ranges_for_range(mapping, inputRange)
local result = {}
for _,mapRange in ipairs(mapping) do
if inputRange["end"] < mapRange.sourceStart then
-- mapping is sorted, so nothing's going to match after this point
break
end
if mapRange.sourceStart < (inputRange.start + inputRange.len) and
inputRange.start < (mapRange.sourceStart + mapRange.rangeLength) then
-- there is some overlap! break into three pieces:
-- unmapped_low mapped unmapped_high
if inputRange.start < mapRange.sourceStart then
-- unmapped low. since the mapping is sorted, we know no other
-- mapping range overlaps this, so we can add it to the result
-- as-is
table.insert(result, new_range(inputRange.start, mapRange.sourceStart - inputRange.start))
end
-- mapped middle
local overlapStart = math.max(inputRange.start, mapRange.sourceStart)
local overlapEnd = math.min(inputRange["end"], mapRange.sourceEnd)
table.insert(result, new_range(mapRange.destStart + overlapStart - mapRange.sourceStart, 1 + overlapEnd - overlapStart))
if mapRange.sourceEnd < inputRange["end"] then
-- unmapped high: we need to keep going for this one
inputRange = new_range(mapRange.sourceEnd, inputRange["end"] - mapRange.sourceEnd)
else
-- nothing left to remap!
return result
end
end
end
-- not mapped => unchanged
table.insert(result, inputRange)
return result
end
function get_first_location_for_range(seedStart, rangeLen, maps)
-- print("First location for", seedStart,"-",seedStart + rangeLen - 1)
local have = "seed"
local want = "location"
local ranges = { new_range(seedStart, rangeLen) }
while have ~= want do
-- print("Have", have, "Want", want)
local m = maps[have]
local result = {}
for _,r in ipairs(ranges) do
-- print("Mapping range", r)
addTo(result, map_ranges_for_range(m.ranges, r))
end
ranges = result
have = m.dest
--[[
for _,r in ipairs(ranges) do
print(" Got", r)
end
]]--
end
-- now we just need to find the lowest value in a range
local starts = {}
for _,r in ipairs(ranges) do
table.insert(starts, r.start)
end
table.sort(starts)
return starts[1]
end
function get_first_location_part2(source)
local seeds, maps = parse(source)
-- print(inspect(maps))
local locations = {}
for i=1,#seeds,2 do
table.insert(locations, get_first_location_for_range(seeds[i], seeds[i+1], maps))
end
table.sort(locations)
return locations[1]
end
--[[ CLI start ] ]--
--local source = io.input("day5.input"):read("a")
--print(get_first_location_part1(source))
local source = io.input("day5.input"):read("a")
print(get_first_location_part2(source))
--[ [ CLI end ]]--
return {
part1 = function(frame)
local s = mw.title.new(frame.args[1]):getContent()
return get_first_location_part1(s)
end,
part2 = function(frame)
local s = mw.title.new(frame.args[1]):getContent()
return get_first_location_part2(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('day5')
end)()
