🎁 - 2023 DAY 5 SOLUTIONS -🎁

# Day 5: If You Give a Seed a Fertilizer

Megathread guidelines

Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)

FAQ

What is this?: Here is a post with a large amount of details: programming.dev/post/6637268
Where do I participate?: adventofcode.com
Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: programming.dev/post/6631465

🔒This post will be unlocked when there is a decent amount of submissions on the leaderboard to avoid cheating for top spots

🔓 Unlocked after 27 mins (current record for time, hard one today)

Image

Image alternative text

iAvicenna, 6 months ago (edited 6 months ago)

Language: Python

solution

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

iAvicenna, 6 months ago

Started 4 days late so coming up from behind. Day 5 was the first solution I am somewhat proud of. I used interval arithmetics. I had to somewhat extend a class interval from pyinterval into something I called PointedInterval. In the end part 2 was completed in 0.32 seconds. It does not reverse engineer the solution starting from 0 location and inverse mapping until you find a seed (that was how I was initially planning to do it). It maps forward everything as intervals. There is a bit of a boiler plate which is in the utils file.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Massahud, 6 months ago

Language: Python

Github

Catching up missed days.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Gobbel2000, 6 months ago (edited 6 months ago)

Rust

Ooof. Part 1 was easy enough, but for part two I initially went with the naive solution of trying every single seed which took more than a minute (I never really measured). Although that got me the right answer, to me that was just unacceptable.

I proceeded to try and combine all mappings into one but gave up after spending way too much time on it.

Then I had the idea that the lowest number in the end must lie at the beginning of a range somewhere. Either the start of a seed range in the beginning or the start of a range in one of the mappings. Any in-between numbers must end up with a higher result. So I considered the start points of all ranges, went through the mappings in reverse to find out if that point is actually within a seed range, and only tested those starting points.

Finally I had only 183 points to test which ran much faster (0.9ms).

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

bamboo, 6 months ago

Then I had the idea that the lowest number in the end must lie at the beginning of a range somewhere. Either the start of a seed range in the beginning or the start of a range in one of the mappings.

This really helped me out. I was stuck on either trying every single seed, or working backwards and trying every single location from 0 to infinity, and couldn’t wrap my head around how to filter down the list to be manageable. Your comment made it all make sense.

In the end, was able to work backwards with the 172 lowest locations in each range to get potential seeds, and from there was able to get a short list of 89 valid seeds (including the original seed values) to then figure out which one has the shortest location.

Thanks!

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Treeniks, 6 months ago (edited 6 months ago)
I’m a little confused about this one. The mappings are total, that is any number that is not defined explicitly gets mapped to itself. So it’s easy to create an example where the lowest number does not get mentioned within a range:
seeds: 0 3

seed-to-soil map:
10 0 2

soil-to-fertilizer map:
100 200 5

fertilizer-to-water map:
100 200 5

water-to-light map:
100 200 5

light-to-temperature map:
100 200 5

temperature-to-humidity map:
100 200 5

humidity-to-location map:
100 200 5

Here, we have seeds 0, 1 and 2. seed 0 gets mapped to location 10, seed 1 gets mapped to location 11 and seed 2 gets mapped to location 2. That means location 2 would be the answer, but it’s not a start of any range. I guess this just doesn’t happen in any of the inputs?

EDIT: actually it’s double weird. If you implemented a backwards search, that is you create reverse mappings and then try out all locations (which is what I and many others did), the result of the above example is location 0, whereas if you create a forwards brute force of all seeds, the result is 2. For the reverse approach to work in all cases, the mappings would have to be bijective.
reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Gobbel2000, 6 months ago

Indeed, my solution fails on this input (returns 10, which is the location to seed 0), but it can be easily solved by also adding the ends of each range as well.

Maybe the input was quite forgiving. Thinking about it more, reversing the mapping can get quite involved, because it is neither surjective nor injective, so the inverse can actually have any number of results.

In your example there is no input that maps to 0, but there are two inputs that map to 11 (1 and 11). If the seed-to-soil map also included 10 20 2, 21 would also map to 11.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

morrowind, 6 months ago

CRYSTAL

finally solved part 2, and in just 1 second :)))


<span style="color:#323232;">Input = File.read("input.txt").lines
</span><span style="color:#323232;">
</span><span style="color:#323232;"># {source, destination}
</span><span style="color:#323232;">alias Map = Tuple(Range(Int64, Int64), Range(Int64, Int64))
</span><span style="color:#323232;">
</span><span style="color:#323232;">Maps = Array(Array(Map)).new(7)
</span><span style="color:#323232;">index = 1
</span><span style="color:#323232;">7.times do |i| 
</span><span style="color:#323232;">	a, index = get_ranges(index + 2)
</span><span style="color:#323232;">	Maps << a
</span><span style="color:#323232;">end
</span><span style="color:#323232;">
</span><span style="color:#323232;">part2
</span><span style="color:#323232;"># part1
</span><span style="color:#323232;">
</span><span style="color:#323232;">def part1()
</span><span style="color:#323232;">	seeds = Input[0].split(":")[1].split.map(&.to_i64)
</span><span style="color:#323232;">	locs = Array(Int64).new(7)
</span><span style="color:#323232;">	
</span><span style="color:#323232;">	seeds.each do |seed|
</span><span style="color:#323232;">		val = seed
</span><span style="color:#323232;">		Maps.each do |maplist|
</span><span style="color:#323232;">			maplist.each do |map|
</span><span style="color:#323232;">				if map[0].includes?(val)
</span><span style="color:#323232;">					val = map[1].begin + (val - map[0].begin)
</span><span style="color:#323232;">					break
</span><span style="color:#323232;">		end     end     end
</span><span style="color:#323232;">		locs << val
</span><span style="color:#323232;">	end
</span><span style="color:#323232;">	puts locs.min
</span><span style="color:#323232;">end
</span><span style="color:#323232;">
</span><span style="color:#323232;">def part2()
</span><span style="color:#323232;">	seeds = Input[0].split(":")[1].split.map(&.to_i64)
</span><span style="color:#323232;">	seeds = seeds.in_groups_of(2, 0).map { |a| a[0]..(a[0]+a[1]) }
</span><span style="color:#323232;">
</span><span style="color:#323232;">	found = false
</span><span style="color:#323232;">	loc = 0
</span><span style="color:#323232;">	until found 
</span><span style="color:#323232;">		val = loc
</span><span style="color:#323232;">		Maps.reverse_each do |maplist|
</span><span style="color:#323232;">			maplist.each do |map|
</span><span style="color:#323232;">				if map[1].includes?(val)
</span><span style="color:#323232;">					val = map[0].begin + (val - map[1].begin)
</span><span style="color:#323232;">					break
</span><span style="color:#323232;">		end     end     end
</span><span style="color:#323232;">
</span><span style="color:#323232;">		seeds.each { |seedrange| break if found = seedrange.includes?(val) }
</span><span style="color:#323232;">		loc += 1
</span><span style="color:#323232;">	end
</span><span style="color:#323232;">	puts loc - 1
</span><span style="color:#323232;">end
</span><span style="color:#323232;">
</span><span style="color:#323232;">def get_ranges(index : Int) : {Array(Map), Int32}
</span><span style="color:#323232;">	line = Input[index]
</span><span style="color:#323232;">	ranges = [] of Map
</span><span style="color:#323232;">	until line == ""
</span><span style="color:#323232;">		a, b, l = line.split.map(&.to_i64)
</span><span style="color:#323232;">		ranges << {b...(b+l), a...(a+l)}
</span><span style="color:#323232;">		
</span><span style="color:#323232;">		index += 1
</span><span style="color:#323232;">		break if index == Input.size
</span><span style="color:#323232;">		line = Input[index]
</span><span style="color:#323232;">	end
</span><span style="color:#323232;">	{ranges, index}
</span><span style="color:#323232;">end
</span>

soulsource, 6 months ago (edited 6 months ago)

[Language: Lean4]

I’ll only post the actual parsing and solution. I have written some helpers (in this case particularly relevant: Quicksort) which are in other files, as is the main function. For the full code, please see my github repo.

This one also ended up quite long, because I couldn’t resist to use different types for the different things, and to have the type checker confirm that I’m combining the maps between them in the correct order.

Also, I am not 100% certain that part 2 doesn’t have any off-by-one errors. I didn’t write any unit tests for it… The answer is correct though, so I probably didn’t mess it up too horribly. Also, it is pretty fast. Part 2 takes about 1.2 milliseconds on my machine, and this is including the file parsing (but not the loading of the file).

It seems my solution is too long for a single post though, so I’ll split off part 2 and post it separately.

Edit: There was a bug in the function that checks overlaps between ranges while parsing.

