Nim

Pretty easy one today. Made a Pyramid type to hold the values and their layers of diffs, and an extend function to predict the next value. For part 2 I just had to make an extendLeft version of it that inserts and subtracts instead of appending and adding.

• Day 9, part 1
• Day 9, part 2

Nim

Part 1:
The extrapolated value to the right is just the sum of all last values in the diff pyramid. 45 + 15 + 6 + 2 + 0 = 68
Part 2:
The extrapolated value to the left is just a right-folded difference (right-associated subtraction) between all first values in the pyramid. e.g. 10 - (3 - (0 - (2 - 0))) = 5

So, extending the pyramid is totally unneccessary.

Total runtime: 0.9 ms
Puzzle rating: Easy, but interesting 6.5/10
Full Code: day_09/solution.nim
Snippet:

proc solve(lines: seq[string]): AOCSolution[int] =
  for line in lines:
    var current = line.splitWhitespace().mapIt(it.parseInt())
    var firstValues: seq[int]

    while not current.allIt(it == 0):
      firstValues.add current[0]
      block p1:
        result.part1 += current[^1]

      var nextIter = newSeq[int](current.high)
      for i, v in current[1..^1]:
        nextIter[i] = v - current[i]
      current = nextIter

    block p2:
      result.part2 += firstValues.foldr(a-b)

APL

I finally managed to make use of ⍣ :D

input←⊃⎕NGET'inputs/day9.txt'1
p←{⍎('¯'@((⍸'-'∘=)⍵))⍵}¨input
f←({⍵⍪⊂2-⍨/⊃¯1↑⍵}⍣{∧/0=⊃¯1↑⍺})
⎕←+/{+/⊢/¨f⊂⍵}¨p ⍝ part 1
⎕←+/{-/⊣/¨f⊂⍵}¨p ⍝ part 2

Removed by mod

Python

from .solver import Solver

class Day09(Solver):

  def __init__(self):
    super().__init__(9)
    self.numbers: list[list[int]] = []

  def presolve(self, input: str):
    lines = input.rstrip().split('\n')
    self.numbers = [[int(n) for n in line.split(' ')] for line in lines]
    for line in self.numbers:
      stack = [line]
      while not all(x == 0 for x in stack[-1]):
        diff = [stack[-1][i+1] - stack[-1][i] for i in range(len(stack[-1]) - 1)]
        stack.append(diff)
      stack.reverse()
      stack[0].append(0)
      stack[0].insert(0, 0)
      for i in range(1, len(stack)):
        stack[i].append(stack[i-1][-1] + stack[i][-1])
        stack[i].insert(0, stack[i][0] - stack[i-1][0])

  def solve_first_star(self) -> int:
    return sum(line[-1] for line in self.numbers)

  def solve_second_star(self) -> int:
    return sum(line[0] for line in self.numbers)

Rust

Discrete derivatives!

Python

Easy one today

import pathlib

base_dir = pathlib.Path(__file__).parent
filename = base_dir / "day9_input.txt"

with open(base_dir / filename) as f:
    lines = f.read().splitlines()

histories = [[int(n) for n in line.split()] for line in lines]

answer_p1 = 0
answer_p2 = 0

for history in histories:
    deltas: list[list[int]] = []
    last_line: list[int] = history

    while any(last_line):
        deltas.append(last_line)
        last_line = [last_line[i] - last_line[i - 1] for i in range(1, len(last_line))]

    first_value = 0
    last_value = 0
    for delta_list in reversed(deltas):
        last_value = delta_list[-1] + last_value
        first_value = delta_list[0] - first_value

    answer_p1 += last_value
    answer_p2 += first_value

print(f"{answer_p1=}")
print(f"{answer_p2=}")

Crystal

recursion is awesome! (sometimes)

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

seqs = input.lines.map &.split.map &.to_i

sums = seqs.reduce({0, 0}) do |prev, sequence|
	di = diff(sequence)
	{prev[0] + sequence[0] - di[0], prev[1] + di[1] + sequence[-1]}
end
puts sums


def diff(sequence)
	new = Array.new(sequence.size-1) {|i| sequence[i+1] - sequence[i]}

	return {0, 0} unless new.any?(&.!= 0)

	di = diff(new)
	{new[0] - di[0], di[1] + new[-1]}
end

Dart

I was getting a bad feeling when it explained in such detail how to solve part 1 that part 2 was going to be some sort of nightmare of traversing all those generated numbers in some complex fashion, but this has got to be one of the shortest solutions I’ve ever written for an AoC challenge.

int nextTerm(Iterable ns) {
  var diffs = ns.window(2).map((e) => e.last - e.first);
  return ns.last +
      ((diffs.toSet().length == 1) ? diffs.first : nextTerm(diffs.toList()));
}

List> parse(List lines) => [
      for (var l in lines) [for (var n in l.split(' ')) int.parse(n)]
    ];

part1(List lines) => parse(lines).map(nextTerm).sum;
part2(List lines) => parse(lines).map((e) => nextTerm(e.reversed)).sum;

Scala3

def diffs(a: Seq[Long]): List[Long] =
    a.drop(1).zip(a).map(_ - _).toList

def predictNext(a: Seq[Long], combine: (Seq[Long], Long) => Long): Long =
    if a.forall(_ == 0) then 0 else combine(a, predictNext(diffs(a), combine))

def predictAllNexts(a: List[String], combine: (Seq[Long], Long) => Long): Long = 
    a.map(l => predictNext(l.split(raw"\s+").map(_.toLong), combine)).sum

