year2018/
day10.rs

1use utils::geometry::Vec2;
2use utils::prelude::*;
3
4/// Recognizing text formed by converging points.
5#[derive(Clone, Debug)]
6pub struct Day10 {
7    message: String,
8    seconds: u32,
9}
10
11impl Day10 {
12    pub fn new(input: &str, _: InputType) -> Result<Self, InputError> {
13        let vec2 = parser::i32()
14            .with_prefix(parser::take_while(|&x| x == b' '))
15            .repeat_n(b',')
16            .map(Vec2::from);
17
18        let mut points = vec2
19            .with_prefix("position=<")
20            .with_suffix("> velocity=<")
21            .then(vec2)
22            .with_suffix(">")
23            .repeat(parser::eol(), 2)
24            .parse_complete(input)?;
25
26        let mut seconds = 0;
27        let (mut last_x_diff, mut last_y_diff) = (i32::MAX, i32::MAX);
28        let message = 'time: loop {
29            let (mut min_x, mut max_x) = (i32::MAX, i32::MIN);
30            let (mut min_y, mut min_y_vel, mut max_y, mut max_y_vel) = (i32::MAX, 0, i32::MIN, 0);
31            for (p, v) in &points {
32                min_x = min_x.min(p.x);
33                max_x = max_x.max(p.x);
34
35                if p.y < min_y {
36                    min_y = p.y;
37                    min_y_vel = v.y;
38                }
39                if p.y > max_y {
40                    max_y = p.y;
41                    max_y_vel = v.y;
42                }
43            }
44
45            let (x_diff, y_diff) = (max_x.saturating_sub(min_x), max_y.saturating_sub(min_y));
46            if x_diff > last_x_diff
47                || y_diff > last_y_diff
48                || (x_diff == last_x_diff && y_diff == last_y_diff)
49            {
50                return Err(InputError::new(input, 0, "points never converge"));
51            }
52            (last_x_diff, last_y_diff) = (x_diff, y_diff);
53
54            // Letters are 6 wide and 10 tall, with 2 wide gaps between them
55            if y_diff != 9 || x_diff % 8 != 5 {
56                let advance_by = if y_diff >= 10 && min_y_vel.saturating_sub(max_y_vel) > 0 {
57                    ((y_diff - 9) / min_y_vel.saturating_sub(max_y_vel)).max(1)
58                } else {
59                    1
60                };
61
62                for (p, v) in points.iter_mut() {
63                    *p += *v * advance_by;
64                }
65                seconds += advance_by as u32;
66
67                continue;
68            }
69
70            let len = ((max_x - min_x + 3) / 8) as usize;
71            let mut letters = vec![0u64; len];
72            for (p, _) in points.iter() {
73                if (p.x - min_x) % 8 >= 6 {
74                    // Point where there should be a 2-wide gap
75                    continue 'time;
76                }
77
78                letters[(p.x - min_x) as usize / 8] |=
79                    1 << (59 - ((p.x - min_x) % 8 + 6 * (p.y - min_y)));
80            }
81            break letters.into_iter().map(Self::ocr).collect::<String>();
82        };
83
84        Ok(Self { message, seconds })
85    }
86
87    fn ocr(letter: u64) -> char {
88        //   ##    #####    ####   ######  ######   ####   #    #     ###  #    #  #       #    #
89        //  #  #   #    #  #    #  #       #       #    #  #    #      #   #   #   #       ##   #
90        // #    #  #    #  #       #       #       #       #    #      #   #  #    #       ##   #
91        // #    #  #    #  #       #       #       #       #    #      #   # #     #       # #  #
92        // #    #  #####   #       #####   #####   #       ######      #   ##      #       # #  #
93        // ######  #    #  #       #       #       #  ###  #    #      #   ##      #       #  # #
94        // #    #  #    #  #       #       #       #    #  #    #      #   # #     #       #  # #
95        // #    #  #    #  #       #       #       #    #  #    #  #   #   #  #    #       #   ##
96        // #    #  #    #  #    #  #       #       #   ##  #    #  #   #   #   #   #       #   ##
97        // #    #  #####    ####   ######  #        ### #  #    #   ###    #    #  ######  #    #
98        //
99        // #####   #####   #    #  ######
100        // #    #  #    #  #    #       #
101        // #    #  #    #   #  #        #
102        // #    #  #    #   #  #       #
103        // #####   #####     ##       #
104        // #       #  #      ##      #
105        // #       #   #    #  #    #
106        // #       #   #    #  #   #
107        // #       #    #  #    #  #
108        // #       #    #  #    #  ######
109        match letter {
110            //000000111111222222333333444444555555666666777777888888999999
111            0b001100010010100001100001100001111111100001100001100001100001 => 'A',
112            0b111110100001100001100001111110100001100001100001100001111110 => 'B',
113            0b011110100001100000100000100000100000100000100000100001011110 => 'C',
114            0b111111100000100000100000111110100000100000100000100000111111 => 'E',
115            0b111111100000100000100000111110100000100000100000100000100000 => 'F',
116            0b011110100001100000100000100000100111100001100001100011011101 => 'G',
117            0b100001100001100001100001111111100001100001100001100001100001 => 'H',
118            0b000111000010000010000010000010000010000010100010100010011100 => 'J',
119            0b100001100010100100101000110000110000101000100100100010100001 => 'K',
120            0b100000100000100000100000100000100000100000100000100000111111 => 'L',
121            0b100001110001110001101001101001100101100101100011100011100001 => 'N',
122            0b111110100001100001100001111110100000100000100000100000100000 => 'P',
123            0b111110100001100001100001111110100100100010100010100001100001 => 'R',
124            0b100001100001010010010010001100001100010010010010100001100001 => 'X',
125            0b111111000001000001000010000100001000010000100000100000111111 => 'Z',
126            _ => Self::unknown_letter(letter),
127        }
128    }
129
130    #[cold]
131    fn unknown_letter(letter: u64) -> char {
132        let mut display = String::new();
133        for b in (0..60).rev() {
134            display.push(if letter & (1 << b) == 0 { ' ' } else { '#' });
135            if b % 6 == 0 {
136                display.push('\n');
137            }
138        }
139        panic!("unknown letter {letter:#062b}:\n{display}");
140    }
141
142    #[must_use]
143    pub fn part1(&self) -> &str {
144        &self.message
145    }
146
147    #[must_use]
148    pub fn part2(&self) -> u32 {
149        self.seconds
150    }
151}
152
153examples!(Day10 -> (&'static str, u32) []);
year2018/day10.rs

year2018/
day10.rs
