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

[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

// Part 1
// ======

function part1(input) {
  const split = input.split("\r\n\r\n");

  let pastValues = split[0].match(/\d+/g).map((x) => parseInt(x));
  let currentValues = [];

  for (const section of split.slice(1)) {
    for (const line of section.split("\r\n")) {
      const values = line.match(/\d+/g)?.map((x) => parseInt(x));

      if (!values) {
        continue;
      }

      const sourceStart = values[1];
      const destinationStart = values[0];
      const length = values[2];

      for (let i = 0; i < pastValues.length; i++) {
        if (
          pastValues[i] >= sourceStart &&
          pastValues[i] < sourceStart + length
        ) {
          currentValues.push(destinationStart + pastValues[i] - sourceStart);
          pastValues.splice(i, 1);
          i--;
        }
      }
    }

    for (let i = 0; i < pastValues.length; i++) {
      currentValues.push(pastValues[i]);
    }

    pastValues = [...currentValues];
    currentValues = [];
  }

  return Math.min(...pastValues);
}

// Part 2
// ======

function part2(input) {
  const split = input.split("\r\n\r\n");

  let seeds = split[0].match(/\d+/g).map((x) => parseInt(x));
  seeds = seeds
    .filter((x, i) => i % 2 == 0)
    .map((x, i) => [x, seeds[i * 2 + 1]]);

  const maps = split
    .slice(1)
    .map((x) => {
      const lines = x.split("\r\n");
      return lines
        .map((x) => x.match(/\d+/g)?.map((x) => parseInt(x)))
        .filter((x) => x);
    })
    .reverse();

  for (let i = 0; true; i++) {
    let curValue = i;

    for (const map of maps) {
      for (const line of map) {
        const sourceStart = line[1];
        const destinationStart = line[0];
        const length = line[2];

        if (
          curValue >= destinationStart &&
          curValue < destinationStart + length
        ) {
          curValue = sourceStart + curValue - destinationStart;
          break;
        }
      }
    }

    for (const [seedRangeStart, seedRangeLength] of seeds) {
      if (
        curValue >= seedRangeStart &&
        curValue < seedRangeStart + seedRangeLength
      ) {
        return i;
      }
    }
  }
}

Haskell

Not hugely proud of this one; part one would have been easier if I’d spend more time reading the question and not started on an overly-general solution, and I lost a lot of time on part two to a missing a +. More haste, less speed, eh?

import Data.List
import Data.List.Split

readInput :: String -> ([Int], [(String, [(Int, Int, Int)])])
readInput s =
  let (seedsChunk : mapChunks) = splitOn [""] $ lines s
      seeds = map read $ tail $ words $ head seedsChunk
      maps = map readMapChunk mapChunks
   in (seeds, maps)
  where
    readMapChunk (title : rows) =
      let name = head $ words title
          entries = map ((\[a, b, c] -> (a, b, c)) . map read . words) rows
       in (name, entries)

part1 (seeds, maps) =
  let f = foldl1' (flip (.)) $ map (ref . snd) maps
   in minimum $ map f seeds
  where
    ref [] x = x
    ref ((a, b, c) : rest) x =
      let i = x - b
       in if i >= 0 && i < c
            then a + i
            else ref rest x

mapRange :: [(Int, Int, Int)] -> (Int, Int) -> [(Int, Int)]
mapRange entries (start, end) =
  go start $ sortOn (\(_, b, _) -> b) entries
  where
    go i [] = [(i, end)]
    go i es@((a, b, c) : rest)
      | i > end = []
      | b > end = go i []
      | b + c <= i = go i rest
      | i < b = (i, b - 1) : go b es
      | otherwise =
          let d = min (b + c - 1) end
           in (a + i - b, a + d - b) : go (d + 1) rest

part2 (seeds, maps) =
  let seedRanges = map (\[a, b] -> (a, a + b - 1)) $ chunksOf 2 seeds
   in minimum $ map fst $ foldl' (flip mapRanges) seedRanges $ map snd maps
  where
    mapRanges m = concatMap (mapRange m)

main = do
  input <- readInput <$> readFile "input05"
  print $ part1 input
  print $ part2 input

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
        }
    }
}

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.