advent_of_code/year2016/
day13.rs

1use crate::input::Input;
2use std::cmp::Reverse;
3use std::collections::{BinaryHeap, HashSet};
4
5const fn is_wall(x: i32, y: i32, magic_number: i32) -> bool {
6    let sum = x * x + 3 * x + 2 * x * y + y + y * y + magic_number;
7    sum.count_ones() % 2 == 1
8}
9
10pub fn solve(input: &Input) -> Result<u32, String> {
11    const TARGET: (i32, i32) = (31, 39);
12
13    let magic_number = input
14        .text
15        .parse::<i32>()
16        .map_err(|e| format!("Invalid magic number: {e}"))?;
17
18    let mut to_visit = BinaryHeap::new();
19    let mut visited_states = HashSet::new();
20
21    let initial_state = (1, 1);
22    let mut visit_count = 0;
23
24    to_visit.push(Reverse((0, 0, initial_state)));
25    visited_states.insert(initial_state);
26
27    while let Some(Reverse((_estimate, visited_state_cost, visited_state))) = to_visit.pop() {
28        if input.is_part_one() {
29            if visited_state == TARGET {
30                return Ok(visited_state_cost);
31            }
32        } else if visited_state_cost > 50 {
33            return Ok(visit_count);
34        } else {
35            visit_count += 1;
36        }
37
38        for (diffx, diffy) in [(-1, 0), (1, 0), (0, -1), (0, 1)] {
39            let new_x = visited_state.0 + diffx;
40            let new_y = visited_state.1 + diffy;
41            if new_x < 0 || new_y < 0 || is_wall(new_x, new_y, magic_number) {
42                continue;
43            }
44
45            let new_cost = visited_state_cost + 1;
46
47            let do_insert = visited_states.insert((new_x, new_y));
48            if do_insert {
49                let new_estimate = new_cost
50                    + if input.is_part_one() {
51                        (new_x - TARGET.0).unsigned_abs() + (new_y - TARGET.1).unsigned_abs()
52                    } else {
53                        0
54                    };
55                to_visit.push(Reverse((new_estimate, new_cost, (new_x, new_y))));
56            }
57        }
58    }
59
60    Err("No solution found".to_string())
61}
62
63#[test]
64pub fn tests() {
65    use crate::input::{test_part_one, test_part_two};
66
67    let real_input = include_str!("day13_input.txt");
68    test_part_one!(real_input => 82);
69    test_part_two!(real_input => 138);
70}
advent_of_code/year2016/day13.rs

advent_of_code/year2016/
day13.rs
