Day 15: Rambunctious Recitation

First think I do is preallocate an area to work with. Then I can load the numbers that I already know of in there. I also create a memory dictionary which will be used to track when any given number was last spoken.

The first few passes deal with numbers already loaded in, so they're not a big deal. I just pass over them. But still dump them into memory and keep track of the 'spoken'

For all new numbers I first check if the 'last spoken' number is in my memory. If not I know it's new, so we get a '0'. Otherwise I do the subtraction as described. Then just update my history, memory, and last spoken.

#data = test_data.split(',')
data = input_data.split(',')

distance = 2020
memory = {}
history = [None] * distance

last_spoken = None
for index, num in enumerate(data):
    history[index] = int(num)

for index in range(distance):
    
    num = history[index]
    first_time = True
    if last_spoken in memory.keys():
        first_time = False
    if num is not None:
        new_val = num
    else:
        if not first_time:
            new_val = index - memory[last_spoken]
        else:
            new_val = 0
    history[index] = new_val
    memory[last_spoken] = index
    last_spoken = new_val
print(history[-1])

This is the exact same as part A. The only thing I changed is the value loaded into the 'distance' variable. It takes slightly longer (maybe 30s?), but it's still fine. I suspect if I had designed it differently, it would take much longer.

#data = test_data.split(',')
data = input_data.split(',')

distance = 30000000
memory = {}
history = [None] * distance

last_spoken = None
for index, num in enumerate(data):
    history[index] = int(num)

for index in range(distance):
    
    num = history[index]
    first_time = True
    if last_spoken in memory.keys():
        first_time = False
    if num is not None:
        new_val = num
    else:
        if not first_time:
            new_val = index - memory[last_spoken]
        else:
            new_val = 0
    history[index] = new_val
    memory[last_spoken] = index
    last_spoken = new_val
print(history[-1])