Parsing and Part 1Lean4 structure Seed where id : Nat deriving BEq, Ord, Repr structure Soil where id : Nat deriving BEq, Ord, Repr structure Fertilizer where id : Nat deriving BEq, Ord, Repr structure Water where id : Nat deriving BEq, Ord, Repr structure Light where id : Nat deriving BEq, Ord, Repr structure Temperature where id : Nat deriving BEq, Ord, Repr structure Humidity where id : Nat deriving BEq, Ord, Repr structure Location where id : Nat deriving BEq, Ord, Repr private class NatId (α : Type) where fromNat : Nat → α toNat : α → Nat private instance : NatId Seed where fromNat := Seed.mk toNat := Seed.id private instance : NatId Soil where fromNat := Soil.mk toNat := Soil.id private instance : NatId Fertilizer where fromNat := Fertilizer.mk toNat := Fertilizer.id private instance : NatId Water where fromNat := Water.mk toNat := Water.id private instance : NatId Light where fromNat := Light.mk toNat := Light.id private instance : NatId Temperature where fromNat := Temperature.mk toNat := Temperature.id private instance : NatId Humidity where fromNat := Humidity.mk toNat := Humidity.id private instance : NatId Location where fromNat := Location.mk toNat := Location.id private instance : Min Location where min a b := if Ord.compare a b == Ordering.lt then a else b structure Mapping (α β : Type) where inputStart : α outputStart : β length : Nat deriving Repr structure Mappings (α β : Type) where mappings : List $ Mapping α β deriving Repr private def Mapping.apply? {α β : Type} [NatId α] [NatId β] (mapping : Mapping α β) (input : α) : Option β := let input := NatId.toNat input let fromStart := NatId.toNat mapping.inputStart let toStart := NatId.toNat mapping.outputStart if input ≥ fromStart ∧ input < fromStart + mapping.length then some $ NatId.fromNat $ toStart + input - fromStart else none private def Mappings.apply {α β : Type} [NatId α] [NatId β] (mappings : Mappings α β) (input : α) : β := let applied := mappings.mappings.findSome? $ flip Mapping.apply? input applied.getD $ NatId.fromNat $ NatId.toNat input structure Almanach where seedsToSoil : Mappings Seed Soil soilToFertilizer : Mappings Soil Fertilizer fertilizerToWater : Mappings Fertilizer Water waterToLight : Mappings Water Light lightToTemperature : Mappings Light Temperature temperatureToHumidity : Mappings Temperature Humidity humidityToLocation : Mappings Humidity Location deriving Repr private def parseSeeds (input : String) : Option (List Seed) := if input.startsWith "seeds: " then let input := input.drop 7 let input := String.trim <$> input.split Char.isWhitespace let numbers := input.mapM String.toNat? List.map NatId.fromNat <$> numbers else none private def parseMapping {α β : Type} [NatId α] [NatId β] (input : String) : Option $ Mapping α β := do let input := String.trim <$> input.split Char.isWhitespace let nums ← input.mapM String.toNat? match nums with | [a,b,c] => some $ {inputStart := NatId.fromNat b, outputStart := NatId.fromNat a, length := c} | _ => none private def Mapping.overlap {α β : Type} [NatId α] [NatId β] (a : Mapping α β) (b : Mapping α β) : Bool := let aStart := NatId.toNat $ a.inputStart let aEnd := aStart + a.length let bStart := NatId.toNat $ b.inputStart let bEnd := bStart + b.length (bStart ≥ aStart && bStart < aEnd) || (bEnd > aStart && bEnd ≤ aEnd) || (aStart ≥ bStart && aStart < bEnd) || (aEnd > bStart && aEnd ≤ bEnd) private def parseMappings (α β : Type) [NatId α] [NatId β] (input : String) (header : String) : Option $ Mappings α β := if input.startsWith header then let lines := String.trim <$> input.splitOn “n” |> List.drop 1 |> List.filter (not ∘ String.isEmpty) let mappings := lines.mapM parseMapping let rec overlapHelper := λ (a : List $ Mapping α β) ↦ match a with | [] => false | a :: as => as.any (λ b ↦ a.overlap b) || overlapHelper as let mappings := mappings.filter $ not ∘ overlapHelper --make sure no ranges overlap. That would be faulty Mappings.mk <$> mappings else none def parse (input : String) : Option ((List Seed) × Almanach) := do let blocks := input.splitOn “nn” |> List.filter (not ∘ String.isEmpty) let blocks := String.trim <$> blocks if let [seeds, seedToSoil, soilToFertilizer, fertilizerToWater, waterToLight, lightToTemperature, temperatureToHumidity, humidityToLocation] := blocks then let seeds ← parseSeeds seeds let seedToSoil ← parseMappings Seed Soil seedToSoil “seed-to-soil map:” let soilToFertilizer ← parseMappings Soil Fertilizer soilToFertilizer “soil-to-fertilizer map:” let fertilizerToWater ← parseMappings Fertilizer Water fertilizerToWater “fertilizer-to-water map:” let waterToLight ← parseMappings Water Light waterToLight “water-to-light map:” let lightToTemperature ← parseMappings Light Temperature lightToTemperature “light-to-temperature map:” let temperatureToHumidity ← parseMappings Temperature Humidity temperatureToHumidity “temperature-to-humidity map:” let humidityToLocation ← parseMappings Humidity Location humidityToLocation “humidity-to-location map:” (seeds, { seedsToSoil := seedToSoil soilToFertilizer := soilToFertilizer fertilizerToWater := fertilizerToWater waterToLight := waterToLight lightToTemperature := lightToTemperature temperatureToHumidity := temperatureToHumidity humidityToLocation := humidityToLocation : Almanach}) else none def part1 (input : ((List Seed) × Almanach)) : Option Nat := let a := input.snd let seedToLocation := a.humidityToLocation.apply ∘ a.temperatureToHumidity.apply ∘ a.lightToTemperature.apply ∘ a.waterToLight.apply ∘ a.fertilizerToWater.apply ∘ a.soilToFertilizer.apply ∘ a.seedsToSoil.apply let locations := input.fst.map seedToLocation NatId.toNat <$> locations.minimum?

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

soulsource, 6 months ago

Part 2private structure Mapping2 (α β : Type) where start : α --okay, next time I do this, I’ll encode end and offset, not start and offset… offset : Int deriving Repr private structure Mappings2 (α β : Type) where mappings : List $ Mapping2 α β deriving Repr private def Mappings2.fromMappings {α β : Type} [NatId α] [NatId β] [Ord α] (input : Mappings α β) : Mappings2 α β := let input := input.mappings.quicksortBy λ a b ↦ (Ord.compare a.inputStart b.inputStart == Ordering.lt) let rec helper := λ | [] => [] | a :: [] => [{ start:= a.inputStart, offset := (NatId.toNat a.outputStart) - (NatId.toNat a.inputStart)}, {start:= NatId.fromNat (NatId.toNat a.inputStart + a.length), offset := 0}] | a :: b :: as => if (NatId.toNat b.inputStart) != (NatId.toNat a.inputStart + a.length) then { start:= a.inputStart, offset := (NatId.toNat a.outputStart) - (NatId.toNat a.inputStart)} :: { start:= NatId.fromNat (NatId.toNat a.inputStart + a.length), offset := 0} :: helper (b :: as) else { start:= a.inputStart, offset := (NatId.toNat a.outputStart) - (NatId.toNat a.inputStart)} :: helper (b :: as) let result := match input with | [] => [] | a :: _ => if NatId.toNat a.inputStart != 0 then { start:= NatId.fromNat 0, offset := 0 : Mapping2 α β} :: helper input else helper input Mappings2.mk result private def Mappings2.apply (α β : Type) [NatId α] [NatId β] [Ord α] (mapping : Mappings2 α β) (value : α) : β := let rec findOffsetHelper := λ | [] => 0 | a :: [] => a.offset | a :: b :: as => if (Ord.compare value b.start == Ordering.lt) then a.offset else findOffsetHelper (b :: as) let offset : Int := findOffsetHelper mapping.mappings let result : Int := (NatId.toNat value + offset) NatId.fromNat result.toNat private def Mappings2.combine {α β γ : Type} [NatId α] [NatId β] [NatId γ] (a : Mappings2 α β) (b : Mappings2 β γ) : Mappings2 α γ := – at this point, let’s just go integer let a : List (Int × Int) := a.mappings.map λ m ↦ (NatId.toNat m.start, m.offset) let b : List (Int × Int):= b.mappings.map λ m ↦ (NatId.toNat m.start, m.offset) let rec findOffsetHelper := λ (list : List (Int × Int)) (value : Int) ↦ match list with | [] => 0 | a :: [] => a.snd | a :: b :: as => if (value < b.fst) then a.snd else findOffsetHelper (b :: as) value let rec helper := λ | [] => b | a :: [] => let bOffsetAtA := findOffsetHelper b (a.fst + a.snd) let bRemainder := b.dropWhile (λ (bb : Int × Int) ↦ a.fst + a.snd > bb.fst) match bRemainder with | [] => [(a.fst, a.snd + bOffsetAtA)] | b :: _ => if b.fst - a.snd == a.fst then bRemainder.map λ (b : Int × Int) ↦ (b.fst - a.snd, a.snd + b.snd) else (a.fst, a.snd + bOffsetAtA) :: bRemainder.map λ (b : Int × Int) ↦ (b.fst - a.snd, a.snd + b.snd) | a :: aa :: as => let bOffsetAtA := findOffsetHelper b (a.fst + a.snd) let relevantBs := b.filter (λ (bb : Int × Int) ↦ a.fst + a.snd ≤ bb.fst && aa.fst + a.snd > bb.fst) match relevantBs with | [] => (a.fst, a.snd + bOffsetAtA) :: (helper (aa :: as)) | b :: _ => if b.fst - a.snd == a.fst then (relevantBs.map λ (b : Int × Int) ↦ (b.fst - a.snd, a.snd + b.snd)) ++ helper (aa :: as) else (a.fst, a.snd + bOffsetAtA) :: (relevantBs.map λ (b : Int × Int) ↦ (b.fst - a.snd, a.snd + b.snd)) ++ helper (aa :: as) let result := helper a Mappings2.mk $ result.map λ p ↦ { start := NatId.fromNat p.fst.toNat, offset := p.snd : Mapping2 α γ} private structure SeedRange where start : Seed ending : Seed deriving Repr private def SeedRange.fromList (input : List Seed) : List SeedRange := let rec helper : List Seed → List SeedRange := λ | [] => [] | _ :: [] => [] | a :: b :: as => { start := a, ending := Seed.mk $ b.id + a.id} :: SeedRange.fromList as (helper input).quicksortBy λ a b ↦ a.start.id < b.start.id private def SeedRange.findSmallestSeedAbove (seedRanges : List SeedRange) (value : Seed) : Option Seed := – two options: If the value is inside a seedRange, the value itself is the result – If not, the start of the first seedRange above the value is the result let rangeContains := λ r ↦ (Ord.compare r.start value != Ordering.gt) && (Ord.compare r.ending value == Ordering.gt) let rec helper := λ | [] => none | r :: rs => if rangeContains r then some value else if Ord.compare r.start value == Ordering.gt then r.start else helper rs helper seedRanges def part2 (input : ((List Seed) × Almanach)) : Option Nat := let a := input.snd let seedToLocation := Mappings2.fromMappings a.seedsToSoil |> flip Mappings2.combine (Mappings2.fromMappings a.soilToFertilizer) |> flip Mappings2.combine (Mappings2.fromMappings a.fertilizerToWater) |> flip Mappings2.combine (Mappings2.fromMappings a.waterToLight) |> flip Mappings2.combine (Mappings2.fromMappings a.lightToTemperature) |> flip Mappings2.combine (Mappings2.fromMappings a.temperatureToHumidity) |> flip Mappings2.combine (Mappings2.fromMappings a.humidityToLocation) let seedRanges := SeedRange.fromList input.fst let potentialSeeds := seedToLocation.mappings.filterMap λ m ↦ (SeedRange.findSmallestSeedAbove seedRanges m.start) – could filter by range end, but who cares? let locations := potentialSeeds.map seedToLocation.apply NatId.toNat <$> locations.minimum?

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Adanisi, 6 months ago

