Advent of Code 2020 Solution Megathread - Day 15: Rambunctious Recitation

I was certain that C would really help me with the bit fiddly puzzles, but yesterday kicked my booty and left me slapping together something ugly but functional in Python. I switched over after encountering a realloc bug in my custom hashmap implementation. So. I've got some more studying to do on that front. Hopefully you had a better day.

The Puzzle

In today’s puzzle, we're hanging out with the elves! They're playing a number game that involves remembering the last time a particular number was said and generating an infinite sequence from that. I'm thinking that there may be some tricks learned from past years that may be applicable here, but I'll confirm once I've gone through it and submitted my solution. Good luck!

The Leaderboards

As always, this is the spot where I’ll plug any leaderboard codes shared from the community.

Ryan's Leaderboard: 224198-25048a19

If you want to generate your own leaderboard and signal boost it a little bit, send it to me either in a DEV message or in a comment on one of these posts and I'll add it to the list above.

Yesterday’s Languages

Updated 07:36AM 12/15/2020 PST.

Language	Count
Rust	2
Haskell	2
JavaScript	2
COBOL	1

Merry Coding!

Comments

[Benjamin Trent]

I did a basic dynamic programming solution

fn last_spoken(input: &Vec<usize>, last: usize) -> usize {
    let mut turns_spoken: HashMap<usize, usize> = input
        .iter()
        .take(input.len() - 1)
        .enumerate()
        .map(|(i, x)| (*x, i))
        .collect();
    let mut last_spoken = *input.last().unwrap();
    for i in input.len()..last {
        let newly_spoken = match turns_spoken.get(&last_spoken) {
            Some(last_time) => i - *last_time - 1,
            None => 0,
        };
        turns_spoken.insert(last_spoken, i - 1);
        last_spoken = newly_spoken as usize;
    }
    return last_spoken;
}

#[aoc(day15, part1)]
fn number_spoken(input: &Vec<usize>) -> usize {
    last_spoken(input, 2020)
}

#[aoc(day15, part2)]
fn number_spoken_big(input: &Vec<usize>) -> usize {
    last_spoken(input, 30000000)
}

[Derk-Jan Karrenbeld]

Didn't really find this one interesting. Apparently it's a known series.

Either way, Ruby it was:

numbers = File.read('input.txt').chomp.split(',').map(&:to_i)

turns = numbers.dup
memory = Hash.new { [] }

numbers.each_with_index do |number, turn|
  memory[number] = [turn]
  puts "Turn #{turn + 1}: #{number}"
end

goal = 30000000

while turns.length < goal
  turn = turns.length
  previous = turns.last

  before_last, last = memory[previous][-2..]

  speak = last.nil? ? 0 : last - before_last

  # You could store only the last two numbers, but with this set of data there
  # is really no point
  memory[speak] = memory[speak].push(turn)

  puts "Turn #{turn + 1}, speaking #{speak} (#{(turn / goal.to_f * 100).round}%)" if (turn + 1) % (goal / 100) == 0

  turns.push speak
end

puts turns.last

[Kudos Beluga]

