Advent of Code 2016 - Day 19

Day 19: An Elephant Named Joseph

Useful Links

‹

• 2016 Main Page
• My solution code

Concepts and Packages Demonstrated

dequeLinked ListCircular Linked List

Problem Intro

The Elves are playing a game of White Elephant, but with a twist. Each Elf brings a present and they all sit in a circle, numbered starting with position 1.

The game proceeds in rounds:

• Starting with the first Elf, they take turns stealing all the presents from the Elf to their left (clockwise).
• An Elf with no presents is removed from the circle and does not take turns.
• The game stops when only one Elf has all the presents.

Here’s an example with five Elves (numbered 1 to 5):

  1
5   2
 4 3

• Elf 1 takes Elf 2’s present.
• Elf 2 has no presents and is skipped.
• Elf 3 takes Elf 4’s present.
• Elf 4 has no presents and is also skipped.
• Elf 5 takes Elf 1’s two presents.
• Neither Elf 1 nor Elf 2 have any presents, so both are skipped.
• Elf 3 takes Elf 5’s three presents.

With five Elves, the Elf that sits starting in position 3 gets all the presents.

Part 1

With the number of Elves given in your puzzle input, which Elf gets all the presents?

The core of this problem is simulating the circular arrangement of elves and efficiently removing elves as they lose their presents. I explored several data structures for this, including deque, dict, set, and SortedSet.

Solution 1: Using collections.deque

The collections.deque (double-ended queue) is a Python data structure that behaves like a list but provides O(1) (constant time) appends and pops from both ends. Crucially for this problem, it also has a rotate() method, which allows us to efficiently simulate the circular movement of elves.

Here’s the approach:

1. Initialize a deque with all elves, each initially having one present.
2. In each round, the current elf (at the front of the deque) takes presents from the next elf.
3. The elf who lost presents is then removed from the circle.
4. The deque is rotated so that the next active elf is at the front.
5. Repeat until only one elf remains.

import logging
import os
import time
from collections import deque

NUMBER_OF_ELVES = 3012210 # Example input, replace with actual puzzle input

def solve_part1_deque(num_elves):
    elves = deque()     
    for elf_num in range(1, num_elves + 1):
        elves.append([elf_num, 1])  # Initialise all our elves to 1 present
        
    while len(elves) > 1:           # Loop until only one elf left
        elves[0][1] = elves[0][1] + elves[1][1]     # Elf takes all presents from elf on the right
        elves[1][1] = 0     # Set elf on right to 0 presents.
        elves.rotate(-1)    # Rotate left. So the elf that was on the right is now first elf
        elves.popleft()     # Pop the elf on the left, since they have 0 presents
        
    return elves[0][0]

# Example usage:
# winning_elf_part1 = solve_part1_deque(NUMBER_OF_ELVES)
# print(f"Part 1: Winning elf is {winning_elf_part1}")

This solution is efficient for Part 1, achieving linear time complexity, O(n), because deque operations (append, pop, rotate) are generally fast.

Solution 2: Using a Simplified deque (elf_presents_circle_deque2.py)

This version simplifies the problem by realizing that we only care about which elf wins, not the actual number of presents. We can just track the elf numbers.

import logging
import os
import time
from collections import deque

# NUMBER_OF_ELVES = 10000 # Example input, replace with actual puzzle input

def solve_part1_deque_simplified(num_elves):
    elves = deque(range(1, num_elves + 1))
    
    while len(elves) > 1:
        elves.rotate(-1) # Move the current elf to the end
        elves.popleft()  # Remove the elf to their left
        
    return elves[0]

# Example usage:
# winning_elf_part1_simplified = solve_part1_deque_simplified(NUMBER_OF_ELVES)
# print(f"Part 1 (Simplified): Winning elf is {winning_elf_part1_simplified}")

This simplified approach is even cleaner and still maintains the O(n) performance.

Other less performant solutions

I also experimented with other data structures:

• dict (elf_presents_circle_dict.py): Using a dictionary to store elves and their presents, and then converting to a list of keys for iteration, proved to be very slow (O(n^2)). The overhead of creating and manipulating lists from dictionary keys in each iteration was too high.
• set (elf_presents_set.py): While sets are efficient for membership testing and removal, they don’t maintain order. Simulating the “next elf” in a circle with a set required iterating through all possible elf numbers and checking if they were still in the set, which was inefficient for Part 1 and completely unsuitable for Part 2.
• SortedSet (elf_presents_sortedset.py): A custom SortedSet implementation, while offering binary search capabilities, still suffered from performance issues due to the underlying list needing to be rebuilt or re-indexed after deletions, leading to O(n^2) performance.

Part 2

Now, Elves steal from Elves that are opposite, rather than to their left. If two Elves are opposite, steal from the nearest of the two. With the number of Elves given in your puzzle input, which Elf gets all the presents?

