Language: Python

Github

Catching up missed days.

Language: Python

solution

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).

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

package day5

import "core:fmt"
import "core:strings"
import "core:slice"
import "core:strconv"

Range :: struct {
    dest: int,
    src: int,
    range: int,
}

Mapper :: struct {
    ranges: []Range,
}

parse_range :: proc(s: string) -> (ret: Range) {
    rest := s

    parseLen := -1

    destOk: bool
    ret.dest, destOk = strconv.parse_int(rest, 10, &parseLen)
    rest = strings.trim_left_space(rest[parseLen:])

    srcOk: bool
    ret.src, srcOk = strconv.parse_int(rest, 10, &parseLen)
    rest = strings.trim_left_space(rest[parseLen:])

    rangeOk: bool
    ret.range, rangeOk = strconv.parse_int(rest, 10, &parseLen)

    return
}

parse_mapper :: proc(ss: []string) -> (ret: Mapper) {
    ret.ranges = make([]Range, len(ss)-1)
    for s, i in ss[1:] {
        ret.ranges[i] = parse_range(s)
    }

    return
}

parse_mappers :: proc(ss: []string) -> []Mapper {
    mapsStr := make([dynamic][]string)
    defer delete(mapsStr)

    restOfLines := ss
    isLineEmpty :: proc(s: string)->bool {return len(s)==0}

    for i, found := slice.linear_search_proc(restOfLines, isLineEmpty); 
        found; 
        i, found  = slice.linear_search_proc(restOfLines, isLineEmpty) {
        
        append(&mapsStr, restOfLines[:i])
        restOfLines = restOfLines[i+1:]
    }
    append(&mapsStr, restOfLines[:])

    return slice.mapper(mapsStr[1:], parse_mapper)
}

apply_mapper :: proc(mapper: Mapper, num: int) -> int {
    for r in mapper.ranges {
        if num >= r.src && num - r.src < r.range do return num - r.src + r.dest
    }

    return num
}

p1 :: proc(input: []string) {
    maps := parse_mappers(input)
    defer {
        for m in maps do delete(m.ranges)
        delete(maps)
    }

    restSeeds := input[0][len("seeds: "):]
    min := 0x7fffffff

    for len(restSeeds) > 0 {
        seedLen := -1
        seed, seedOk := strconv.parse_int(restSeeds, 10, &seedLen)
        restSeeds = strings.trim_left_space(restSeeds[seedLen:])

        fmt.print(seed)
        for m in maps {
            seed = apply_mapper(m, seed)
            fmt.print(" ->", seed)
        }
        fmt.println()

        if seed < min do min = seed
    }

    fmt.println(min)
}

apply_mapper_reverse :: proc(mapper: Mapper, num: int) -> int {
    for r in mapper.ranges {
        if num >= r.dest && num - r.dest < r.range do return num - r.dest + r.src
    }

    return num
}

p2 :: proc(input: []string) {
    SeedRange :: struct {
        start: int,
        len: int,
    }

    seeds := make([dynamic]SeedRange)
    restSeeds := input[0][len("seeds: "):]

    for len(restSeeds) > 0 {
        seedLen := -1
        seedS, seedSOk := strconv.parse_int(restSeeds, 10, &seedLen)
        restSeeds = strings.trim_left_space(restSeeds[seedLen:])

        seedL, seedLOk := strconv.parse_int(restSeeds, 10, &seedLen)
        restSeeds = strings.trim_left_space(restSeeds[seedLen:])

        append(&seeds, SeedRange{seedS, seedL})
    }

    maps := parse_mappers(input)
    defer {
        for m in maps do delete(m.ranges)
        delete(maps)
    }

    for i := 0; true; i += 1 {
        rseed := i
        #reverse for m in maps {
            rseed = apply_mapper_reverse(m, rseed)
        }

        found := false
        for sr in seeds {
            if rseed >= sr.start && rseed < sr.start + sr.len {
                found = true
                break
            }
        }
        if found {
            fmt.println(i)
            break
        }
    }
}

[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.

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 "\n\n" |> 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?

CRYSTAL

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

Input = File.read("input.txt").lines

# {source, destination}
alias Map = Tuple(Range(Int64, Int64), Range(Int64, Int64))

Maps = Array(Array(Map)).new(7)
index = 1
7.times do |i| 
	a, index = get_ranges(index + 2)
	Maps << a
end

part2
# part1

def part1()
	seeds = Input[0].split(":")[1].split.map(&.to_i64)
	locs = Array(Int64).new(7)
	
	seeds.each do |seed|
		val = seed
		Maps.each do |maplist|
			maplist.each do |map|
				if map[0].includes?(val)
					val = map[1].begin + (val - map[0].begin)
					break
		end     end     end
		locs << val
	end
	puts locs.min
end

def part2()
	seeds = Input[0].split(":")[1].split.map(&.to_i64)
	seeds = seeds.in_groups_of(2, 0).map { |a| a[0]..(a[0]+a[1]) }

	found = false
	loc = 0
	until found 
		val = loc
		Maps.reverse_each do |maplist|
			maplist.each do |map|
				if map[1].includes?(val)
					val = map[0].begin + (val - map[1].begin)
					break
		end     end     end

		seeds.each { |seedrange| break if found = seedrange.includes?(val) }
		loc += 1
	end
	puts loc - 1
end

def get_ranges(index : Int) : {Array(Map), Int32}
	line = Input[index]
	ranges = [] of Map
	until line == ""
		a, b, l = line.split.map(&.to_i64)
		ranges << {b...(b+l), a...(a+l)}
		
		index += 1
		break if index == Input.size
		line = Input[index]
	end
	{ranges, index}
end

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