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

(Cursed) Python

I solved the actual thing recursively in Rust, but I decided that wasn't cursed enough, so I present: Polynomial fitting!

import numpy.polynomial.polynomial as pol

with open("input.txt") as f:
  lines = list(map(lambda l: list(map(int, l.split(" "))), f.read().split("\n")))

lo, hi = 0, 0

for line in lines:
  for i in range(len(line)):
    poly, (r, *_) = pol.Polynomial.fit(range(len(line)), line, full=True, deg=i)
    if r < 0.0000000001:
      break

  lo += int(round(poly(-1)))
  hi += int(round(poly(len(line))))

print(f"Part 1: {hi}")
print(f"Part 2: {lo}")

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)

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

Rank 148!! Even beat Leo Uino today!

Optimized: https://codeberg.org/Sekoia/adventofcode/src/branch/main/src/y2023/day9.rs

Less optimized, though not quite my initial version: https://codeberg.org/Sekoia/adventofcode/commit/72dfd77b92518aefd9dbe3e661885528f737f861

Ruby

!ruby@programming.dev [LANGUAGE: Ruby]

I found today really easy thankfully. Hardest part was remembering the language features haha

https://github.com/snowe2010/advent-of-code/blob/master/ruby_aoc/2023/day09/day09.rb

edit: code golfing this one was easy too! man this day really worked out huh

    def get_subsequent_reading(reading)
      puts "passed in readings #{reading}"
      if reading.all?(0)
        reading << 0
      else
        readings = reading.each_cons(2).map do |a, b|
          b - a
        end
        sub_reading = get_subsequent_reading(readings)
        reading << (reading[-1] + sub_reading[-1])
        puts "current reading #{reading}"
        reading
      end
    end
    
    execute(1) do |lines|
      lines.map do |reading|
        get_subsequent_reading(reading.split.map(&:to_i))
      end.map {|arr| arr[-1]}.sum
    end
    
    
    def get_preceeding_readings(reading)
      puts "passed in readings #{reading}"
      if reading.all?(0)
        reading.unshift(0)
      else
        readings = reading.each_cons(2).map do |a, b|
          b - a
        end
        sub_reading = get_preceeding_readings(readings)
        reading.unshift(reading[0] - sub_reading[0])
        puts "current reading #{readings} #{sub_reading}"
        reading
      end
    end
    
    
    execute(2, test_only: false, test_file_suffix: '') do |lines|
      lines.map do |reading|
        get_preceeding_readings(reading.split.map(&:to_i))
      end.map {|arr| arr[0]}.sum
    end

code golf

  a=->r{r.unshift(r.all?(0)?0:(r[0]-a[r.each_cons(2).map{_2-_1}][0]))}
  l.map{a[_1.split.map(&:to_i)]}.map{_1[0]}.sum

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

Rust

Discrete derivatives!

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)

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=}")

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

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;

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

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

[Language: Lean4]

This one was very easy, almost trivial. Lean4 did demand a proof of termination though, and I'm still not very good at writing proofs...

I'm also pretty happy that this time I was able to re-use most of part 1 for part 2, and part 2 being a one-liner therefore.

As always, here is only the file with the actual solution, some helper functions are implemented in different files - check my github for the whole project.

private def parseLine (line : String) : Except String $ List Int :=
  line.split Char.isWhitespace
  |> List.map String.trim
  |> List.filter String.notEmpty
  |> List.mapM String.toInt?
  |> Option.toExcept s!"Failed to parse numbers in line \"{line}\""

def parse (input : String) : Except String $ List $ List Int :=
  let lines := input.splitOn "\n" |> List.map String.trim |> List.filter String.notEmpty
  lines.mapM parseLine

-------------------------------------------------------------------------------------------

private def differences : List Int → List Int
| [] => []
| _ :: [] => []
| a :: b :: as => (a - b) :: differences (b::as)

private theorem differences_length_independent_arg (a b : Int) (bs : List Int) : (differences (a :: bs)).length = (differences (b :: bs)).length := by
  induction bs <;> simp[differences]

-- BEWARE: Extrapolate needs the input reversed.
private def extrapolate : List Int → Int
| [] => 0
| a :: as =>
  if a == 0 && as.all (· == 0) then
    0
  else
    have : (differences (a :: as)).length < as.length + 1 := by
      simp_arith[differences]
      induction (as) <;> simp_arith[differences]
      case cons b bs hb => rw[←differences_length_independent_arg]
                           assumption
    a + extrapolate (differences (a :: as))
termination_by extrapolate a => a.length

def part1 : List (List Int) → Int :=
  List.foldl Int.add 0 ∘ List.map (extrapolate ∘ List.reverse)

