year2017/
day03.rs

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

year2017/
day03.rs
