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 horizontal or vertical distance from the center 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.
30//!
31//! Note that [OEIS A141481](https://oeis.org/A141481/b141481.txt) shows the sequence well
32//! past the limit requested by the puzzle.  However, this is fast enough to solve to not
33//! be worth turning this into a lookup table.
34use crate::util::hash::*;
35use crate::util::parse::*;
36use crate::util::point::*;
37
38pub fn parse(input: &str) -> u32 {
39    input.unsigned()
40}
41
42pub fn part1(input: &u32) -> u32 {
43    let target = *input;
44    let mut a = 3;
45
46    // Find the donut that contains the value.
47    while a * a < target {
48        a += 2;
49    }
50    let b = a - 1;
51    let c = a - 2;
52
53    // Distance to donut plus distance to center of edge.
54    (b / 2) + (c / 2).abs_diff((target - c * c - 1) % b)
55}
56
57pub fn part2(input: &u32) -> u32 {
58    let target = *input;
59    let mut size = 2;
60
61    let mut position = Point::new(1, 0);
62    let mut direction = UP;
63    let mut left = LEFT;
64
65    let mut values = FastMap::build([(ORIGIN, 1)]);
66
67    'outer: loop {
68        // Fill in one donut at a time.
69        for edge in 0..4 {
70            for i in 0..size {
71                // Default to zero if a value doesn't exist yet.
72                let value = |point| values.get(&point).unwrap_or(&0);
73
74                // Values in front and to the right (relative to our current direction) are not
75                // filled in yet, so we only need to consider values to the left and behind.
76                let next = value(position - direction)
77                    + value(position + left + direction)
78                    + value(position + left)
79                    + value(position + left - direction);
80
81                if next > target {
82                    break 'outer next;
83                }
84                values.insert(position, next);
85
86                // Turn left at the very end of each edge, unless this is the last edge of
87                // the square.
88                if i == size - 1 && edge < 3 {
89                    position += left;
90                } else {
91                    position += direction;
92                }
93            }
94
95            direction = left;
96            left = left.counter_clockwise();
97        }
98
99        size += 2;
100    }
101}
aoc/year2017/day03.rs

aoc/year2017/
day03.rs
