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 = (input as f64).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
30            .iter()
31            .map(|m| m.abs_diff(input))
32            .min()
33            .unwrap();
34        ring + offset
35    }
36
37    #[must_use]
38    pub fn part2(&self) -> u64 {
39        // To cover 0..=u32::MAX only the first 150 values in the sequence are necessary. The 150th
40        // value is in the 6th ring, meaning a grid of 13x13 is required, or 15x15 with an extra
41        // ring around the edge to avoid needing bounds checks.
42        const LEN: usize = 15;
43
44        let mut grid = [[0; LEN]; LEN];
45        let (mut x, mut y) = (LEN / 2, LEN / 2);
46        grid[x][y] = 1;
47
48        // Store the number of turns and remaining steps until the next turn. The number of previous
49        // turns gives you the current direction and next number of steps by following the pattern:
50        //  1x Right
51        //  1x Up
52        //  2x Left
53        //  2x Down
54        //  3x Right
55        //  3x Up
56        //  4x Left
57        //  ...
58        let mut turns = 0;
59        let mut steps = 1;
60
61        while grid[x][y] < u64::from(self.input.get()) {
62            if steps == 0 {
63                turns += 1;
64                steps = (turns / 2) + 1;
65            }
66            steps -= 1;
67            match turns % 4 {
68                0 => x += 1,
69                1 => y += 1,
70                2 => x -= 1,
71                3 => y -= 1,
72                _ => unreachable!(),
73            }
74
75            grid[x][y] = grid[x - 1][y - 1]
76                + grid[x - 1][y]
77                + grid[x - 1][y + 1]
78                + grid[x][y - 1]
79                + grid[x][y + 1]
80                + grid[x + 1][y - 1]
81                + grid[x + 1][y]
82                + grid[x + 1][y + 1];
83        }
84
85        grid[x][y]
86    }
87}
88
89examples!(Day03 -> (u32, u64) [
90    {input: "1", part1: 0},
91    {input: "12", part1: 3},
92    {input: "23", part1: 2},
93    {input: "1024", part1: 31},
94    // Custom examples
95    {input: "100", part2: 122},
96    {input: "200", part2: 304},
97    {input: "4294967295", part2: 4429173742},
98]);
year2017/day03.rs

year2017/
day03.rs
