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

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)

(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

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

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

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

[email protected] [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

Rust

Discrete derivatives!

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;

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

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

Python

Also on Github

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)

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

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

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.

import re
import math
import argparse
import itertools

#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()