Honestly this one was quite easy for me. Not so much for my computer though…

git.sr.ht/~aidenisik/aoc23/tree/master/item/day5

C solutions. Disclaimer, part 2 has not finished running. But it’s mostly the same code as part 1 and it works on the small sample data so it’ll be fine.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Adramis, 6 months ago

Disclaimer, part 2 has not finished running. But it’s mostly the same code as part 1 and it works on the small sample data so it’ll be fine.

RIP?

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Adanisi, 6 months ago

Still running :)

I don’t have the most powerful hardware unfortunately

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

hades, 6 months ago

Python

Questions and feedback welcome!


<span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">portion </span><span style="font-weight:bold;color:#a71d5d;">as </span><span style="color:#323232;">P
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">from .</span><span style="color:#323232;">solver </span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">Solver
</span><span style="color:#323232;">
</span><span style="color:#323232;">_maps </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[
</span><span style="color:#323232;">  </span><span style="color:#183691;">'seed-to-soil'</span><span style="color:#323232;">,
</span><span style="color:#323232;">  </span><span style="color:#183691;">'soil-to-fertilizer'</span><span style="color:#323232;">,
</span><span style="color:#323232;">  </span><span style="color:#183691;">'fertilizer-to-water'</span><span style="color:#323232;">,
</span><span style="color:#323232;">  </span><span style="color:#183691;">'water-to-light'</span><span style="color:#323232;">,
</span><span style="color:#323232;">  </span><span style="color:#183691;">'light-to-temperature'</span><span style="color:#323232;">,
</span><span style="color:#323232;">  </span><span style="color:#183691;">'temperature-to-humidity'</span><span style="color:#323232;">,
</span><span style="color:#323232;">  </span><span style="color:#183691;">'humidity-to-location'</span><span style="color:#323232;">,
</span><span style="color:#323232;">]
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">group_lines_in_maps</span><span style="color:#323232;">(lines):
</span><span style="color:#323232;">  group </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[]
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">line </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">lines:
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">if not </span><span style="color:#323232;">line:
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">yield </span><span style="color:#323232;">group
</span><span style="color:#323232;">      group </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[]
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">continue
</span><span style="color:#323232;">    group.append(line)
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">yield </span><span style="color:#323232;">group
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">class </span><span style="color:#0086b3;">Day05</span><span style="color:#323232;">(</span><span style="color:#0086b3;">Solver</span><span style="color:#323232;">):
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#62a35c;">__init__</span><span style="color:#323232;">(self):
</span><span style="color:#323232;">    </span><span style="color:#62a35c;">super</span><span style="color:#323232;">().</span><span style="color:#62a35c;">__init__</span><span style="color:#323232;">(</span><span style="color:#0086b3;">5</span><span style="color:#323232;">)
</span><span style="color:#323232;">    self.seeds </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[]
</span><span style="color:#323232;">    self.mappings </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">{}
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">presolve</span><span style="color:#323232;">(self, input: </span><span style="color:#0086b3;">str</span><span style="color:#323232;">):
</span><span style="color:#323232;">    lines </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">input</span><span style="color:#323232;">.rstrip().split(</span><span style="color:#183691;">'</span><span style="color:#0086b3;">n</span><span style="color:#183691;">'</span><span style="color:#323232;">)
</span><span style="color:#323232;">    self.seeds </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">list</span><span style="color:#323232;">(</span><span style="color:#62a35c;">map</span><span style="color:#323232;">(</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, lines[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].split(</span><span style="color:#183691;">' '</span><span style="color:#323232;">)[</span><span style="color:#0086b3;">1</span><span style="color:#323232;">:]))
</span><span style="color:#323232;">    self.mappings </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">{}
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">mapping </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">group_lines_in_maps(lines[</span><span style="color:#0086b3;">2</span><span style="color:#323232;">:]):
</span><span style="color:#323232;">      mapping_name </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">mapping[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].split(</span><span style="color:#183691;">' '</span><span style="color:#323232;">)[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">]
</span><span style="color:#323232;">      mapping_ranges </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">map</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">lambda </span><span style="color:#323232;">rng: </span><span style="color:#0086b3;">tuple</span><span style="color:#323232;">(</span><span style="color:#62a35c;">map</span><span style="color:#323232;">(</span><span style="color:#0086b3;">int</span><span style="color:#323232;">, rng.split(</span><span style="color:#183691;">' '</span><span style="color:#323232;">))), mapping[</span><span style="color:#0086b3;">1</span><span style="color:#323232;">:])
</span><span style="color:#323232;">      self.mappings[mapping_name] </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">list</span><span style="color:#323232;">(mapping_ranges)
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">solve_first_star</span><span style="color:#323232;">(self):
</span><span style="color:#323232;">    locations </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">[]
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">seed </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">self.seeds:
</span><span style="color:#323232;">      location </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">seed
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">mapping </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#62a35c;">map</span><span style="color:#323232;">(self.mappings.get, _maps):
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">assert </span><span style="color:#323232;">mapping
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">dest, source, length </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">mapping:
</span><span style="color:#323232;">          </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#0086b3;">0 </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;</span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">location </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">source </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; length:
</span><span style="color:#323232;">            location </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">dest </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">(location </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">source)
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">break
</span><span style="color:#323232;">      locations.append(location)
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#62a35c;">min</span><span style="color:#323232;">(locations)
</span><span style="color:#323232;">
</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#323232;">solve_second_star</span><span style="color:#323232;">(self):
</span><span style="color:#323232;">    current_set </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">P.empty()
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">i </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#62a35c;">range</span><span style="color:#323232;">(</span><span style="color:#0086b3;">0</span><span style="color:#323232;">, </span><span style="color:#62a35c;">len</span><span style="color:#323232;">(self.seeds), </span><span style="color:#0086b3;">2</span><span style="color:#323232;">):
</span><span style="color:#323232;">      current_set </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">current_set </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">P.closedopen(self.seeds[i], self.seeds[i] </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">self.seeds[i </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#0086b3;">1</span><span style="color:#323232;">])
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">mapping </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#62a35c;">map</span><span style="color:#323232;">(self.mappings.get, _maps):
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">assert </span><span style="color:#323232;">mapping
</span><span style="color:#323232;">      unmapped </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">current_set
</span><span style="color:#323232;">      next_set </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">P.empty()
</span><span style="color:#323232;">      </span><span style="font-weight:bold;color:#a71d5d;">for </span><span style="color:#323232;">dest, source, length </span><span style="font-weight:bold;color:#a71d5d;">in </span><span style="color:#323232;">mapping:
</span><span style="color:#323232;">        delta </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">dest </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">source
</span><span style="color:#323232;">        source_range </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">P.closedopen(source, source </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">length)
</span><span style="color:#323232;">        mappable </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">unmapped </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp; source_range
</span><span style="color:#323232;">        mapped_to_destination </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">mappable.apply(
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">lambda </span><span style="color:#323232;">x: (x.left, x.lower </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">delta, x.upper </span><span style="font-weight:bold;color:#a71d5d;">+ </span><span style="color:#323232;">delta, x.right))  </span><span style="font-style:italic;color:#969896;"># pylint: disable=cell-var-from-loop
</span><span style="color:#323232;">        next_set </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">next_set </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">mapped_to_destination
</span><span style="color:#323232;">        unmapped </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">unmapped </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">source_range
</span><span style="color:#323232;">      current_set </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">next_set </span><span style="font-weight:bold;color:#a71d5d;">| </span><span style="color:#323232;">unmapped
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#62a35c;">next</span><span style="color:#323232;">(P.iterate(current_set, step</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#0086b3;">1</span><span style="color:#323232;">))
</span>

