return (functionlocal builders = local function register(name, f) builders[name] = fendregister('llpeg.lpegrex', function return require end)
register('day5', function(myrequire)--DAY 5 --
local lpegrex = myrequire('llpeg.lpegrex')
--PARSING --local patt = lpegrex.compile(Map (nl nl Map)* |} :} nl* !.
Seeds <-- `seeds:` NumberListMapTitle <- `-` `to` `-` SKIP `map:`Map <--
| .) |
|---|
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, mapsend
--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 => unchangedend
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 valend
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) endend
local RangeMT = function RangeMT:__tostring return self.start .. "-" .. self["end"]end
function new_range(start, len) return setmetatable(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 resultend
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 = 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
end)
local modules = modules['table'] = require('table')modules['string'] = require('string')modules['strict'] = local function myrequire(name) if modules[name]