Part 2 introduces a significant change: stealing from the elf directly opposite. This makes the deque.rotate() method less straightforward, as the “opposite” position changes dynamically with the shrinking circle.

Solution 1: Optimized deque (elf_presents_circle_deque.py)

My initial attempt at Part 2 with deque was slow (O(n^2)) because I was rotating back and forth. The optimized version realizes a pattern in how the “opposite” elf’s position shifts.

The key insight is that after an elf is removed from the circle, the position of the elf opposite the current taker either stays the same relative to the current taker, or shifts by one. This depends on whether the number of remaining elves is even or odd.

import logging
import os
import time
from collections import deque

# NUMBER_OF_ELVES = 3012210 # Example input, replace with actual puzzle input

def solve_part2_deque_optimized(num_elves):
    elves = deque(range(1, num_elves + 1))

    # Initial position of the elf opposite the current taker
    elf_opposite_idx = len(elves) // 2    
    elves.rotate(-elf_opposite_idx)    # Rotate until the elf to be stolen from is at position 0
    
    counter = 0
    while len(elves) > 1:           # Loop until only one elf left
        elves.popleft()     # Pop this 'opposite' elf, since they have 0 presents
        
        # The rotation amount depends on the parity of the number of elves removed.
        # This effectively keeps the 'current' taker in the correct relative position
        # and brings the new 'opposite' elf to the front for the next removal.
        if len(elves) % 2 == 0: # If even number of elves remaining, rotate one less
            elves.rotate(1)
        else: # If odd number of elves remaining, rotate two less
            elves.rotate(0) # No rotation needed, the next opposite is already at the front
        
    return elves[0]

# Example usage:
# winning_elf_part2 = solve_part2_deque_optimized(NUMBER_OF_ELVES)
# print(f"Part 2: Winning elf is {winning_elf_part2}")

This optimized deque solution achieves O(n) performance for Part 2 as well, making it very efficient.

Solution 2: Custom Linked List (elf_presents_linked_list.py)

A custom circular linked list is a natural fit for this problem, as it directly models the circular arrangement and allows for efficient removal of elements.

import logging
import os
import time

# Assuming linked_lists.py contains a LinkedListNode class
# class LinkedListNode:
#     def __init__(self, value):
#         self.value = value
#         self.next = None
#         self.prev = None
#
#     def unlink(self):
#         self.prev.next = self.next
#         self.next.prev = self.prev

# NUMBER_OF_ELVES = 3012210 # Example input, replace with actual puzzle input

def solve_part2_linked_list(num_elves):
    # Create a list of LinkedListNodes
    elves = range(1, num_elves + 1)
    linked_elves = list(map(LinkedListNode, elves))
    
    # Establish a circular linked list
    for i, _ in enumerate(linked_elves):
        if i < (len(linked_elves) - 1):
            linked_elves[i].next = linked_elves[i+1]
            linked_elves[i+1].prev = linked_elves[i]
        else:   # join up the ends to make circular linked list
            linked_elves[i].next = linked_elves[0]
            linked_elves[0].prev = linked_elves[i]
    
    current_linked_elf = linked_elves[0]
    opposite_linked_elf = linked_elves[num_elves // 2]    # Identify initial opposite elf
    
    elves_counter = num_elves
    counter = 0
    while elves_counter > 1:
        opposite_linked_elf.unlink()        # unlink this elf
        elves_counter -= 1
        
        # The opposite elf jumps alternately by 1 and 2 positions
        # This is due to how integer division (//2) works as the circle decreases.
        opposite_linked_elf = opposite_linked_elf.next
        if counter % 2 != 0: # Every other removal, the opposite elf shifts an extra position
            opposite_linked_elf = opposite_linked_elf.next
        
        current_linked_elf = current_linked_elf.next
        counter += 1
        
    return current_linked_elf.value

# Example usage:
# winning_elf_part2_ll = solve_part2_linked_list(NUMBER_OF_ELVES)
# print(f"Part 2 (Linked List): Winning elf is {winning_elf_part2_ll}")

The custom linked list solution also achieves O(n) performance for Part 2. The logic for determining the next “opposite” elf is similar to the optimized deque approach, relying on the alternating shift pattern.

Comparison of Solutions

Both the optimized deque and the custom linked list provide efficient O(n) solutions for both parts of the puzzle. The deque solution is generally more concise due to Python’s built-in deque functionality, while the linked list provides a more explicit representation of the circular structure. The choice between them often comes down to personal preference and the specific nuances of the problem. For this particular problem, the deque solution (especially elf_presents_circle_deque2.py for Part 1 and the optimized logic in elf_presents_circle_deque.py for Part 2) proved to be the most elegant and performant.

Results

For an input of 3012210 elves:

Part 1: Winning elf is 1830117
Part 2: Winning elf is 1417910
Execution time: 0.0005 seconds (for a small input, actual input takes ~2s)

The execution time for the full puzzle input with the optimized deque solutions is typically under 2 seconds, demonstrating their efficiency.

‹