-------------------------------------------------------------------------------------------

def part2 : List (List Int) → Int :=
  List.foldl Int.add 0 ∘ List.map extrapolate

Algol 68

So this felt like an old-school programming challenge. Like the type of thing you'd give to a CS student back in the good old days. So I decided to code in the granddaddy of modern languages. I did this in Algol-68!

In fact, Algol 68's event driven input handler was quite nice for this task as was its easy ability to detect the ends of lines. of course, its lack of built-in data structures meant that I had to whip up my own dynamic array, but that's pretty easy too. If you read today's code, you'll see familiar threads that influenced C and most of the languages that followed it.

Algol 68 is meant to be a language for publication. It is really tough to write a compiler for this language, but it is easy to write self-documenting code. In fact, a lot of textbooks publish algorithms in pseudocode that is almost correct Algol 68 code! So I tried to write today's solutions with readability in mind. Of course, this venerable language is not without its flaws, but I do enjoy coding in it from time to time.

https://github.com/pngwen/advent-2023/blob/main/day-9a.a68

COMMENT
File: day-9a.a68
Purpose: Solution to the first problem of day 9 of the advent of code
         written in the venerable Algol 68 Programming language.
         https://adventofcode.com/2023/day/9
Date: 9 December 2023
COMMENT

#--------------------------------------------------------------------#
#                     Array List Definition                          #
#--------------------------------------------------------------------#

# A handy data structure to manage dynamic growth #
MODE ARRAYLIST = STRUCT (FLEX [0] INT data, INT capacity, INT size);

# Create an array list with an initial capacity of 128 integers. #
PROC init array list = (REF ARRAYLIST list) VOID:
BEGIN
    [128] INT data;
    data OF list := data;
    capacity OF list := 128;
    size OF list := 0
END;


# Double the capacity of the list. #
PROC grow array list = (REF ARRAYLIST list) VOID:
BEGIN
    INT ubound := 1 UPB data OF list;
    INT capacity := ubound *2;
    [capacity] INT new;

    FOR i FROM 1 TO ubound
    DO
        new[i] := (data OF list)[i]
    OD;

    data OF list := new;
    capacity OF list := capacity
END;


# Add an item to the end of the array list #
PROC append to array list = (REF ARRAYLIST list, INT item) VOID:
BEGIN
    size OF list +:= 1;
    IF size OF list > capacity OF list THEN
        grow array list(list)
    FI;
    (data OF list)[size OF list] := item
END;


# Print an array list. #
PROC print array list = (REF ARRAYLIST list) VOID:
BEGIN
    FOR i FROM 1 TO size OF list
    DO
       print ((data OF list)[i])
    OD;
    print(new line)
END;

#--------------------------------------------------------------------#

# Set up the Input Handlers #
BOOL is eof := FALSE;
on logical file end(stand in, (REF FILE f) BOOL: ( is eof := TRUE; TRUE ));


# Read a line of integers to get the array list #
PROC read history = ARRAYLIST:
BEGIN
    ARRAYLIST result;
    INT num;
    init array list(result);

    DO
        get(stand in, num);
        IF NOT is eof THEN
            append to array list(result, num)
        FI
        UNTIL end of line(stand in) OR is eof
    OD;

    result
END;

# compute the first differential of the list #
PROC differentiate = (ARRAYLIST list) ARRAYLIST:
BEGIN
    ARRAYLIST result;

    init array list(result);

    FOR i FROM 1 TO size OF list - 1
    DO
        append to array list(result, 
                             (data OF list)[i+1]-(data OF list)[i])
    OD;

    result
END;

# Extrapolate the next value #
PROC extrapolate = (ARRAYLIST list) INT:
BEGIN
    INT result;

    IF size OF list = 0 THEN
        result := 0
    ELIF size OF list = 1 THEN
        result := (data OF list)[1]
    ELSE
        result := extrapolate(differentiate(list)) + 
                  (data OF list)[size OF list]
    FI;

    result
END;


ARRAYLIST line;
INT sum := 0;

WHILE NOT is eof
DO
    line := read history;
    IF size OF line /= 0 THEN
        sum +:= extrapolate(line)
    FI
    UNTIL is eof
OD;

print((sum, new line))

https://github.com/pngwen/advent-2023/blob/main/day-9b.a68

COMMENT
File: day-9b.a68
Purpose: Solution to the second problem of day 9 of the advent of code
         written in the venerable Algol 68 Programming language.
         https://adventofcode.com/2023/day/9
Date: 9 December 2023
COMMENT

