Ryan Palo

Posted on

# 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!

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

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
JavaScript 2
COBOL 1

Merry Coding!

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:

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 • 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()

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

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.

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

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