use std::collections::VecDeque;

fn is_space(seed: usize, (x, y): (usize, usize)) -> bool {
    let sum = x*x + 3*x + 2*x*y + y + y*y + seed;
    let bin = format!("{:#b}", sum);
    bin.matches('1').count() % 2 == 0
}

fn solve_puzzle(seed: usize, part1_goal: (usize, usize), part2_limit: usize) -> (usize, usize) {
    let mut part1_found = false;
    let mut part1_depth = 0;
    let mut part2_count = 1;

    // Breadth-first search of the maze
    let start = (1, 1);
    let mut visited = vec![start];
    let mut queue = VecDeque::from([(start, 0)]);
    loop {
        let (pos, depth) = queue.pop_front().unwrap();

        // Is this the shortest path to `part1_goal'?
        if pos == part1_goal && !part1_found {
            part1_found = true;
            part1_depth = depth;
        }
        // Have we found all the information we want?
        if depth > part2_limit && part1_found {
            return (part1_depth, part2_count);
        }

        // The grid extends infinitely far in the positive directions
        let mut adjacents = vec![
            (pos.0 + 1, pos.1),
            (pos.0, pos.1 + 1),
        ];
        if pos.0 > 0 {
            adjacents.push((pos.0 - 1, pos.1));
        }
        if pos.1 > 0 {
            adjacents.push((pos.0, pos.1 - 1));
        }

        for adj in adjacents {
            // Is this a valid move to a space we haven't visited before?
            if is_space(seed, adj) && !visited.contains(&adj) {
                visited.push(adj);
                queue.push_back((adj, depth + 1));

                // Count locations reachable in at most `part2_limit' steps
                if depth < part2_limit {
                    part2_count += 1;
                }
            }
        }
    }
}

fn main() {
    // My personal puzzle input
    let seed = 1358;

    let (part1, part2) = solve_puzzle(seed, (31, 39), 50);

    // Part 1 gives 96 for me
    println!("Part 1 solution: {}", part1);

    // Part 2 gives 141 for me
    println!("Part 2 solution: {}", part2);
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn part1_example1() {
        assert_eq!(solve_puzzle(10, (7, 4), 42).0, 11);
    }
}