advent_of_code/year2023/
day14.rs

1use crate::common::array_stack::ArrayStack;
2use crate::input::Input;
3use std::collections::hash_map::DefaultHasher;
4use std::hash::{Hash, Hasher};
5
6pub fn solve(input: &Input) -> Result<u64, String> {
7    let mut moving = ArrayStack::<128, u128>::new();
8    let mut fixed = ArrayStack::<128, u128>::new();
9    let mut num_cols = 0;
10
11    for row_str in input.text.lines() {
12        let mut moving_bits = 0;
13        let mut fixed_bits = 0;
14        for (col_idx, b) in row_str.bytes().enumerate() {
15            num_cols = num_cols.max(col_idx + 1);
16            match b {
17                b'#' => {
18                    fixed_bits |= 1 << col_idx;
19                }
20                b'O' => {
21                    moving_bits |= 1 << col_idx;
22                }
23                _ => {}
24            }
25        }
26        moving.push(moving_bits)?;
27        fixed.push(fixed_bits)?;
28    }
29
30    if input.is_part_one() {
31        for x in 0..num_cols {
32            move_dir(0, 1, x, 0, num_cols, moving.slice_mut(), fixed.slice());
33        }
34        return Ok(total_load(moving.slice()));
35    }
36
37    let mut hashes = ArrayStack::<256, u64>::new();
38    hashes.push(calculate_hash(moving.slice()))?;
39
40    let mut remaining = 1_000_000_000;
41    loop {
42        for x in 0..num_cols {
43            move_dir(0, 1, x, 0, num_cols, moving.slice_mut(), fixed.slice());
44        }
45        for y in 0..moving.len() {
46            move_dir(1, 0, 0, y, num_cols, moving.slice_mut(), fixed.slice());
47        }
48        for x in 0..num_cols {
49            move_dir(
50                0,
51                -1,
52                x,
53                moving.len() - 1,
54                num_cols,
55                moving.slice_mut(),
56                fixed.slice(),
57            );
58        }
59        for y in 0..moving.len() {
60            move_dir(
61                -1,
62                0,
63                num_cols - 1,
64                y,
65                num_cols,
66                moving.slice_mut(),
67                fixed.slice(),
68            );
69        }
70        let hash = calculate_hash(moving.slice());
71        remaining -= 1;
72        for i in 0..hashes.len() {
73            if hashes.elements[i] == hash {
74                let cycle_length = hashes.len() - i;
75                remaining %= cycle_length;
76            }
77        }
78        hashes.push(hash)?;
79        if remaining == 0 {
80            return Ok(total_load(moving.slice()));
81        }
82    }
83}
84
85fn move_dir(
86    x_dir: i32,
87    y_dir: i32,
88    mut x: usize,
89    mut y: usize,
90    num_cols: usize,
91    moving: &mut [u128],
92    fixed: &[u128],
93) {
94    let mut position_at = (x, y);
95
96    loop {
97        if (moving[y] & (1 << x)) != 0 {
98            moving[y] &= !(1 << x);
99            moving[position_at.1] |= 1 << position_at.0;
100            position_at = (
101                (position_at.0 as i32 + x_dir) as usize,
102                (position_at.1 as i32 + y_dir) as usize,
103            );
104        } else if (fixed[y] & (1 << x)) != 0 {
105            position_at = ((x as i32 + x_dir) as usize, (y as i32 + y_dir) as usize);
106        }
107
108        if (x_dir == -1 && x == 0)
109            || (y_dir == -1 && y == 0)
110            || (x_dir == 1 && x == num_cols - 1)
111            || (y_dir == 1 && y == moving.len() - 1)
112        {
113            break;
114        }
115        x = (x as i32 + x_dir) as usize;
116        y = (y as i32 + y_dir) as usize;
117    }
118}
119
120fn total_load(moving: &[u128]) -> u64 {
121    moving
122        .iter()
123        .rev()
124        .enumerate()
125        .map(|(idx, row)| (idx + 1) as u64 * u64::from(row.count_ones()))
126        .sum()
127}
128
129fn calculate_hash(t: &[u128]) -> u64 {
130    let mut s = DefaultHasher::new();
131    t.hash(&mut s);
132    s.finish()
133}
134
135#[test]
136pub fn tests() {
137    use crate::input::{test_part_one_no_allocations, test_part_two_no_allocations};
138
139    let test_input = "O....#....
140O.OO#....#
141.....##...
142OO.#O....O
143.O.....O#.
144O.#..O.#.#
145..O..#O..O
146.......O..
147#....###..
148#OO..#....";
149    test_part_one_no_allocations!(test_input => 136);
150    test_part_two_no_allocations!(test_input => 64);
151
152    let real_input = include_str!("day14_input.txt");
153    test_part_one_no_allocations!(real_input => 108_641);
154    test_part_two_no_allocations!(real_input => 84_328);
155
156    let real_input = include_str!("day14_input_other.txt");
157    test_part_two_no_allocations!(real_input => 91_286);
158}
advent_of_code/year2023/day14.rs

advent_of_code/year2023/
day14.rs
