DEV Community

loading...
Cover image for Advent of Code 2020 Solution Megathread - Day 15: Rambunctious Recitation

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

rpalo profile image Ryan Palo ・1 min read

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
Enter fullscreen mode Exit fullscreen mode

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!

Discussion (12)

pic
Editor guide
Collapse
benwtrent profile image
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)
}
Enter fullscreen mode Exit fullscreen mode
Collapse
sleeplessbyte profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
kudostoy0u profile image
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()
Enter fullscreen mode Exit fullscreen mode
Collapse
shalvah profile image
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.

Collapse
kudostoy0u profile image
Kudos Beluga

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

Collapse
neilgall profile image
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);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
shalvah profile image
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
Enter fullscreen mode Exit fullscreen mode
Collapse
cappe987 profile image
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.
Enter fullscreen mode Exit fullscreen mode
Collapse
rpalo profile image
Ryan Palo Author

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)
Enter fullscreen mode Exit fullscreen mode
Collapse
galoisgirl profile image
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.

Enter fullscreen mode Exit fullscreen mode
Collapse
bgaster profile image
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)
Enter fullscreen mode Exit fullscreen mode
Collapse
thibpat profile image
Thibaut Patel

My JavaScript walkthrough:

Video: