Oh yeah, me too. I ran the test suite so much times because I would not believe that splitting the ranges would work with only 4 or 5 clauses. I expected to have to check for //-1 ranges or something, but no.
lud
1
rugyoga
Produces the answer in 1ms using native Ranges.
import AOC
aoc 2023, 5 do
def p1(input) do
{seeds, maps} = process(input)
Enum.map(seeds, &maps_number(&1, maps)) |> Enum.min
end
def map_number([], n), do: n
def map_number([{range, _} = fun | maps], n) do
if n in range do
apply_fun(fun, n)
else
map_number(maps, n)
end
end
def apply_fun({range, dest}, n), do: dest+n-range.first
def process(input) do
["seeds: " <> seeds | maps] = input |> String.split("\n\n", trim: true)
{parse_nums(seeds),
maps
|> Enum.map(
fn map ->
[_name, elements] = String.split(map, " map:\n")
elements
|> String.split("\n", trim: true)
|> Enum.map(&parse_nums/1)
|> Enum.map(&create_mapping/1)
end
)}
end
def create_mapping([dest, source, length]) do
{source..(source+length-1), dest}
end
def map_range(range, []), do: [range]
def map_range(arg_range, [{fun_range, _} = fun_def | maps]) do
if Range.disjoint?(fun_range, arg_range) do
map_range(arg_range, maps)
else
fun_lo..fun_hi = fun_range
arg_lo..arg_hi = arg_range
lo = [fun_lo, arg_lo] |> Enum.max
hi = [fun_hi, arg_hi] |> Enum.min
[apply_fun(fun_def, lo)..apply_fun(fun_def, hi) |
(if arg_lo < lo, do: map_range(arg_lo..lo-1, maps), else: [])
++ (if hi < arg_hi, do: map_range(hi+1..arg_hi, maps), else: [])]
end
end
def map_ranges(ranges, []), do: normalize_ranges(ranges)
def map_ranges(ranges, [map | maps]) do
ranges
|> normalize_ranges()
|> Enum.map(fn arg -> map_range(arg, map) end)
|> List.flatten
|> map_ranges(maps)
end
def normalize_ranges(ranges) do
ranges
|> Enum.sort()
|> merge_ranges()
end
def merge_ranges([]), do: []
def merge_ranges([a]), do: [a]
def merge_ranges([a | [b | ranges]]) do
if Range.disjoint?(a, b) do
[a | merge_ranges([b | ranges])]
else
merge_ranges([Enum.min([a.first, b.first])..Enum.max(a.last, b.last) | ranges])
end
end
def maps_number(n, maps) do
Enum.reduce(maps, n, &map_number/2)
end
def parse_nums(nums), do: nums |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1)
def p2(input) do
{seeds, maps} = process(input)
seeds
|> Enum.chunk_every(2)
|> Enum.map(fn [start, length] -> start..(start+length-1) end)
|> map_ranges(maps)
|> hd
|> then(&(&1.first))
end
end
3
bengtson
I took a somewhat different approach and coded a program that generated an Elixir module with a set of guarded functions, one for each map. Further, the solution for each seed is a recursive call returning the location.
Here’s a module that solves part 1 in a super quick 80us. I’ve not provided the code that automatically generates this module … it was really messy but super fun to write.
iex(188)> Aoc.Day05.Mappers.run
Closest Location : 226172555
.. Calculation time: 80 uS
defmodule Aoc.Day05.Mappers do
def run do
time = System.monotonic_time(:microsecond)
answer =
seeds()
|> Enum.map(fn seed -> map_unit_num({:seed, seed}) end)
|> Enum.sort()
|> hd()
time = System.monotonic_time(:microsecond) - time
IO.puts("Closest Location : #{answer}")
IO.puts(" .. Calculation time: #{time} uS")
end
def map_unit_num({:location, dist}), do: dist
def map_unit_num(unit_num), do: map_unit_num(Aoc.Day05.Mappers.map(unit_num))
def seeds() do
[
3_037_945_983,
743_948_277,
2_623_786_093,
391_282_324,
195_281_306,
62_641_412,
769_611_781,
377_903_357,
2_392_990_228,
144_218_002,
1_179_463_071,
45_174_621,
2_129_467_491,
226_193_957,
1_994_898_626,
92_402_726,
1_555_863_421,
340_215_202,
426_882_817,
207_194_644
]
end
def map({:seed, num}) when num in 2_182_201_339..2_212_684_610, do: {:soil, num + 895_805_021}
def map({:seed, num}) when num in 624_445_326..789_672_169, do: {:soil, num + 179_184_978}
def map({:seed, num}) when num in 2_745_251_526..3_026_372_471, do: {:soil, num + -351_515_193}
def map({:seed, num}) when num in 789_672_170..875_365_603, do: {:soil, num + -71_735_300}
def map({:seed, num}) when num in 410_599_330..438_584_017, do: {:soil, num + 188_117_989}
def map({:seed, num}) when num in 2_024_628_810..2_182_201_338, do: {:soil, num + 1_974_466_197}
def map({:seed, num}) when num in 3_026_372_472..3_048_695_274, do: {:soil, num + 579_215_719}
def map({:seed, num}) when num in 2_678_166_775..2_681_563_693, do: {:soil, num + 877_492_801}
def map({:seed, num}) when num in 438_584_018..440_364_324, do: {:soil, num + 530_273_130}
def map({:seed, num}) when num in 2_212_684_611..2_300_144_177, do: {:soil, num + 1_003_543_207}
def map({:seed, num}) when num in 4_122_083_708..4_213_735_664,
do: {:soil, num + -1_819_999_332}
def map({:seed, num}) when num in 0..188_112_121, do: {:soil, num + 970_637_455}
def map({:seed, num}) when num in 299_146_916..339_559_261, do: {:soil, num + 208_035_312}
def map({:seed, num}) when num in 1_689_624_457..1_892_569_465, do: {:soil, num + -317_322_423}
def map({:seed, num}) when num in 191_483_770..193_662_171, do: {:soil, num + 1_178_639_862}
def map({:seed, num}) when num in 193_662_172..299_146_915, do: {:soil, num + 131_125_032}
def map({:seed, num}) when num in 2_671_328_191..2_678_166_774, do: {:soil, num + 445_097_279}
def map({:seed, num}) when num in 875_365_604..958_121_807, do: {:soil, num + -248_663_597}
def map({:seed, num}) when num in 978_774_853..1_296_097_275, do: {:soil, num + 596_472_190}
def map({:seed, num}) when num in 4_213_735_665..4_294_967_295,
do: {:soil, num + -1_078_739_478}
def map({:seed, num}) when num in 2_681_563_694..2_745_251_525, do: {:soil, num + -656_934_884}
def map({:seed, num}) when num in 188_112_122..191_483_769, do: {:soil, num + 526_453_100}
def map({:seed, num}) when num in 1_620_884_480..1_672_007_224,
do: {:soil, num + -1_073_289_906}
def map({:seed, num}) when num in 3_374_604_163..3_400_875_651, do: {:soil, num + 154_783_924}
def map({:seed, num}) when num in 973_428_243..978_535_253, do: {:soil, num + -263_970_032}
def map({:seed, num}) when num in 3_985_570_976..4_083_932_710,
do: {:soil, num + -1_272_562_700}
def map({:seed, num}) when num in 3_048_695_275..3_262_463_008, do: {:soil, num + -960_378_633}
def map({:seed, num}) when num in 2_300_144_178..2_671_328_190, do: {:soil, num + 1_327_766_816}
def map({:seed, num}) when num in 4_083_932_711..4_122_083_707,
do: {:soil, num + -1_409_075_432}
def map({:seed, num}) when num in 958_121_808..973_428_242, do: {:soil, num + 271_667_837}
def map({:seed, num}) when num in 3_328_662_676..3_374_604_162, do: {:soil, num + 828_004_860}
def map({:seed, num}) when num in 1_296_097_276..1_620_884_479,
do: {:soil, num + -1_296_097_276}
def map({:seed, num}) when num in 3_320_726_838..3_328_662_675, do: {:soil, num + -212_237_206}
def map({:seed, num}) when num in 3_667_512_001..3_759_870_273, do: {:soil, num + 535_097_022}
def map({:seed, num}) when num in 978_535_254..978_774_852, do: {:soil, num + 373_731_547}
def map({:seed, num}) when num in 1_672_007_225..1_689_624_456, do: {:soil, num + -319_500_825}
def map({:seed, num}) when num in 440_364_325..547_535_045, do: {:soil, num + 804_731_755}
def map({:seed, num}) when num in 3_400_875_652..3_667_512_000, do: {:soil, num + -589_505_641}
def map({:seed, num}) when num in 547_535_046..624_445_325, do: {:soil, num + -117_263_098}
def map({:seed, num}) when num in 339_559_262..410_599_329, do: {:soil, num + 819_190_315}
def map({:seed, num}) when num in 3_262_463_009..3_308_994_704, do: {:soil, num + 296_593_486}
def map({:seed, num}) when num in 3_308_994_705..3_320_726_837, do: {:soil, num + -185_730_651}
def map({:seed, num}) when num in 3_759_870_274..3_985_570_975, do: {:soil, num + -456_182_889}
def map({:seed, num}), do: {:soil, num}
def map({:soil, num}) when num in 2_957_653_952..3_297_634_843,
do: {:fertilizer, num + -19_779_182}
def map({:soil, num}) when num in 2_145_122_669..2_337_416_322,
do: {:fertilizer, num + -258_652_935}
def map({:soil, num}) when num in 822_424_488..842_203_669,
do: {:fertilizer, num + 2_455_431_174}
def map({:soil, num}) when num in 2_393_077_006..2_708_069_579,
do: {:fertilizer, num + 229_805_190}
def map({:soil, num}) when num in 3_769_116_301..4_294_967_295,
do: {:fertilizer, num + -319_239_622}
def map({:soil, num}) when num in 842_203_670..2_145_122_668,
do: {:fertilizer, num + -258_652_935}
def map({:soil, num}) when num in 345_297_835..822_424_487,
do: {:fertilizer, num + 1_800_457_708}
def map({:soil, num}) when num in 2_890_661_797..2_957_653_951,
do: {:fertilizer, num + -811_898_409}
def map({:soil, num}) when num in 2_708_069_580..2_890_661_796,
do: {:fertilizer, num + -2_705_419_066}
def map({:soil, num}) when num in 2_337_416_323..2_340_066_836,
do: {:fertilizer, num + -2_337_416_323}
def map({:soil, num}) when num in 2_340_066_837..2_393_077_005,
do: {:fertilizer, num + -1_809_526_271}
def map({:soil, num}) when num in 0..345_297_834, do: {:fertilizer, num + 185_242_731}
def map({:soil, num}) when num in 3_449_876_679..3_769_116_300,
do: {:fertilizer, num + 525_850_995}
def map({:soil, num}), do: {:fertilizer, num}
def map({:fertilizer, num}) when num in 5_168_332..73_380_238, do: {:water, num + 856_308_802}
def map({:fertilizer, num}) when num in 2_229_711_837..2_258_806_277,
do: {:water, num + -2_092_742_328}
def map({:fertilizer, num}) when num in 1_150_509_810..1_268_877_854,
do: {:water, num + 1_672_739_119}
def map({:fertilizer, num}) when num in 3_073_610_919..3_127_109_356,
do: {:water, num + 605_277_365}
def map({:fertilizer, num}) when num in 3_682_691_325..3_778_925_916,
do: {:water, num + 265_360_496}
def map({:fertilizer, num}) when num in 2_387_840_795..2_892_098_588,
do: {:water, num + -1_085_013_604}
def map({:fertilizer, num}) when num in 1_926_818_347..2_030_902_289,
do: {:water, num + -728_075_099}
def map({:fertilizer, num}) when num in 1_104_177_008..1_150_509_809,
do: {:water, num + 702_907_977}
def map({:fertilizer, num}) when num in 619_653_304..879_458_526,
do: {:water, num + 1_523_442_794}
def map({:fertilizer, num}) when num in 2_385_211_148..2_387_840_794,
do: {:water, num + -321_774_202}
def map({:fertilizer, num}) when num in 445_026_117..480_785_565,
do: {:water, num + 1_621_040_476}
def map({:fertilizer, num}) when num in 537_865_723..619_653_303,
do: {:water, num + -179_857_300}
def map({:fertilizer, num}) when num in 0..5_168_331, do: {:water, num + 621_204_445}
def map({:fertilizer, num}) when num in 1_861_632_296..1_926_818_346,
do: {:water, num + 862_806_608}
def map({:fertilizer, num}) when num in 2_258_806_278..2_385_211_147,
do: {:water, num + -405_388_491}
def map({:fertilizer, num}) when num in 4_141_091_197..4_155_831_937,
do: {:water, num + -207_780_117}
def map({:fertilizer, num}) when num in 2_892_098_589..2_901_836_444,
do: {:water, num + -2_040_359_311}
def map({:fertilizer, num}) when num in 3_029_323_079..3_073_610_918,
do: {:water, num + 1_014_963_334}
def map({:fertilizer, num}) when num in 1_778_018_007..1_861_632_295,
do: {:water, num + 201_804_650}
def map({:fertilizer, num}) when num in 2_084_781_230..2_087_851_740,
do: {:water, num + 17_044_812}
def map({:fertilizer, num}) when num in 4_268_409_625..4_294_967_295,
do: {:water, num + -179_835_372}
def map({:fertilizer, num}) when num in 111_346_117..323_320_166,
do: {:water, num + 818_342_924}
def map({:fertilizer, num}) when num in 4_155_831_938..4_268_409_624,
do: {:water, num + -589_521_341}
def map({:fertilizer, num}) when num in 2_030_902_290..2_084_781_229,
do: {:water, num + -1_591_106_286}
def map({:fertilizer, num}) when num in 1_490_707_297..1_682_651_769,
do: {:water, num + -1_324_643_347}
def map({:fertilizer, num}) when num in 888_219_041..1_016_428_035,
do: {:water, num + -879_458_527}
def map({:fertilizer, num}) when num in 3_778_925_917..3_836_129_159,
do: {:water, num + 15_769_926}
def map({:fertilizer, num}) when num in 3_127_109_357..3_536_155_112,
do: {:water, num + -97_786_278}
def map({:fertilizer, num}) when num in 77_722_143..108_335_955,
do: {:water, num + 2_714_912_973}
def map({:fertilizer, num}) when num in 4_013_149_435..4_141_091_196,
do: {:water, num + -574_780_600}
def map({:fertilizer, num}) when num in 3_620_382_204..3_682_691_324,
do: {:water, num + 112_004_518}
def map({:fertilizer, num}) when num in 1_682_651_770..1_778_018_006,
do: {:water, num + 720_249_551}
def map({:fertilizer, num}) when num in 879_458_527..888_219_040,
do: {:water, num + -879_458_527}
def map({:fertilizer, num}) when num in 2_901_836_445..2_941_616_973,
do: {:water, num + -2_408_161_501}
def map({:fertilizer, num}) when num in 3_536_155_113..3_617_567_106,
do: {:water, num + 315_743_973}
def map({:fertilizer, num}) when num in 1_268_877_855..1_490_707_296,
do: {:water, num + 1_229_389_703}
def map({:fertilizer, num}) when num in 3_836_129_160..4_013_149_434,
do: {:water, num + 281_817_861}
def map({:fertilizer, num}) when num in 108_335_956..111_346_116,
do: {:water, num + 2_681_288_999}
def map({:fertilizer, num}) when num in 480_785_566..537_865_722,
do: {:water, num + 660_877_525}
def map({:fertilizer, num}) when num in 406_826_572..445_026_116,
do: {:water, num + 1_698_069_981}
def map({:fertilizer, num}) when num in 1_016_428_036..1_104_177_007,
do: {:water, num + -482_972_563}
def map({:fertilizer, num}) when num in 2_087_851_741..2_229_711_836,
do: {:water, num + -1_461_478_964}
def map({:fertilizer, num}) when num in 73_380_239..77_722_142,
do: {:water, num + 2_646_716_761}
def map({:fertilizer, num}) when num in 3_617_567_107..3_620_382_203,
do: {:water, num + 497_564_817}
def map({:fertilizer, num}) when num in 323_320_167..406_826_571,
do: {:water, num + 444_912_706}
def map({:fertilizer, num}), do: {:water, num}
def map({:water, num}) when num in 367_033_980..465_127_811, do: {:light, num + 3_479_848_485}
def map({:water, num}) when num in 3_292_746_518..3_355_664_500,
do: {:light, num + -1_414_180_541}
def map({:water, num}) when num in 661_438_934..700_676_809, do: {:light, num + 3_594_290_486}
def map({:water, num}) when num in 2_191_298_319..2_492_980_114,
do: {:light, num + -1_721_707_810}
def map({:water, num}) when num in 1_999_013_894..2_086_656_168,
do: {:light, num + -1_617_065_660}
def map({:water, num}) when num in 199_351_627..355_914_292, do: {:light, num + 3_489_144_459}
def map({:water, num}) when num in 2_086_656_169..2_191_298_318,
do: {:light, num + -785_837_416}
def map({:water, num}) when num in 2_798_447_654..3_022_913_971,
do: {:light, num + -1_991_907_742}
def map({:water, num}) when num in 355_914_293..367_033_979, do: {:light, num + 909_422_626}
def map({:water, num}) when num in 1_914_042_148..1_942_924_673,
do: {:light, num + -508_581_245}
def map({:water, num}) when num in 1_942_924_674..1_999_013_893, do: {:light, num + 634_466_396}
def map({:water, num}) when num in 4_136_990_116..4_145_246_895,
do: {:light, num + -456_750_810}
def map({:water, num}) when num in 700_676_810..1_308_631_663, do: {:light, num + 1_240_807_150}
def map({:water, num}) when num in 3_022_913_972..3_024_737_684, do: {:light, num + 822_144_780}
def map({:water, num}) when num in 1_308_631_664..1_324_703_045,
do: {:light, num + 2_931_026_374}
def map({:water, num}) when num in 4_254_580_741..4_265_809_615,
do: {:light, num + -1_688_418_546}
def map({:water, num}) when num in 3_831_845_903..3_842_308_374,
do: {:light, num + -2_160_053_520}
def map({:water, num}) when num in 3_842_308_375..4_136_990_115, do: {:light, num + 102_667_922}
def map({:water, num}) when num in 3_160_062_910..3_292_746_517, do: {:light, num + 130_599_589}
def map({:water, num}) when num in 1_324_703_046..1_341_426_426,
do: {:light, num + 1_224_735_768}
def map({:water, num}) when num in 1_341_426_427..1_368_534_730,
do: {:light, num + 2_081_919_680}
def map({:water, num}) when num in 3_355_664_501..3_589_995_189,
do: {:light, num + -2_324_658_271}
def map({:water, num}) when num in 4_145_246_896..4_169_609_042,
do: {:light, num + -2_868_790_290}
def map({:water, num}) when num in 54_538_430..199_351_626, do: {:light, num + 3_395_915_981}
def map({:water, num}) when num in 465_127_812..661_438_933, do: {:light, num + 1_217_127_043}
def map({:water, num}) when num in 1_403_802_338..1_676_593_193,
do: {:light, num + -1_349_263_908}
def map({:water, num}) when num in 2_492_980_115..2_798_447_653, do: {:light, num + 140_500_175}
def map({:water, num}) when num in 4_169_609_043..4_254_580_740,
do: {:light, num + -574_341_435}
def map({:water, num}) when num in 3_644_614_138..3_693_212_531,
do: {:light, num + -402_550_033}
def map({:water, num}) when num in 4_265_809_616..4_294_967_295,
do: {:light, num + -1_188_228_416}
def map({:water, num}) when num in 1_368_534_731..1_403_802_337,
do: {:light, num + -597_262_426}
def map({:water, num}) when num in 1_676_593_194..1_914_042_147,
do: {:light, num + -242_249_765}
def map({:water, num}) when num in 3_589_995_190..3_644_614_137,
do: {:light, num + -3_262_665_904}
def map({:water, num}) when num in 3_024_737_685..3_160_062_909, do: {:light, num + 82_001_195}
def map({:water, num}) when num in 3_693_212_532..3_831_845_902,
do: {:light, num + -754_264_703}
def map({:water, num}), do: {:light, num}
def map({:light, num}) when num in 2_971_073_270..3_557_284_071,
do: {:temperature, num + -193_259_972}
def map({:light, num}) when num in 0..334_152_506, do: {:temperature, num + 1_687_968_665}
def map({:light, num}) when num in 3_882_460_035..4_018_320_296,
do: {:temperature, num + 276_646_999}
def map({:light, num}) when num in 2_095_520_416..2_288_320_627,
do: {:temperature, num + -2_095_520_416}
def map({:light, num}) when num in 3_557_284_072..3_560_429_441,
do: {:temperature, num + 83_387_027}
def map({:light, num}) when num in 3_560_429_442..3_882_460_034,
do: {:temperature, num + -1_104_646_737}
def map({:light, num}) when num in 1_272_848_785..1_539_048_240,
do: {:temperature, num + 749_272_387}
def map({:light, num}) when num in 914_869_331..1_272_848_784,
do: {:temperature, num + -141_352_295}
def map({:light, num}) when num in 1_539_048_241..2_095_520_415,
do: {:temperature, num + -407_551_751}
def map({:light, num}) when num in 4_018_320_297..4_078_989_662,
do: {:temperature, num + -654_296_197}
def map({:light, num}) when num in 2_455_782_705..2_971_073_269,
do: {:temperature, num + 1_188_033_764}
def map({:light, num}) when num in 334_152_507..914_869_330,
do: {:temperature, num + -141_352_295}
def map({:light, num}) when num in 4_078_989_663..4_294_967_295,
do: {:temperature, num + -654_296_197}
def map({:light, num}), do: {:temperature, num}
def map({:temperature, num}) when num in 605_654_847..623_405_527,
do: {:humidity, num + 3_466_868_465}
def map({:temperature, num}) when num in 540_191_835..605_654_846,
do: {:humidity, num + 634_418_183}
def map({:temperature, num}) when num in 3_792_024_734..3_892_226_981,
do: {:humidity, num + -1_753_568_827}
def map({:temperature, num}) when num in 866_566_556..995_025_736,
do: {:humidity, num + 1_672_830_227}
def map({:temperature, num}) when num in 2_296_045_868..2_310_760_925,
do: {:humidity, num + -2_199_703_196}
def map({:temperature, num}) when num in 1_522_255_720..1_628_956_940,
do: {:humidity, num + 2_305_075_024}
def map({:temperature, num}) when num in 4_081_148_893..4_092_289_608,
do: {:humidity, num + -264_958_865}
def map({:temperature, num}) when num in 3_892_226_982..4_081_148_892,
do: {:humidity, num + -2_186_125_258}
def map({:temperature, num}) when num in 623_405_528..658_755_603,
do: {:humidity, num + 3_157_434_424}
def map({:temperature, num}) when num in 1_813_669_629..2_222_662_697,
do: {:humidity, num + -1_048_052_680}
def map({:temperature, num}) when num in 3_778_728_770..3_792_024_733,
do: {:humidity, num + 447_040_718}
def map({:temperature, num}) when num in 1_645_897_858..1_813_669_628,
do: {:humidity, num + 1_106_207_687}
def map({:temperature, num}) when num in 1_121_517_092..1_522_255_719,
do: {:humidity, num + 1_017_141_063}
def map({:temperature, num}) when num in 4_155_853_973..4_211_755_816,
do: {:humidity, num + 83_211_479}
def map({:temperature, num}) when num in 96_342_672..132_069_065,
do: {:humidity, num + 3_837_689_293}
def map({:temperature, num}) when num in 658_755_604..681_480_156,
do: {:humidity, num + 2_346_517_050}
def map({:temperature, num}) when num in 4_211_755_817..4_294_967_295,
do: {:humidity, num + -222_443_984}
def map({:temperature, num}) when num in 3_186_777_866..3_507_563_180,
do: {:humidity, num + -2_906_347_414}
def map({:temperature, num}) when num in 2_310_760_926..2_376_029_195,
do: {:humidity, num + -2_199_703_196}
def map({:temperature, num}) when num in 3_659_551_759..3_763_656_210,
do: {:humidity, num + -3_483_225_759}
def map({:temperature, num}) when num in 1_628_956_941..1_645_897_857,
do: {:humidity, num + 266_066_694}
def map({:temperature, num}) when num in 3_507_563_181..3_639_998_284,
do: {:humidity, num + 585_771_203}
def map({:temperature, num}) when num in 132_069_066..311_490_417,
do: {:humidity, num + 2_895_928_141}
def map({:temperature, num}) when num in 311_490_418..540_191_834,
do: {:humidity, num + 1_165_909_889}
def map({:temperature, num}) when num in 2_225_723_089..2_296_045_867,
do: {:humidity, num + 709_226_786}
def map({:temperature, num}) when num in 681_480_157..782_316_974,
do: {:humidity, num + -80_264_390}
def map({:temperature, num}) when num in 3_763_656_211..3_778_728_769,
do: {:humidity, num + -843_778_895}
def map({:temperature, num}) when num in 3_639_998_285..3_659_551_758,
do: {:humidity, num + 329_760_074}
def map({:temperature, num}) when num in 2_613_356_473..3_186_777_865,
do: {:humidity, num + 594_062_086}
def map({:temperature, num}) when num in 2_222_662_698..2_225_723_088,
do: {:humidity, num + 1_867_611_295}
def map({:temperature, num}) when num in 995_025_737..1_121_517_091,
do: {:humidity, num + 916_938_815}
def map({:temperature, num}) when num in 782_316_975..866_566_555,
do: {:humidity, num + 1_885_538_989}
def map({:temperature, num}) when num in 2_376_029_196..2_613_356_472,
do: {:humidity, num + -1_135_956_166}
def map({:temperature, num}) when num in 4_092_289_609..4_155_853_972,
do: {:humidity, num + -3_390_237_024}
def map({:temperature, num}), do: {:humidity, num}
def map({:humidity, num}) when num in 2_982_177_676..3_004_463_335,
do: {:location, num + -133_442_994}
def map({:humidity, num}) when num in 3_717_224_958..3_741_424_830,
do: {:location, num + -336_748_298}
def map({:humidity, num}) when num in 734_568_132..834_656_253,
do: {:location, num + 2_467_362_553}
def map({:humidity, num}) when num in 4_087_339_561..4_158_513_215,
do: {:location, num + -3_322_488_201}
def map({:humidity, num}) when num in 2_953_711_255..2_982_177_675,
do: {:location, num + -2_765_541_942}
def map({:humidity, num}) when num in 2_832_231_336..2_844_786_119,
do: {:location, num + 357_144_565}
def map({:humidity, num}) when num in 47_909_639..58_477_196,
do: {:location, num + 3_321_999_463}
def map({:humidity, num}) when num in 3_741_424_831..3_841_187_208,
do: {:location, num + -3_693_515_192}
def map({:humidity, num}) when num in 58_477_197..65_877_216,
do: {:location, num + 2_812_543_145}
def map({:humidity, num}) when num in 3_409_715_295..3_556_213_169,
do: {:location, num + -366_837_269}
def map({:humidity, num}) when num in 2_734_551_883..2_832_231_335,
do: {:location, num + -1_538_202_941}
def map({:humidity, num}) when num in 3_387_790_447..3_409_715_294,
do: {:location, num + 30_920_724}
def map({:humidity, num}) when num in 573_552_831..639_385_980,
do: {:location, num + 1_014_420_310}
def map({:humidity, num}) when num in 889_063_447..964_405_692,
do: {:location, num + 231_943_249}
def map({:humidity, num}) when num in 567_796_360..573_552_830,
do: {:location, num + 726_232_035}
def map({:humidity, num}) when num in 499_906_065..567_796_359,
do: {:location, num + 2_802_112_742}
def map({:humidity, num}) when num in 2_921_050_411..2_953_711_254,
do: {:location, num + -6_015_380}
def map({:humidity, num}) when num in 3_064_299_481..3_366_281_635,
do: {:location, num + -1_081_877_195}
def map({:humidity, num}) when num in 4_084_864_539..4_087_339_560,
do: {:location, num + -3_380_077_830}
def map({:humidity, num}) when num in 834_656_254..889_063_446,
do: {:location, num + -535_579_628}
def map({:humidity, num}) when num in 2_182_055_199..2_389_757_488,
do: {:location, num + 1_441_368_525}
def map({:humidity, num}) when num in 2_881_400_789..2_921_050_410,
do: {:location, num + -2_492_549_080}
def map({:humidity, num}) when num in 3_592_293_988..3_632_791_283,
do: {:location, num + -3_444_621_971}
def map({:humidity, num}) when num in 639_385_981..734_568_131,
do: {:location, num + 2_308_309_894}
def map({:humidity, num}) when num in 3_556_213_170..3_592_293_987,
do: {:location, num + -2_848_951_439}
def map({:humidity, num}) when num in 2_389_757_489..2_528_415_407,
do: {:location, num + -105_353_048}
def map({:humidity, num}) when num in 2_146_687_309..2_182_055_198,
do: {:location, num + -1_793_203_490}
def map({:humidity, num}) when num in 441_189_704..499_509_271,
do: {:location, num + 2_078_436_836}
def map({:humidity, num}) when num in 3_366_281_636..3_387_790_446,
do: {:location, num + -2_622_939_087}
def map({:humidity, num}) when num in 2_844_786_120..2_881_400_788,
do: {:location, num + 33_634_242}
def map({:humidity, num}) when num in 4_212_526_404..4_294_967_295,
do: {:location, num + -3_995_890_670}
def map({:humidity, num}) when num in 1_235_194_267..1_417_981_971,
do: {:location, num + 2_205_441_752}
def map({:humidity, num}) when num in 964_405_693..1_235_194_266,
do: {:location, num + 1_613_540_415}
def map({:humidity, num}) when num in 3_877_915_244..3_948_350_380,
do: {:location, num + -2_424_693_288}
def map({:humidity, num}) when num in 1_861_705_628..2_146_687_308,
do: {:location, num + -1_025_680_613}
def map({:humidity, num}) when num in 499_509_272..499_906_064,
do: {:location, num + 800_275_594}
def map({:humidity, num}) when num in 3_948_350_381..4_070_829_900,
do: {:location, num + -2_088_407_615}
def map({:humidity, num}) when num in 3_004_463_336..3_064_299_480,
do: {:location, num + -581_400_976}
def map({:humidity, num}) when num in 4_070_829_901..4_084_864_538,
do: {:location, num + -666_153_368}
def map({:humidity, num}) when num in 4_158_513_216..4_212_526_403,
do: {:location, num + -2_759_304_448}
def map({:humidity, num}) when num in 342_162_595..441_189_703,
do: {:location, num + 958_019_064}
def map({:humidity, num}) when num in 3_652_908_910..3_717_224_957,
do: {:location, num + -2_129_251_817}
def map({:humidity, num}) when num in 1_417_981_972..1_861_705_627,
do: {:location, num + 2_433_261_668}
def map({:humidity, num}) when num in 3_632_791_284..3_652_908_909,
do: {:location, num + 198_334_730}
def map({:humidity, num}) when num in 2_528_415_408..2_734_551_882,
do: {:location, num + -874_609_117}
def map({:humidity, num}) when num in 65_877_217..342_162_594,
do: {:location, num + 362_624_114}
def map({:humidity, num}) when num in 3_841_187_209..3_877_915_243,
do: {:location, num + -1_358_288_704}
def map({:humidity, num}), do: {:location, num}
end
2
adamu
I’m getting slower 
Not much to add to the solutions provided above. Here’s my code that calculates the ranges in part 2 (less than 1ms on a Core i5).
# inside def process_ranges(map_ranges, [item_range | rest]) do
to_shift = max(source.first, item_range.first)..min(source.last, item_range.last)
remainders =
[
if(item_range.first < source.first, do: item_range.first..(source.first - 1)),
if(item_range.last > source.last, do: (source.last + 1)..item_range.last)
]
|> Enum.reject(&is_nil/1)
[Range.shift(to_shift, offset) | process_ranges(map_ranges, remainders ++ rest)]
https://git.adamu.jp/adam/AdventOfCode/src/branch/main/2023/day5.exs
1
hauleth
I have stolen been inspired by your code and with some personal tweaks to it it ended like that
defmodule Mapping do
@behaviour Access
import Kernel, except: [apply: 2]
defstruct [:values]
def from_list(lst) do
%__MODULE__{values: Enum.sort(lst)}
end
defp apply({a.._, to}, v), do: v - a + to
@impl Access
def fetch(%__MODULE__{values: list}, key) when is_integer(key) do
{:ok, sorted_find(list, key)}
end
def fetch(%__MODULE__{values: map}, %RangeSet{ranges: ranges}) do
ranges
|> Enum.flat_map(&map_range(&1, map))
|> RangeSet.new()
|> then(&{:ok, &1})
end
defp sorted_find([], n), do: n
defp sorted_find([{a..b, _} = result | _], n) when n in a..b, do: apply(result, n)
defp sorted_find([{a.._, _} | _], n) when n < a, do: n
defp sorted_find([_ | rest], n), do: sorted_find(rest, n)
defp map_range(range, []), do: [range]
defp map_range(_..hi = range, [{lo.._, _} | _]) when lo > hi, do: [range]
defp map_range(lo.._ = range, [{_..hi, _} | rest]) when lo > hi, do: map_range(range, rest)
defp map_range(arg_range, [{fun_range, _} = fun_def | maps]) do
fun_lo..fun_hi = fun_range
arg_lo..arg_hi = arg_range
lo = max(fun_lo, arg_lo)
hi = min(fun_hi, arg_hi)
[
apply(fun_def, lo)..apply(fun_def, hi)
| if(hi < arg_hi, do: map_range((hi + 1)..arg_hi, maps), else: [])
]
end
end
[seeds | maps] =
puzzle_input
|> String.split("\n\n", trim: true)
mappings =
maps
|> Enum.map(fn map ->
[_ | lines] = String.split(map, "\n")
lines
|> Enum.map(&String.split/1)
|> Enum.map(fn line ->
[to, from, len] = Enum.map(line, &String.to_integer/1)
{from..(from + len - 1), to}
end)
|> Mapping.from_list()
end)
seeds =
seeds
|> String.split()
|> tl()
|> Enum.map(&String.to_integer/1)
Part 1:
seeds
|> Enum.map(&Enum.reduce(mappings, &1, fn mapping, val -> mapping[val] end))
|> Enum.min()
Part 2:
seeds
|> Enum.chunk_every(2)
|> Enum.map(fn [start, length] -> start..(start + length - 1) end)
|> RangeSet.new()
|> then(&Enum.reduce(mappings, &1, fn map, r -> map[r] end))
|> RangeSet.min()
1
mrsk
At first I tried algorithm to slice and remap ranges, but I was hitting some failing edge case(s) and after writing some few hundreds lines of tests I gave up and wrote a bruteforce algorithm to do reverse search (from location to seed). It took 15secs to find the answer. Now that I have the correct answer I will be able to troubleshoot my 1st approach:)
Full solution: lib/Aoc2023/D05.ex · main · Marius K / aoc-elixir · GitLab
0
stevensonmt
When I run your code on the example for part 2 it returns 56 rather than 46. Strangely it returns the correct answer for the real input.
0
igorb
Huh, something is not right. Indeed it returns 56 on the test input, yet the real answer is still correct. When I first arrived at the correct answer I had a solution without Task.async_stream/2, and when I incorporated it I only tested the real input. The output seemed identical so I just assumed it worked when posting here. If you switch back to Enum.map/2 and then a regular Enum.min/1 call at the end it works on the test input again just fine. I’ll look into why the discrepancy happens later.
1
APB9785
Creator of ECSx
Went the reverse bruteforce approach for part 2. Takes about a minute to find the solution.
possible_location_values = Stream.iterate(1, &(&1 + 1))
seed_ranges =
seeds
|> Enum.chunk_every(2)
|> Enum.map(fn [start, range] -> start..(start + range - 1) end)
possible_location_values
|> Stream.filter(fn location ->
seed = seed_for_location(location, maps)
Enum.any?(seed_ranges, &(&1.first <= seed and seed <= &1.last))
end)
|> Enum.take(1)
|> hd()
Full solution here on Github
1
stevensonmt
I got some sort of mental block on part 2. I kept thinking my logic was off on the approach to the problem without recognizing I had simply made several errors in the arithmetic of splitting the ranges. I started from scratch multiple times but continued to make different errors in the splitting. Finally thought to do some unit testing of the range splitting function and discovered my error. Ended up stealing from @igorb’s solution to improve efficiency.
def solve(input) do
input
|> parse()
|> get_locations(Day5.map_keys())
|> Enum.min()
end
defp get_locations(maps, [seeds | keys]) when seeds == "seeds" do
maps
|> Map.get(seeds)
|> Task.async_stream(fn {start, stop} ->
keys
|> Enum.reduce([{start, stop}], fn key, processed_ranges ->
maps
|> Map.get(key)
|> Enum.reduce(processed_ranges, fn mapper, p_rs ->
Enum.flat_map(p_rs, fn p_r ->
split_if_not_mapped(p_r, mapper)
end)
end)
|> Enum.map(&normalize_tuple/1)
end)
|> Enum.map(&elem(&1, 0))
|> Enum.min()
end)
end
defp normalize_tuple({a, b}), do: {a, b}
defp normalize_tuple({a, b, _}), do: {a, b}
defp split_if_not_mapped({a, b, c}, _), do: [{a, b, c}]
defp split_if_not_mapped({a, b}, mapper), do: split_range({a, b}, mapper)
def split_range(p_r, {{sl, sh}, {dl, dh}}) do
cond do
disjoint?(p_r, {sl, sh}) -> disjoint(p_r)
subset?(p_r, {sl, sh}) -> subset(p_r, {sl, sh}, {dl, dh})
superset?(p_r, {sl, sh}) -> superset(p_r, {sl, sh}, {dl, dh})
intersect_low?(p_r, {sl, sh}) -> intersect_low(p_r, {sl, sh}, {dl, dh})
intersect_hi?(p_r, {sl, sh}) -> intersect_hi(p_r, {sl, sh}, {dl, dh})
true -> raise "extra dimensional forces at play"
end
|> Enum.reject(&is_nil(&1))
|> Enum.sort(&(elem(&1, 0) <= elem(&2, 0)))
end
defp disjoint?({l, h}, {sl, sh}), do: h < sl or l > sh
defp disjoint?({l, h, _}, {sl, sh}), do: disjoint?({l, h}, {sl, sh})
defp disjoint(p_r), do: [p_r]
defp subset?({l, h}, {sl, sh}), do: l >= sl and h <= sh
defp subset?({l, h, _}, {sl, sh}), do: subset?({l, h}, {sl, sh})
defp subset({l, h}, {sl, sh}, {dl, dh}), do: [{dl + l - sl, h + dl - sl, :mapped}]
defp subset({l, h, flag}, {sl, sh}, {dl, dh}), do: [{l + sl - dl, h + sl - dl, flag}]
defp superset?({l, h}, {sl, sh}), do: subset?({sl, sh}, {l, h})
defp superset?({l, h, _}, {sl, sh}), do: subset?({sl, sh}, {l, h})
defp superset({l, h}, {sl, sh}, {dl, dh}), do: [{l, sl - 1}, {dl, dh, :mapped}, {sh + 1, h}]
defp superset({l, h, flag}, {sl, sh}, {dl, dh}),
do: [{l, sl - 1}, {dl, dh, flag}, {sh + 1, h}]
defp intersect_low?({l, h}, {sl, sh}), do: l < sl and h < sh
defp intersect_low?({l, h, _}, {sl, sh}), do: intersect_low?({l, h}, {sl, sh})
defp intersect_low({l, h}, {sl, sh}, {dl, dh}), do: [{l, sl - 1}, {dl, h + dl - sl, :mapped}]
defp intersect_low({l, h, _}, {sl, sh}, {dl, dh}),
do: [{l, sl - 1}, {dl, h + dl - sl, :mapped}]
defp intersect_hi?({l, h}, {sl, sh}), do: sl < l and sh < h
defp intersect_hi?({l, h, _}, {sl, sh}), do: intersect_hi?({l, h}, {sl, sh})
defp intersect_hi({l, h}, {sl, sh}, {dl, dh}), do: [{l + dl - sl, dh, :mapped}, {sh + 1, h}]
defp intersect_hi({l, h, _}, {sl, sh}, {dl, dh}),
do: [{l + dl - sl, dh, :mapped}, {sh + 1, h}]
defp parse(input) do
Part1.parse(input)
|> Enum.map(fn
{"seeds", seeds} ->
{"seeds", Enum.chunk_every(seeds, 2) |> Enum.map(fn [a, b] -> {a, a + b - 1} end)}
{k, v} ->
{k, do_ranges(v)}
end)
|> Enum.into(%{})
end
defp do_ranges(dsr_map, acc \\ [])
defp do_ranges([], acc), do: acc
defp do_ranges([[d, s, r] | rest], acc),
do: [{{s, s + r - 1}, {d, d + r - 1}} | do_ranges(rest, acc)]
end
1