year2017/
day03.rs

1use std::num::NonZeroU32;
2use utils::prelude::*;
3
4/// Calculating spiral patterns.
5#[derive(Clone, Debug)]
6pub struct Day03 {
7    input: NonZeroU32,
8}
9
10impl Day03 {
11    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
12        Ok(Self {
13            input: parser::nonzero_u32().parse_complete(input)?,
14        })
15    }
16
17    #[must_use]
18    pub fn part1(&self) -> u32 {
19        let input = self.input.get();
20        let ring = f64::from(input).sqrt().ceil() as u32 / 2;
21        let side_length = ring * 2 + 1;
22        let bottom_right = side_length * side_length;
23        let middles = [
24            bottom_right - ring,       // Bottom
25            bottom_right - (ring * 3), // Left
26            bottom_right - (ring * 5), // Top
27            bottom_right - (ring * 7), // Right
28        ];
29        let offset = middles.iter().map(|m| m.abs_diff(input)).min().unwrap();
30        ring + offset
31    }
32
33    #[must_use]
34    pub fn part2(&self) -> u64 {
35        // To cover 0..=u32::MAX only the first 150 values in the sequence are necessary. The 150th
36        // value is in the 6th ring, meaning a grid of 13x13 is required, or 15x15 with an extra
37        // ring around the edge to avoid needing bounds checks.
38        const LEN: usize = 15;
39
40        let mut grid = [[0; LEN]; LEN];
41        let (mut x, mut y) = (LEN / 2, LEN / 2);
42        grid[x][y] = 1;
43
44        // Store the number of turns and remaining steps until the next turn. The number of previous
45        // turns gives you the current direction and next number of steps by following the pattern:
46        //  1x Right
47        //  1x Up
48        //  2x Left
49        //  2x Down
50        //  3x Right
51        //  3x Up
52        //  4x Left
53        //  ...
54        let mut turns = 0;
55        let mut steps = 1;
56
57        while grid[x][y] < u64::from(self.input.get()) {
58            if steps == 0 {
59                turns += 1;
60                steps = (turns / 2) + 1;
61            }
62            steps -= 1;
63            match turns % 4 {
64                0 => x += 1,
65                1 => y += 1,
66                2 => x -= 1,
67                3 => y -= 1,
68                _ => unreachable!(),
69            }
70
71            grid[x][y] = grid[x - 1][y - 1]
72                + grid[x - 1][y]
73                + grid[x - 1][y + 1]
74                + grid[x][y - 1]
75                + grid[x][y + 1]
76                + grid[x + 1][y - 1]
77                + grid[x + 1][y]
78                + grid[x + 1][y + 1];
79        }
80
81        grid[x][y]
82    }
83}
84
85examples!(Day03 -> (u32, u64) [
86    {input: "1", part1: 0},
87    {input: "12", part1: 3},
88    {input: "23", part1: 2},
89    {input: "1024", part1: 31},
90    // Custom examples
91    {input: "100", part2: 122},
92    {input: "200", part2: 304},
93    {input: "4294967295", part2: 4429173742},
94]);
year2017/day03.rs

year2017/
day03.rs
