aoc/year2016/
day19.rs

1//! # An Elephant Named Joseph
2//!
3//! The title is a reference to the [Josephus problem](https://en.wikipedia.org/wiki/Josephus_problem).
4//! We can solve both parts efficiently in `O(1)` constant storage without needing any
5//! auxiliary data structures.
6//!
7//! ## Part One
8//!
9//! Part one is exactly the Josephus problem with k = 2. Each round the number of elves is either
10//! odd or even. If the number of elves is even then every second elf is eliminated and the starting
11//! elf remains the same, for example starting with 8 elves and a step size of 1:
12//!
13//! 1 ~~2~~ 3 ~~4~~ 5 ~~6~~ 7 ~~8~~
14//!
15//! The next round we double the step size used to find elves from 1 to 2:
16//!
17//! 1 ~~2~~ ~~3~~ ~~4~~ 5 ~~6~~ ~~7~~ ~~8~~
18//!
19//! In the special case that the number of elves is power of two then the starting elf will always
20//! win.
21//!
22//! If the number of elves is odd then the last elf will also eliminate the starting elf,
23//! so the new starting elf increases by the step size.
24//!
25//! ~~1~~ ~~2~~ 3 ~~4~~ 5
26//!
27//! We can represent this as a loop:
28//!
29//! ```none
30//!    let mut n = <starting number of elves>
31//!    let mut step = 1;
32//!    let mut winner = 1;
33//!    while n > 1 {
34//!        if n % 2 == 1 {
35//!            winner += step * 2;
36//!        }
37//!        n /= 2;
38//!        step *= 2;
39//!    }
40//! ```
41//!
42//! If we examine the loop we can see that the winner is simply the binary digits of `n` multiplied
43//! by two, excluding the highest bit, with one added. For example for 5 elves:
44//!
45//! ```none
46//!     n = 5 = 101
47//!     n * 2 = 10 = 1010
48//!     n minus high bit = 010
49//!     n plus one = 011 = 3
50//! ```
51//!
52//! The [`ilog2`] function will return the number of zeroes before the highest one bit, for example
53//! `10.ilog2() = 3`. We can then shift a bit by that amount and subtract to get the result in
54//! constant `O(1)` time.
55//!
56//!
57//! ## Part Two
58//!
59//! Part two is a variant of the problem. We solve in `log(n)` time by working *backwards*
60//! from the winning elf until we reach the starting number of elves.
61//! Starting with the winning elf `a` it must have eliminated its neighbor to the right:
62//!
63//! `a` => `a b`
64//!
65//! We then choose the previous elf to the left wrapping around to elf `b` in this case. Elf `b`
66//! must have eliminated its neighbor 1 step to the right:
67//!
68//! `a b` => `a b c`
69//!
70//! Play passes to the left, in this case elf `a` must have eliminated an elf 2 steps away:
71//!
72//! `a b c` => `a b d c`
73//!
74//! Play passes to the left, wrapping around to elf `c` that must have eliminated an elf 2 steps
75//! away:
76//!
77//! `a b d c` => `a e b d c`
78//!
79//! Now that we have 5 elves our starting elf `a` is one step away from `c` so the answer is 2.
80//!
81//! ## Part Two alternative
82//!
83//! There is a also a closed form `O(1)` mathematical solution,
84//! called the n-cowboy shootout problem, described in [OEIS A334473](https://oeis.org/A334473).
85//!
86//! [`ilog2`]: u32::ilog2
87use crate::util::parse::*;
88
89pub fn parse(input: &str) -> u32 {
90    input.unsigned()
91}
92
93pub fn part1(input: &u32) -> u32 {
94    let mut elf = *input;
95
96    elf *= 2;
97    // Remove highest 1 bit
98    elf -= 1 << elf.ilog2();
99    // Elves use 1-based indexing
100    elf += 1;
101
102    elf
103}
104
105pub fn part2(input: &u32) -> u32 {
106    let target = *input;
107    let mut elf = 0;
108    let mut size = 1;
109
110    while size < target {
111        let remaining = target - size;
112
113        // The trick to log(n) time is that we can handle all elves greater than or less than
114        // the starting point in one pass, greatly increasing efficiency.
115        if elf > size / 2 {
116            // If the elf is greater than the half way point, then an elf will be inserted before
117            // it. This cancels out moving to the previous elf so our position remains the same.
118            let possible = 2 * elf - size;
119            size += possible.min(remaining);
120        } else {
121            // The next elf will be the one before us. If we are at the start then wrap around
122            // to the last elf.
123            if elf >= remaining {
124                elf -= remaining;
125                size += remaining;
126            } else {
127                elf += size;
128                size = elf + 1;
129            }
130        }
131    }
132
133    // The winning position is at 0, so its number is the distance from the starting elf.
134    target - elf
135}
aoc/year2016/day19.rs

aoc/year2016/
day19.rs
