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 strucutres.
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 neighbour 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 neighbour 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//! [`ilog2`]: u32::ilog2
82use crate::util::parse::*;
83
84pub fn parse(input: &str) -> u32 {
85    input.unsigned()
86}
87
88pub fn part1(input: &u32) -> u32 {
89    let mut elf = *input;
90
91    elf *= 2;
92    // Remove highest 1 bit
93    elf -= 1 << elf.ilog2();
94    // Elves use 1-based indexing
95    elf += 1;
96
97    elf
98}
99
100pub fn part2(input: &u32) -> u32 {
101    let target = *input;
102    let mut elf = 0;
103    let mut size = 1;
104
105    while size < target {
106        let remaining = target - size;
107
108        // The trick to log(n) time is that we can handle all elves greater than or less than
109        // the starting point in one pass, greatly increasing efficiency.
110        if elf > size / 2 {
111            // If the elf is greater than the half way point, then an elf will be inserted before
112            // it. This cancels out moving to the previous elf so our position remains the same.
113            let possible = 2 * elf - size;
114            size += possible.min(remaining);
115        } else {
116            // The next elf will be the one before us. If we are at the start then wrap around
117            // to the last elf.
118            if elf >= remaining {
119                elf -= remaining;
120                size += remaining;
121            } else {
122                elf += size;
123                size = elf + 1;
124            }
125        }
126    }
127
128    // The winning position is at 0, so its number is the distance from the starting elf.
129    target - elf
130}
aoc/year2016/day19.rs

aoc/year2016/
day19.rs