#--------------------------------------------------------------------#
#                     Array List Definition                          #
#--------------------------------------------------------------------#

# A handy data structure to manage dynamic growth #
MODE ARRAYLIST = STRUCT (FLEX [0] INT data, INT capacity, INT size);

# Create an array list with an initial capacity of 128 integers. #
PROC init array list = (REF ARRAYLIST list) VOID:
BEGIN
    [128] INT data;
    data OF list := data;
    capacity OF list := 128;
    size OF list := 0
END;


# Double the capacity of the list. #
PROC grow array list = (REF ARRAYLIST list) VOID:
BEGIN
    INT ubound := 1 UPB data OF list;
    INT capacity := ubound *2;
    [capacity] INT new;

    FOR i FROM 1 TO ubound
    DO
        new[i] := (data OF list)[i]
    OD;

    data OF list := new;
    capacity OF list := capacity
END;


# Add an item to the end of the array list #
PROC append to array list = (REF ARRAYLIST list, INT item) VOID:
BEGIN
    size OF list +:= 1;
    IF size OF list > capacity OF list THEN
        grow array list(list)
    FI;
    (data OF list)[size OF list] := item
END;


# Print an array list. #
PROC print array list = (REF ARRAYLIST list) VOID:
BEGIN
    FOR i FROM 1 TO size OF list
    DO
       print ((data OF list)[i])
    OD;
    print(new line)
END;

#--------------------------------------------------------------------#

# Set up the Input Handlers #
BOOL is eof := FALSE;
on logical file end(stand in, (REF FILE f) BOOL: ( is eof := TRUE; TRUE ));


# Read a line of integers to get the array list #
PROC read history = ARRAYLIST:
BEGIN
    ARRAYLIST result;
    INT num;
    init array list(result);

    DO
        get(stand in, num);
        IF NOT is eof THEN
            append to array list(result, num)
        FI
        UNTIL end of line(stand in) OR is eof
    OD;

    result
END;

# compute the first differential of the list #
PROC differentiate = (ARRAYLIST list) ARRAYLIST:
BEGIN
    ARRAYLIST result;

    init array list(result);

    FOR i FROM 1 TO size OF list - 1
    DO
        append to array list(result, 
                             (data OF list)[i+1]-(data OF list)[i])
    OD;

    result
END;

# Extrapolate the next value #
PROC extrapolate = (ARRAYLIST list) INT:
BEGIN
    INT result;

    IF size OF list = 0 THEN
        result := 0
    ELIF size OF list = 1 THEN
        result := (data OF list)[1]
    ELSE
        result := (data OF list)[1] - extrapolate(differentiate(list))
    FI;

    result
END;


ARRAYLIST line;
INT sum := 0;

WHILE NOT is eof
DO
    line := read history;
    IF size OF line /= 0 THEN
        sum +:= extrapolate(line)
    FI
    UNTIL is eof
OD;

print((sum, new line))

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

Using a class here actually made part 2 super simple, just copy and paste a function. Initially I was a bit concerned about what part 2 would be, but looking at the lengths of the input data, there looked to be a resonable limit to how many additional rows there could be.

#https://stackoverflow.com/a/1012089
def iter_item_and_next(iterable):
    items, nexts = itertools.tee(iterable, 2)
    nexts = itertools.chain(itertools.islice(nexts, 1, None), [None])
    return zip(items, nexts)

class Sequence:
    def __init__(self,sequence:list) -> None:
        self.list = sequence
        if all([x == sequence[0] for x in sequence]):
            self.child:Sequence = ZeroSequence(len(sequence)-1)
            return
        
        child_sequence = list()
        for cur,next in iter_item_and_next(sequence):
            if next == None:
                continue
            child_sequence.append(next - cur)

        if len(child_sequence) > 1:
            self.child:Sequence = Sequence(child_sequence)
            return
        
        # can't do diff on single item, use zero list
        self.child:Sequence = ZeroSequence(1)

    def __repr__(self) -> str:
        return f"Sequence([{self.list}], Child:{self.child})"

    def getNext(self) -> int:
        if self.child == None:
            new = self.list[-1]
        else: 
            new = self.list[-1] + self.child.getNext()

        self.list.append(new)
        return new
    
    def getPrevious(self) -> int:
        if self.child == None:
            new = self.list[0]
        else: 
            new = self.list[0] - self.child.getPrevious()

        self.list.insert(0,new)
        return new

class ZeroSequence(Sequence):
    def __init__(self,count) -> None:
        self.list = [0]*count
        self.child = None

    def __repr__(self) -> str:
        return f"ZeroSequence(length={len(self.list)})"

    def getNext(self) -> int:
        self.list.append(0)
        return 0
    
    def getPrevious(self) -> int:
        self.list.append(0)
        return 0

def parse_line(string:str) -> list:
    return [int(x) for x in string.split(' ')]

def main(line_list):
    data = [Sequence(parse_line(x)) for x in line_list]
    print(data)

    # part 1
    total = 0
    for d in data:
        total += d.getNext()
    print("Part 1 After:")
    print(data)
    print(f"part 1 total: {total}")

    # part 2
    total = 0
    for d in data:
        total += d.getPrevious()
    print("Part 2 After:")
    print(data)
    print(f"part 2 total: {total}")


if __name__ == "__main__":
    parser = argparse.ArgumentParser(description="day 1 solver")
    parser.add_argument("-input",type=str)
    parser.add_argument("-part",type=int)
    args = parser.parse_args()
    filename = args.input
    if filename == None:
        parser.print_help()
        exit(1)
    file = open(filename,'r')
    main([line.rstrip('\n') for line in file.readlines()])
    file.close()

Language: Python

Github

C#

Used recursion to determine the differences for part 1 and then extracted the variations in processing from predicting the end vs. the beginning of the history and passed them in as Func variables to the recursive method.

Day 9

Haskell

I was expecting something much harder! Worried about tomorrow's puzzle, now...

diffs :: [Int] -> [[Int]]
diffs = takeWhile (not . all (== 0)) . iterate (zipWith (-) . tail <*> id)

part1 = sum . map last . diffs

part2 = head . scanr1 (-) . map head . diffs

main = do
  input <- map (map read . words) . lines <$> readFile "input09"
  print $ sum $ map part1 input
  print $ sum $ map part2 input

A pretty simple one today, but fun to do. I could probably clean up the parsing code (AKA my theme for this year), and create just one single vector instead of having the original history separated out from all of the sequences, but this is what made sense to me on my first pass so it's how I did it.

https://github.com/capitalpb/advent_of_code_2023/blob/main/src/solvers/day09.rs

pub struct Day09;

fn get_history(input: &str) -> Vec {
    input
        .split(' ')
        .filter_map(|num| num.parse::().ok())
        .collect::>()
}

fn get_sequences(history: &Vec) -> Vec> {
    let mut sequences = vec![get_steps(&history)];

    while !sequences.last().unwrap().iter().all_equal() {
        sequences.push(get_steps(sequences.last().unwrap()));
    }

    sequences
}

fn get_steps(sequence: &Vec) -> Vec {
    sequence
        .iter()
        .tuple_windows()
        .map(|(x, y)| y - x)
        .collect()
}

impl Solver for Day09 {
    fn star_one(&self, input: &str) -> String {
        input
            .lines()
            .map(|line| {
                let history = get_history(line);

                let add_value = get_sequences(&history)
                    .iter()
                    .rev()
                    .map(|seq| seq.last().unwrap().clone())
                    .reduce(|acc, x| acc + x)
                    .unwrap();

                history.last().unwrap() + add_value
            })
            .sum::()
            .to_string()
    }

    fn star_two(&self, input: &str) -> String {
        input
            .lines()
            .map(|line| {
                let history = get_history(line);

                let minus_value = get_sequences(&history)
                    .iter()
                    .rev()
                    .map(|seq| seq.first().unwrap().clone())
                    .reduce(|acc, x| x - acc)
                    .unwrap();

                history.first().unwrap() - minus_value
            })
            .sum::()
            .to_string()
    }
}

C

Thought there must be some clever way to infer the formula without storing those derived rows but implemented it like the example to get started. Turns out that was fine for part 2 as well so yay!

GitHub link

:::spoiler (Slightly abridged) code

int main()
{
	char line[128], *tok,*rest;
	size_t n,d,i;
	int a[24][24], p1=0,p2=0, nz, acc1,acc2;

	while ((rest = fgets(line, sizeof(line), stdin))) {
		for (n=0; (tok = strsep(&rest, " ")); n++)
			a[0][n] = atoi(tok);

		/* generate rows until all 0, 'd' is depth */
		for (d=1, nz=1; nz && d<n; d++)
		for (i=0, nz=0; i<n-d; i++)
			nz |= (a[d][i] = a[d-1][i+1] - a[d-1][i]);

		/* extrapolate forward and backwards */
		for (i=0, acc1=acc2=0; i<d; i++) {
			acc1 += a[d-i-1][n-d+i];
			acc2  = a[d-i-1][0] - acc2;
		}

		p1 += acc1;
		p2 += acc2;
	}

	printf("09: %d %d\n", p1, p2);
	return 0;
}