DEV Community

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

Ryan Palo on December 15, 2020

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 b...

Read full post

Benjamin Trent • Dec 15 '20

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)
}

Casper • Dec 15 '20

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.

Neil Gall • Dec 15 '20 • Edited

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 • Dec 15 '20 • Edited

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

Derk-Jan Karrenbeld • Dec 17 '20

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

Benedict Gaster • Dec 15 '20

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)

Anna • Dec 15 '20

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.

Ryan Palo • Dec 16 '20

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)

Thibaut Patel • Dec 16 '20

My JavaScript walkthrough:

Video:

Shalvah • Dec 15 '20

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.