Day 9: Mirage Maintenance
Megathread guidelines
- Keep top level comments as only solutions, if you want to say something other than a solution put it in a new post. (replies to comments can be whatever)
- Code block support is not fully rolled out yet but likely will be in the middle of the event. Try to share solutions as both code blocks and using something such as https://topaz.github.io/paste/ , pastebin, or github (code blocks to future proof it for when 0.19 comes out and since code blocks currently function in some apps and some instances as well if they are running a 0.19 beta)
FAQ
- What is this?: Here is a post with a large amount of details: https://programming.dev/post/6637268
- Where do I participate?: https://adventofcode.com/
- Is there a leaderboard for the community?: We have a programming.dev leaderboard with the info on how to join in this post: https://programming.dev/post/6631465
🔒 Thread is locked until there’s at least 100 2 star entries on the global leaderboard
🔓 Unlocked after 5 mins
(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}")
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)
Rust
Discrete derivatives!
Nim
Pretty easy one today. Made a
Pyramid
type to hold the values and their layers of diffs, and anextend
function to predict the next value. For part 2 I just had to make anextendLeft
version of it that inserts and subtracts instead of appending and adding.Hi there! Looks like you linked to a Lemmy community using a URL instead of its name, which doesn’t work well for people on different instances. Try fixing it like this: !nim@programming.dev
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 ⇌))
Scala3
def diffs(a: Seq[Long]): List[Long] = a.drop(1).zip(a).map(_ - _).toList def predictNext(a: Seq[Long], combine: (Seq[Long], Long) => Long): Long = if a.forall(_ == 0) then 0 else combine(a, predictNext(diffs(a), combine)) def predictAllNexts(a: List[String], combine: (Seq[Long], Long) => Long): Long = a.map(l => predictNext(l.split(raw"\s+").map(_.toLong), combine)).sum def task1(a: List[String]): Long = predictAllNexts(a, _.last + _) def task2(a: List[String]): Long = predictAllNexts(a, _.head - _)
Dart
I was getting a bad feeling when it explained in such detail how to solve part 1 that part 2 was going to be some sort of nightmare of traversing all those generated numbers in some complex fashion, but this has got to be one of the shortest solutions I’ve ever written for an AoC challenge.
int nextTerm(Iterable ns) { var diffs = ns.window(2).map((e) => e.last - e.first); return ns.last + ((diffs.toSet().length == 1) ? diffs.first : nextTerm(diffs.toList())); } List> parse(List lines) => [ for (var l in lines) [for (var n in l.split(' ')) int.parse(n)] ]; part1(List lines) => parse(lines).map(nextTerm).sum; part2(List lines) => parse(lines).map((e) => nextTerm(e.reversed)).sum;
Language: Python
Part 1
Pretty straightforward. Took advantage of
itertools.pairwise
.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))
Part 2
Only thing that changed from the first part was that I used
functools.reduce
to take the differences of the first elements of the generated sequences (rather than the sum of the last elements for Part 1).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))
Python
from .solver import Solver class Day09(Solver): def __init__(self): super().__init__(9) self.numbers: list[list[int]] = [] def presolve(self, input: str): lines = input.rstrip().split('\n') self.numbers = [[int(n) for n in line.split(' ')] for line in lines] for line in self.numbers: stack = [line] while not all(x == 0 for x in stack[-1]): diff = [stack[-1][i+1] - stack[-1][i] for i in range(len(stack[-1]) - 1)] stack.append(diff) stack.reverse() stack[0].append(0) stack[0].insert(0, 0) for i in range(1, len(stack)): stack[i].append(stack[i-1][-1] + stack[i][-1]) stack[i].insert(0, stack[i][0] - stack[i-1][0]) def solve_first_star(self) -> int: return sum(line[-1] for line in self.numbers) def solve_second_star(self) -> int: return sum(line[0] for line in self.numbers)
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
how in the world are you getting top 1k with rust? sheesh!
- Setting up boilerplate beforehand, I only need to fill in the functions (and the return types)
- Really good parsing library (aoc_parse). Today my entire parsing code was
parser!(lines(repeat_sep(i64, " ")))
- Iterators! Actually really ideal for AoC, where pipelines of data are really common. Today both the main part (sum of lines) and inner part (getting a vec of differences) can be done pretty easily through iterators
Today was pretty ideal for my setup. In general I think Rust is really good for later days, because the safety and explicitness make small mistakes rarer (like if you get an element from a HashMap that doesn’t exist, you don’t get a None later down the road (unless you want it, in which case it’s explicit), you get an exception where it happened.
I just really like Rust :3
I guess I’ll have to take rustaceans who claim they’re more productive in rust than python seriously now
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
TypeScript
It’s nice to have a quick easy one for a change
Code
import fs from "fs"; const rows = fs.readFileSync("./09/input.txt", "utf-8") .split(/[\r\n]+/) .map(row => row.trim()) .filter(Boolean) .map(row => row.split(/\s+/).map(number => parseInt(number))); console.info("Part 1: " + solve(structuredClone(rows))); console.info("Part 2: " + solve(structuredClone(rows), true)); function solve(rows: number[][], part2 = false): number { let total = 0; for (const row of rows) { const sequences: number[][] = [row]; while (sequences[sequences.length - 1].some(number => number !== 0)) { // Loop until all are zero const lastSequence = sequences[sequences.length - 1]; const newSequence: number[] = []; for (let i = 0; i < lastSequence.length; i++) { if (lastSequence[i + 1] !== undefined) { newSequence.push(lastSequence[i + 1] - lastSequence[i]); } } sequences.push(newSequence); } // For part two just reverse the sequences if (part2) { sequences.forEach(sequence => sequence.reverse()); } // Add the first zero manually and loop the rest sequences[sequences.length - 1].push(0); for (let i = sequences.length - 2; i >= 0; i--) { sequences[i].push(part2 ? sequences[i][sequences[i].length - 1] - sequences[i + 1][sequences[i + 1].length - 1] : sequences[i][sequences[i].length - 1] + sequences[i + 1][sequences[i + 1].length - 1] ); } total += sequences[0].reverse()[0]; } return total; }
Using a class here actually made part 2 super simple, just copy and paste a function. Initially I was a bit concerned about what part 2 would be, but looking at the lengths of the input data, there looked to be a resonable limit to how many additional rows there could be.
python
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()
Language: Python