Skip Navigation

🦌 - 2023 DAY 9 SOLUTIONS -🦌

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


🔒 Thread is locked until there's at least 100 2 star entries on the global leaderboard

🔓 Unlocked after 5 mins

27
27 comments
  • 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)
    
  • APL

    I finally managed to make use of ⍣ :D

    input←⊃⎕NGET'inputs/day9.txt'1
    p←{⍎('¯'@((⍸'-'∘=)⍵))⍵}¨input
    f←({⍵⍪⊂2-⍨/⊃¯1↑⍵}⍣{∧/0=⊃¯1↑⍺})
    ⎕←+/{+/⊢/¨f⊂⍵}¨p ⍝ part 1
    ⎕←+/{-/⊣/¨f⊂⍵}¨p ⍝ part 2
    
  • (Cursed) Python

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

    import numpy.polynomial.polynomial as pol
    
    with open("input.txt") as f:
      lines = list(map(lambda l: list(map(int, l.split(" "))), f.read().split("\n")))
    
    lo, hi = 0, 0
    
    for line in lines:
      for i in range(len(line)):
        poly, (r, *_) = pol.Polynomial.fit(range(len(line)), line, full=True, deg=i)
        if r < 0.0000000001:
          break
    
      lo += int(round(poly(-1)))
      hi += int(round(poly(len(line))))
    
    print(f"Part 1: {hi}")
    print(f"Part 2: {lo}")
    
  • Nim

    Pretty easy one today. Made a Pyramid type to hold the values and their layers of diffs, and an extend function to predict the next value. For part 2 I just had to make an extendLeft version of it that inserts and subtracts instead of appending and adding.

  • Crystal

    recursion is awesome! (sometimes)

    input = File.read("input.txt")
    
    seqs = input.lines.map &.split.map &.to_i
    
    sums = seqs.reduce({0, 0}) do |prev, sequence|
    	di = diff(sequence)
    	{prev[0] + sequence[0] - di[0], prev[1] + di[1] + sequence[-1]}
    end
    puts sums
    
    
    def diff(sequence)
    	new = Array.new(sequence.size-1) {|i| sequence[i+1] - sequence[i]}
    
    	return {0, 0} unless new.any?(&.!= 0)
    
    	di = diff(new)
    	{new[0] - di[0], di[1] + new[-1]}
    end
    
  • Rust

    Discrete derivatives!

  • Ruby

    !ruby@programming.dev [LANGUAGE: Ruby]

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

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

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

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

    code golf

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

    from .solver import Solver
    
    class Day09(Solver):
    
      def __init__(self):
        super().__init__(9)
        self.numbers: list[list[int]] = []
    
      def presolve(self, input: str):
        lines = input.rstrip().split('\n')
        self.numbers = [[int(n) for n in line.split(' ')] for line in lines]
        for line in self.numbers:
          stack = [line]
          while not all(x == 0 for x in stack[-1]):
            diff = [stack[-1][i+1] - stack[-1][i] for i in range(len(stack[-1]) - 1)]
            stack.append(diff)
          stack.reverse()
          stack[0].append(0)
          stack[0].insert(0, 0)
          for i in range(1, len(stack)):
            stack[i].append(stack[i-1][-1] + stack[i][-1])
            stack[i].insert(0, stack[i][0] - stack[i-1][0])
    
      def solve_first_star(self) -> int:
        return sum(line[-1] for line in self.numbers)
    
      def solve_second_star(self) -> int:
        return sum(line[0] for line in self.numbers)
    
  • Python

    Easy one today

    code
    import pathlib
    
    base_dir = pathlib.Path(__file__).parent
    filename = base_dir / "day9_input.txt"
    
    with open(base_dir / filename) as f:
        lines = f.read().splitlines()
    
    histories = [[int(n) for n in line.split()] for line in lines]
    
    answer_p1 = 0
    answer_p2 = 0
    
    for history in histories:
        deltas: list[list[int]] = []
        last_line: list[int] = history
    
        while any(last_line):
            deltas.append(last_line)
            last_line = [last_line[i] - last_line[i - 1] for i in range(1, len(last_line))]
    
        first_value = 0
        last_value = 0
        for delta_list in reversed(deltas):
            last_value = delta_list[-1] + last_value
            first_value = delta_list[0] - first_value
    
        answer_p1 += last_value
        answer_p2 += first_value
    
    print(f"{answer_p1=}")
    print(f"{answer_p2=}")
    
  • 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 ⇌))
    
  • 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))
    

    GitHub Repo

  • Raku

    First time using Grammar Actions Object to make parsing a little cleaner. I thought about not keeping track of the left and right values (and I originally didn't for part 1), but I think keeping track allows for an easier to understand solution.

    View code on github

    edit: although I don't know why @values.all != 0 evaluates to true why any value is not zero. I thought that @values.any != 0 would do that, but it seems that their behavior is flipped from my expectations.

    edit2: Oh, I think I understand now. != is a shortcut for !==, and !== is actually the equality operator that is then negated. You can negate most relational operators in Raku by prefixing them with !. So the junction is actually binding to the == equality operator and not the !== inequality operator. Therefore @values.all != 0 becomes !(@values.all == 0). I'm not sure why they would choose this order of operations, though.

    edit3: Ah, it's in the documentation, so it's not even an oversight. https://github.com/rakudo/rakudo/issues/3748

    Code (probably still doesn't render correctly)
    use v6;
    
    sub MAIN($input) {
        my $file = open $input;
    
        grammar Oasis {
            token TOP { +%"\n" "\n"* }
            token history { +%\h+ }
            token val { '-'? \d+ }
        }
    
        class OasisActions {
            method TOP ($/) { make $».made }
            method history ($/) { make $».made }
            method val ($/) { make $/.Int }
        }
    
        my $oasis = Oasis.parse($file.slurp, actions => OasisActions.new);
        my @histories = $oasis.made;
        my $part-one-solution;
        my $part-two-solution;
        sub revdiff { $^b - $^a }
        for @histories -> @history {
            my @values = @history;
            my @rightmosts = [@values.tail];
            my @leftmosts = [@values.head];
            while @values.all != 0 {
                @values = @values.tail(*-1) Z- @values.head(*-1);
                @rightmosts.push(@values.tail);
                @leftmosts.push(@values.head);
            }
            $part-one-solution += [+] @rightmosts;
            $part-two-solution += [[&revdiff]] @leftmosts.reverse;
        }
        say "part 1: $part-one-solution";
        say "part 2: $part-two-solution";
    }
    
  • TypeScript

    GitHub link

    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

    Github

  • C#

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

    Day 9

    • Snippet:

              static void Part1(string data)
              {
                  var result = ParseInput(data)
                      .Select(history => ProcessHistory(history, g => g.Length - 1, (a, b) => a + b))
                      .Sum();
      
                  Console.WriteLine(result);
              }
      
              static void Part2(string data)
              {
                  var result = ParseInput(data)
                      .Select(history => ProcessHistory(history, g => 0, (a, b) => a - b))
                      .Sum();
      
                  Console.WriteLine(result);
              }
      
              static int ProcessHistory(
                  int[] history,
                  Func guessIndex,
                  Func collateGuess)
              {
                  bool allZeros = true;
      
                  var diffs = new int[history.Length - 1];
                  for (int i = 0; i < diffs.Length; i++)
                  {
                      var diff = history[i + 1] - history[i];
                      diffs[i] = diff;
                      allZeros = allZeros && (diff == 0);
                  }
      
                  var guess = history[guessIndex(history)];
      
                  if (!allZeros)
                  {
                      guess = collateGuess(
                          guess,
                          ProcessHistory(diffs, guessIndex, collateGuess));
                  }
      
                  return guess;
              }
      
  • [Language: Lean4]

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

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

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

    Solution
    
    private def parseLine (line : String) : Except String $ List Int :=
      line.split Char.isWhitespace
      |> List.map String.trim
      |> List.filter String.notEmpty
      |> List.mapM String.toInt?
      |> Option.toExcept s!"Failed to parse numbers in line \"{line}\""
    
    def parse (input : String) : Except String $ List $ List Int :=
      let lines := input.splitOn "\n" |> List.map String.trim |> List.filter String.notEmpty
      lines.mapM parseLine
    
    -------------------------------------------------------------------------------------------
    
    private def differences : List Int → List Int
    | [] => []
    | _ :: [] => []
    | a :: b :: as => (a - b) :: differences (b::as)
    
    private theorem differences_length_independent_arg (a b : Int) (bs : List Int) : (differences (a :: bs)).length = (differences (b :: bs)).length := by
      induction bs <;> simp[differences]
    
    -- BEWARE: Extrapolate needs the input reversed.
    private def extrapolate : List Int → Int
    | [] => 0
    | a :: as =>
      if a == 0 && as.all (· == 0) then
        0
      else
        have : (differences (a :: as)).length < as.length + 1 := by
          simp_arith[differences]
          induction (as) <;> simp_arith[differences]
          case cons b bs hb => rw[←differences_length_independent_arg]
                               assumption
        a + extrapolate (differences (a :: as))
    termination_by extrapolate a => a.length
    
    def part1 : List (List Int) → Int :=
      List.foldl Int.add 0 ∘ List.map (extrapolate ∘ List.reverse)
    
    -------------------------------------------------------------------------------------------
    
    def part2 : List (List Int) → Int :=
      List.foldl Int.add 0 ∘ List.map extrapolate
    
  • 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 - _)
    
  • A pretty simple one today, but fun to do. I could probably clean up the parsing code (AKA my theme for this year), and create just one single vector instead of having the original history separated out from all of the sequences, but this is what made sense to me on my first pass so it's how I did it.

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

    pub struct Day09;
    
    fn get_history(input: &str) -> Vec {
        input
            .split(' ')
            .filter_map(|num| num.parse::().ok())
            .collect::>()
    }
    
    fn get_sequences(history: &Vec) -> Vec> {
        let mut sequences = vec![get_steps(&history)];
    
        while !sequences.last().unwrap().iter().all_equal() {
            sequences.push(get_steps(sequences.last().unwrap()));
        }
    
        sequences
    }
    
    fn get_steps(sequence: &Vec) -> Vec {
        sequence
            .iter()
            .tuple_windows()
            .map(|(x, y)| y - x)
            .collect()
    }
    
    impl Solver for Day09 {
        fn star_one(&self, input: &str) -> String {
            input
                .lines()
                .map(|line| {
                    let history = get_history(line);
    
                    let add_value = get_sequences(&history)
                        .iter()
                        .rev()
                        .map(|seq| seq.last().unwrap().clone())
                        .reduce(|acc, x| acc + x)
                        .unwrap();
    
                    history.last().unwrap() + add_value
                })
                .sum::()
                .to_string()
        }
    
        fn star_two(&self, input: &str) -> String {
            input
                .lines()
                .map(|line| {
                    let history = get_history(line);
    
                    let minus_value = get_sequences(&history)
                        .iter()
                        .rev()
                        .map(|seq| seq.first().unwrap().clone())
                        .reduce(|acc, x| x - acc)
                        .unwrap();
    
                    history.first().unwrap() - minus_value
                })
                .sum::()
                .to_string()
        }
    }
    
You've viewed 27 comments.