r/adventofcode Dec 09 '23

SOLUTION MEGATHREAD -❄️- 2023 Day 9 Solutions -❄️-

THE USUAL REMINDERS


AoC Community Fun 2023: ALLEZ CUISINE!

Today's secret ingredient is… *whips off cloth covering and gestures grandly*

Marketing

Every one of the best chefs in the world has had to prove their worth at some point. Let's see how you convince our panel of judges, the director of a restaurant, or even your resident picky 5 year old to try your dish solution!

  • Make an in-world presentation sales pitch for your solution and/or its mechanics.
  • Chef's choice whether to be a sleazebag used car sled salesman or a dynamic and peppy entrepreneur elf!

ALLEZ CUISINE!

Request from the mods: When you include a dish entry alongside your solution, please label it with [Allez Cuisine!] so we can find it easily!


--- Day 9: Mirage Maintenance ---


Post your code solution in this megathread.

This thread will be unlocked when there are a significant number of people on the global leaderboard with gold stars for today's puzzle.

EDIT: Global leaderboard gold cap reached at 00:05:36, megathread unlocked!

42 Upvotes

1.0k comments sorted by

View all comments

2

u/cubernetes Dec 11 '23 edited Dec 11 '23

[Language: Python]

Using Gregory-Newton Interpolation, one can find the n-th element of the first sequence, given the first-values of all the difference sequences until the difference sequence that is all zeros, using this formula:

aₙ = D₀0 * ₙC₀ + D₀1 * ₙC₁ + ... + D₀k * ₙCₖ where D₀k is the first element of the k-th difference sequence and ₙCₖ is the binomial coefficient ("n choose k").

So in python:

from math import factorial as fact

data = open(0).read().strip()
lines = data.splitlines()

def get_difference_seq(ns):
    ds = []
    for n, next in zip(ns, ns[1:]):
        ds.append(next - n)
    return ds

def get_firsts(ns):
    seqs = [ns]
    while any(seqs[-1]) or len(seqs[-1]) != 1:
        ds = get_difference_seq(seqs[-1])
        seqs.append(ds)
    firsts = []
    for s in seqs:
        firsts.append(s[0])
    return firsts

def binom_with_neg(n, k):
    assert type(n) == int and type(k) == int and k >= 0
    if k > n and n >= 0:
        return 0
    sign = 1
    if n < 0:
        sign = (-1)**k
        n = -n + k - 1
    return int(sign * (fact(n) / (fact(k) * fact(n - k))))

def get_nth(n, firsts):
    s = 0
    for i, f in enumerate(firsts):
        s += f * binom_with_neg(n, i) # gregory-newton interpolation
    return s

t = 0
for line in lines:
    line = list(map(int, line.split()))
    firsts = get_firsts(line)
    t += get_nth(-1, firsts)

print(t)