aoc/year2017/
day03.rs

1//! # Spiral Memory
2//!
3//! ## Part One
4//!
5//! Consider the layout as a sequence of hollow donuts. We find the donut that contains the value
6//! which gives one component of the Manhattan value. The second component is the distance from
7//! the center of each edge.
8//!
9//! For example say the target value is 20. We find the donut then subtract the inner donuts
10//! to make the values relative then calculate the values modulo the edge size.
11//!
12//! ```none
13//!                                                      <------------
14//!     17  16  15  14  13      7   6   5   4   3        3   2  [1]  0   3  ^
15//!     18   5   4   3  12      8               2     |  0               2  |
16//!     19   6   1   2  11 =>   9               1 =>  | [1]             [1] |
17//!     20   7   8   9  10     10               0     |  2               0  |
18//!     21  22  23  24  25     11  12  13  14  15     v  3   0  [1]  2   3
19//!                                                          ------------>
20//! ```
21//!
22//! The first component is the horizonal or vertical distance from the centre to the ring,
23//! in this case 2 steps. The second component is the distance from the target number to the
24//! center of each edge, in this case 2 - 1 = 1.
25//!
26//! ## Part Two
27//!
28//! We use the [`Point`] utility to move in the spiral direction. Values are stored in a hashmap
29//! defaulting to zero if the value doesn't exist yet.
30use crate::util::hash::*;
31use crate::util::parse::*;
32use crate::util::point::*;
33
34pub fn parse(input: &str) -> u32 {
35    input.unsigned()
36}
37
38pub fn part1(input: &u32) -> u32 {
39    let target = *input;
40    let mut a = 3;
41
42    // Find the donut that contains the value.
43    while a * a < target {
44        a += 2;
45    }
46    let b = a - 1;
47    let c = a - 2;
48
49    // Distance to donut plus distance to center of edge.
50    (b / 2) + (c / 2).abs_diff((target - c * c - 1) % b)
51}
52
53pub fn part2(input: &u32) -> u32 {
54    let target = *input;
55    let mut size = 2;
56
57    let mut position = Point::new(1, 0);
58    let mut direction = UP;
59    let mut left = LEFT;
60
61    let mut values = FastMap::build([(ORIGIN, 1)]);
62
63    'outer: loop {
64        // Fill in one donut at a time.
65        for edge in 0..4 {
66            for i in 0..size {
67                // Default to zero if a value doesn't exist yet.
68                let value = |point| values.get(&point).unwrap_or(&0);
69
70                // Values in front and to the right (relative to our current direction) are not
71                // filled in yet, so we only need to consider values to the left and behind.
72                let next = value(position - direction)
73                    + value(position + left + direction)
74                    + value(position + left)
75                    + value(position + left - direction);
76
77                if next > target {
78                    break 'outer next;
79                }
80                values.insert(position, next);
81
82                // Turn left at the very end of each edge, unless this is the last edge of
83                // the square.
84                if i == size - 1 && edge < 3 {
85                    position += left;
86                } else {
87                    position += direction;
88                }
89            }
90
91            direction = left;
92            left = left.counter_clockwise();
93        }
94
95        size += 2;
96    }
97}
aoc/year2017/day03.rs

aoc/year2017/
day03.rs
