// 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);
    }
}