Leif's Website

https://github.com/leifmetcalf/aoc-2024/blob/trunk/aoc2024.livemd

Day 2

Problem

You're given a list of reports

7 6 4 2 1
1 2 7 8 9
...

For part 1, find which reports are safe, that is, (strictly) monotone and increase/decrease by at most 3 each step. Then, sum the middle elements of the found reports.

For part 2, you are allowed to remove at most one element from each report to make them safe.

Note

The naive quadratic solution is plenty fast enough for part 2, but there's also a linear solution. If you find an index where a post fails to be safe, then one of the three adjacent indices must be deleted, and it's only a matter of checking the three cases in linear time.

Day 7

Problem

You're given a list of target values and integers:

190: 10 19
3267: 81 40 27
...

Part 1 asks you to find the rows where it is possible to insert left-associative 'plus', 'times', and 'concat' operators into the list of integers such that the resulting expression evaluates to the target value.

Note

One naive approach would be backtracking from the left:

possible?(target, x : xs) = go(x, xs) where
    go(acc, []) = acc == target
    go(acc, x : xs) = or([
        acc + x <= target and go(acc + x, xs),
        acc * x <= target and go(acc * x, xs),
        concat(acc, x) <= target and go(concat(acc, x), xs)
    ])

You can also backtrack from the right:

possible?(target, xs) = go(target, reverse(xs)) where
    go(acc, [x]) = acc == x
    go(acc, x : xs) = or([
        x < acc and go(acc - x, xs),
        divides?(acc, x) and go(acc / x, xs),
        suffix?(acc, x) and go(strip(acc, x), xs)
    ])

The first approach is clearer, but the advantage of the second approach is that it short-circuits earlier. The _ <= target conditions only trigger deep into the tree, whereas divides?(acc, x) and suffix?(acc, x) can trigger anywhere.