Here's part 1 JS, part 2 is a big performance issue. EDIT: I tried using new Map() for a more efficient process but I still ran into the call stack size error. I guess Javascript and heavy processing don't fit together :(

const fs = require("fs")
let arr = fs.readFileSync("input.txt", "utf8").split(",").map(e => Number(e)),
    len = arr.length;
const getnextnumber = (counter = 0) => {
    if (counter == (2020 - len)) console.log(arr[arr.length - 1])
    else {
        let index = arr.slice(arr, arr.length - 1).lastIndexOf(arr[arr.length - 1]);
        if (index > -1) {
            arr.push(arr.length - index - 1)
            getnextnumber(counter + 1)
        } else {
            arr.push(0)
            getnextnumber(counter + 1)
        }
    }
}
getnextnumber()

[Shalvah]

You can use a map to store the numbers you've seen. Map lookup is O(1), compared to looking through a list (O(n)). The keys can be the numbers you've seen, the values the list of positions.

[Kudos Beluga]

Thank you for the suggestion! I'll try it!

[Neil Gall]

Technically simple but designed to catch out the users of, ahem, more academic languages! Rust should offer good performance of course. Optimised build runs both parts in about 5 seconds.

use std::collections::HashMap;

type Turn = usize;
type Number = i64;

struct NumberGame {
    last_turns: HashMap<Number, Turn>,
    prev_turns: HashMap<Number, Turn>,
    starting_numbers: Vec<Number>,
    next_turn: Turn,
    last_spoken: Number
}

impl NumberGame {
    fn new(starting_numbers: &[Number]) -> Self {
        NumberGame {
            last_turns: HashMap::new(),
            prev_turns: HashMap::new(),
            starting_numbers: starting_numbers.iter().cloned().collect(),
            next_turn: 0,
            last_spoken: 0
        }
    }
}

impl Iterator for NumberGame {
    type Item = Number;

    fn next(&mut self) -> Option<Number> {
        let next_number = if self.next_turn < self.starting_numbers.len() {
            self.starting_numbers[self.next_turn]
        } else {
            let last = self.last_turns.get(&self.last_spoken).unwrap();
            match self.prev_turns.get(&self.last_spoken) {
                None => 0,
                Some(prev) => (last - prev) as Number
            }
        };

        if let Some(prev) = self.last_turns.get(&next_number) {
            self.prev_turns.insert(next_number, *prev);
        }
        self.last_turns.insert(next_number, self.next_turn);
        self.last_spoken = next_number;
        self.next_turn += 1;

        Some(next_number)
    }
}


fn number_spoken_at_index(starting_numbers: &[Number], target_index: Turn) -> Number {
    NumberGame::new(starting_numbers)
        .skip(target_index - 1)
        .next()
        .unwrap()
}

fn part1(starting_numbers: &[Number]) -> Number {
    number_spoken_at_index(starting_numbers, 2020)
}

fn part2(starting_numbers: &[Number]) -> Number {
    number_spoken_at_index(starting_numbers, 30000000)
}


fn main() {
    let input = [15,5,1,4,7,0];
    println!("part 1 {}", part1(&input));
    println!("part 2 {}", part2(&input));
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_number_spoken_at_index() {
        assert_eq!(number_spoken_at_index(&[0,3,6], 10), 0);
        assert_eq!(number_spoken_at_index(&[0,3,6], 30000000), 175594);
    }
}

[Shalvah]

Ruby solution. Same thing for Part 1 and 2.

input = [1,17,0,10,18,11,6]

spoken_numbers = {}
current_number = []

# n = 2020 # Part 1
n = 30000000 
n.times do |i|
  if i < input.size
    current_number = input[i]
  else
    last_number_spoken = current_number
    if spoken_numbers[last_number_spoken] != nil
      last_spoken = spoken_numbers[last_number_spoken].last
      if spoken_numbers[last_number_spoken].size == 1
        current_number = 0
      else
        last_spoken_before_that = spoken_numbers[last_number_spoken][-2]
        current_number = last_spoken - last_spoken_before_that
      end
    end
  end

  spoken_numbers[current_number] ||= []
  spoken_numbers[current_number] << i
end

p current_number

[Casper]

My Haskell solution for today was quite short, but performance was shit.

import qualified Data.Map.Strict as Map

solve :: Int -> Map.Map Int Int -> Int -> Int -> Int
solve limit mem t prev 
  | t == limit = prev
  | otherwise =
    case Map.lookup prev mem of
      Nothing -> solve limit (Map.insert prev (t-1) mem) (t+1) 0
      Just t' -> solve limit (Map.insert prev (t-1) mem) (t+1) (t-t'-1)

main = do 
  let input = [20,0,1,11,6,3] -- 436
      initMemory = Map.fromList $ zip  (init input) [1..]

  print $ solve 2021 initMemory (length input+1) (last input)
  print $ solve 30000001 initMemory (length input+1) (last input)
  -- Runtime about 1:20m for part 2.

[Ryan Palo]