cacheson, 6 months ago

Nim

Woof. Part 1 was simple enough. I thought I could adapt my solution to part 2 pretty easily, just add all the values in the ranges to the starting set. Worked fine for the example, but the ranges for the actual input are too large. Ended up taking 16gb of RAM and crunching forever.

I finally abandoned my quick and dirty approach when rewriting part 2, and made some proper types and functions. Treated each range as an object, and used set operations on them. The difference operation tends to fragment the range that it's used on, so I meant to write some code to defragment the ranges after each round of mappings. Forgot to do so, but the code ran quick enough this time anyway.

Day 5, part 1

Day 5, part 2 first attempt

Day 5, part 2 rewrite

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

janAkali, 6 months ago

Treated each range as an object, and used set operations on them

That’s smart. Honestly, I don’t understand how it works. 😅

The difference operation tends to fragment the range that it’s used on, so I meant to write some code to defragment the ranges after each round of mappings. Forgot to do so, but the code ran quick enough this time anyway.

I’ve got different solution from yours, but this part is the same, lol. My code slices the ranges into 1-3 parts on each step, so I also planned to ‘defragment’ them. But performance is plenty without this step, ~450 microseconds for both parts on my PC.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cacheson, 6 months ago

Treated each range as an object, and used set operations on them

That’s smart. Honestly, I don’t understand how it works. 😅

"Set operations" should probably be in quotes. I just mean that I implemented the * (intersection) and - (difference) operators for my ValueRange type. The intersection operator works like it does for sets, just returning the overlap. The difference operator has to work a little differently, because ranges have to be contiguous, whereas sets don't, so it returns a sequence of ValueRange objects.

My ValueMapping type uses a ValueRange for it's source, so applying it to a range just involves using the intersection operator to determine what part of the range needs to move, and the difference operator to determine which parts are left.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

janAkali, 6 months ago (edited 6 months ago)

Well, then we have the same solution but coded very differently. Here’s mine.

ruleApplied is one function with almost all logic. I take a range and compare it to a rule’s source range (50 98 2 is a rule). Overlaps get transformed and collected into the first sequence and everything that left goes in the second. I need two seqs there, for transformed values to skip next rules in the same map.

Repeat for each rule and each map (seq[Rule]). And presto, it’s working!

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cacheson, 6 months ago

Yeah, roughly the same idea. I guess I could have just used HSlice for my range type, I thought maybe there was some special magic to it.

It looks like your if-else ladder misses a corner case, where one range only intersects with the first or last element of the other. Switching to <= and >= for those should take care of it though.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

janAkali, 6 months ago

Thank you, should be fixed now.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

bugsmith, 6 months ago

Like many others, I really didn’t enjoy this one. I particularly struggled with part 02, which ended up with me just brute forcing it and checking each seed. On my system it took over 15 minutes to run, which is truly awful. I’m open to pointers on how I could better have solved part two.

Solution in Rust 🦀

Formatted Solution on GitLab

::: spoiler Code


<span style="font-weight:bold;color:#a71d5d;">use </span><span style="color:#323232;">std::{
</span><span style="color:#323232;">    env, fs,
</span><span style="color:#323232;">    io::{self, BufReader, Read},
</span><span style="color:#323232;">};
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">main</span><span style="color:#323232;">() -> io::Result</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;()</span><span style="font-weight:bold;color:#a71d5d;">> </span><span style="color:#323232;">{
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> args: </span><span style="color:#0086b3;">Vec </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">env::args().</span><span style="color:#62a35c;">collect</span><span style="color:#323232;">();
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> filename </span><span style="font-weight:bold;color:#a71d5d;">= &</span><span style="color:#323232;">amp;args[</span><span style="color:#0086b3;">1</span><span style="color:#323232;">];
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> file1 </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">fs::File::open(filename)</span><span style="font-weight:bold;color:#a71d5d;">?</span><span style="color:#323232;">;
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> file2 </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">fs::File::open(filename)</span><span style="font-weight:bold;color:#a71d5d;">?</span><span style="color:#323232;">;
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> reader1 </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">BufReader::new(file1);
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> reader2 </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#323232;">BufReader::new(file2);
</span><span style="color:#323232;">
</span><span style="color:#323232;">    println!(</span><span style="color:#183691;">"Part one: </span><span style="color:#0086b3;">{}</span><span style="color:#183691;">"</span><span style="color:#323232;">, </span><span style="color:#62a35c;">process_part_one</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut</span><span style="color:#323232;"> reader1));
</span><span style="color:#323232;">    println!(</span><span style="color:#183691;">"Part two: </span><span style="color:#0086b3;">{}</span><span style="color:#183691;">"</span><span style="color:#323232;">, </span><span style="color:#62a35c;">process_part_two</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut</span><span style="color:#323232;"> reader2));
</span><span style="color:#323232;">    </span><span style="color:#0086b3;">Ok</span><span style="color:#323232;">(())
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">#[derive(Debug)]
</span><span style="font-weight:bold;color:#a71d5d;">struct </span><span style="color:#323232;">Map {
</span><span style="color:#323232;">    lines: Vec,
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">impl </span><span style="color:#323232;">Map {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">map_to_lines</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;self, key: </span><span style="font-weight:bold;color:#a71d5d;">u32</span><span style="color:#323232;">) -> </span><span style="font-weight:bold;color:#a71d5d;">u32 </span><span style="color:#323232;">{
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> line </span><span style="font-weight:bold;color:#a71d5d;">in &</span><span style="color:#323232;">amp;self.lines {
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;"> line.</span><span style="color:#62a35c;">in_range</span><span style="color:#323232;">(key) {
</span><span style="color:#323232;">                </span><span style="font-weight:bold;color:#a71d5d;">return</span><span style="color:#323232;"> line.</span><span style="color:#62a35c;">map</span><span style="color:#323232;">(key);
</span><span style="color:#323232;">            }
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">        key
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">#[derive(Debug)]
</span><span style="font-weight:bold;color:#a71d5d;">struct </span><span style="color:#323232;">MapLine {
</span><span style="color:#323232;">    dest_range: </span><span style="font-weight:bold;color:#a71d5d;">u32</span><span style="color:#323232;">,
</span><span style="color:#323232;">    source_range: </span><span style="font-weight:bold;color:#a71d5d;">u32</span><span style="color:#323232;">,
</span><span style="color:#323232;">    range_length: </span><span style="font-weight:bold;color:#a71d5d;">u32</span><span style="color:#323232;">,
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">impl </span><span style="color:#323232;">MapLine {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">map</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;self, key: </span><span style="font-weight:bold;color:#a71d5d;">u32</span><span style="color:#323232;">) -> </span><span style="font-weight:bold;color:#a71d5d;">u32 </span><span style="color:#323232;">{
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> diff </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> key </span><span style="font-weight:bold;color:#a71d5d;">- </span><span style="color:#323232;">self.source_range;
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if </span><span style="color:#323232;">self.dest_range </span><span style="font-weight:bold;color:#a71d5d;">as i64 +</span><span style="color:#323232;"> diff </span><span style="font-weight:bold;color:#a71d5d;">as i64 > </span><span style="color:#0086b3;">0 </span><span style="color:#323232;">{
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">return </span><span style="color:#323232;">(self.dest_range </span><span style="font-weight:bold;color:#a71d5d;">as i64 +</span><span style="color:#323232;"> diff </span><span style="font-weight:bold;color:#a71d5d;">as i64</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">as u32</span><span style="color:#323232;">;
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">        key
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">in_range</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;self, key: </span><span style="font-weight:bold;color:#a71d5d;">u32</span><span style="color:#323232;">) -> </span><span style="font-weight:bold;color:#a71d5d;">bool </span><span style="color:#323232;">{
</span><span style="color:#323232;">        self.source_range </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;</span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> key
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp; (key </span><span style="font-weight:bold;color:#a71d5d;">as i64</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt; self.source_range </span><span style="font-weight:bold;color:#a71d5d;">as i64 + </span><span style="color:#323232;">self.range_length </span><span style="font-weight:bold;color:#a71d5d;">as i64
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">parse_input</span><span style="color:#323232;">(reader: </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut</span><span style="color:#323232;"> BufReader) -> (Vec, Vec<map>) {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> almanac </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">String</span><span style="color:#323232;">::new();
</span><span style="color:#323232;">    reader
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">read_to_string</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut</span><span style="color:#323232;"> almanac)
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"read successful"</span><span style="color:#323232;">);
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> parts: </span><span style="color:#0086b3;">Vec</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">str> =</span><span style="color:#323232;"> almanac.</span><span style="color:#62a35c;">split</span><span style="color:#323232;">(</span><span style="color:#183691;">"</span><span style="color:#0086b3;">nn</span><span style="color:#183691;">"</span><span style="color:#323232;">).</span><span style="color:#62a35c;">collect</span><span style="color:#323232;">();
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let </span><span style="color:#323232;">(seeds, others) </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> parts.</span><span style="color:#62a35c;">split_first</span><span style="color:#323232;">().</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"at least one part"</span><span style="color:#323232;">);
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> seeds: </span><span style="color:#0086b3;">Vec</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;</span><span style="font-weight:bold;color:#a71d5d;">_> =</span><span style="color:#323232;"> seeds
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">split</span><span style="color:#323232;">(</span><span style="color:#183691;">": "</span><span style="color:#323232;">)
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">last</span><span style="color:#323232;">()
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"at least one"</span><span style="color:#323232;">)
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">split_whitespace</span><span style="color:#323232;">()
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">map</span><span style="color:#323232;">(|s| s.</span><span style="color:#62a35c;">to_string</span><span style="color:#323232;">())
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">collect</span><span style="color:#323232;">();
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> maps: </span><span style="color:#0086b3;">Vec</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;</span><span style="font-weight:bold;color:#a71d5d;">_> =</span><span style="color:#323232;"> others
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">iter</span><span style="color:#323232;">()
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">map</span><span style="color:#323232;">(|item| {
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> lines_iter </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> item
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">split</span><span style="color:#323232;">(</span><span style="color:#183691;">':'</span><span style="color:#323232;">)
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">last</span><span style="color:#323232;">()
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"exists"</span><span style="color:#323232;">)
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">trim</span><span style="color:#323232;">()
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">split</span><span style="color:#323232;">(</span><span style="color:#183691;">'</span><span style="color:#0086b3;">n</span><span style="color:#183691;">'</span><span style="color:#323232;">)
</span><span style="color:#323232;">                .</span><span style="color:#62a35c;">map</span><span style="color:#323232;">(|nums| {
</span><span style="color:#323232;">                    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> nums_split </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> nums.</span><span style="color:#62a35c;">split_whitespace</span><span style="color:#323232;">().collect::</span><span style="font-weight:bold;color:#a71d5d;">></span><span style="color:#323232;">();
</span><span style="color:#323232;">                    MapLine {
</span><span style="color:#323232;">                        dest_range: nums_split[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].</span><span style="color:#62a35c;">parse</span><span style="color:#323232;">().</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"is digit"</span><span style="color:#323232;">),
</span><span style="color:#323232;">                        source_range: nums_split[</span><span style="color:#0086b3;">1</span><span style="color:#323232;">].</span><span style="color:#62a35c;">parse</span><span style="color:#323232;">().</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"is digit"</span><span style="color:#323232;">),
</span><span style="color:#323232;">                        range_length: nums_split[</span><span style="color:#0086b3;">2</span><span style="color:#323232;">].</span><span style="color:#62a35c;">parse</span><span style="color:#323232;">().</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"is digit"</span><span style="color:#323232;">),
</span><span style="color:#323232;">                    }
</span><span style="color:#323232;">                });
</span><span style="color:#323232;">            Map {
</span><span style="color:#323232;">                lines: lines_iter.</span><span style="color:#62a35c;">collect</span><span style="color:#323232;">(),
</span><span style="color:#323232;">            }
</span><span style="color:#323232;">        })
</span><span style="color:#323232;">        .</span><span style="color:#62a35c;">collect</span><span style="color:#323232;">();
</span><span style="color:#323232;">    (seeds, maps)
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">process_part_one</span><span style="color:#323232;">(reader: </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut</span><span style="color:#323232;"> BufReader) -> </span><span style="font-weight:bold;color:#a71d5d;">u32 </span><span style="color:#323232;">{
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let </span><span style="color:#323232;">(seeds, maps) </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">parse_input</span><span style="color:#323232;">(reader);
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> res </span><span style="font-weight:bold;color:#a71d5d;">= u32</span><span style="color:#323232;">::</span><span style="color:#0086b3;">MAX</span><span style="color:#323232;">;
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> seed </span><span style="font-weight:bold;color:#a71d5d;">in &</span><span style="color:#323232;">amp;seeds {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> val </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> seed.parse::().</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"is digits"</span><span style="color:#323232;">);
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> map </span><span style="font-weight:bold;color:#a71d5d;">in &</span><span style="color:#323232;">amp;maps {
</span><span style="color:#323232;">            val </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> map.</span><span style="color:#62a35c;">map_to_lines</span><span style="color:#323232;">(val);
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">        res </span><span style="font-weight:bold;color:#a71d5d;">= u32</span><span style="color:#323232;">::min(res, val);
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">    res
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">process_part_two</span><span style="color:#323232;">(reader: </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut</span><span style="color:#323232;"> BufReader) -> </span><span style="font-weight:bold;color:#a71d5d;">u32 </span><span style="color:#323232;">{
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let </span><span style="color:#323232;">(seeds, maps) </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#62a35c;">parse_input</span><span style="color:#323232;">(reader);
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> seed_chunks: </span><span style="color:#0086b3;">Vec</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">lt;</span><span style="font-weight:bold;color:#a71d5d;">_> =</span><span style="color:#323232;"> seeds.</span><span style="color:#62a35c;">chunks</span><span style="color:#323232;">(</span><span style="color:#0086b3;">2</span><span style="color:#323232;">).</span><span style="color:#62a35c;">collect</span><span style="color:#323232;">();
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> res </span><span style="font-weight:bold;color:#a71d5d;">= u32</span><span style="color:#323232;">::</span><span style="color:#0086b3;">MAX</span><span style="color:#323232;">;
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> chunk </span><span style="font-weight:bold;color:#a71d5d;">in</span><span style="color:#323232;"> seed_chunks {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> range_start: </span><span style="font-weight:bold;color:#a71d5d;">u32 =</span><span style="color:#323232;"> chunk[</span><span style="color:#0086b3;">0</span><span style="color:#323232;">].</span><span style="color:#62a35c;">parse</span><span style="color:#323232;">().</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"is digits"</span><span style="color:#323232;">);
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> range_length: </span><span style="font-weight:bold;color:#a71d5d;">u32 =</span><span style="color:#323232;"> chunk[</span><span style="color:#0086b3;">1</span><span style="color:#323232;">].</span><span style="color:#62a35c;">parse</span><span style="color:#323232;">().</span><span style="color:#62a35c;">expect</span><span style="color:#323232;">(</span><span style="color:#183691;">"is digits"</span><span style="color:#323232;">);
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> range_end: </span><span style="font-weight:bold;color:#a71d5d;">u32 =</span><span style="color:#323232;"> range_start </span><span style="font-weight:bold;color:#a71d5d;">+</span><span style="color:#323232;"> range_length;
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> seed </span><span style="font-weight:bold;color:#a71d5d;">in</span><span style="color:#323232;"> range_start</span><span style="font-weight:bold;color:#a71d5d;">..</span><span style="color:#323232;">range_end {
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">let mut</span><span style="color:#323232;"> val </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> seed;
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">for</span><span style="color:#323232;"> map </span><span style="font-weight:bold;color:#a71d5d;">in &</span><span style="color:#323232;">amp;maps {
</span><span style="color:#323232;">                val </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> map.</span><span style="color:#62a35c;">map_to_lines</span><span style="color:#323232;">(val);
</span><span style="color:#323232;">            }
</span><span style="color:#323232;">            res </span><span style="font-weight:bold;color:#a71d5d;">= u32</span><span style="color:#323232;">::min(res, val);
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">    res
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">#[cfg(test)]
</span><span style="font-weight:bold;color:#a71d5d;">mod </span><span style="color:#323232;">tests {
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">use super</span><span style="color:#323232;">::</span><span style="font-weight:bold;color:#a71d5d;">*</span><span style="color:#323232;">;
</span><span style="color:#323232;">
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">const </span><span style="color:#0086b3;">INPUT</span><span style="color:#323232;">: </span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">str = </span><span style="color:#183691;">"seeds: 79 14 55 13
</span><span style="color:#183691;">
</span><span style="color:#183691;">seed-to-soil map:
</span><span style="color:#183691;">50 98 2
</span><span style="color:#183691;">52 50 48
</span><span style="color:#183691;">
</span><span style="color:#183691;">soil-to-fertilizer map:
</span><span style="color:#183691;">0 15 37
</span><span style="color:#183691;">37 52 2
</span><span style="color:#183691;">39 0 15
</span><span style="color:#183691;">
</span><span style="color:#183691;">fertilizer-to-water map:
</span><span style="color:#183691;">49 53 8
</span><span style="color:#183691;">0 11 42
</span><span style="color:#183691;">42 0 7
</span><span style="color:#183691;">57 7 4
</span><span style="color:#183691;">
</span><span style="color:#183691;">water-to-light map:
</span><span style="color:#183691;">88 18 7
</span><span style="color:#183691;">18 25 70
</span><span style="color:#183691;">
</span><span style="color:#183691;">light-to-temperature map:
</span><span style="color:#183691;">45 77 23
</span><span style="color:#183691;">81 45 19
</span><span style="color:#183691;">68 64 13
</span><span style="color:#183691;">
</span><span style="color:#183691;">temperature-to-humidity map:
</span><span style="color:#183691;">0 69 1
</span><span style="color:#183691;">1 0 69
</span><span style="color:#183691;">
</span><span style="color:#183691;">humidity-to-location map:
</span><span style="color:#183691;">60 56 37
</span><span style="color:#183691;">56 93 4"</span><span style="color:#323232;">;
</span><span style="color:#323232;">
</span><span style="color:#323232;">    #[test]
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">test_process_part_one</span><span style="color:#323232;">() {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> input_bytes </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">INPUT</span><span style="color:#323232;">.</span><span style="color:#62a35c;">as_bytes</span><span style="color:#323232;">();
</span><span style="color:#323232;">        assert_eq!(</span><span style="color:#0086b3;">35</span><span style="color:#323232;">, </span><span style="color:#62a35c;">process_part_one</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut </span><span style="color:#323232;">BufReader::new(input_bytes)));
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    #[test]
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">fn </span><span style="font-weight:bold;color:#795da3;">test_process_part_two</span><span style="color:#323232;">() {
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">let</span><span style="color:#323232;"> input_bytes </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">INPUT</span><span style="color:#323232;">.</span><span style="color:#62a35c;">as_bytes</span><span style="color:#323232;">();
</span><span style="color:#323232;">        assert_eq!(</span><span style="color:#0086b3;">46</span><span style="color:#323232;">, </span><span style="color:#62a35c;">process_part_two</span><span style="color:#323232;">(</span><span style="font-weight:bold;color:#a71d5d;">&</span><span style="color:#323232;">amp;</span><span style="font-weight:bold;color:#a71d5d;">mut </span><span style="color:#323232;">BufReader::new(input_bytes)));
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">}
</span>

:::</map>

bamboo, 6 months ago

I got far enough to realize that you probably needed to work backwards and given a location, determine the accompanying seed, and then check if that seed is one of the ones listed in the range. Still though, starting at 0 for location and working up was taking forever to find the first valid seed

Someone in this thread pointed out that if you picked the first value of each range in the map, working backwards from those points will get you a short list of seeds which map to low values. You then check if those seeds are valid, and also check the location of the first seeds in the range (the rest of the seeds in the range don’t matter because those are covered by the first check). This ends up with about 200 locations which you can sort, to get the lowest value.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

walter_wiggles, 6 months ago

I tried brute forcing it but couldn’t get the process to finish. Iterating through hundreds of millions of seeds is no bueno.

After reading your comment though I got the idea to map whole seed ranges instead of individual seeds. That finished in no time of course.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

kartoffelsaft, 6 months ago (edited 6 months ago)

Odin

When I read the problem description I expected the input to also be 2 digit numbers. When I looked at it I just had to say “huh.”

Second part I think you definitely have to do in reverse (edit: if you are doing a linear search for the answer), as that allows you to nope out as soon as you find a match, whereas with doing it forward you have to keep checking just in case.

Formatted code


<span style="color:#323232;">package day5
</span><span style="color:#323232;">
</span><span style="color:#323232;">import "core:fmt"
</span><span style="color:#323232;">import "core:strings"
</span><span style="color:#323232;">import "core:slice"
</span><span style="color:#323232;">import "core:strconv"
</span><span style="color:#323232;">
</span><span style="color:#323232;">Range :: struct {
</span><span style="color:#323232;">    dest: int,
</span><span style="color:#323232;">    src: int,
</span><span style="color:#323232;">    range: int,
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">Mapper :: struct {
</span><span style="color:#323232;">    ranges: []Range,
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">parse_range :: proc(s: string) -> (ret: Range) {
</span><span style="color:#323232;">    rest := s
</span><span style="color:#323232;">
</span><span style="color:#323232;">    parseLen := -1
</span><span style="color:#323232;">
</span><span style="color:#323232;">    destOk: bool
</span><span style="color:#323232;">    ret.dest, destOk = strconv.parse_int(rest, 10, &amp;parseLen)
</span><span style="color:#323232;">    rest = strings.trim_left_space(rest[parseLen:])
</span><span style="color:#323232;">
</span><span style="color:#323232;">    srcOk: bool
</span><span style="color:#323232;">    ret.src, srcOk = strconv.parse_int(rest, 10, &amp;parseLen)
</span><span style="color:#323232;">    rest = strings.trim_left_space(rest[parseLen:])
</span><span style="color:#323232;">
</span><span style="color:#323232;">    rangeOk: bool
</span><span style="color:#323232;">    ret.range, rangeOk = strconv.parse_int(rest, 10, &amp;parseLen)
</span><span style="color:#323232;">
</span><span style="color:#323232;">    return
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">parse_mapper :: proc(ss: []string) -> (ret: Mapper) {
</span><span style="color:#323232;">    ret.ranges = make([]Range, len(ss)-1)
</span><span style="color:#323232;">    for s, i in ss[1:] {
</span><span style="color:#323232;">        ret.ranges[i] = parse_range(s)
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    return
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">parse_mappers :: proc(ss: []string) -> []Mapper {
</span><span style="color:#323232;">    mapsStr := make([dynamic][]string)
</span><span style="color:#323232;">    defer delete(mapsStr)
</span><span style="color:#323232;">
</span><span style="color:#323232;">    restOfLines := ss
</span><span style="color:#323232;">    isLineEmpty :: proc(s: string)->bool {return len(s)==0}
</span><span style="color:#323232;">
</span><span style="color:#323232;">    for i, found := slice.linear_search_proc(restOfLines, isLineEmpty); 
</span><span style="color:#323232;">        found; 
</span><span style="color:#323232;">        i, found  = slice.linear_search_proc(restOfLines, isLineEmpty) {
</span><span style="color:#323232;">        
</span><span style="color:#323232;">        append(&amp;mapsStr, restOfLines[:i])
</span><span style="color:#323232;">        restOfLines = restOfLines[i+1:]
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">    append(&amp;mapsStr, restOfLines[:])
</span><span style="color:#323232;">
</span><span style="color:#323232;">    return slice.mapper(mapsStr[1:], parse_mapper)
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">apply_mapper :: proc(mapper: Mapper, num: int) -> int {
</span><span style="color:#323232;">    for r in mapper.ranges {
</span><span style="color:#323232;">        if num >= r.src &amp;&amp; num - r.src &lt; r.range do return num - r.src + r.dest
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    return num
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">p1 :: proc(input: []string) {
</span><span style="color:#323232;">    maps := parse_mappers(input)
</span><span style="color:#323232;">    defer {
</span><span style="color:#323232;">        for m in maps do delete(m.ranges)
</span><span style="color:#323232;">        delete(maps)
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    restSeeds := input[0][len("seeds: "):]
</span><span style="color:#323232;">    min := 0x7fffffff
</span><span style="color:#323232;">
</span><span style="color:#323232;">    for len(restSeeds) > 0 {
</span><span style="color:#323232;">        seedLen := -1
</span><span style="color:#323232;">        seed, seedOk := strconv.parse_int(restSeeds, 10, &amp;seedLen)
</span><span style="color:#323232;">        restSeeds = strings.trim_left_space(restSeeds[seedLen:])
</span><span style="color:#323232;">
</span><span style="color:#323232;">        fmt.print(seed)
</span><span style="color:#323232;">        for m in maps {
</span><span style="color:#323232;">            seed = apply_mapper(m, seed)
</span><span style="color:#323232;">            fmt.print(" ->", seed)
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">        fmt.println()
</span><span style="color:#323232;">
</span><span style="color:#323232;">        if seed &lt; min do min = seed
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    fmt.println(min)
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">apply_mapper_reverse :: proc(mapper: Mapper, num: int) -> int {
</span><span style="color:#323232;">    for r in mapper.ranges {
</span><span style="color:#323232;">        if num >= r.dest &amp;&amp; num - r.dest &lt; r.range do return num - r.dest + r.src
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    return num
</span><span style="color:#323232;">}
</span><span style="color:#323232;">
</span><span style="color:#323232;">p2 :: proc(input: []string) {
</span><span style="color:#323232;">    SeedRange :: struct {
</span><span style="color:#323232;">        start: int,
</span><span style="color:#323232;">        len: int,
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    seeds := make([dynamic]SeedRange)
</span><span style="color:#323232;">    restSeeds := input[0][len("seeds: "):]
</span><span style="color:#323232;">
</span><span style="color:#323232;">    for len(restSeeds) > 0 {
</span><span style="color:#323232;">        seedLen := -1
</span><span style="color:#323232;">        seedS, seedSOk := strconv.parse_int(restSeeds, 10, &amp;seedLen)
</span><span style="color:#323232;">        restSeeds = strings.trim_left_space(restSeeds[seedLen:])
</span><span style="color:#323232;">
</span><span style="color:#323232;">        seedL, seedLOk := strconv.parse_int(restSeeds, 10, &amp;seedLen)
</span><span style="color:#323232;">        restSeeds = strings.trim_left_space(restSeeds[seedLen:])
</span><span style="color:#323232;">
</span><span style="color:#323232;">        append(&amp;seeds, SeedRange{seedS, seedL})
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    maps := parse_mappers(input)
</span><span style="color:#323232;">    defer {
</span><span style="color:#323232;">        for m in maps do delete(m.ranges)
</span><span style="color:#323232;">        delete(maps)
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    for i := 0; true; i += 1 {
</span><span style="color:#323232;">        rseed := i
</span><span style="color:#323232;">        #reverse for m in maps {
</span><span style="color:#323232;">            rseed = apply_mapper_reverse(m, rseed)
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">
</span><span style="color:#323232;">        found := false
</span><span style="color:#323232;">        for sr in seeds {
</span><span style="color:#323232;">            if rseed >= sr.start &amp;&amp; rseed &lt; sr.start + sr.len {
</span><span style="color:#323232;">                found = true
</span><span style="color:#323232;">                break
</span><span style="color:#323232;">            }
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">        if found {
</span><span style="color:#323232;">            fmt.println(i)
</span><span style="color:#323232;">            break
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">}
</span>

perviouslyiner, 6 months ago (edited 6 months ago)

This was interesting! So iterating through the solution space would be infeasible here and it seems we need to look for boundaries between regions and follow them to find places where a solution could occur.

Python: pastebin.com/8Ckx36fu

Make a list of places where location mappings are discontinuous (0, the end of each mapping, and the number before)

Repeat this for discontinuities in each intermediate layer

Trace each such location to its seed, and filter by seed ranges

Run the very minimal set of interesting seed numbers (around 2000 seeds) through the existing part1 algorithm

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

pnutzh4x0r, 6 months ago

Language: Python

Part 1The first part wasn’t too bad… once I realized you should store the ranges and not actually generate all the numbers o_O. Seeds = list[int] Map = tuple[int, int, int] Maps = list[Map] def read_almanac(stream=sys.stdin) -> tuple[Seeds, list[Map]]: seeds: Seeds = [int(seed) for seed in stream.readline().split(‘:’)[-1].split()] maps: Maps = [] for line in map(str.strip, stream): if line.endswith(‘map:’): maps.append([]) continue try: dst, src, length = map(int, line.split()) except ValueError: continue maps[-1].append((dst, src, length)) return seeds, maps def locate_seed(seed: int, maps: list[Map]) -> int: location = seed for amap in maps: for dst, src, length in amap: if src <= location < src + length: location = dst + (location - src) break return location def main(stream=sys.stdin) -> None: seeds, maps = read_almanac(stream) locations = [locate_seed(seed, maps) for seed in seeds] print(min(locations))

Part 2This part took me forever, mostly to actually run, but also to fix a few off-by-one errors :| Fortunately, I was able to re-use most of my code in Part A and just add a new function to search the range of seeds. Even with concurrent.futures and a 24-core machine, it still took me about 30 - 45 minutes to complete with Python (that said, there were only 10 seed range s in the input, so I could only use 10 cores, and of those 5 of the ranges appeared to be really large, leading to a long tail effect). def locate_seeds(srange: Range, maps: list[Map]={}) -> int: seeds = range(srange[0], srange[0] + srange[1]) locator = functools.partial(locate_seed, maps=maps) return min(map(locator, seeds)) # Main Execution def main(stream=sys.stdin) -> None: seeds, maps = read_almanac(stream) locator = functools.partial(locate_seeds, maps=maps) with concurrent.futures.ProcessPoolExecutor() as executor: locations = executor.map(locator, batched(seeds, 2)) print(min(locations))

GitHub Repo

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

purplemonkeymad, 6 months ago

Finally. :cries:

Part 1 was fine, I was figuring I might be able to practice classes.

Part 2 told me that nope, memory management required for you. In the end instead of calculating seeds, I resolved the whole thing down to a single mapping of seeds to locations. Then I could just sort by location ranges and try to see if they were a seed. Code is full of old parts from failed solutions but I’ve had enough of day 5, so I no longer care to clean it up.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Ategon, 6 months ago

[JavaScript] Well that was by far the hardest out of all of the days, part 1 was relatively fine but part 2 took me awhile of trying different things

Ended up solving it by working backwards by trying different location values and seeing if that can become a valid seed. Takes around 3 secs to compute the answer.

Link to code

:::spoiler Part 1 Code Block


<span style="color:#323232;">// Part 1
</span><span style="color:#323232;">// ======
</span><span style="color:#323232;">
</span><span style="color:#323232;">function part1(input) {
</span><span style="color:#323232;">  const split = input.split("rnrn");
</span><span style="color:#323232;">
</span><span style="color:#323232;">  let pastValues = split[0].match(/d+/g).map((x) => parseInt(x));
</span><span style="color:#323232;">  let currentValues = [];
</span><span style="color:#323232;">
</span><span style="color:#323232;">  for (const section of split.slice(1)) {
</span><span style="color:#323232;">    for (const line of section.split("rn")) {
</span><span style="color:#323232;">      const values = line.match(/d+/g)?.map((x) => parseInt(x));
</span><span style="color:#323232;">
</span><span style="color:#323232;">      if (!values) {
</span><span style="color:#323232;">        continue;
</span><span style="color:#323232;">      }
</span><span style="color:#323232;">
</span><span style="color:#323232;">      const sourceStart = values[1];
</span><span style="color:#323232;">      const destinationStart = values[0];
</span><span style="color:#323232;">      const length = values[2];
</span><span style="color:#323232;">
</span><span style="color:#323232;">      for (let i = 0; i &lt; pastValues.length; i++) {
</span><span style="color:#323232;">        if (
</span><span style="color:#323232;">          pastValues[i] >= sourceStart &amp;&amp;
</span><span style="color:#323232;">          pastValues[i] &lt; sourceStart + length
</span><span style="color:#323232;">        ) {
</span><span style="color:#323232;">          currentValues.push(destinationStart + pastValues[i] - sourceStart);
</span><span style="color:#323232;">          pastValues.splice(i, 1);
</span><span style="color:#323232;">          i--;
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">      }
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    for (let i = 0; i &lt; pastValues.length; i++) {
</span><span style="color:#323232;">      currentValues.push(pastValues[i]);
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    pastValues = [...currentValues];
</span><span style="color:#323232;">    currentValues = [];
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">
</span><span style="color:#323232;">  return Math.min(...pastValues);
</span><span style="color:#323232;">}
</span>

::: :::spoiler Part 2 Code Block


<span style="color:#323232;">// Part 2
</span><span style="color:#323232;">// ======
</span><span style="color:#323232;">
</span><span style="color:#323232;">function part2(input) {
</span><span style="color:#323232;">  const split = input.split("rnrn");
</span><span style="color:#323232;">
</span><span style="color:#323232;">  let seeds = split[0].match(/d+/g).map((x) => parseInt(x));
</span><span style="color:#323232;">  seeds = seeds
</span><span style="color:#323232;">    .filter((x, i) => i % 2 == 0)
</span><span style="color:#323232;">    .map((x, i) => [x, seeds[i * 2 + 1]]);
</span><span style="color:#323232;">
</span><span style="color:#323232;">  const maps = split
</span><span style="color:#323232;">    .slice(1)
</span><span style="color:#323232;">    .map((x) => {
</span><span style="color:#323232;">      const lines = x.split("rn");
</span><span style="color:#323232;">      return lines
</span><span style="color:#323232;">        .map((x) => x.match(/d+/g)?.map((x) => parseInt(x)))
</span><span style="color:#323232;">        .filter((x) => x);
</span><span style="color:#323232;">    })
</span><span style="color:#323232;">    .reverse();
</span><span style="color:#323232;">
</span><span style="color:#323232;">  for (let i = 0; true; i++) {
</span><span style="color:#323232;">    let curValue = i;
</span><span style="color:#323232;">
</span><span style="color:#323232;">    for (const map of maps) {
</span><span style="color:#323232;">      for (const line of map) {
</span><span style="color:#323232;">        const sourceStart = line[1];
</span><span style="color:#323232;">        const destinationStart = line[0];
</span><span style="color:#323232;">        const length = line[2];
</span><span style="color:#323232;">
</span><span style="color:#323232;">        if (
</span><span style="color:#323232;">          curValue >= destinationStart &amp;&amp;
</span><span style="color:#323232;">          curValue &lt; destinationStart + length
</span><span style="color:#323232;">        ) {
</span><span style="color:#323232;">          curValue = sourceStart + curValue - destinationStart;
</span><span style="color:#323232;">          break;
</span><span style="color:#323232;">        }
</span><span style="color:#323232;">      }
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">
</span><span style="color:#323232;">    for (const [seedRangeStart, seedRangeLength] of seeds) {
</span><span style="color:#323232;">      if (
</span><span style="color:#323232;">        curValue >= seedRangeStart &amp;&amp;
</span><span style="color:#323232;">        curValue &lt; seedRangeStart + seedRangeLength
</span><span style="color:#323232;">      ) {
</span><span style="color:#323232;">        return i;
</span><span style="color:#323232;">      }
</span><span style="color:#323232;">    }
</span><span style="color:#323232;">  }
</span><span style="color:#323232;">}
</span>

:::

cacheson, 6 months ago

Ended up solving it by working backwards by trying different location values and seeing if that can become a valid seed.

Huh, that's clever.

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

Ategon, 6 months ago

Turns out I got really lucky and my location value is much lower than most peoples which is why it can be solved relatively quickly

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

lwhjp, 6 months ago

Torn between doing the problem backwards and implementing a more general case – glad to know both approaches work out in the end!

reply

report

activity

copy /kbin url

copy original url

open original url

Loading...

cvttsd2si, 6 months ago

Scala3

kind of convoluted, but purely functional


<span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">scala.collection.immutable.NumericRange.Exclusive
</span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">math.max
</span><span style="font-weight:bold;color:#a71d5d;">import </span><span style="color:#323232;">math.min
</span><span style="color:#323232;">
</span><span style="color:#323232;">extension </span><span style="color:#0086b3;">A</span><span style="color:#323232;">
</span><span style="color:#323232;">  </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">chunk</span><span style="color:#323232;">(pred: </span><span style="color:#0086b3;">A </span><span style="font-weight:bold;color:#a71d5d;">=> Boolean</span><span style="color:#323232;">): </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">A</span><span style="color:#323232;">]] </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">go</span><span style="color:#323232;">(l: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">A</span><span style="color:#323232;">], partial_acc: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">A</span><span style="color:#323232;">], acc: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">A</span><span style="color:#323232;">]]): </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">A</span><span style="color:#323232;">]] </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">      l </span><span style="font-weight:bold;color:#a71d5d;">match
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">case</span><span style="color:#323232;"> (h :: t) </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;"> pred(h) </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> go(t, </span><span style="color:#0086b3;">List</span><span style="color:#323232;">(), partial_acc.reverse :: acc)
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">case</span><span style="color:#323232;"> (h :: t) </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> go(t, h :: partial_acc, acc)
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#323232;">_ </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> partial_acc.reverse :: acc
</span><span style="color:#323232;">    
</span><span style="color:#323232;">    go(l, </span><span style="color:#0086b3;">List</span><span style="color:#323232;">(), </span><span style="color:#0086b3;">List</span><span style="color:#323232;">()).reverse
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">type </span><span style="color:#323232;">R </span><span style="font-weight:bold;color:#a71d5d;">= </span><span style="color:#0086b3;">Exclusive</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">]
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">intersectTranslate</span><span style="color:#323232;">(r: </span><span style="color:#0086b3;">R</span><span style="color:#323232;">, c: </span><span style="color:#0086b3;">R</span><span style="color:#323232;">, t: </span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">): </span><span style="color:#0086b3;">R </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    (t + max(r.start, c.start) - c.start) until (t + min(r.end, c.end) - c.start)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">case class </span><span style="color:#0086b3;">MappingEntry</span><span style="color:#323232;">(from: </span><span style="color:#0086b3;">R</span><span style="color:#323232;">, to: </span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">)
</span><span style="font-weight:bold;color:#a71d5d;">case class </span><span style="color:#0086b3;">Mapping</span><span style="color:#323232;">(entries: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">MappingEntry</span><span style="color:#323232;">], produces: </span><span style="color:#0086b3;">String</span><span style="color:#323232;">):
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">resolveRange</span><span style="color:#323232;">(in: </span><span style="color:#0086b3;">R</span><span style="color:#323232;">): </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">R</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">        entries.map(e </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> intersectTranslate(in, e.from, e.to)).filter(!_.isEmpty)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">completeEntries</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">MappingEntry</span><span style="color:#323232;">]): </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">MappingEntry</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">= 
</span><span style="color:#323232;">    a ++ ((</span><span style="color:#0086b3;">0L</span><span style="color:#323232;"> until </span><span style="color:#0086b3;">0L</span><span style="color:#323232;">) +: a.map(_.from).sorted :+ (</span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">.</span><span style="color:#0086b3;">MaxValue</span><span style="color:#323232;"> until </span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">.</span><span style="color:#0086b3;">MaxValue</span><span style="color:#323232;">)).sliding(</span><span style="color:#0086b3;">2</span><span style="color:#323232;">).flatMap{ </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#0086b3;">List</span><span style="color:#323232;">(a, b) </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">Some</span><span style="color:#323232;">(</span><span style="color:#0086b3;">MappingEntry</span><span style="color:#323232;">(a.end until b.start, a.end)); </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#323232;">_ </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">None</span><span style="color:#323232;">}.toList
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">parse</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">], init: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">R</span><span style="color:#323232;">]): (</span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">R</span><span style="color:#323232;">], </span><span style="color:#0086b3;">Map</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">, </span><span style="color:#0086b3;">Mapping</span><span style="color:#323232;">]) </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">parseEntry</span><span style="color:#323232;">(s: </span><span style="color:#0086b3;">String</span><span style="color:#323232;">): </span><span style="color:#0086b3;">MappingEntry </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">        s </span><span style="font-weight:bold;color:#a71d5d;">match
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#62a35c;">s</span><span style="color:#183691;">"</span><span style="color:#323232;">$end $start $range</span><span style="color:#183691;">" </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">MappingEntry</span><span style="color:#323232;">(start.toLong until start.toLong + range.toLong, end.toLong)
</span><span style="color:#323232;">
</span><span style="color:#323232;">    a.chunk(_ == </span><span style="color:#183691;">""</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">match
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#0086b3;">List</span><span style="color:#323232;">(</span><span style="color:#62a35c;">s</span><span style="color:#183691;">"seeds: </span><span style="color:#323232;">$seeds</span><span style="color:#183691;">"</span><span style="color:#323232;">) :: maps </span><span style="font-weight:bold;color:#a71d5d;">=> 
</span><span style="color:#323232;">            init(seeds.split(</span><span style="color:#62a35c;">raw</span><span style="color:#183691;">"</span><span style="background-color:#f5f5f5;font-weight:bold;color:#b52a1d;"></span><span style="color:#183691;">s+"</span><span style="color:#323232;">).map(_.toLong).toList) -> (maps.flatMap{ </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#62a35c;">s</span><span style="color:#183691;">"</span><span style="color:#323232;">$from</span><span style="color:#183691;">-to-</span><span style="color:#323232;">$to</span><span style="color:#183691;"> map:"</span><span style="color:#323232;"> :: entries </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">Some</span><span style="color:#323232;">(from -> </span><span style="color:#0086b3;">Mapping</span><span style="color:#323232;">(completeEntries(entries.map(parseEntry)), to)); </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#323232;">_ </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">None </span><span style="color:#323232;">}).toMap
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#323232;">_ </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#323232;">(</span><span style="color:#0086b3;">List</span><span style="color:#323232;">(), </span><span style="color:#0086b3;">Map</span><span style="color:#323232;">()).ensuring(</span><span style="color:#0086b3;">false</span><span style="color:#323232;">)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">singletons</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">]): </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">R</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> a.map(s </span><span style="font-weight:bold;color:#a71d5d;">=></span><span style="color:#323232;"> s until s + </span><span style="color:#0086b3;">1</span><span style="color:#323232;">)
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">paired</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="font-weight:bold;color:#a71d5d;">Long</span><span style="color:#323232;">]): </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">R</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> a.grouped(</span><span style="color:#0086b3;">2</span><span style="color:#323232;">).flatMap{ </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#0086b3;">List</span><span style="color:#323232;">(x, y) </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">Some</span><span style="color:#323232;">(x until x+y); </span><span style="font-weight:bold;color:#a71d5d;">case </span><span style="color:#323232;">_ </span><span style="font-weight:bold;color:#a71d5d;">=> </span><span style="color:#0086b3;">None </span><span style="color:#323232;">}.toList
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">chase</span><span style="color:#323232;">(d: (</span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">R</span><span style="color:#323232;">], </span><span style="color:#0086b3;">Map</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">, </span><span style="color:#0086b3;">Mapping</span><span style="color:#323232;">]), initial: </span><span style="color:#0086b3;">String</span><span style="color:#323232;">, target: </span><span style="color:#0086b3;">String</span><span style="color:#323232;">) </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">val</span><span style="color:#323232;"> (init, m) </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> d
</span><span style="color:#323232;">    </span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">go</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">R</span><span style="color:#323232;">], s: </span><span style="color:#0086b3;">String</span><span style="color:#323232;">): </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">R</span><span style="color:#323232;">] </span><span style="font-weight:bold;color:#a71d5d;">=
</span><span style="color:#323232;">        </span><span style="font-weight:bold;color:#a71d5d;">if</span><span style="color:#323232;"> trace(s) == target then a </span><span style="font-weight:bold;color:#a71d5d;">else
</span><span style="color:#323232;">            </span><span style="font-weight:bold;color:#a71d5d;">val </span><span style="color:#323232;">x </span><span style="font-weight:bold;color:#a71d5d;">=</span><span style="color:#323232;"> m(s)
</span><span style="color:#323232;">            go(a.flatMap(x.resolveRange), x.produces)
</span><span style="color:#323232;">    go(trace(init), initial)
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">task1</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">]): </span><span style="font-weight:bold;color:#a71d5d;">Long = 
</span><span style="color:#323232;">    chase(parse(a, singletons), </span><span style="color:#183691;">"seed"</span><span style="color:#323232;">, </span><span style="color:#183691;">"location"</span><span style="color:#323232;">).min.start
</span><span style="color:#323232;">
</span><span style="font-weight:bold;color:#a71d5d;">def </span><span style="font-weight:bold;color:#795da3;">task2</span><span style="color:#323232;">(a: </span><span style="color:#0086b3;">List</span><span style="color:#323232;">[</span><span style="color:#0086b3;">String</span><span style="color:#323232;">]): </span><span style="font-weight:bold;color:#a71d5d;">Long =
</span><span style="color:#323232;">    chase(parse(a, paired), </span><span style="color:#183691;">"seed"</span><span style="color:#323232;">, </span><span style="color:#183691;">"location"</span><span style="color:#323232;">).min.start
</span>