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 a 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 [`isolate_highest_one`] method returns just the highest one bit, for example
53//! `10.isolate_highest_one() = 8`. We can then subtract to get the result in
54//! constant `O(1)` time.
55//!
56//! ## Part Two
57//!
58//! Part two is a variant of the problem. We solve in `log(n)` time by working *backwards*
59//! from the winning elf until we reach the starting number of elves.
60//! Starting with the winning elf `a` it must have eliminated its neighbor to the right:
61//!
62//! `a` => `a b`
63//!
64//! We then choose the previous elf to the left wrapping around to elf `b` in this case. Elf `b`
65//! must have eliminated its neighbor 1 step to the right:
66//!
67//! `a b` => `a b c`
68//!
69//! Play passes to the left, in this case elf `a` must have eliminated an elf 2 steps away:
70//!
71//! `a b c` => `a b d c`
72//!
73//! Play passes to the left, wrapping around to elf `c` that must have eliminated an elf 2 steps
74//! away:
75//!
76//! `a b d c` => `a e b d c`
77//!
78//! Now that we have 5 elves our starting elf `a` is one step away from `c` so the answer is 2.
79//!
80//! ## Part Two alternative
81//!
82//! There is also a closed form `O(1)` mathematical solution,
83//! called the n-cowboy shootout problem, described in [OEIS A334473](https://oeis.org/A334473).
84//!
85//! [`isolate_highest_one`]: u32::isolate_highest_one
86use crate::util::parse::*;
87
88pub fn parse(input: &str) -> u32 {
89    input.unsigned()
90}
91
92pub fn part1(input: &u32) -> u32 {
93    let n = *input * 2;
94    // Remove highest 1 bit, then add 1 for one-based indexing.
95    n - n.isolate_highest_one() + 1
96}
97
98pub fn part2(input: &u32) -> u32 {
99    let target = *input;
100    let mut elf = 0;
101    let mut size = 1;
102
103    while size < target {
104        let remaining = target - size;
105
106        // The trick to log(n) time is that we can handle all elves greater than or less than
107        // the starting point in one pass, greatly increasing efficiency.
108        if elf > size / 2 {
109            // If the elf is greater than the half way point, then an elf will be inserted before
110            // it. This cancels out moving to the previous elf so our position remains the same.
111            let possible = 2 * elf - size;
112            size += possible.min(remaining);
113        } else {
114            // The next elf will be the one before us. If we are at the start then wrap around
115            // to the last elf.
116            if elf >= remaining {
117                elf -= remaining;
118                size += remaining;
119            } else {
120                elf += size;
121                size = elf + 1;
122            }
123        }
124    }
125
126    // The winning position is at 0, so its number is the distance from the starting elf.
127    target - elf
128}
aoc/year2016/day19.rs

aoc/year2016/
day19.rs