• If you're planning to store the whole history, I highly recommend pre-allocating it since you know exactly how many numbers you're going to care about. If you keep resizing your storage area (for example, through python list's append method) you're going to waste a lot of time unnecessarily. I don't think you actually have to store the history beyond the first few though.

• You'll need a way to tell how recently a given number was spoken. You can search for it each time, or you can find a way to store that information so that it can be retrieved more quickly. Searching each time will get slower as your history gets bigger

• Make sure you're careful at what point you make your checks and comparisons. It's very important, but the correct order might be non-obvious.

class SeenMap
  def initialize
    @hash = Hash.new
  end

  def [](n)
    if @hash[n].nil?
      @hash[n] = []
    else
      @hash[n]
    end
  end

  def log(n, age)
    if @hash[n].nil?
      @hash[n] = []
    end
    @hash[n].append(age)
  end
end

def compute_p1(input, max=2020)
  starting_numbers = input.strip.split(',').map(&:to_i)
  seen = SeenMap.new

  starting_numbers.each_with_index do |n,i|
    seen.log(n, i+1) #+1 since turn numbers start at 1 instead of 0
  end

  last_number = starting_numbers.last
  (max-starting_numbers.size).times do |n|
    cur_turn = starting_numbers.size + n + 1
    next_number = if seen[last_number].size < 2
                    0
                  else
                    seen[last_number][-2..].reduce(&:-).abs
                  end
    seen.log(next_number, cur_turn)
    #puts "turn #{cur_turn}: #{next_number}"
    last_number = next_number
  end

  return last_number
end

def compute_p2(input)
  compute_p1(input, max=30000000)
end

Sometimes brute force works well enough! I set this up and left it to run while I started googling and hitting up the OEIS to see if I could find some other reference for this kind of sequence (I'm sure it's out there somewhere, but I haven't found it yet, as of this comment). Before I'd gotten very far, my terminal pinged me with the correct solution. Turns out my brute force search finishes in about 34s, which is fast enough for now.

I might go back and golf down my solution later, since it could be a bit prettier/more idiomatic.

I did the first part in the most straight-forward and naive way possible... just did a reverse linear search to find the previous location of a number. Turns out that Python lists do not have a rindex method (strings do though!), so I had to make that myself. Once that was in place, the solution was straightforward.

import sys

# Functions

def list_rindex(data, target):
    for index, value in enumerate(reversed(data)):
        if value == target:
            return len(data) - index
    return None

def play_game(numbers, limit=2020):
    turns = numbers[:]

    while len(turns) < limit:
        prev = list_rindex(turns[:-1], turns[-1])

        if prev is None:
            turns.append(0)
        else:
            turns.append(len(turns) - prev)

    return turns[-1]

# Main Execution

def main():
    for line in sys.stdin:
        numbers = [int(n) for n in line.split(',')]
        result  = play_game(numbers)

        print(result)

if __name__ == '__main__':
    main()

For the second part, I knew I had to use a cache/history of some sort, but I just couldn't figure out how to order the logic to search for the last value while also not having in the history. My compromise then was to have a bounded buffer (ie. deque) for each number. For each number, I add it to the corresponding deque and if the deque is length 2, then I have seen it before. With that structure in place I could determine if I had seen a number before in an efficient manner (no longer need to do a reverse linear search).

Overall, the code is still slow (takes about 50 seconds on my computer), but it is still better than my naive solution for the first part.

import collections
import sys

# Functions

def play_game(numbers, limit=30000000):
    seen = collections.defaultdict(lambda: collections.deque(maxlen=2))

    for turn, number in enumerate(numbers, 1):
        seen[number].append(turn)

    last = 0
    for turn in range(len(numbers) + 1, limit):
        seen[last].append(turn)

        if len(seen[last]) == 1:
            last = 0
        else:
            last = seen[last][1] - seen[last][0]

    return last

# Main Execution

def main():
    for line in sys.stdin:
        numbers = [int(n) for n in line.split(',')]
        result  = play_game(numbers)

        print(result)

if __name__ == '__main__':
    main()

using (var fs = new StreamReader(Inputs.Year2020.Inputs2020.Input15))
{
	// Number - turn
	var history = new Dictionary<int, int>();
	var pastHistory = new Dictionary<int, int>();
	history.Add(9, 1);
	history.Add(3, 2);
	history.Add(1, 3);
	history.Add(0, 4);
	history.Add(8, 5);
	history.Add(4, 6);

	var last = 4;
	for (int i = 7; i <= 2020; i++)
	{
		if (!pastHistory.ContainsKey(last))
		{
			if (history.ContainsKey(0))
			{
				pastHistory[0] = history[0];
			}
			history[0] = i;
			last = 0;
		}
		else
		{
			var diff = history[last] - pastHistory[last];
			pastHistory[last] = history[last];
			if (history.ContainsKey(diff))
			{
				pastHistory[diff] = history[diff];
			}
			history[diff] = i;
			last = diff;
		}


	}
	return $"Last number is {last}";
}

function main()

    input = []
    open("Day15/input.txt") do fp
        input = parse.(Int32, split(readchomp(fp), ','))
    end

    game = Dict{Int32, Tuple{Int32, Int32}}()

    for (idx, num) in enumerate(input)
        add_num!(game, idx, num)
    end

    result_1 = play_game!(deepcopy(game), 2020, input[end])
    println(result_1)

    result_2 = play_game!(deepcopy(game), 30_000_000, input[end])
    println(result_2)

end

function add_num!(game, turn, num)
    if !(num in keys(game))
        game[num] = (0, turn)
    else
        game[num] = (game[num][2], turn)
    end
end

function play_game!(game, last_turn, first_num)
    first_turn = length(game) + 1
    prev_num = first_num
    for turn = first_turn:last_turn
        prev_num = advance_game!(game, prev_num, turn)
    end
    return prev_num
end

function advance_game!(game, prev_num, turn)
    if game[prev_num][1] == 0
        add_num!(game, turn, 0)
        new_num = 0
    else
        new_num = game[prev_num][2] - game[prev_num][1]
        add_num!(game, turn, new_num)
    end
    return new_num
end

main()

(define (elf-game input limit)
  (define spoken (make-fxvector limit 0))
  (define ns (map string->number (regexp-match* #px"\\d+" (first input))))
  (for ([(n i) (in-indexed ns)]) (unsafe-fxvector-set! spoken n (unsafe-fx+ i 1)))
  (for/fold ([last-spoken (last ns)])
            ([turn (in-range (length ns) limit)])
    (define peek (unsafe-fxvector-ref spoken last-spoken))
    (define speak (unsafe-fx- turn (if (zero? peek) turn peek)))
    (unsafe-fxvector-set! spoken last-spoken turn)
    speak))

1. I used an immutable hash table - although Racket handles the indirection of the contents to avoid having thousands of copies of the same values, there is still the overhead of managing memory of all the top level hash table objects - 1 per iteration. This got me both answers though, but I was unhappy with the ~28 seconds for Part 2.

2. I swapped to a single mutable hash table which sped things up by almost 50% - 17s. At this stage I was using a list of (up to) two previous locations per spoken number which is wasteful and a lot of memory pressure.

3. I traced out on paper the process and realised I only need to store a single value per iteration - not a list of the previous 2! This brought the runtime down to ~7s.

4. Finally I converted the hash table to a vector (array) which allocates all the memory at once instead of dynamically expanding the hash table. Down to around 1s. Then I also remembered Racket can use fixed size numbers - instead of generic (unlimited value) numbers (since there can no number greater than 30,000,000) and "unsafe" operations which gave a final 10% boost to about 800/900 ms from 28 seconds! I often like to try out various other approaches once the problem is solved and a different data structure worked well today.

def play(numbers, to):
    last = [-1] * to
    for i in range(0, len(numbers)):
        last[numbers[i]] = i

    numbers.append(0)
    previous = 0
    for i in range(len(numbers), to):
        distance = 0
        if last[previous] >= 0:
            distance = i - 1 - last[previous]
        last[previous] = i - 1
        previous = distance
        numbers.append(distance)
    return previous


start = [0, 3, 1, 6, 7, 5]

print("2020th number =", play(start, 2020))
print("30000000th number =", play(start, 30000000))

use std::env;
use std::io::{self, prelude::*, BufReader};
use std::fs::File;
use std::collections::HashMap;

fn day15(input: &str) -> io::Result<()> {
    let file = File::open(input).expect("Input file not found.");
    let reader = BufReader::new(file);

    let input: Vec<String> = match reader.lines().collect() {
        Err(err) => panic!("Unknown error reading input: {}", err),
        Ok(result) => result,
    };
    let input: Vec<_> = input
        .concat()
        .split(",")
        .map(|x| x.parse::<usize>().unwrap())
        .collect();

    let mut announced: HashMap<usize,usize> = HashMap::new();
    let mut turn = 0;
    let mut last;
    let mut this = 0;

    // Preload inputs
    for (i,num) in input.iter().enumerate() {
        turn = i + 1;
        if turn != input.len() { announced.insert(*num,turn); }
    }
    last = *input.iter().last().unwrap();

    // Play game
    loop {
        if turn == 2020     { println!("Part 1: {}", this); } // 260
        if turn == 30000000 { println!("Part 2: {}", this); break; } // 950
        this = match announced.get(&last) {
            Some(v) => turn - v,
            None => 0,
        };
        announced.insert(last,turn);
        turn += 1;
        last = this;
    }
    Ok(())
}

fn main() {
    let args: Vec<String> = env::args().collect();
    let filename = &args[1];
    day15(&filename).unwrap();
}