1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

//! # Spiral Memory
//!
//! ## Part One
//!
//! Consider the layout as a sequence of hollow donuts. We find the donut that contains the value
//! which gives one component of the Manhattan value. The second component is the distance from
//! the center of each edge.
//!
//! For example say the target value is 20. We find the donut then subtract the inner donuts
//! to make the values relative then calculate the values modulo the edge size.
//!
//! ```none
//!                                                      <------------
//!     17  16  15  14  13      7   6   5   4   3        3   2  [1]  0   3  ^
//!     18   5   4   3  12      8               2     |  0               2  |
//!     19   6   1   2  11 =>   9               1 =>  | [1]             [1] |
//!     20   7   8   9  10     10               0     |  2               0  |
//!     21  22  23  24  25     11  12  13  14  15     v  3   0  [1]  2   3
//!                                                          ------------>
//! ```
//!
//! The first component is the horizonal or vertical distance from the centre to the ring,
//! in this case 2 steps. The second component is the distance from the target number to the
//! center of each edge, in this case 2 - 1 = 1.
//!
//! ## Part Two
//!
//! We use the [`Point`] utility to move in the spiral direction. Values are stored in a hashmap
//! defaulting to zero if the value doesn't exist yet.
use crate::util::hash::*;
use crate::util::parse::*;
use crate::util::point::*;

pub fn parse(input: &str) -> u32 {
    input.unsigned()
}

pub fn part1(input: &u32) -> u32 {
    let target = *input;
    let mut a = 3;

    // Find the donut that contains the value.
    while a * a < target {
        a += 2;
    }
    let b = a - 1;
    let c = a - 2;

    // Distance to donut plus distance to center of edge.
    (b / 2) + (c / 2).abs_diff((target - c * c - 1) % b)
}

pub fn part2(input: &u32) -> u32 {
    let target = *input;
    let mut size = 2;

    let mut position = Point::new(1, 0);
    let mut direction = UP;
    let mut left = LEFT;

    let mut values = FastMap::build([(ORIGIN, 1)]);

    'outer: loop {
        // Fill in one donut at a time.
        for edge in 0..4 {
            for i in 0..size {
                // Default to zero if a value doesn't exist yet.
                let value = |point| values.get(&point).unwrap_or(&0);

                // Values in front and to the right (relative to our current direction) are not
                // filled in yet, so we only need to consider values to the left and behind.
                let next = value(position - direction)
                    + value(position + left + direction)
                    + value(position + left)
                    + value(position + left - direction);

                if next > target {
                    break 'outer next;
                }
                values.insert(position, next);

                // Turn left at the very end of each edge, unless this is the last edge of
                // the square.
                if i == size - 1 && edge < 3 {
                    position += left;
                } else {
                    position += direction;
                }
            }

            direction = left;
            left = left.counter_clockwise();
        }

        size += 2;
    }
}