1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

use crate::input::Input;

pub fn solve(input: &mut Input) -> Result<u32, String> {
    const MAX_ITERATIONS: usize = 1000;
    let mut region = Region::parse(input.text)?;
    for round in 1..MAX_ITERATIONS {
        if region.update_is_stable() {
            return Ok(round as u32);
        }
    }
    Err(format!(
        "Did not stabilize in {} iterations",
        MAX_ITERATIONS
    ))
}

#[derive(Copy, Clone, Eq, PartialEq)]
enum Location {
    Empty,
    CucumberFacingEast,
    CucumberFacingSouth,
}

pub struct Region {
    locations: Vec<Location>,
    new_locations: Vec<Location>,
    width: u16,
    height: u16,
}

impl Region {
    fn parse(text: &str) -> Result<Self, String> {
        let height = text.lines().count();
        let width = text.lines().next().unwrap_or_default().len();
        if height < 1 || width < 1 {
            return Err("Too small input".to_string());
        }

        let mut locations = vec![Location::Empty; width * height];
        for (y, line) in text.lines().enumerate() {
            if line.len() != width {
                return Err("Not all lines have equal length".to_string());
            }
            for (x, byte) in line.bytes().enumerate() {
                let location = match byte {
                    b'.' => Location::Empty,
                    b'>' => Location::CucumberFacingEast,
                    b'v' => Location::CucumberFacingSouth,
                    _ => {
                        return Err("Invalid input".to_string());
                    }
                };
                locations[x + y * width] = location;
            }
        }
        Ok(Self {
            new_locations: locations.clone(),
            locations,
            width: width as u16,
            height: height as u16,
        })
    }

    fn update_is_stable(&mut self) -> bool {
        self.new_locations.fill(Location::Empty);

        for y in 0..self.height {
            for x in 0..self.width {
                let existing_idx = (x + y * self.width) as usize;
                if Location::CucumberFacingEast == self.locations[existing_idx] {
                    let new_x = (x + 1) % self.width;
                    let new_idx = (new_x + y * self.width) as usize;
                    self.new_locations[if matches!(self.locations[new_idx], Location::Empty) {
                        new_idx
                    } else {
                        existing_idx
                    }] = Location::CucumberFacingEast;
                }
            }
        }

        for y in 0..self.height {
            for x in 0..self.width {
                let existing_idx = (x + y * self.width) as usize;
                if Location::CucumberFacingSouth == self.locations[existing_idx] {
                    let new_y = (y + 1) % self.height;
                    let new_idx = (x + new_y * self.width) as usize;
                    let is_new_location_empty =
                        matches!(self.new_locations[new_idx], Location::Empty);
                    self.new_locations[if is_new_location_empty
                        && !matches!(self.locations[new_idx], Location::CucumberFacingSouth)
                    {
                        new_idx
                    } else {
                        existing_idx
                    }] = Location::CucumberFacingSouth;
                }
            }
        }

        std::mem::swap(&mut self.locations, &mut self.new_locations);
        self.locations == self.new_locations
    }
}

#[test]
pub fn tests() {
    use crate::input::test_part_one;

    let example = "v...>>.vv>
.vv>>.vv..
>>.>v>...v
>>v>>.>.v.
v>v.vv.v..
>.>>..v...
.vv..>.>v.
v.v..>>v.v
....v..v.>";
    test_part_one!(example => 58);

    let real_input = include_str!("day25_input.txt");
    test_part_one!(real_input => 582);
}