def task1(a: List[String]): Long = predictAllNexts(a, _.last + _)
def task2(a: List[String]): Long = predictAllNexts(a, _.head - _)

Language: Python

def predict(history: list[int]) -> int:
    sequences = [history]
    while len(set(sequences[-1])) > 1:
        sequences.append([b - a for a, b in itertools.pairwise(sequences[-1])])
    return sum(sequence[-1] for sequence in sequences)

def main(stream=sys.stdin) -> None:
    histories   = [list(map(int, line.split())) for line in stream]
    predictions = [predict(history) for history in histories]
    print(sum(predictions))

def predict(history: list[int]) -> int:
    sequences = [history]
    while len(set(sequences[-1])) > 1:
        sequences.append([b - a for a, b in itertools.pairwise(sequences[-1])])
    return functools.reduce(
        lambda a, b: b - a, [sequence[0] for sequence in reversed(sequences)]
    )

def main(stream=sys.stdin) -> None:
    histories   = [list(map(int, line.split())) for line in stream]
    predictions = [predict(history) for history in histories]
    print(sum(predictions))

GitHub Repo

Raku

First time using Grammar Actions Object to make parsing a little cleaner. I thought about not keeping track of the left and right values (and I originally didn’t for part 1), but I think keeping track allows for an easier to understand solution.

View code on github

edit: although I don’t know why @values.all != 0 evaluates to true why any value is not zero. I thought that @values.any != 0 would do that, but it seems that their behavior is flipped from my expectations.

edit2: Oh, I think I understand now. != is a shortcut for !==, and !== is actually the equality operator that is then negated. You can negate most relational operators in Raku by prefixing them with !. So the junction is actually binding to the == equality operator and not the !== inequality operator. Therefore @values.all != 0 becomes !(@values.all == 0). I’m not sure why they would choose this order of operations, though.

edit3: Ah, it’s in the documentation, so it’s not even an oversight. https://github.com/rakudo/rakudo/issues/3748

use v6;

sub MAIN($input) {
    my $file = open $input;

    grammar Oasis {
        token TOP { +%"\n" "\n"* }
        token history { +%\h+ }
        token val { '-'? \d+ }
    }

    class OasisActions {
        method TOP ($/) { make $».made }
        method history ($/) { make $».made }
        method val ($/) { make $/.Int }
    }

    my $oasis = Oasis.parse($file.slurp, actions => OasisActions.new);
    my @histories = $oasis.made;
    my $part-one-solution;
    my $part-two-solution;
    sub revdiff { $^b - $^a }
    for @histories -> @history {
        my @values = @history;
        my @rightmosts = [@values.tail];
        my @leftmosts = [@values.head];
        while @values.all != 0 {
            @values = @values.tail(*-1) Z- @values.head(*-1);
            @rightmosts.push(@values.tail);
            @leftmosts.push(@values.head);
        }
        $part-one-solution += [+] @rightmosts;
        $part-two-solution += [[&revdiff]] @leftmosts.reverse;
    }
    say "part 1: $part-one-solution";
    say "part 2: $part-two-solution";
}

I even have time to knock out a quick Uiua solution before going out today, using experimental recursion support. Bleeding edge code:

# Experimental!
{"0 3 6 9 12 15"
 "1 3 6 10 15 21"
 "10 13 16 21 30 45"}
StoInt ← /(+×10)▽×⊃(≥0)(≤9).-@0
NextTerm ← ↬(
  ↘1-↻¯1..      # rot by one and take diffs
  (|1 ↫|⊢)=1⧻⊝. # if they're all equal grab else recurse
  +⊙(⊢↙¯1)      # add to last value of input
)
≡(⊜StoInt≠@\s.⊔) # parse
⊃(/+≡NextTerm)(/+≡(NextTerm ⇌))

TypeScript

GitHub link

It’s nice to have a quick easy one for a change

import fs from "fs";

const rows = fs.readFileSync("./09/input.txt", "utf-8")
    .split(/[\r\n]+/)
    .map(row => row.trim())
    .filter(Boolean)
    .map(row => row.split(/\s+/).map(number => parseInt(number)));

console.info("Part 1: " + solve(structuredClone(rows)));
console.info("Part 2: " + solve(structuredClone(rows), true));

function solve(rows: number[][], part2 = false): number {
    let total = 0;
    for (const row of rows) {
        const sequences: number[][] = [row];
        while (sequences[sequences.length - 1].some(number => number !== 0)) { // Loop until all are zero
            const lastSequence = sequences[sequences.length - 1];
            const newSequence: number[] = [];
            for (let i = 0; i < lastSequence.length; i++) {
                if (lastSequence[i + 1] !== undefined) {
                    newSequence.push(lastSequence[i + 1] - lastSequence[i]);
                }
            }
            sequences.push(newSequence);
        }

        // For part two just reverse the sequences
        if (part2) {
            sequences.forEach(sequence => sequence.reverse());
        }

        // Add the first zero manually and loop the rest
        sequences[sequences.length - 1].push(0);
        for (let i = sequences.length - 2; i >= 0; i--) {
            sequences[i].push(part2
                ? sequences[i][sequences[i].length - 1] - sequences[i + 1][sequences[i + 1].length - 1]
                : sequences[i][sequences[i].length - 1] + sequences[i + 1][sequences[i + 1].length - 1]
            );
        }
    
        total += sequences[0].reverse()[0];
    }

    return total;
}

Language: Python

Github