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 values = FastMap::build([(ORIGIN, 1)]);
60    let mut position = ORIGIN;
61    let mut direction = RIGHT;
62    let mut steps = 1;
63
64    loop {
65        for _ in 0..2 {
66            for _ in 0..steps {
67                position += direction;
68
69                let next: u32 =
70                    DIAGONAL.iter().map(|&d| values.get(&(position + d)).unwrap_or(&0)).sum();
71
72                if next > target {
73                    return next;
74                }
75                values.insert(position, next);
76            }
77            direction = direction.counter_clockwise();
78        }
79        steps += 1;
80    }
81}
aoc/year2017/day03.rs

aoc/year2017/
day03.rs
