Initial commit

1 files changed, 85 insertions, 0 deletions

diff --git a/d19/src/main.rs b/d19/src/main.rs
new file mode 100644
index 0000000..91d9524
--- /dev/null
+++ b/d19/src/main.rs
@@ -0,0 +1,85 @@
+// Find the next Elf still in the game, to the left of `i'
+fn next_elf(elves: &[bool], i: usize) -> usize {
+    let mut n = (i + 1) % elves.len();
+    while !elves[n] {
+        n = (n + 1) % elves.len();
+    }
+    n
+}
+
+fn solve_puzzle(
+    num_elves: usize,
+    victim1: usize,
+    next_victim: fn(&[bool], usize, usize, usize) -> usize,
+) -> usize {
+    // We only need to store whether an Elf is still in the game;
+    // we don't care how many presents each one has.
+    let mut elves = [true].repeat(num_elves);
+
+    // Thief and victim indices, respectively
+    let mut t = 0;
+    let mut v = victim1;
+
+    let mut rem = num_elves;
+    while rem > 1 {
+        // Perform the act of stealing
+        elves[v] = false;
+        rem -= 1;
+
+        // Who does the stealing next?
+        t = next_elf(&elves, t);
+
+        // Who gets stolen from next?
+        v = next_victim(&elves, rem, t, v);
+    }
+
+    // Elves should be numbered from 1 instead of 0
+    t + 1
+}
+
+// Part 1: victim is always to the left of thief.
+fn next_victim_part1(elves: &[bool], _rem: usize, nthief: usize, _victim: usize) -> usize {
+    next_elf(elves, nthief)
+}
+
+// Part 2: victim is always across from thief.
+// It's less clear that this function is correct, but it is!
+fn next_victim_part2(elves: &[bool], rem: usize, _nthief: usize, victim: usize) -> usize {
+    let mut nv = next_elf(elves, victim);
+    if rem % 2 == 0 {
+        nv = next_elf(elves, nv);
+    }
+    nv
+}
+
+fn main() {
+    // My personal puzzle input
+    let input = 3014603;
+
+    // Part 1 gives 1834903 for me
+    println!(
+        "Part 1 solution: {}",
+        solve_puzzle(input, 1, next_victim_part1)
+    );
+
+    // Part 2 gives 1420280 for me
+    println!(
+        "Part 2 solution: {}",
+        solve_puzzle(input, input / 2, next_victim_part2)
+    );
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn part1_example1() {
+        assert_eq!(solve_puzzle(5, 1, next_victim_part1), 3);
+    }
+
+    #[test]
+    fn part2_example1() {
+        assert_eq!(solve_puzzle(5, 5 / 2, next_victim_part2), 2);
+    }
+}