DEV Community

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

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...
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 • Edited

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 • 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);
    }
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
shalvah profile image
Shalvah • 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
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

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: