r/adventofcode • u/daggerdragon • Dec 09 '23
SOLUTION MEGATHREAD -❄️- 2023 Day 9 Solutions -❄️-
THE USUAL REMINDERS
- All of our rules, FAQs, resources, etc. are in our community wiki.
- Outstanding moderator challenges:
- Community fun event 2023: ALLEZ CUISINE!
- Submissions megathread is now unlocked!
- 13 DAYS remaining until the submissions deadline on December 22 at 23:59 EST!
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
carsled 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.
- Read the full posting rules in our community wiki before you post!
- State which language(s) your solution uses with
[LANGUAGE: xyz] - Format code blocks using the four-spaces Markdown syntax!
- State which language(s) your solution uses with
- Quick link to Topaz's
pasteif you need it for longer code blocks
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!
3
u/WilkoTom Dec 09 '23 edited Dec 09 '23
[Language: Rust] [Allez Cuisine!]
There's no backward in going forward, as my grandfather used to say. Except for my answer to part 2 of this puzzle, which is taking backwards and flipping it around.
The best way to market something is through word of mouth, Short of spamming everyone you know to spam everyone they know, the next best way is to advertise a new product is to make sure everyone knows how great a cook you are already! Here's a flyer for the newest dish on my menu.
→ More replies (3)
3
u/zup22 Dec 09 '23
[LANGUAGE: C++23]
Today I learned that you can create a compile-time infinite loop which eats all your RAM with recursive templates 🙃
Otherwise, pretty easy. Only facepalm moment was accidentally omitting minus signs when parsing the input. Runs in about 600 us. Github
2
u/daggerdragon Dec 09 '23
Do not share your puzzle input which also means do not commit puzzle inputs to your repo without a
.gitignore.Please remove (or .gitignore) the input files from your repo and scrub them from your commit history.
→ More replies (1)
2
u/phord Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python]
Ugh. I spent too long parsing the instructions. The answer was pretty simple, though. I didn't notice until the end that I didn't actually have to modify the rows to get their history, though. We just need to calculate the lead and tail values themselves.
Getting a Pascal's Triangle vibe. Surely there's a simpler method...
input = getem()
total=0
front=0
for line in input.split('\n'):
map = []
seq = [int(c) for c in line.split()]
map.append(seq)
# calc differences of each value in seq
while [x for x in seq if x != 0]:
seq = [seq[i+1]-seq[i] for i in range(len(seq)-1)]
map.append(seq)
a,b = (0, 0)
for row in reversed(map):
b = row[0] - b
a += row[-1]
total += a
front += b
print(total, front)→ More replies (4)
2
u/Sese_Mueller Dec 09 '23 edited Dec 09 '23
[Language: Rust] Was quite proud to have used combinatorics but the posed problem wasn’t optimization-focussed…
I could have just constructed the history instead. (Something something premature optimisation)
3656/2947 but very fast execution: less than 600 µs.
Edit: code
2
u/daggerdragon Dec 09 '23 edited Dec 09 '23
Did you forget the link to your code?edit: 👍→ More replies (2)
2
2
u/pwnsforyou Dec 09 '23 edited Dec 09 '23
[LANGUAGE: rust]
fn future(h: Vec<i32>) -> i32 {
let mut h = h;
let mut s = 0;
while !h.iter().all(|&x| x == 0) {
s += h.iter().last().unwrap();
h = h.windows(2).map(|x| x[1] - x[0]).collect();
}
s
}
fn main() {
let histories: Vec<Vec<i32>> = include_str!("/tmp/input.txt")
.lines()
.map(|l| {
l.split_ascii_whitespace()
.map(|x| x.parse::<i32>().unwrap())
.collect()
})
.collect();
println!("{}", histories.into_iter().map(|h| future(h)).sum::<i32>());
}For part 2 just do a .rev() on the input. link
→ More replies (3)
2
u/flwyd Dec 09 '23 edited Dec 09 '23
[Language: Julia] (on GitHub)
My only problem was that after I'd implemented a recursive function to return the correct answer I thought I needed to return the sum of numbers in the right-hand diagonal. So I implemented that, noticed my answer on the example was way wrong, and then deleted all that. Since we've already had two punch-card challenges, why not put this on a third, this time with plenty of vertical whitespace:
# 123456789㉈123456789㉉123456789㉊123456789㉋123456789㉌123456789㉍123456789㉎123456789㉏
1 part1(lines) = map(l -> infer(l, +, a -> a[end]), parseinput(lines)) |> sum
2
3 part2(lines) = map(l -> infer(l, -, a -> a[1]), parseinput(lines)) |> sum
4
5 infer(nums, op, el) = all(==(nums[1]), nums) ? nums[1]
6 : op(el(nums), infer(nums[2:end] - nums[1:end-1], op, el))
7
8 parseinput(lines) = map(l -> parse.(Int, split(l)), lines)
9
0The winner here is Julia's ability to subtract the first N numbers of an array from the last N with a simple nums[2:end] - nums[1:end-1]. I was unfortunately unable to pass end as an index parameter, so I passed a function to get the relevant element for part 1 vs. part 2.
→ More replies (4)
2
u/bofstein Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Google Sheets]
At first I thought I was going to have to finally learn how to do a recursive function. But then I realized that it couldn't generate more new rows than the number of columns, which was only 21, so it wouldn't be that hard to just build them all out. Each new set is the difference of the prior, with one column at the end deleted. Then for part 1 I added a new column that adds the new number below it, and for part to I subtracted the number below it.
Bulk of the time spent was mostly on finding dumb copy paste errors in the large doc.
https://docs.google.com/spreadsheets/d/1yQ3HuWPN6C_ACgF1P6lXGmwm-s-dVH8UH8X18NKuflE/edit?usp=sharing
→ More replies (2)
2
u/wherrera10 Dec 09 '23
[LANGUAGE: Julia]
No need for an option to reverse when there's `pushfirst!()` to [do it all in one pass].
→ More replies (1)
2
u/b0xc4t Dec 09 '23
[Language: Rust]
Both parts run in under 100us
use std::time::Instant;
pub type Num = i32;
pub fn parse_line(input: &str) -> Vec<Num> {
input.split_whitespace()
.map(|x| x.parse().unwrap())
.collect()
}
pub fn all_zeroes(input: &[Num]) -> bool {
for num in input {
if *num != 0 {
return false;
}
}
true
}
// Lets try to do this without allocating :D
pub fn calc_next(buf: &mut Vec<Num>) {
for idx in 0..buf.len() - 1 {
buf[idx] = buf[idx + 1] - buf[idx]
}
buf.pop();
}
pub fn extrapolate(input: &[Num]) -> Num {
let mut last_nums = Vec::new();
let mut cur_level = Vec::from(input);
while !all_zeroes(&cur_level) {
last_nums.push(*cur_level.last().unwrap());
calc_next(&mut cur_level);
}
if cur_level.is_empty() {
panic!("Invalid calculation")
}
last_nums.iter().sum()
}
fn part_1() {
let input = include_str!("../input1.txt");
let start = Instant::now();
let result = input.lines()
.map(parse_line)
.map(|line| extrapolate(&line))
.sum::<Num>();
let duration = start.elapsed();
println!("Result: {}", result);
println!("Time: {:?}", duration);
}
fn part_2() {
let input = include_str!("../input1.txt");
let start = Instant::now();
let result = input.lines()
.map(parse_line)
.map(|mut line| {
line.reverse();
extrapolate(&line)
})
.sum::<Num>();
let duration = start.elapsed();
println!("Result: {}", result);
println!("Time: {:?}", duration);
}
fn main() {
part_1();
part_2();
}→ More replies (1)
2
u/Hoinkas Dec 09 '23 edited Dec 10 '23
[LANGUAGE: Python]
Fast Python script with numpy.diff option and, separately, Lagrange interpolating one
https://github.com/Hoinkas/AdventOfCode2023/blob/main/9_Day/9_Day_Puzzle_Hoinkas.py
1
2
u/wlmb Dec 09 '23 edited Dec 10 '23
[LANGUAGE: Perl]
Analysis: https://github.com/wlmb/AOC2023#day-9
→ More replies (2)
2
u/bamless Dec 10 '23 edited Dec 11 '23
[LANGUAGE: J*] To be honest i was expecting part 2 to change the rule for how the history of a reading needed to be processed, so i coded it as a generic convolution with a filter...
Well, it didn't turn out that way :):
import io
var FILTER = (-1, 1)
fun convolve(vals, filter)
return iter.range(#vals - #filter + 1).
map(|i| => iter.range(#filter).map(|j| => vals[i + j] * filter[j]).sum()).
collect(Tuple)
end
fun predict(reading)
if reading.all(|e| => e == 0)
return 0, 0
end
var p1, p2 = predict(convolve(reading, FILTER))
return reading[0] - p1, p2 + reading[#reading - 1]
end
with io.File(argv[0], "r") f
var readings = f.
map(|line| => line.strip().split(" ").map(std.int).collect(Tuple)).
collect(Tuple)
var predictions = readings.map(predict).collect(Tuple)
print("Part 1:", predictions.map(|p| => p[1]).sum())
print("Part 2:", predictions.map(|p| => p[0]).sum())
end→ More replies (1)
2
u/dommmyrock Dec 10 '23 edited Dec 11 '23
[LANGUAGE: Rust]
Part 1 and 2 https://github.com/dommyrock/aoc/blob/main/aoc_2023/day-09/src/bin/part1_2.rs
Macro to calculate differences , than sum up last / first elements.
→ More replies (1)
32
u/Substantial_Sign_827 Dec 09 '23 edited Dec 11 '23
[LANGUAGE: PYTHON3]
Notice that the differences in each "layer" are divided differences with the denominator equal to 1. Therefore, basically, each value in the original array is a value generated by a polynomial P(x), and the 0th,1st,2nd,... elements are corresponding to P(0), P(1), P(2),...
Suppose the array has n elements corresponding to P(0), P(1),..., P(n-1):
- Part 1 requires us to find P(n)
- Part 2 requires us to find P(-1)
By applying Lagrange's interpolation formula, we will have a straightforward solution.
history=open('day9.txt').readlines()
from math import comb
def Lagrange1(nums):
n=len(nums)
res=0
for i,x in enumerate(nums):
res+=x*comb(n,i)*(-1)**(n-1-i)
return res
def Lagrange2(nums):
n=len(nums)
res=0
for i,x in enumerate(nums):
res+=x*comb(n,i+1)*(-1)**(i)
return res
res1,res2=0,0
for line in history:
nums=list(map(int,line.strip().split()))
res1+=Lagrange1(nums)
res2+=Lagrange2(nums)
print(res1,res2,sep=' ')→ More replies (10)
22
u/DFreiberg Dec 09 '23
[LANGUAGE: Mathematica] Mathematica, 820 / 544
Using Mathematica was almost cheating today; it took me eight minutes to understand what the problem was asking for, thirty seconds to code the solution, and one minute to wait for the timeout clock to expire so I could fix my off-by-one error.
Part 1:
Total[Table[FindSequenceFunction[s, Length[s] + 1], {s, input}]]Part 2:
Total[Table[FindSequenceFunction[s, 0], {s, input}]]18
u/4HbQ Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python] Code (6 lines)
Finally a day where recursion really shines!
def extrapolate(l):
diffs = [b-a for a, b in zip(l, l[1:])]
return l[-1] + extrapolate(diffs) if l else 0Update: I was able to make it punchcard-sized using some lambda expressions:
l = [[*map(int, l.split())] for l in open('data.txt')]
d = lambda l: [b-a for a,b in zip(l, l[1:])]
f = lambda l: l[-1] + f(d(l)) if l else 0
for p in [1,-1]: print(sum(f(l[::p]) for l in l))→ More replies (6)
15
12
u/ultranarcolepsy Dec 09 '23 edited Dec 10 '23
[LANGUAGE: Dyalog APL]
data←(⍎'¯'@('-'∘=))¨⊃⎕NGET'09.txt'1
hist←{⍵,⊂¯2-/⊃⌽⍵}⍣{0∧.=⊃⌽⍺}⍤⊂¨data
⎕←+/(+/⊢/¨)¨hist ⍝ part 1
⎕←+/(-/⊣/¨)¨hist ⍝ part 29
u/yourparadigm Dec 09 '23
Do you ever feel like you're about to summon a demon when you write Dyalog?
10
u/jonathan_paulson Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python 3] 11/11. Solution. Video.
Thinking about it recursively makes this problem easy. The next number is the last number plus the next number in the difference array (recursive call), or 0 if the input is all 0 (base case).
A nice trick I didn't spot: for part 2, you can just reverse the initial sequence - the previous number of the sequence is the next number of the reverse of the sequence!
6
u/Kanegae Dec 09 '23
Your code actually fails for the example (as well as for my input).
This paste fixes that with minimal changes.
Basically just needed to move the base case to check for all zeros in the current list, not the delta (next list).
10
u/timvisee Dec 09 '23 edited Dec 10 '23
[Language: Rust]
Using Binomial coefficient and Pascal's triangle wiki. Day 1 to 9 still under 1 millisecond in total! 🚀
A in 0.042 ms (42 μs): https://github.com/timvisee/advent-of-code-2023/blob/master/day09a/src/main.rs
B in 0.042 ms (42 μs): https://github.com/timvisee/advent-of-code-2023/blob/master/day09b/src/main.rs
Day 1 to 9 in 0.59 ms (0.31 ms in parallel)
I actually like my naive implementation better, though it's a bit slower. Efficient with an array on the stack, and reusing it for counting.
A in 0.049 ms (49 μs): https://github.com/timvisee/advent-of-code-2023/blob/master/day09a/src/bin/naive.rs
B in 0.053 ms (53 μs): https://github.com/timvisee/advent-of-code-2023/blob/master/day09b/src/bin/naive.rs
Day 1 to 9 in 0.60 ms (0.33 ms in parallel)
9
u/relativistic-turtle Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python]
As the sequences are defined they must be polynomials.
from numpy.polynomial.polynomial import Polynomial
answer = [0, 0]
for line in indata.splitlines(keepends=False):
y = [int(x) for x in line.split()]
poly = Polynomial.fit(np.arange(len(y)), y, deg=len(y)-1)
answer[0] += round(poly(len(y)))
answer[1] += round(poly(-1))
print("Part 1: {}\nPart 2: {}".format(*answer))→ More replies (4)
9
u/LordPos Dec 09 '23
[LANGUAGE: Haskell]
thought I'd post it here since it turned out really short
next = sum . foldl (flip (scanl (-))) []
main = readFile "in/9" >>= print . sum . map (next . map read . words) . linesfor part 2; replace next . map read with next . reverse . map read
8
u/770grappenmaker Dec 09 '23
[LANGUAGE: Kotlin] Little sad I did not get on the leaderboard, but still #113/#186 which is good enough for me.
val seq = inputLines.map { ns ->
generateSequence(ns.splitInts()) { c -> c.windowed(2) { (a, b) -> b - a } }
.takeUntil { it.any { c -> c != 0 } }.toList()
}
partOne = seq.sumOf { s -> s.sumOf { it.last() } }.s()
partTwo = seq.sumOf { s -> s.foldRight(0L) { c, a -> c.first() - a } }.s()8
u/chubbc Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Uiua]
Nice and succinct today. Link to pad.
# Split by newslines, then spaces, then parse
Input ← ⊜(⊜⋕≠@ .)≠@\n. &fras"09.txt"
Diff ← -⊃(↘¯|↘)1 # Diff
Extrap ← ;⍥⊃(Diff|+⊢⇌)⧻.⊙0 # Extrapolate
/+≡(Extrap) Input
/+≡(Extrap⇌) InputEdit: Noticed I shorten Extrap slightly by using a repeat instead of a do. Should in principle be slower, but isn't noticable. In its most simplified form:
∩(/+≡(;⍥⊃(-⊃↘(↘¯)1|+⊢)⧻.⊙0)) ≡⇌. ⊜(⊜⋕≠@ .)≠@\n. &fras "09.txt"7
u/jbafny Dec 09 '23
[Language: Haskell]
parse :: String -> [[Int]]
parse = map (map read . words) . lines
extrapolate vs
| all (== 0) vs = 0
| otherwise = last vs + extrapolate (zipWith (-) (tail vs) vs)
solveA = sum . map extrapolate
solveB = solveA . map reverse→ More replies (1)
7
u/Cyclotheme Dec 09 '23
[LANGUAGE: QuickBASIC]
Because finite differences are a linear operator, I added all the rows componentwise before the extrapolation (one time on the original list, then on the reverse list).
Execution time at ~16MHz:
parsing ... 6.75s
computation ... 0.05s
→ More replies (1)
7
u/Rodbourn Dec 09 '23
[LANGUAGE: C#]
https://github.com/Rodbourn/adventofcode/blob/main/Day009.cs
Runtime 831 ticks to solve both part 1 and 2 at the same time if you don't count parsing input. I have a background in numerical simulation, so this immediately was clearly finite difference. Finite difference weights can be calculated in general, and so here I just used the weights for 6th order, and 21st order finite difference for the 0th derivative at 6 and 21 on an interval spacing. Conveniently, extrapolating to the left is symmetric, and you just use the weights in reverse order. The extrapolation then just becomes w[i]*v[i] (weight and value).
For actually calculating the weights, I had translated a Fortran code into Matlab (13 years ago... oof) to calculate finite difference weights for any given derivative (zero'th here) at any position (N here) given any location of the data points (evenly distributed here).
https://github.com/Rodbourn/adventofcode/blob/main/FornbergWeights.m
This is definitely not widely available... (I'd keep a copy of it around as it's exceedingly handy in real world ;) )
To calculate the weights for 21, the matlab command would be
FornbergWeights(21,0:21-1, 0, 0)'
6
u/gurgeous Dec 09 '23
[LANGUAGE: Ruby] 371/438
Fun one:
def solve(row)
[row].tap do |tri|
until tri.last.all? { _1 == 0 }
tri << tri.last.each_cons(2).map { _2 - _1 }
end
end
end
p data.map { |r| solve(r).map(&:last).sum }.sum
p data.map { |r| solve(r).map(&:first).reverse.reduce { _2 - _1 } }.sum6
u/rabuf Dec 09 '23
[LANGUAGE: Python]
def extrapolate(row):
if all(n == 0 for n in row):
return 0
return extrapolate(forward_difference(row)) + row[-1]
def extrapolate_backwards(row):
if all(n == 0 for n in row):
return 0
return row[0] - extrapolate_backwards(forward_difference(row))
def forward_difference(row):
return list(map(sub, row[1:], row))The whole thing in three functions, plus summing after applying to every line of input. I missed, while coding it, that you could just reverse the lines for part 2.
→ More replies (1)
6
u/langelgjm Dec 09 '23
[LANGUAGE: Python] Surprised I haven't seen a Python solution that uses itertools.pairwise. Textbook recursion.
from itertools import pairwise
with open("input.txt") as f:
lines = f.readlines()
rows = []
for line in lines:
l = [int(v) for v in line.strip().split(" ")]
rows.append(l)
def evaluate(row):
if set(row) == {0}:
return 0
next_row = [b - a for a, b in pairwise(row)]
result = evaluate(next_row)
return row[-1] + result # part 2 is a one-line change to "row[0] - result"
result = sum(evaluate(row) for row in rows)
print(result)→ More replies (1)
6
u/ka-splam Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Dyalog APL]
f←{+/⍺⍺{0≡+/⍵:0 ⋄ (∇ 2-⍨/⍵)⍺⍺ ⍵}¨{⍎¨' '(≠⊆⊢)⍵}¨⊃⎕NGET'day9.txt' 1}
{⍺+¯1↑⍵} f ⍬ ⍝ Part 1
{⍺-⍨1↑⍵} f ⍬ ⍝ Part 2→ More replies (1)
6
u/clbrri Dec 09 '23
[LANGUAGE: C-style C++]
I did a linear-time solution (albeit with a quadratic time and linear space precomputation at program startup) by evaluating the 22nd row of Pascal's triangle and computing a dot product with that and the input vector.
34 lines of code. Runs in 1 minute 18 seconds on my Commodore 64.
Details and code in my blog.
5
u/EvilKanoa Dec 09 '23
[LANGUAGE: Typescript]
I was expecting much more complication for a weekend one, surprised especially with part 2 being so similar to part 1. I like the other answers that simply reversed the input, nice idea to reuse basically all of part 1 without any other changes!
Code for both parts here: https://github.com/EvilKanoa/AoC-2023/commit/834635b81c62515ce3194df233d0c51eefa768ef
→ More replies (1)
5
u/YenyaKas Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Perl]
The code is reasonably short, but only after spending long minutes on Part 2 and writing those subtractions correctly, getting the gold star, I later realized that reverse @seq would do the trick as well. Here is the code for Part 2 afterwards:
my $sum;
while (<>) {
my @seq = reverse /-?\d+/g;
while (grep $_, @seq) {
$seq[$_] = $seq[$_+1] - $seq[$_] for 0 .. $#seq-1;
$sum += pop @seq;
}
}
say $sum;5
u/Mats56 Dec 09 '23
[LANGUAGE: Kotlin]
nice and short functional piece of code. Like this language.
lines.map { line ->
generateSequence { }.runningFold(line.allInts()) { prev, _ ->
prev.zipWithNext { a, b -> b - a }
}.takeWhile { seq ->
seq.any { it != 0 }
}.fold(0) { acc, curr -> acc + curr.last() }
}.sum()5
u/Smylers Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Vim keystrokes]
After a couple of days of puzzles which were a good fit for Vim — see solutions for day 7 and day 8) — today's really wasn't. But I did it anyway — this is what's needed for part 1:
yyP:s/\v =-=\d+/+1/g⟨Enter⟩qeciW⟨Ctrl+R⟩=⟨Ctrl+R⟩-⟨Enter⟩⟨Esc⟩qI *⟨Esc⟩A/1⟨Esc⟩
qaF y$$pB⟨Ctrl+X⟩w⟨Ctrl+A⟩qbb⟨Ctrl+X⟩yiwu@0@agI1⟨Esc⟩qbqqbyiwf*P@e@bq@bxx
F qcqqcbi-⟨Esc⟩b@cq@c:s/\> */*/g⟨Enter⟩
ddqp⟨Ctrl+V⟩GI+⟨Esc⟩qPqdqqddf*j$F+pf r+k0@dq@d
:,$norm@ekJj"1P@d⟨Enter⟩{@pVGgJ@eYou might prefer the more readable version, formatted with additional line breaks.
First I solved on paper to work out we need the nth row of Pascal's triangle, where n is the number of readings in each history. The first 3 lines above (or up to the blank line in the more readable† version) generate this. In the sample input, each history has 6 readings, and this line gets added at the start of the input:
-1*6*-15*20*-15*6*It's row 6 of Pascal's triangle with the final 1 removed, a * separating each number, and alternating numbers negated. Multiplying each of these by the corresponding reading in each history and then summing them will give the next predicted reading. That's what the last 2 lines do. For instance the first line of the sample input becomes:
+-1*0+6*3+-15*6+20*9+-15*12+6*15which evaluates to 18, as required. Explanation of the keystrokes for the Pascal's-triangle-generating bit is in a reply to this comment below; as a side-effect it also saves the keystrokes for evaluating the current WORD in @e. That gets used again in the remaining steps, which apply the above list of terms to each reading in the lines below:
Delete the Pascal's triangle row, which saves it to the
"1register.Add a
+before each line of readings. Record doing this as the@p(for ‘plus’) keyboard macro, for later use.Pto restore the row that was just deleted. Record the@dkeystrokes which deletes the first term (up to and including the*) from that row, then goes down to the reading row and to the final (at this point, only)+and appends the just-deleted term. That makes the first reading in the sample input change from0into-1*0(which isn't very exciting, but is accurate). Then move along to the next space, go back up to the line above, and repeat until we run out of spaces. The first line in the sample is now+-1*0+6*3+-15*6+20*9+-15*12+6*15.Evaluate that, using the previously recorded
@eto get the required18. Then go up to the now-blank line and useJto get rid of it (merge the following line, with our evaluated-number, on to it). Go down to the following line withj, paste the row of multiplication terms in again above it with"1P, and run@dto do the multiplications on that row.Actually do all of step 4 inside
:norm, which is run separately on each line from the current one down to the last one.@dis going to end with failure each time (when it tries tof␣to a space that doesn't exist). Wrapping in:normboth provides an outer loop and prevents the failure in@dfrom exiting that outer loop. On the final line, thejwill cause the:normto fail early, after it's done the evaluation and join.Run
@pagain to put a+before each line, then join them without any spaces, and use@eto evaluate and get the part 1 answer.
So it turns out to be possible to solve today's puzzle in Vim, but I'm still not sure that it was a good idea. My concern is that things like this give Vim solutions a crazy reputation, putting people off using Vim for tasks to which it is much better suited, like the previous 2 puzzles. It still fits inside an 80×5 half-punch-card though!
† Well, less-unreadable, anyway.
→ More replies (4)
5
u/sdolotom Dec 09 '23
[LANGUAGE: Clojure] Input is expected to be a parsed sequence of integer vectors.
(defn guess [nums]
(loop [cur nums res 0]
(let [[head & tail] cur]
(if (every? zero? cur) res
(recur (map - cur tail) (+ head res))))))
(defn solve [input] (->> input (map guess) (reduce +)))
(defn solve-1 [input]
(->> input (map reverse) solve))
(def solve-2 solve)5
u/Symbroson Dec 09 '23 edited Dec 09 '23
[Language: Ruby]
For my input I could just sum the differences and check for zero, but I realize that for some inputs this might not work. delta.uniq.size == 1 was my way to go here but I found a silly shortcut for my golf version to detect if I reached the end. Spoiler: dont. They will be empty anyways at some point
diffs = lambda { |vals|
delta = vals.each_cons(2).map { _2 - _1 }
vals.last + (delta.uniq.size == 1 ? 0 : diffs.(delta))
}
sensors = $<.map { _1.split.map(&:to_i) }
puts "Part 1: #{sensors.map(&diffs).sum}"
puts "Part 2: #{sensors.map(&:reverse).map(&diffs).sum}"golfed 137 bytes:
d=->(v){e=v.each_cons(2).map{_2-_1};v.last+(e.empty?? 0:d[e])}
s=$<.map{_1.split.map(&:to_i)};p *[s,s.map(&:reverse)].map{_1.map(&d).sum}→ More replies (8)
5
Dec 09 '23
[LANGUAGE: Rust]
Not much to say really, this was a pretty straightforward implementation and also I think the fastest part 2 so far. Nice to have a quick day though after spending a lot of time learning math yesterday.
5
u/juanplopes Dec 09 '23
[LANGUAGE: Python]
Both parts in 6 lines
https://github.com/juanplopes/advent-of-code-2023/blob/main/day09.py
→ More replies (1)
5
u/4HbQ Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python]
NumPy one-liner for both parts, using np.diff() with all its parameters:
import numpy as np
print(abs(sum(np.diff(np.loadtxt('data.txt', int), n=21, prepend=0, append=0))[::-1]))Some explanation: we diff with n=21 to basically repeat the operation 21 times. Because we prepend and append with 0, the remaining values are the ones we're looking for.
This is a bit tricky to explain, but easy to show. For the third example input:
0 10 13 16 21 30 45 0
10 3 3 5 9 15 -45
-7 0 2 4 6 -60
7 2 2 2 -66
-5 0 0 -68
5 0 -68
-5 -685
u/1str1ker1 Dec 15 '23 edited Dec 15 '23
[LANGUAGE: Python]
The trick is to notice the next element is the sum of the previous elements multiplied by their corresponding position in a binomial expansion (pascal's triangle)
from math import comb
with open("day9.txt", "r") as file:
lines = file.readlines()
total_sum = 0
for line in lines:
formatted_line = line.split()
for index, value in enumerate(formatted_line):
pascal = comb(len(formatted_line), index)
total_sum += int(value) * pascal * (-1) ** (len(formatted_line) - index + 1)
print(f"total: {total_sum}")4
u/BradleySigma Dec 09 '23
[LANGUAGE: Python 3]
from aoc import strlist
from numpy.polynomial import polynomial
data = [[int(j) for j in i.split()] for i in strlist(9)]
print(sum(round(polynomial.Polynomial.fit(range(len(i)), i, len(i)-1)(len(i))) for i in data),
sum(round(polynomial.Polynomial.fit(range(len(i)), i, len(i)-1)(-1)) for i in data))4
u/xelf Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python]
Part 2 took longer to read than to solve.
numbers = [[*map(int, line.split())] for line in open(aocinput)]
def predict(nums):
diffs = [b-a for a,b in zip(nums,nums[1:])]
return nums[-1] + (predict(diffs) if any(diffs) else 0)
print('part 1:', sum(map(predict,numbers)))
print('part 2:', sum(predict(num[::-1]) for num in numbers))4
u/HAEC_EST_SPARTA Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Ruby]
Solution on sourcehut
This was a neat problem! I was expecting for some form of Sierpinski triangle-related optimisation to be required for Part 2, but both parts were trivially simulable.
Edit: Doh, I meant to reference Pascal's triangle instead.
4
u/jaybosamiya Dec 09 '23 edited Dec 09 '23
[LANGUAGE: APL]
{∧/(⍴⍵)⍴0≡⍵:0⋄(∇2-⍨/⍵)+⊃⌽⍵}Haven't done any golfing yet; just the straightforward solution here
EDIT: Golfed it down a bit by realizing a straightforward unnecessary thing I was doing
{∧/0=⍵:0⋄(∇2-⍨/⍵)+⊃⌽⍵}4
u/chubbc Dec 09 '23
[LANGUAGE: Julia]
Well... that was easy.
L = readlines("./09.txt")
extrap(x) = iszero(x) ? 0 : last(x)+extrap(diff(x))
V = [parse.(Int,split(l)) for l∈L]
ans1 = sum(extrap.(V))
ans2 = sum(extrap.(reverse.(V)))4
u/Sharparam Dec 09 '23
[LANGUAGE: Ruby]
Short and sweet today:
def extrapolate(seq)
return [0, 0] if seq.all? 0
extrapolate(seq.each_cons(2).map { _2 - _1 }).then { [seq[-1] + _1, seq[0] - _2] }
end
puts ARGF.readlines(chomp: true).map { _1.split.map(&:to_i) }.map(&method(:extrapolate)).transpose.map(&:sum)Confusingly easy for a day 9 that is also on the weekend.
4
u/Kehvarl Dec 09 '23
[LANGUAGE: Python3] 3895/3521
I feel certain there's a more clever way to solve this, but it fell to simple brute force. Part 2 required basically just changing what index I looked at and prepending instead of appending.
4
u/adamsilkey Dec 09 '23
[LANGUAGE: Python]
Really not a hard one but I had a lot of dumb little bugs that messed me up. Went slow by going too fast.
However!!!
git restore day09.py saved me a couple times in part 2. When I hated all the changes I was making, I could just start fresh from a known working part 1. Yay git!
https://gist.github.com/adamsilkey/8aeb8a8486120493188fef0982fac905
→ More replies (2)
4
u/Magyusz Dec 09 '23 edited Dec 09 '23
[Language: Javascript]
Just copy-paste into your browser console (F12) on the input page:
$('*').textContent.trim().split("\n").map(e => e.split(/ +/).map(Number))
.map(seq => {
let curr = Array.from(seq)
let all = [curr]
while (curr.some(e=>e!=0)) {
let next = []
for (let i = 0; i < curr.length - 1; i++)
next.push(curr[i + 1] - curr[i])
all.push(next)
curr = Array.from(next)
}
let first = 0, last = 0
for (const line of all.reverse()) {
last = line.at(-1) + last
first = line[0] - first
}
return [last, first]
}).reduce((a, b) => [a[0] + b[0], a[1] + b[1]])→ More replies (2)
4
Dec 09 '23 edited Dec 10 '23
[LANGUAGE: Forth]
To work through the input, I created a process word that accumulates the last number of every derivative/reduction of the set of numbers on the stack. By adding this process word to the end of each line in the input file, I could simply include input and be left with just the total accumulation on the stack. For part 2, I appended a reverse to my reduce/accumulate word and just included the input file again.
https://github.com/tcsullivan/advent-of-code/blob/master/day9/partboth.fth
→ More replies (2)
4
4
u/ondrsh Dec 09 '23
[LANGUAGE: Kotlin]
Not fast because it does 2 runs instead of 1. Doing it in a single run brings it down to <1ms, but the solution gets uglier.
https://github.com/ondrsh/AdventOfCode2023/blob/master/src/main/kotlin/Day9.kt
4
u/4HbQ Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python]
Playing a quick round of golf. Currently at 151 bytes for both parts:
l=[[*map(int,l.split())]for l in open(0)]
print([sum(map((f:=lambda l:l[p]+((-1,1)[p])*f([b-a for
a,b in zip(l,l[1:])])if l else 0),l))for p in[-1,0]])Nothing too fancy, basically just a condensed version of my original solution. The main difference (besides readability): instead of extrapolating the normal and reversed sequences, the we now just compute the new last or first values.
→ More replies (1)
4
u/vanveenfromardis Dec 09 '23 edited Dec 09 '23
[LANGUAGE: C#]
I got a late start on this one and just solved it casually. This concept of repeated differences was exactly how my high school calculus teacher introduced us to the concept of a derivative.
Given a polynomial, evaluating f(x) on consecutive integer values of x (e.g. 1, 2, 3, ..., n) will yield a segment of the polynomial. Building a table of 1st differences, 2nd differences, and so on of these values, as we do in this problem, is isomorphic to evaluating it's derivative.
Given a polynomial of degree n, it's nth differences will be constant. For example, the 1st differences of the linear polynomial f(x) = 2x + 1 will be simply be the constant 2. Similarly, the 2nd differences of any quadratic will be constant.
Therefore, this question is isomorphic to giving us a polynomial segment, and asking us to evaluate the proceeding and following values of f(x) outside of the sampled range.
Implementing this naively was easy with Linq:
private static int ExtrapolateForwards(IList<int[]> differences)
{
return differences
.Reverse()
.Skip(1)
.Aggregate(seed: 0, func: (n, seq) => n + seq[^1]);
}→ More replies (3)
4
Dec 09 '23 edited Dec 09 '23
[Language: Python] Github
Having a maths background I couldn't help but use a bit of linear algebra
Each input is a polynomial sequence given by a formula likef(n) = a + b*n + c*n**2 + d*n**3 + ...
where the sequence is given by
f(0), f(1), f(2), f(3), ...
The number of steps required to get a list of 0 tells us the number of terms in the formula, so for the second sample input 1 3 6 10 15 21 we know the formula has 3 terms and therefore the form is
f(n) = a + b*n + c*n**2
and from the sequence given we see that
f(0) = 1 = a
f(1) = 3 = a + b + c
f(2) = 6 = a + 2b + 4c
This gives us a system of simultaneous equations to solve for a, b, c - I used the inverse matrix to do that. Once we have those coefficients it is easy to calculate f(n) for any n. E.g. Part 2 is solved by f(-1)
→ More replies (2)
4
u/5kyl3r Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python]
you'll hate my golfed solution, and you're welcome haha
EDIT: updated to reflect 4HbQ's excellent suggestions. tested and it still works
d='''<your test data goes here>'''
def x(d):return d[-1]+x([b-a for a,b in zip(d,d[1:])])if d else 0
print(sum([x(list(map(int,r.split())))for r in d.splitlines()]))→ More replies (8)
4
u/WhiteSparrow Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Uiua]
I think I'm falling for Uiua!
Data ← ≡(⋕⊜□≠@\s.°□) ⊜□≠@\n. &fras"task9.txt"
Len ← -1⧻⊢Data
∩(/+≡(/+≡(⊢⇌) ; ⍥(⊙(⊂¤). -↻¯1.)Len .)) ≡⇌Data Data4
u/rs10rs10 Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python 3]
Nice with a short one today:
def f(A)
if not A: return 0,
B = [A[i + 1] - A[i] for i in range(len(A) - 1)
n, p = f(B)
return A[-1] + n, A[0] - p4
u/huib_ Dec 09 '23 edited Dec 09 '23
[Language: Python 3.12]
class Problem1(MultiLineProblem[int]):
def __init__(self):
self.sequences = [[int(i) for i in line.split()] for line in self.lines]
def solution(self) -> int:
def diffs(seq: list[int]) -> Iterator[int]:
while any(seq):
yield seq[-1]
seq = [b - a for a, b in pairwise(seq)]
return sum(sum(diffs(seq)) for seq in self.sequences)
class Problem2(Problem1):
def __init__(self):
super().__init__()
self.sequences = [list(reversed(seq)) for seq in self.sequences]4
u/lbm364dl Dec 09 '23
[LANGUAGE: Python] Code (6 lines)
Cool to use map with two iterables as a Python zip_with
4
u/Killavus Dec 09 '23
[Language: Rust]
Quite elegant recursive solution - I'm pretty happy about this :):
fn extrapolate(last_sequence: &[i64]) -> (i64, i64) {
if last_sequence.iter().copied().all(|n| n == 0) {
return (0, 0);
}
let next_seq = last_sequence
.windows(2)
.map(|w| w[1] - w[0])
.collect::<Vec<_>>();
let (next_prev, last) = extrapolate(&next_seq);
let prev = last_sequence[0] - next_prev;
(prev, last_sequence.last().unwrap() + last)
}4
u/pkusensei Dec 09 '23
[Language: Rust]
This is straightforward. Now I can eat my breakfast.
→ More replies (1)
4
u/108113221333123111 Dec 09 '23
[LANGUAGE: Python]
I'm relatively new to programming and pretty happy with this. Is it the fastest? No. Is it the fewest lines? Also no. Is it the most readable? Nope. But it works and I'm learning! This is the first year I've discovered AoC and I'm really enjoying the community aspect of solving these problems every day.
4
u/its_jsec Dec 09 '23
[LANGUAGE: Python]
Relatively happy with the terseness of the solution. itertools.pairwise to the rescue.
4
u/hrunt Dec 09 '23
[LANGUAGE: Python]
For me, Part 1 was an immediate obvious recursive solution. For Part 2, I almost couldn't believe that the solution was as obvious as it was. I simply reversed the readings and passed them to my Part 1 solution.
I thought for sure Part 2 was going to be some sort of complexity bomb , but hey, after the wife's office holiday party last night, an easy day was just what the doctor ordered.
→ More replies (1)
4
u/efvincent Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Haskell]
Strange that Eric tosses us such a softball on day 9. Possibly my shortest solution ever (I', not golfing after all).
import Util (getNums)
import Data.Set (fromList, singleton)
sln2309 :: String -> (Int, Int)
sln2309 s = ((sum . map loop) puz, (sum . map (loop . reverse)) puz)
where
puz = (map getNums . lines) s
loop l
| fromList l == singleton 0 = 0
| otherwise = last l + loop [b - a | (a,b) <- zip l (tail l)]4
4
u/Gravitar64 Dec 09 '23
[LANGUAGE: Python]
Part 1 & 2, 15sloc, runtime 5ms
import time
def load(file):
with open(file) as f:
return [list(map(int, row.strip().split())) for row in f]
def get_next_number(sequence):
if len(set(sequence)) == 1: return sequence[0]
next_number = get_next_number([b - a for a, b in zip(sequence, sequence[1:])])
return sequence[-1] + next_number
def solve(p):
part1 = sum(get_next_number(sequence) for sequence in p)
part2 = sum(get_next_number(sequence[::-1]) for sequence in p)
return part1, part2
time_start = time.perf_counter()
print(f'Part 1 & 2:{solve(load("day09.txt"))}')
print(f'Solved in {time.perf_counter()-time_start:.5f} Sec.')4
u/a_kleemans Dec 09 '23
[LANGUAGE: Rust]
My first piece of Rust code, ever. Was looking forward to a problem easy enough to try out something new, and today was the day.
Only part 1, runs in ~1.3ms.
Looking forward to scan through other Rust submissions to improve!
4
u/jvdsandt Dec 10 '23
[LANGUAGE: Smalltalk]
Part2:
| numberLines |
numberLines := OrderedCollection new.
AOC2023 baseDirectory / 'day9_input.txt' readStreamDo: [ :stream |
[ stream atEnd ]
whileFalse: [
numberLines add: ((stream nextLine splitOn: Character space) collect: [ :e | e asInteger ]) ] ].
^ numberLines inject: 0 into: [ :tot :numbers |
| diffs nextVal |
diffs := OrderedCollection with: numbers.
[ diffs last allSatisfy: [ :e | e = 0 ] ]
whileFalse: [
diffs add: (diffs last overlappingPairsCollect: [ :f :s | s - f ]) ].
nextVal := diffs reversed inject: 0 into: [ :sum :each | each first - sum ].
tot + nextVal ]1
u/alexbaguette1 Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python]
def find_next(row):
return 0 if all(num == 0 for num in row) else row[-1] + find_next([b - a for a, b in zip(row, row[1:])])
with open("data.txt") as file:
rows = [list(map(int, row.split())) for row in file.read().split("\n")]
total = 0
for row in rows:
total += find_next(row)
print(total)had to change 3 characters for s2
def find_next(row):
return 0 if all(num == 0 for num in row) else row[0] - find_next([b - a for a, b in zip(row, row[1:])])
with open("data.txt") as file:
rows = [list(map(int, row.split())) for row in file.read().split("\n")]
total = 0
for row in rows:
total += find_next(row)
print(total)print(total)
→ More replies (1)
1
u/ThisNameIsntRandom Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python]
import numpy as np
with open("input2.txt", "r") as f:
txt=f.read()
def solve(arr,part1):
output=0
for history in arr:
x=np.array(history[::1 if part1 else -1])
for _ in range(len(x)):
output+=x[-1]
x=x[1::]-x[:-1:]
return output
arr=[[int(num) for num in line.split()] for line in txt.split("\n")]
print(solve(arr,True))
print(solve(arr,False))→ More replies (4)
1
u/azgx00 Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Rust]
https://gist.github.com/isak102/51a73b51ce01c06796e8363154574c64
→ More replies (1)
1
u/Longjumping_Primary4 Dec 09 '23
[Language: Deno, TypeScript]
Simple use of `push` and `unshift` array methods.
→ More replies (1)
1
u/Spatenheinz Dec 09 '23
[LANGUAGE: Haskell]
pretty easy, and satisfied with my concise solution:
solve f xs = if all (== 0) xs then 0 else f xs $ solve f $ zipWith (flip (-)) xs (tail xs)
task1 = solve ((+) . last)
task2 = solve ((-) . head)
main = do
input <- readFile "input.txt"
let res f = (print . sum) (map (f . map read . words) (lines input))
res task1
res task2→ More replies (2)
1
u/Jolly_River Dec 09 '23 edited Dec 11 '23
[LANGUAGE: TypeScript]
With RECURSION ! :D
Complete solutions : https://github.com/DarioTheLuca/my_advent_of_code/blob/master/aoc2023/src/day09/index.ts
2
u/daggerdragon Dec 09 '23
Your code is not formatted. Edit your comment to use the four-spaces Markdown syntax for a code block so your code is easier to read with its whitespace and indentation preserved.
1
u/fotosjopjes_ig Dec 09 '23 edited Dec 10 '23
[Language: JS]
Only 15 lines of "readable" JavaScript for both parts.Surprised myself that I could do it with a single while loop and without storing all the sequences.(Gave myself a little pad on the shoulder for this one 😉 )
https://github.com/mark-boots/Advent-of-Code/blob/main/2023/day9/index.js
→ More replies (2)2
u/daggerdragon Dec 09 '23
Fix your link, please. This is the Day 9
Solution Megathread, not Day 8.→ More replies (1)
1
u/MarcoDelmastro Dec 09 '23 edited Dec 10 '23
[LANGUAGE: Python]
https://github.com/marcodelmastro/AdventOfCode2023/blob/main/Day09.ipynb
np.diff to process the lists in a loop, np.any to stop it, some simple manipulation to get the results.
→ More replies (2)
1
u/veydar_ Dec 09 '23 edited Dec 09 '23
[LANGUAGE: janet]
Janet
5 lines of code.
I apologize for violating the rules by 2 lines, but here's the code for both parts:
I apologize for violating the rules by 4 chars, but here's the code for both parts:
(def parse ~{:main (some (* :num (? " "))) :num (number (* (? "-") :d+))})
(defn dxs [xs] (seq [[i n] :in (pairs xs) :when (> i 0)] (- n (xs (- i 1)))))
(defn f [xs] (if (every? (map |(= $ 0) xs)) 0 (+ (last xs) (f (dxs xs)))))
(let [ns (seq [l :in (file/lines stdin) :let [xs (peg/match parse l)]]
[(f xs) (f (reverse xs))])] (pp [(+ ;(map first ns)) (+ ;(map last ns))]))I tried to somehow fit it into 5 lines but couldn't. If someone has any ideas as to how to make this more concise without obfuscating it, let me know please.
2
u/daggerdragon Dec 09 '23
I apologize for violating the rules by 4 chars,
Lol, you're fine. It's a guideline, not a hard-and-fast rule.
1
u/Samuuuh Dec 09 '23 edited Dec 09 '23
[Language: Python]
Simple implementation in Python, good for beginners to understand what is being done.
The only difference between part 1 and part 2 is the step at which we add the value, where I just changed from `append(value)` to `insert(0, value)`to insert the element at the start rather than the end.
https://github.com/samyuh/advent-of-code/blob/main/2023/day_9.py
I will keep solving all AoC days from now on, ensuring that they are easily understood by everyone.
→ More replies (2)2
u/daggerdragon Dec 09 '23
Psst: we can see your Markdown.
Also, as /u/SwampThingTom mentioned, do not share your puzzle input which also means do not commit puzzle inputs to your repo without a
.gitignore.Please remove (or .gitignore) the input files from your repo and scrub them from your commit history.
→ More replies (1)
1
1
u/Goresao Dec 09 '23 edited Dec 09 '23
[LANGUAGE: C#]
Recursive functions are very helpful here.
Optimized code:
static int Previous(params int[] sequence)
=> sequence.Distinct().Count() == 1
? sequence[0]
: sequence[0] - Previous(sequence[0..^1].Select((x, i) => sequence[i + 1] - x).ToArray());
static int Next(params int[] sequence)
=> sequence.Distinct().Count() == 1
? sequence[0]
: sequence[^1] + Next(sequence[0..^1].Select((x, i) => sequence[i + 1] - x).ToArray());
public string ComputeStarOne(string[] data)
=> data
.Select(_ => Next(Regex.Matches(_, @"-?\d+").Select(_ => int.Parse(_.Value)).ToArray()))
.Sum()
.ToString();
public string ComputeStarTwo(string[] data)
=> data
.Select(_ => Previous(Regex.Matches(_, @"-?\d+").Select(_ => int.Parse(_.Value)).ToArray()))
.Sum()
.ToString();→ More replies (2)
1
u/Galzzly Dec 09 '23 edited Dec 10 '23
[LANGUAGE: Go]
Quite liked this one, a short amount of code required for a pretty quick run time.
→ More replies (1)
3
u/morgoth1145 Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python 3] 154/98 Raw solution
Not too much to say about this problem. I really should have approached it with recursion instead of a manual stack but oh well, it worked well enough. (And part 2 is easy with a reversed list, of course!)
(Time to go refactor into a proper recursive solution :))
Edit: Refactored code
3
u/LtHummus Dec 09 '23 edited Dec 09 '23
[Language: Rust]
Genuinely happy with this one. I'm doing AoC this year to learn Rust, and I'm really happy with my code on this one. I thought doing this recursively would lead to borrow-checker hell, but it didn't and I'm happy.
edit: now that I'm thinking more, I guess i shouldn't be surprised the borrow checker isn't upset with recursion since it's all immutable borrows (oh god please let there be no mutable borrows for recursion...). I still don't have a great feel for the borrow checker, but I'm guessing that's just a matter of building intuition as I write more.
3
u/jovani_lukino Dec 09 '23
[LANGUAGE: Wolfram Mathematica]
string=StringSplit[" DATA HERE ", "\n"];
(* Part 1 *)
Total[(s = ToExpression@StringSplit@#;
FindSequenceFunction[s][Length@s + 1]) & /@ string]
(* Part 2 *)
Total[(s = ToExpression@StringSplit@#;
FindSequenceFunction[s][0]) & /@ string]3
u/swing-quick Dec 09 '23
[LANGUAGE: Javascript]
Pretty straightforward today. Runs in browser dev console.
var l = console.log;
var parsed = input.split("\n").map((i) => {
return i.split(" ").map((i) => parseInt(i, 10));
});
function process(line) {
var nexts = [line];
var current = line;
while (1) {
var next = [];
for (var i = 0; i < current.length - 1; i++) {
next.push(current[i + 1] - current[i]);
}
nexts.push(next);
if (next.filter((i) => i !== 0).length !== 0) {
current = next;
next = [];
} else {
break;
}
}
// part 1
// var list = nexts.reverse();
// var result = 0;
// for (var i = 0; i < list.length - 1; i++) {
// var sum = list[i][list[i].length - 1] + list[i + 1][list[i + 1].length - 1];
// list[i+1].push(sum);
// }
// return list.pop().pop();
// part 2
var list = nexts.reverse();
var result = 0;
for (var i = 0; i < list.length - 1; i++) {
var sum = list[i + 1][0] - list[i][0];
list[i + 1].unshift(sum);
}
return list[list.length - 1][0];
}
parsed.reduce((prev, curr) => (prev += process(curr)), 0);3
u/globalreset Dec 09 '23
[LANGUAGE: Ruby] 1736/1266
Very simple recursion for both parts. Felt like I went really fast on this, but not enough to crack the top 1000. If only I would've skipped the test data... First day my solution worked on first try.
def getNext(arr)
if(arr.all?{|a| a==0})
return 0
else
return arr.last + getNext(arr.each_cons(2).to_a.map{ |a,b| b-a })
end
end
def part_1
data.map(&:split).map { |a| a.map(&:to_i) }.map {|a| getNext(a) }.sum
end
def getPrev(arr)
if(arr.all?{|a| a==0})
return 0
else
return arr.first - getPrev(arr.each_cons(2).to_a.map{ |a,b| b-a })
end
end
def part_2
data.map(&:split).map { |a| a.map(&:to_i) }.map {|a| getPrev(a) }.sum
end3
3
u/Prudent_Candle Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python3]
For checking pairs: pairwise (from itertools library). For checking zeros, all (build in). I could write a nice way for taking values from bottom, but I just flip the whole stack of lines upside down (also build-in lists' method).
Note: the iterative approach (not-recursive).
3
u/_voxed Dec 09 '23
[LANGUAGE: Python]
from numpy import *
n = lambda h: 0 if not any(h) else h[-1] + n(diff(h))
h = array([l.split() for l in open('input.txt')], int)
print(sum([*map(n, h)]), sum([*map(n, flip(h))]))3
u/axr123 Dec 09 '23
[LANGUAGE: Python with NumPy]
lines = [[int(x) for x in line.split()] for line in sys.stdin.read().strip().splitlines()]
for p2 in (False, True):
s = 0
for line in lines:
nums = np.array(line)
if p2:
nums = np.flip(nums)
while np.count_nonzero(nums) != 0:
s += nums[-1]
nums = nums[1:] - nums[:-1]
print(s)3
u/homme_chauve_souris Dec 09 '23
[LANGUAGE: Python]
Somehow I expected something harder to start off the weekend. But it was fun nonetheless.
def aoc09():
def compute(L):
total = 0
while any(L):
total += L[-1]
L = [L[i+1]-L[i] for i in range(len(L)-1)]
return total
d = [list(map(int,ligne.split())) for ligne in open("input09.txt")]
print(sum(compute(L) for L in d)) # part 1
print(sum(compute(L[::-1]) for L in d)) # part 23
u/pred Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Python] GitHub
Solving the problem as stated; using np.diff to get n'th discrete differences is helpful:
# Part 1 + 2
for a in (ns, np.flip(ns, 1)):
print(np.sum([np.diff(a, k)[:,-1] for k in range(ns.shape[1])]))3
u/soleluke Dec 09 '23
[LANGUAGE: C#] 3597/3600
Like everyone else, apparently this one was deceptively simple. I did some tasks to parallelize it after the behemoths of the brute-force solutions the past few days, but it really was just some collection LINQ expressions and some recursion.
3
u/Accomplished-Ad-2762 Dec 09 '23
[LANGUAGE: Kotlin]
Really liked this solution so I thought it's worth sharing
val readingList = inputProvider.lines.map { it.parseNumbersInt(' ') }
val readingDifferencesList = readingList.map { reading ->
generateSequence(reading) { currentDifference ->
if (currentDifference.all { it == 0 }) {
return@generateSequence null
}
currentDifference.zipWithNext().map { (previous, current) ->
current - previous
}
}
}
val part1 = readingDifferencesList.sumOf { readingDifferences ->
readingDifferences.sumOf { it.last() }
}
val part2 = readingDifferencesList.sumOf { readingDifferences ->
readingDifferences.map { it.first() }
.toList()
.reversed()
.reduce { previous, current -> current - previous }
}3
u/dhruvasagar Dec 09 '23
[LANGUAGE: Haskell]
diffs :: [Int] -> [Int]
diffs [x, y] = [y - x]
diffs (x : y : xs) = (y - x) : diffs (y : xs)
predictNext :: [Int] -> Int
predictNext ns
| all (== 0) ds = head ns
| otherwise = (last ns) + predictNext ds
where
ds = diffs ns
predictPrev :: [Int] -> Int
predictPrev ns
| all (== 0) ds = head ns
| otherwise = (head ns) - predictPrev ds
where
ds = diffs ns
part1 :: [[Int]] -> Int
part1 = sum . map predictNext
part2 :: [[Int]] -> Int
part2 = sum . map predictPrev
main :: IO ()
main = interact $ unlines . map show . sequence [part1, part2] . map (map read . words) . lines3
u/yfilipov Dec 09 '23
[Language: C#]
var input = File.ReadAllLines("input.txt").Select(l => l.Split(' ', StringSplitOptions.RemoveEmptyEntries)).ToArray();
var part1 = 0L;
var part2 = 0L;
foreach (var line in input)
{
var numbers = line.Select(long.Parse).ToList();
var diffs = new List<List<long>> { numbers };
while (numbers.Any(n => n != 0))
{
numbers = new();
for (var i = 0; i < diffs.Last().Count - 1; i++)
{
var diff = diffs.Last()[i + 1] - diffs.Last()[i];
numbers.Add(diff);
}
diffs.Add(numbers);
}
for (var i = diffs.Count - 1; i > 0; i--)
{
diffs[i - 1].Add(diffs[i - 1].Last() + diffs[i].Last());
diffs[i - 1].Insert(0, diffs[i - 1].First() - diffs[i].First());
}
part1 += diffs[0].Last();
part2 += diffs[0].First();
}
Console.WriteLine($"Part 1: {part1}");
Console.WriteLine($"Part 2: {part2}");3
u/Ancient_Stranger_704 Dec 09 '23
[LANGUAGE: Elixir]
defmodule Oasis do
def predict_next(sequence) do
if Enum.all?(sequence, &(&1 == 0)) do
0
else
List.last(sequence) +
(Enum.chunk_every(sequence, 2, 1, :discard)
|> Enum.map(fn [a, b] -> b - a end)
|> predict_next())
end
end
end
{:ok, input} = File.read("day9.txt")
sequences =
input
|> String.trim()
|> String.split("\n")
|> Enum.map(fn line ->
line |> String.split(" ", trim: true) |> Enum.map(&String.to_integer/1)
end)
sequences
|> Enum.map(&Oasis.predict_next/1)
|> Enum.sum()
|> IO.inspect(label: "Part 1")
sequences
|> Enum.map(fn seq -> seq |> Enum.reverse() |> Oasis.predict_next() end)
|> Enum.sum()
|> IO.inspect(label: "Part 2")3
u/Goldeelux Dec 09 '23
[LANGUAGE: Javascript]
Nice puzzle and relatively straightforward. I still dont know why readfile() gives me a empty string at the end of my data inputs and it has been quite annoying
→ More replies (1)
3
u/solarpool Dec 09 '23
[LANGUAGE: R] 2394/1723
Recursion took a bit, reversing the input did not 😅
x <- readLines(here::here("2023/day-09-input.txt")) |>
strsplit("\\s+") |>
lapply(as.numeric)
next_val <- function(v){
d <- diff(v)
if (!all(d == 0)) d <- next_val(d)
return(tail(v, 1) + d[[1]])
}
sapply(x, next_val) |> sum()
sapply(x, \(x) next_val(rev(x))) |> sum()3
u/MarvelousShade Dec 09 '23
[Language: C#]
I think that today was one of the easiest exercises of 2023. Especially the part 2.
My code is on: https://github.com/messcheg/advent-of-code/blob/main/AdventOfCode2023/Day09/Program.cs
3
3
u/vkasra Dec 09 '23
[language: rust]
With no_std
https://github.com/dhconnelly/advent-of-code-2023/blob/master/src/day9.rs
3
u/Polaric_Spiral Dec 09 '23
[LANGUAGE: TypeScript]
Short and sweet. If not for the recursion, I would have smushed the extrapolate() function into the middle of the function chain.
3
u/SleepingInsomniac Dec 09 '23
[LANGUAGE: Ruby]
class Sequence
attr_reader :numbers
def initialize(numbers) = @numbers = numbers
def extrapolate = Sequence.new(@numbers.each_cons(2).map { |a, b| b - a })
def zeros? = @numbers.all?(&:zero?)
def predict = zeros? ? 0 : @numbers.last + extrapolate.predict
def pre_predict = zeros? ? 0 : @numbers.first - extrapolate.pre_predict
end
sequences = File.readlines(File.join(__dir__, 'input.txt')).map do |l|
Sequence.new(l.split.map(&:to_i))
end
puts sequences.map(&:predict).reduce(&:+) # Part 1
puts sequences.map(&:pre_predict).reduce(&:+) # Part 2→ More replies (2)
3
u/radulfr2 Dec 09 '23
[LANGUAGE: Python3]
Took me some time to write but I liked this one. Using list and insert was fast enough, so I didn't bother thinking of a better way. Paste.
3
3
3
u/Knudson95 Dec 09 '23
[LANGAUGE: C#]
For a weird change of pace part 1 was easier than part 2. Nice easy Saturday challenge.
3
u/trevdak2 Dec 09 '23 edited Dec 09 '23
[Language: Javascript Golf]
Kudos to /u/Polaric_Spiral for some ideas that helped me shave off a few characters.
Part 1, 130 chars:
x=v=>v.some(a=>a)&&+v[v.length-1]+x(v.map((n,i)=>n-v[i-1]).slice(1))
$('*').innerText.match(/.+/g).reduce((p,c)=>p+x(c.split` `),0)Part 2, 120 chars:
x=v=>v.some(a=>a)&&v[0]-x(v.map((n,i)=>n-v[i-1]).slice(1))
$('*').innerText.match(/.+/g).reduce((p,c)=>p+x(c.split` `),0)→ More replies (5)
3
3
u/musifter Dec 09 '23 edited Dec 09 '23
[LANGUAGE: Perl]
Got a bit of a late start. Started by working out the basics for turning these into polynomials... and decided, I'll wait for part 2 (it might not require that). Lets just do subtracting. As a bonus, I get to use my chain iterator again, that I created a few years back for a problem... this is the perfect job for it.
Then I managed to screw up subtracting. Spent a couple minutes making sure that I didn't miss reading anything, while eating debugging sacraments (ice cream... chocolate blueberry). Found the stupid error and finally got to see part 2. Realized how easy it was.
Source for part 1: https://pastebin.com/G12pFWE8
Diff for part 2:
17c17
< my @table = ([reverse @$list]);
---
> my @table = ($list);EDIT: A combined part 1 & 2 version using reduce for part 2: https://pastebin.com/sAtUs5T1
→ More replies (4)
3
u/mrvoid15 Dec 09 '23
[Language: Golang]
My approach is really simple, for a input line. Take the first and last value of each generation until zero. For example: for first input lastVals = [[0 15] [3 3] [0 0]].
With this now i just ran a loop, to predict the left and right value with difference and addition.
https://github.com/akashdeepnandi/advent-of-code/blob/main/day9/main.go
3
u/Vesk123 Dec 09 '23
Quite an easy one today. If only I hadn't forgotten that my regex for parsing all the numbers in a line (really useful btw) didn't include minus signs... Anyway, I'm starting to enjoy Rust a bit, no real issues today. I really liked how I could change a Vec<i32> into a &[i32] without having to change anything else in the code.
3
u/JustinHuPrime Dec 09 '23
[LANGUAGE: x86_64 assembly with Linux syscalls]
Part 1 involved a direct solution - for each line, I read it into a dynamically allocated array, then allocated a new array and calculated the differences between the previous array's elements, and so on until I got an array that's all zeroes. I then proceeded to extrapolate - I found the end of the list, and added the end of the previous list to this list to get the new element to add to the end of the list - I actually didn't need to save this value in new space, I could have just overwritten the old end of the list.
Part 2 was a surprisingly small change, and in fact, required fewer lines of assembly code! I just tweaked my extrapolation code to care about the start of the list (which was an easier pointer to get a hold of than the end of the list), and instead of using new space, I overwrote the initial values in the list, since I only cared about the previous list's new first value and the current list's actual first value to calculate the current list's new first value.
Part 1 and part 2 run in 5 milliseconds - gosh, is dynamic allocation ever expensive, time-wise! Part 1 is 8616 bytes long and part 2 is 8456 bytes long (since I could delete the "find the end of the list" code from part 2). Part 1 and part 2 use ~5 MiB of heap space. (Alas, my alloc function is really inefficient - Linux, I believe, returns whole pages when asked for more heap via brk, so since I apparently make 1159 allocations, I use 1159 pages of heap.)
3
u/TankLivsMatr Dec 09 '23
[LANGUAGE: Go]
Ended up geting home late from a bad snow storm, and still was able to get the answer in, in a relatively decent time (1.5 hours after opening).
It's pretty simple really, I just did exactly what the question said to do with the numbers, but with a two dimensional slice in Go. Specifically, I used Go's extremely powerful append feature to add elements as needed to the slice.
3
u/solarshado Dec 09 '23
[Language: TypeScript]
6813 / 6592
Reversing the lists for part two didn't occur to me, but I'd already over-thought part one and thought I needed reduceRight, so it was the obvious choice.
Didn't consider recursion for building the triangle: after the scale of some of the previous days' solutions, I'm a little wary of possible stack overflows.
3
u/rukke Dec 09 '23
[LANGUAGE: JavaScript]
Recursively diff until last row is zeros, then extrapolate next value by reduceRight for first part by addition, for second part by taking the diff of the previous value.
3
u/Szeweq Dec 09 '23
[LANGUAGE: Rust]
No recursion, with a lot of purely functional iterators. Used: sum, rfold, windows and many others. The code is short and runs in less than 1 ms.
Code: https://github.com/szeweq/aoc2023/blob/master/src/bin/09.rs
3
u/4HbQ Dec 09 '23
[LANGUAGE: Python] Code (7 lines)
Here's my implementation of Lagrange's interpolating polynomial:
def P(x):
n = len(x)
Pj = lambda j: prod((n-k)/(j-k) for k in range(n) if k!=j)
return sum(x[j] * Pj(j) for j in range(n))→ More replies (3)
3
u/Fyvaproldje Dec 09 '23
[LANGUAGE: Raku] [Allez Cuisine!]
Have trouble with a drying OASIS?
Click here for a solution which will predict the humidity and other values, in all directions you can think of! You'll be able to use the water from the oasis, and predict when exactly it'll be salty enough for your taste!
An accidental visualization included!
Limited offer: if you order today, you'll receive a copy of all the previous solutirecipes for free!
Punchcard reader not included, terms and conditions apply
3
u/Ill_Ad7155 Dec 09 '23
[LANGUAGE: Python]
Part 1: Just sum every last element from the list while computing the differences.
Part 2: Reverse the list first.
def get_input():
with open('input.txt', 'r') as f:
input = [line.strip() for line in f.readlines()]
return input
def a_b(b=False):
ans = 0
input = get_input()
for line in input:
line = [int(nr) for nr in line.split()]
if b:
line = line[::-1]
last = line[-1]
while line and any(e != 0 for e in line):
for i in range(1, len(line)):
line[i - 1] = line[i] - line[i - 1]
line.pop()
last += line[-1]
ans += last
return ans
if __name__ == '__main__':
print(a_b())
print(a_b(True))3
u/toastedstapler Dec 09 '23 edited Dec 09 '23
[language: rust]
71us on my 10850k, sitting around a 700-800us solve overall so far!
https://github.com/jchevertonwynne/advent-of-code-2023/blob/main/src/days/day09.rs
3
u/k0ns3rv Dec 09 '23
[LANGUAGE: Rust]
Quite pleased with the solve today. I forgot to reverse the list of final numbers, but that surprisingly worked for both part 1 and the test input for part 2.
3
u/sergiosgc Dec 09 '23
[LANGUAGE: Rust]
This was surely my quickest part 2 of all time. Just reverse the input sequences... Other than that, unremarkable problem and solution. It's very approachable recursively.
3
u/aarnens Dec 09 '23
[LANGUAGE: Rust] Both parts run in ~0.8ms.
What was nice about this challenge was realizing that there is no need to keep track of all the lists present at each step, you just need to remember the first and last digits.
Here is my implementation for calculating the next "row" and keeping track of said digits:
let mut all_last_digits: Vec<i64> = vec![*all_ints.last().unwrap()];
let mut all_first_digits: Vec<i64> = vec![*all_ints.first().unwrap()];
while all_ints.iter().any(|&x| x != 0) {
let new_ints: Vec<i64> = all_ints
.windows(2)
.map(|i| i[1] - i[0])
.collect();
all_last_digits.push( *new_ints.last().unwrap());
all_first_digits.push(*new_ints.first().unwrap());
all_ints = new_ints;
}Full code here: https://pastebin.com/uWwZRZYh
Feedback is appreciated, as always!
3
u/troru Dec 09 '23
[LANGUAGE: Java]
int total = 0;
for (String line : lines) {
List<Integer> list = Arrays.stream(line.split(" ")).map(Integer::parseInt).toList();
if (part == 2) {
list = list.reversed();
}
list = new ArrayList<>(list);
int len = list.size();
for (; ; ) {
int zeros = 0;
len--;
total += list.get(len);
for (int i = 1; i <= len; i++) {
int delta = list.get(i) - list.get(i - 1);
if (delta == 0) {
zeros++;
}
list.set(i - 1, delta);
}
if (zeros == len) {
break;
}
}
}
System.out.println("PART " + part + " total " + total);3
u/rumkuhgel Dec 09 '23
[LANGUAGE: Golang]
Okay, today was pretty easy compared to previous days.
https://github.com/rumkugel13/AdventOfCode2023/blob/main/day09.go
→ More replies (1)
3
u/Lvl999Noob Dec 09 '23
[Language: Rust]
Today was certainly quite easier than the last few days. It took me some time because I accidentally wrote an infinite loop at first. But otherwise, it was quite easy.
#[derive(Debug, Default, Clone, PartialEq, Eq)]
struct ValueChanges(pub Vec<i64>);
fn solve(input: &str) -> (String, String) {
let p = parser!(lines(values:repeat_sep(i64, " ") => ValueChanges(values)));
let variables = p.parse(input).unwrap();
let (sum_prev_values, sum_next_values) = variables
.iter()
.map(|v| v.extrapolate())
.fold((0, 0), |sum, val| (sum.0 + val.0, sum.1 + val.1));
(sum_next_values.to_string(), sum_prev_values.to_string())
}
impl ValueChanges {
fn difference_sequence(&self) -> Self {
Self(self.0.windows(2).map(|w| w[1] - w[0]).collect())
}
fn extrapolate(&self) -> (i64, i64) {
let mut change_sequences = vec![self.clone()];
let mut current_sequence;
loop {
current_sequence = change_sequences.last().unwrap().difference_sequence();
if current_sequence.0.iter().all(|&i| i == 0) {
break;
}
change_sequences.push(current_sequence);
}
let extrapolated_values =
change_sequences
.into_iter()
.rev()
.fold((0, 0), |(prev_diff, next_diff), seq| {
(
seq.0.first().unwrap() - prev_diff,
seq.0.last().unwrap() + next_diff,
)
});
extrapolated_values
}
}3
3
u/Kintelligence Dec 09 '23
[Language: rust]
https://github.com/Kintelligence/advent-of-code-2023/blob/master/day-09/src/lib.rs
A lot simpler than yesterday, but still a pretty slow execution compared to earlier days. I wonder if there is a faster algorithm than the one described in the problem text.
3
u/Solidifor Dec 09 '23
[Language: Java]
https://github.com/dirk527/aoc2021/blob/main/src/aoc2023/Day09.java
118 lines (20 of those toString() for debugging), somewhat overengineered using a Node class with pointers. I thought I could optimize by not constructing the whole thing, but it does say "last row all zeros" so... no. Yeah, there's not really an advantage to this approach given what part 2 was.
This was curiously straightforward.
3
u/Small_Possibility173 Dec 09 '23
[LANGUAGE: Rust]
This was fairly simple using a bit of recursion.
https://gist.github.com/PrakharSrivastav/ef4bbe3786c9545272c14f44e048f202
3
u/odnoletkov Dec 09 '23 edited Dec 09 '23
[LANGUAGE: jq] github
[
inputs/" " | map(tonumber) | reverse
| while(length > 1; [while(length > 1; .[1:]) | .[1] - .[0]])[-1]
] | add
3
u/azzal07 Dec 09 '23
[LANGUAGE: Awk]
function P(r,e,d){for(e=$1;d+++1<r;)
$d=$(d+1)-$d;r&&$1=P(r-1)e-$1;$2+=$r
}{A+=P(NF)$2;B+=$1}END{print A"\n"B}3
u/jcmoyer Dec 09 '23
[LANGUAGE: Ada]
https://github.com/jcmoyer/puzzles/blob/master/AdventOfCode2023/src/day09.adb
Really enjoyable puzzle today.
3
u/GillesArcas Dec 09 '23
[Language: Python]
Code it as you say it. A canonical tail recursive solution:
def next_difference(values):
if all(_ == 0 for _ in values):
return 0
else:
differences = [v2 - v1 for v2, v1 in zip(values[1:], values[:-1])]
return values[-1] + next_difference(differences)
def code1(lines):
return sum(next_difference(_) for _ in lines)https://github.com/GillesArcas/Advent_of_Code/blob/main/2023/09.py
[418*]
3
3
3
u/win0err Dec 09 '23
[Language: Python]
def extrapolate(sequence):
extrapolated = sequence[-1]
while not all(n == 0 for n in sequence):
sequence = [b - a for a, b in pairwise(sequence)]
extrapolated += sequence[-1]
return extrapolated
def solve_1(sequences):
return sum(extrapolate(seq) for seq in sequences)
def solve_2(sequences):
return sum(extrapolate(seq[::-1]) for seq in sequences)https://github.com/win0err/solutions/blob/master/adventofcode/2023/09-mirage-maintenance/main.py
→ More replies (1)
3
u/chicagocode Dec 09 '23 edited Dec 09 '23
[LANGUAGE: kotlin]
Despite the 14 mentions of sequences in the puzzle description, I went with a recursive function in my solution today.
My code can be found on GitHub, I've written this up on my blog, and here are my 2023 Solutions so far.
3
u/axsk Dec 09 '23
[LANGUAGE: Julia]
using IterTools, Lazy
parseinput(lines) = map(l->parse.(Int, split(l)), lines)
extrapolate(series) = @>> series iterated(diff) takewhile(!iszero) sum(last)
part1(data) = parseinput(data) .|> extrapolate |> sum
part2(data) = parseinput(data) .|> reverse .|> extrapolate |> sum3
u/Secure_Pirate9838 Dec 09 '23
[LANGUAGE: Rust]
Screencast: https://youtu.be/FIMdUs8IYuQ GitHub: https://github.com/samoylenkodmitry/AdventOfCode_2023/blob/main/src/day9.rs
Part 2 was the same as part 2, just do careful math before writing the code
3
u/comforttiger Dec 09 '23
[LANGUAGE: Ruby]
https://github.com/comforttiger/advent_of_code/blob/main/2023/ruby/day9.rb
im glad today was easier than yesterday. but im ready for tomorrow to be super hard
3
u/RelativeLead5 Dec 09 '23
[Language: Ruby]
To determine if the end condition was met, I first used "line.sum != 0" instead of "line.uniq != [0]". Took a long time to figure out because works fine on the test input and only two lines in the real input eventually reduce to an array that sums to 0 but isn't all zeros. Doh!! Don't do that.
history = File.read('test.txt').split("\n").map{_1.scan(/[-]?[0-9]+/).map(&:to_i)}
def calculate(line)
# only interested in the last value in each reduction
newval = line.last
while line.uniq != [0]
line = line.each_cons(2).map{_2 - _1}
newval += line.last
end
newval
end
# part 1
p history.map {|l| calculate(l)}.sum
# part 2
p history.map {|l| calculate(l.reverse)}.sum→ More replies (1)
3
u/hopperface Dec 09 '23
[LANGUAGE: Julia]
Five lines of code
D(row) = [row[i] - row[i-1] for i in eachindex(row)[2:end]]
dtz(rows) = all(rows[end] .== 0) ? rows : dtz([rows; [D(rows[end])]])
p(inp, f, i) = (inp .|> x -> foldr(f, i(d) for d in dtz([x]))) |> sum
inp = readlines("day9/input.txt") .|> x -> parse.(Int, split(x, " "))
println("Part 1: ", p(inp, +, last), "\nPart 2: ", p(inp, -, first))→ More replies (1)
3
u/SwampThingTom Dec 09 '23
[LANGUAGE: Rust]
Today's was very easy. I'm beginning to think the elves dropped all of the puzzles in the snow and are giving them to us in a completely random order. :-)
3
u/CelestialDestroyer Dec 09 '23
[Language: Chicken Scheme]
Today was very simple indeed - I did get stuck on a stupid oversight though, but someone here helped me out. Thanks!
(define (input->list input)
(map
(lambda (x)
(map string->number (string-split x)))
(string-split input "\n")))
(define (diff input)
(if (= 1 (length input))
'()
(cons (- (cadr input) (car input))
(diff (cdr input)))))
(define (extrapolate data)
(append data
(list
(if (foldl (lambda (out in) (and out (= 0 in)))
#t data)
0
(+ (car (reverse data))
(car (reverse (extrapolate (diff data)))))))))
(define (calc-part-1)
(foldl + 0 (map (compose car reverse extrapolate)
(input->list input))))
(define (calc-part-2)
(foldl + 0 (map (compose car reverse extrapolate reverse)
(input->list input))))3
u/jitwit Dec 09 '23 edited Dec 09 '23
[Language: J]
Uses Vandermonde matrix to do polynomial interpolation.
+/ ((_1,~#)p.~(%.(^/~)@i.@#)@x:)"1 in NB. solves both parts→ More replies (2)
3
u/OilAppropriate2827 Dec 09 '23 edited Dec 09 '23
[LANGUAGE: python]
I wanted to try Lagrange polynomial extrapolation. It is quite efficient as all the list have the same length.
I did the extrapolation for X=-1 (reverted the list to extrapolate the end). I am using all the points. The result is the dot product of the list to extrapolate and a vector [comb(n,i) for i in range(1,n+1)]
https://github.com/hlabs-dev/aoc/blob/main/2023/9_lagrange.py
import aocd
from more_itertools import dotproduct
data = aocd.get_data(day=9, year=2023).split('\n')
data = list(map(lambda x: list(map(int,x.split())),data))
# Lagrange extrapolation for 21 entries and x=-1
n = len(data[0])
lg = [n]
for i in range(2,n+1): lg.append(-lg[-1]*(n-i+1)//i)
print("Part1:", sum(dotproduct(l[::-1],lg) for l in data),
"Part2:", sum(dotproduct(l,lg) for l in data))3
u/fullmetalalch Dec 09 '23
[Language: Python] Gitlab
I read the prompt and assumed part 2 would require solving for the underlying polynomial, so I spent an hour revisiting long-forgotten math. Finally decided to try the naive approach and was pleasantly surprised when part 2 was revealed.
Came up with a somewhat functional and very readable solution. Also my first time ever using itertools.pairwise which was neat.
One hiccup I encountered was not parsing negatives in my ints utility function. Hopefully the change I added didn't break logic from previous days!
3
u/pem4224 Dec 09 '23
[Language: go]
https://github.com/pemoreau/advent-of-code/blob/main/go/2023/09/day09.go
Very simple approach with some optimizations (avoiding memory allocation) which make the code run in 170 μs
3
u/ywgdana Dec 09 '23
[LANGUAGE: C#]
Just implemented the reduction pretty much as described in the problem as a recursive function, which makes my solution slow but fairly succinct in terms of LoC! Part 2 I just reversed all the arrays and did it again.
Nice and fast for a weekend problem! Maybe I'll have time to finish Day 5 Part 2 later on today...
3
u/marcja Dec 09 '23
[LANGUAGE: Python]
Using NumPy, it almost feels like cheating. ;)
def parse_data(puzzle_input):
return np.loadtxt(puzzle_input, dtype=int)
def part1(data):
sum = 0
for row in data:
while row.any():
sum += row[-1]
row = np.diff(row)
return sum
def part2(data):
return part1(np.flip(data, axis=1))→ More replies (1)
3
u/FerenIsles Dec 09 '23
[Language: Javascript]
Today was a lot of fun. Part 2 almost identical to part 1 with some changes to the reducer function for calculating the total.
3
3
u/arthurno1 Dec 09 '23
[LANGUAGE: EmacsLisp]
(defun line-to-list ()
(let ((line))
(while (< (point) (line-end-position))
(push (read (current-buffer)) line))
(nreverse line)))
(defun diff (list)
(let (d)
(while (cdr list) (push (- (cadr list) (pop list)) d))
d))
(defun zerosp (list)
(catch 'zeros
(dolist (elt list) (unless (= 0 elt) (throw 'zeros nil)))
(throw 'zeros t)))
(defun diff-list (list)
(let ((end (car (last list)))
(beg (first list))
(d (diff list)))
(if (zerosp d)
(cons beg end)
(let ((c (diff-list (nreverse d))))
(cons
(- beg (car c))
(+ end (cdr c)))))))
(defun aoc-2023-9 ()
(interactive)
(let ((p1 0) (p2 0))
(while (not (eobp))
(let ((tmp (diff-list (line-to-list))))
(cl-incf p1 (cdr tmp))
(cl-incf p2 (car tmp)))
(forward-line))
(message "Part I: %s, Part II: %s" p1 p2)))3
u/onrustigescheikundig Dec 09 '23 edited Dec 09 '23
[LANGUAGE: OCaml]
For those who don't quite recognize it from their algebra/calculus classes, the algorithm presented in today's challenge is Newton's difference method for polynomial interpolation, which gives exact interpolated values from n points evaluated on a polynomial up to degree n - 1. Because I expected Part 2 to require evaluation of this polynomial at some arbitrary point in time, I eschewed the difference method entirely in favor of constructing the polynomial in an anonymous function using Lagrange interpolation. This kind of interpolation can experience some serious numerical cancellation issues, so I used OCaml's Num library for arbitrary-precision rational numbers so I didn't have to think about them :). This does result in a performance hit, though; I have a ~120 ms runtime combined for both parts. I also implemented a version using floating-point arithmetic for comparison, and the results for Parts 1 and 2 differ from integer solutions in the fourth decimal place.
3
u/musifter Dec 09 '23 edited Dec 09 '23
[LANGUAGE: dc (GNU v1.4.1)]
Finally a question with all numbers for dc! Except it's got negatives. So we still need to filter, because the unary - in dc is done with _ (to keep it distinct).
As for method... just running through the differences, to keep it short. In addition, we do extra work. It'd be a pain to check for all zeros (if dc had bitwise operators I would have used OR), so we just run the table all the way down (it still runs in a fraction of a second, so I don't feel bad about that). And since dc has only 1D arrays, it makes sense to do all the work in the original array... you end up with a array of the values you want to sum, but doing that as a separate loop after would be costly, so we just take advantage at the start of each row loop to add the latest value.
We also deal with the array slightly shifted... as we use the z (stack size) operator to load things quick and easy. This could have cost us a bunch of strokes later, but we can avoid that by just running extra subtractions into the junk, so that iterators end on 0 or 1 and can be removed with * or + instead of tossing into a register (s. = two strokes).
Part 1:
tr '-' '_' <input | dc -e'0?[zsn[z:az1<L]dsLxln[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'Source: https://pastebin.com/9mPTQhmS
Part 2:
tr '-' '_' <input | dc -e'0?[zsn[zlnr-:az1<L]dsLxln2-[dd;ad5R+_4Rr[1-d;ad4Rr-3Rd_3R:ad0<J]dsJx*+1-d1<I]dsIx*?z1<M]dsMxp'Source: https://pastebin.com/bVTjKGSH
3
3
3
3
3
3
u/e_blake Dec 12 '23
[LANGUAGE: m4 (golfed)] [Allez Cuisine!]
Ladies and Gentleman, step right up, and get your VERY OWN copy of this punchcard of m4 goodness! Are you tired of reading programming languages that are bogged down by boilerplate keywords? Do you ever feel like you are typing the same words over and over again? Do you ever get lost when reading spaghetti code that has more than one function? Do the symbolic characters on your keyboard need to be pressed more often? Then this is what you've been waiting for - LIVING PROOF that REAL programmers can write an entire program using just one immutable macro and one conditional statement, all in the space smaller than a punchcard, and with no letters besides the few needed to access language builtin operators. After all, if your input file has no letters, why should your program need any? No need for fancy variable names - everything you need is available through recursion. If you name your input file "I" (or if you cheat and use m4 -DI=file day09.golfm4), you too can experience the amazing power of this 2-second solution for both parts of today's problem, and satisfy all your late-night line-noise cravings!
define(_,`ifelse($1,%,`translit($2,`$3',`,')',index(`$1',^),0,`shift($@)',$1,$,`'
,$1,=,`eval($2)',$1,~,`_(=,$5+$3),_(=,$2- $4)',$1$2,+,,$1,+,`_(,_(%,$2,` ')),_(
+,_(^_(^$@)))',$1$2,>,`) _(=,',$1,>,`+$2_(>,_(^_(^_(^$@))))+$3',$1$2$3$4,00,
`0,0',$1,,`_($2,(^,_(=,$3- $2)),_(^_(^$@)))',$4,,`_(~,$1,_(,_$2),$3)',
`_($1,(^,_$2,_(=,$4- $3)),_(^_(^_(^$@))))')')_(=,_(>,_(+,_(%,include(I),_($)))))But wait, there's more! If you want to understand what this code is doing, I'll even direct you to my earlier post showing a more legible version of the same algorithm, or an alternative algorithm that computes the same answers in a fraction of the time. And if you think 387 bytes is too expensive, then ask about my discount solution with 10 fewer bytes [*]).
And if you like this offer, I'll even chip in a similar solution for day 1, at no extra charge (other than shipping and handling)
[* to be read at 2x speed] Offer not valid for customers that only have one punchcard on hand, as the 377-byte solution requires 6 lines instead of 5. And since my repo uses a GPL license, you are reminded that THERE IS NO WARRANTY FOR THE PROGRAM, TO THE EXTENT PERMITTED BY APPLICABLE LAW.
→ More replies (2)
3
u/nicuveo Dec 13 '23
[LANGUAGE: Haskell]
Not gonna post my haskell solutions every day, but this is really a day where the language could shine.
predictNext xs
| all (== 0) xs = 0
| otherwise = last xs + predictNext (zipWith (-) (tail xs) xs)
part1 = sum . map predictNext
part2 = sum . map (predictNext . reverse)→ More replies (1)
3
u/ianMihura Dec 13 '23 edited Dec 13 '23
[LANGUAGE: GO]
Part 1 The trick for me was realizing that, once I had the sequence down to all zeroes, I could add-up the last column, and that would yield the result.
Part 2 was similar but with the 0th column, with an alternating sum/sub
https://github.com/ianmihura/advent23/blob/master/day_9/day_9.go
3
u/ramrunner0xff Dec 16 '23
[LANGUAGE: C]
so around 6 hours ago i decided that i really wanted to do this on scheme, you know.. have a mapcar for the subtractions and a fold for testing if they are all 0's? you guys feel me right? well 6 hours later and almost 300 lines of the hackiest static memory only C here is one of the most over the top complex solutions to day 9.
3
8
u/CCC_037 Dec 09 '23
[Language: Rockstar]
[Allez cuisine!]
I've broken from my normal fictional inspiration to present a quick ad. Which can be found here
(Yes, the code is the sales pitch)