aoc/year2018/
day10.rs

1//! # The Stars Align
2use crate::util::grid::*;
3use crate::util::iter::*;
4use crate::util::parse::*;
5use crate::util::point::*;
6
7type Input = (String, i32);
8
9pub fn parse(input: &str) -> Input {
10    let (mut points, velocity): (Vec<_>, Vec<_>) = input
11        .iter_signed::<i32>()
12        .chunk::<4>()
13        .map(|[x, y, dx, dy]| (Point::new(x, y), Point::new(dx, dy)))
14        .unzip();
15
16    // Find two points traveling in opposite directions.
17    let up = velocity.iter().position(|v| v.y < 0).unwrap();
18    let down = velocity.iter().position(|v| v.y > 0).unwrap();
19
20    // Use relative velocity and position to find the time when they are 10 units apart.
21    let p = (points[up].y - points[down].y).abs();
22    let v = (velocity[up].y - velocity[down].y).abs();
23    let mut time = (p - 10) / v;
24
25    // Fast forward time.
26    tick(&mut points, &velocity, time);
27
28    // Message is 62 wide and 10 high (8 characters each 6 wide with 2 space gap between).
29    // Shrink one second at a time until area of points is exactly 620.
30    let mut area = size(&points);
31
32    while area > 620 {
33        tick(&mut points, &velocity, 1);
34        area = size(&points);
35        time += 1;
36    }
37
38    // Move top left corner of points to origin.
39    adjust(&mut points);
40
41    // Convert points to human readable string.
42    let mut grid = Grid::new(63, 10, '.');
43
44    (0..10).for_each(|y| grid[Point::new(0, y)] = '\n');
45    points.iter().for_each(|&p| grid[p + RIGHT] = '#');
46
47    let message = grid.bytes.iter().collect();
48
49    // Return answer
50    (message, time)
51}
52
53pub fn part1(input: &Input) -> &str {
54    &input.0
55}
56
57pub fn part2(input: &Input) -> i32 {
58    input.1
59}
60
61fn bounding_box(points: &[Point]) -> (i32, i32, i32, i32) {
62    points.iter().fold(
63        (i32::MAX, i32::MIN, i32::MAX, i32::MIN),
64        |(min_x, max_x, min_y, max_y), &p| {
65            (min_x.min(p.x), max_x.max(p.x), min_y.min(p.y), max_y.max(p.y))
66        },
67    )
68}
69
70fn size(points: &[Point]) -> i32 {
71    let (min_x, max_x, min_y, max_y) = bounding_box(points);
72    (max_x - min_x + 1) * (max_y - min_y + 1)
73}
74
75fn adjust(points: &mut [Point]) {
76    let (min_x, _, min_y, _) = bounding_box(points);
77    let top_left = Point::new(min_x, min_y);
78    points.iter_mut().for_each(|p| *p -= top_left);
79}
80
81fn tick(points: &mut [Point], velocity: &[Point], time: i32) {
82    for (p, &v) in points.iter_mut().zip(velocity) {
83        *p += v * time;
84    }
85}