It's in Python, and it's not pretty, but I'm busy and it works and keeps me on track, so I'm counting that as a win. Just got to get through this week of finals and then I'll have more time :) Part two takes a while, but not like a "get up and get some coffee" while, so I'll take it.

"""Day 15: Rambunctions Recitation

Help the elves play a memory game where they remember which numbers
they said at which timestep.

It's not pretty, but it gets the job done, and I'm busy.
"""

history = dict()
starting = list(reversed([9,3,1,0,8,4]))

for i in range(1, 30000001):
    if starting:
        current = starting.pop()
    elif first:
        current = 0
    else:
        current = time_since_last

    first = (current not in history)
    if not first:
        time_since_last = i - history[current]
    history[current] = i

print(current)

[Anna]

COBOL as usual

       IDENTIFICATION DIVISION.
       PROGRAM-ID. AOC-2020-15-2.
       AUTHOR ANNA KOSIERADZKA.

       DATA DIVISION.

       WORKING-STORAGE SECTION.
         01 WS-INPUT PIC 9(4) OCCURS 8 TIMES.
         01 N PIC 9.
         01 N1 PIC 9.
         01 WS-NUMBERS OCCURS 67108864 TIMES.
           05 NUM-LAST PIC 9(8) VALUE 0.
           05 NUM-PREV PIC 9(8) VALUE 0.
         01 LAST-NUM PIC 9(8) VALUE 0.
         01 SPOKEN-NUM PIC 9(8) VALUE 0.
         01 LAST-I PIC 9(8) VALUE 0.
         01 PREV-I PIC 9(8) VALUE 0.
         01 I PIC 9(8) VALUE 1.

       PROCEDURE DIVISION.
       001-MAIN.
           PERFORM INIT-DATA.
           PERFORM SPEAK-NUMBERS.
           STOP RUN.

       INIT-DATA.
           MOVE 6 TO N.
      *2,15,0,9,1,20
           MOVE 2 TO WS-INPUT(1).
           MOVE 15 TO WS-INPUT(2).
           MOVE 0 TO WS-INPUT(3).
           MOVE 9 TO WS-INPUT(4).
           MOVE 1 TO WS-INPUT(5).
           MOVE 20 TO WS-INPUT(6).

       SPEAK-NUMBERS.
           PERFORM VARYING I FROM 1 BY 1 UNTIL I > N
              MOVE WS-INPUT(I) TO LAST-NUM
              MOVE I TO NUM-LAST(LAST-NUM + 1)
           END-PERFORM. 

           COMPUTE N1 = N + 1.
           PERFORM VARYING I FROM N1 BY 1 UNTIL I > 30000000
               COMPUTE LAST-I = NUM-LAST(LAST-NUM + 1)
               COMPUTE PREV-I = NUM-PREV(LAST-NUM + 1)
               IF PREV-I = 0 THEN 
                 COMPUTE SPOKEN-NUM = 0
               ELSE 
                 COMPUTE SPOKEN-NUM = LAST-I - PREV-I
               END-IF
      *         DISPLAY I ":" LAST-NUM "->" SPOKEN-NUM
               MOVE NUM-LAST(SPOKEN-NUM + 1) TO NUM-PREV(SPOKEN-NUM + 1)
               COMPUTE NUM-LAST(SPOKEN-NUM + 1) = I
               COMPUTE LAST-NUM = SPOKEN-NUM
           END-PERFORM. 
           DISPLAY LAST-NUM.

[Benedict Gaster]

Here is my Haskell solution, please don't ask about performance for that big number :-)

input :: [Int]
input = [16,1,0,18,12,14,19]

tasks :: [Int] -> Int -> Int
tasks input goal = aux (M.fromList $ zip input [1..length input -1], last input) (length input) goal
    where 
        aux (nums, l) size goal 
            | size == goal = l
            | otherwise = let idx = M.findWithDefault size l nums
                          in aux (M.insert l size nums, size-idx) (size+1) goal

main = do
    print (tasks input 2020)
    print (tasks input 30000000)

[Thibaut Patel]

My JavaScript walkthrough:

Video: