11 votes

Day 15: Rambunctious Recitation

Today's problem description: https://adventofcode.com/2020/day/15


Join the Tildes private leaderboard! You can do that on this page, by entering join code 730956-de85ce0c.

Please post your solutions in your own top-level comment. Here's a template you can copy-paste into your comment to format it nicely, with the code collapsed by default inside an expandable section with syntax highlighting (you can replace python with any of the "short names" listed in this page of supported languages):

<details>
<summary>Part 1</summary>

```python
Your code here.
```

</details>

9 comments

  1. PapaNachos
    (edited )
    Link
    I got stuck in debugging hell for a bit, but eventually got it to work. My solution to part B is almost identical to part A, the only parameter I changed is how far it goes. Tonight's eurobeat...

    I got stuck in debugging hell for a bit, but eventually got it to work. My solution to part B is almost identical to part A, the only parameter I changed is how far it goes.

    Tonight's eurobeat selection. It helped me distract myself from the pain of dropping a weight on my foot earlier.

    Day 15 Part A – Python

    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])
    
    Day 15 Part B – Python

    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])
    
    Tips and Commentary
    • 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.

    4 votes
  2. Crespyl
    Link
    Ruby I was worried that this would be way harder than it turned out to be. Part 1 Reading the description had me thinking there was going to be some kind of tricky manipulation involved in part 2,...

    Ruby

    I was worried that this would be way harder than it turned out to be.

    Part 1 Reading the description had me thinking there was going to be some kind of tricky manipulation involved in part 2, so I built out a separate class to keep track of the history for each number. The biggest slow down for actually solving part 1, at least for me, was reading and re-reading the directions several times to make sure I understood the requirements. Something about the writing here kept making me feel like I was missing something.
    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
    
    Part 2
    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.

    3 votes
  3. pnutzh4x0r
    Link
    Python Repo Link Part 1 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

    Repo Link

    Part 1

    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()
    
    Part 2

    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()
    
    3 votes
  4. JRandomHacker
    Link
    This is the first day I didn't finish before going to bed, and it really shows the importance of sometimes just stepping back and sleeping on a problem. Last night, I was trying to keep going as...

    This is the first day I didn't finish before going to bed, and it really shows the importance of sometimes just stepping back and sleeping on a problem. Last night, I was trying to keep going as fast as I could, and my solution kept adding unnecessary complexity because of the way I started. After I restarted this morning, I knocked it out in ~15min.

    This was also my first solution that ran in more than 1s, so that's a fun milestone. Part 2 took 6.996 seconds.

    Parts 1/2 (just different loop bounds)
    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}";
    }
    
    3 votes
  5. Gyrfalcon
    Link
    Language: Julia Repository This was a nice simple one I thought. Interesting performance note, I originally did not type the dictionary that I use to store the game state, which was fine in part...

    This was a nice simple one I thought. Interesting performance note, I originally did not type the dictionary that I use to store the game state, which was fine in part 1, but was noticeable in part 2. By adding that type, runtime was cut from a little over 21 seconds down to 8.5, of which about one eighth was memory allocation. After looking at some of the solutions here, I decided to tweak a little more, and by not saving every value in the history, switching to an immutable type to store the values, and typing down my numbers, I was able to get the time down even further to a ~2.7 seconds. Not the fastest here, but pretty good I think!

    Parts 1 and 2
    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()
    
    3 votes
  6. bhrgunatha
    Link
    Racket 💜 Shared Game Engine (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...

    Racket 💜

    Shared Game Engine
    (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))
    
    Part 1 and 2 both just call the game with appropriate inputs
    (elf-game input 2020)
    (elf-game input 30000000)
    
    Explanation of code evolution I went through 4 stages.
    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.

    2 votes
  7. Bauke
    Link
    Language: Rust. Repository. Main function (run harness). For some reason I struggled a bit with what exactly the puzzle was asking of me, but once I figured it out I got to a result pretty quick....

    For some reason I struggled a bit with what exactly the puzzle was asking of me, but once I figured it out I got to a result pretty quick.

    When I got to part two I hoped I wouldn't have to change too much to make it output a result within my lifetime, and after reading @PapaNachos' tip on making sure the previous number can be retrieved quickly my solution got a lot faster. And finished within 20 seconds, which is pretty good I think.

    Solution
    use std::collections::HashMap;
    
    use crate::DayResult;
    
    pub(crate) fn solve(data: String) -> DayResult {
      let result_one = Some(calculate(&data, 2020).to_string());
      let result_two = Some(calculate(&data, 30000000).to_string());
    
      Ok((result_one, result_two))
    }
    
    fn calculate(data: &str, target: usize) -> isize {
      let mut numbers = HashMap::new();
      let mut previous_number = (0, (0, 0));
    
      for (index, number) in data
        .trim()
        .split(',')
        .map(str::parse::<isize>)
        .map(Result::unwrap)
        .enumerate()
      {
        numbers.insert(number, (index, index));
        previous_number = (number, (index, index));
      }
    
      for index in numbers.len()..target {
        let next_num = previous_number.1 .1 - previous_number.1 .0;
        let num = numbers
          .entry(next_num as isize)
          .or_insert_with(|| (index, index));
        num.0 = num.1;
        num.1 = index;
    
        previous_number = (next_num as isize, *num);
      }
    
      *numbers.iter().max_by(|a, b| a.1 .1.cmp(&b.1 .1)).unwrap().0
    }
    
    #[test]
    fn test_sample() {
      let sample = "0,3,6";
      let result_one = calculate(sample, 2020);
      assert_eq!(result_one, 436);
    }
    
    Output
    🌟 Day 15  |
    🎆 Part 1  | 441
    🎇 Part 2  | 10613991
    🌠 Runtime | 18.874561785s
    
    2 votes
  8. nothis
    (edited )
    Link
    Python Alright, a bit late, but I did it. I spent way too long looking for some math-y trick but, of course there is none (I'm still paranoid, though). The solution turned out to just store the...

    Python

    Alright, a bit late, but I did it. I spent way too long looking for some math-y trick but, of course there is none (I'm still paranoid, though). The solution turned out to just store the last index for each number, which isn't a big deal, memory-wise and lead to linear run time. It still takes a few seconds for part 2 and I assume you can optimize it further but I can't be bothered.

    Part 1+2
    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))
    
    2 votes
  9. wycy
    Link
    Rust Solution 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 =...

    Rust

    Solution
    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();
    }
    
    1 vote