summaryrefslogtreecommitdiff
path: root/2019/src/bin/day_19.rs
blob: 73c8374348877f7548afd2d748aa6c38b685c933 (plain)
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
use aoc2019::*;
use cached::cached_key;
use cached::UnboundCache;
use rpds::list;
use rpds::list::List;
use rpds::vector;
use std::io;
use std::io::prelude::*;
use std::process;
use structopt::StructOpt;

#[derive(Debug, StructOpt)]
#[structopt(name = "Day 19: Tractor Beam")]
/// Finds the effective area of a tractor beam in an n x n square, and
/// how far away you need to be to capture Santa's ship.
///
/// See https://adventofcode.com/2019/day/19 for details.
struct Opt {
    /// The size for a diagnostics scan.
    #[structopt(long = "diagnostics-size")]
    diagnostics_size: Option<usize>,
    /// The size of Santa's ship
    #[structopt(long = "ship-size")]
    ship_size: Option<usize>,
}

fn main() {
    let stdin = io::stdin();
    let opt = Opt::from_args();

    let program: IntcodeProgram = stdin
        .lock()
        .split(b',')
        .map(|x| exit_on_failed_assertion(x, "Error reading input"))
        .map(|x| exit_on_failed_assertion(String::from_utf8(x), "Input was not valid UTF-8"))
        .map(|x| exit_on_failed_assertion(x.trim().parse::<Intcode>(), "Invalid number"))
        .collect::<IntcodeProgram>();

    if let Some(size) = opt.diagnostics_size {
        println!("{}", count_active_in_area(program.clone(), 0, 0, size));
    }
    if let Some(size) = opt.ship_size {
        println!("{:?}", find_closest_ship_space(program, size))
    }
}

fn exit_on_failed_assertion<A, E: std::error::Error>(data: Result<A, E>, message: &str) -> A {
    match data {
        Ok(data) => data,
        Err(e) => {
            eprintln!("{}: {}", message, e);
            process::exit(1);
        }
    }
}

fn count_active_in_area(program: IntcodeProgram, left: usize, top: usize, size: usize) -> usize {
    (left..left + size)
        .flat_map(|x| (top..top + size).map(move |y| (x, y)))
        .filter(|(x, y)| tractor_beam_is_active(program.clone(), *x, *y))
        .count()
}

fn area_is_all_full(program: IntcodeProgram, left: usize, top: usize, size: usize) -> bool {
    // This check with a grid that's aligned to 10 gives an early exit
    // for most, that will have the program executions shared. This
    // makes the memoized tractor function more effective at cutting
    // down on execution, even though you need to do the whole lot
    // again to verify if this passes.
    (left..left + size)
        .flat_map(|x| (top..top + size).map(move |y| (x, y)))
        .filter(|(x, y)| x % 10 == 0 && y % 10 == 0)
        .all(|(x, y)| tractor_beam_is_active(program.clone(), x, y))
        && (left..left + size)
            .flat_map(|x| (top..top + size).map(move |y| (x, y)))
            .all(|(x, y)| tractor_beam_is_active(program.clone(), x, y))
}

fn find_closest_ship_space(program: IntcodeProgram, size: usize) -> (usize, usize) {
    (0..)
        .flat_map(|radius| {
            (0..radius)
                .flat_map(move |x| (0..radius).map(move |y| (x, y)))
                .filter(move |(x, y)| {
                    (radius - 1) * (radius - 1) < x * x + y * y && x * x + y * y <= radius * radius
                })
        })
        .find(|(x, y)| area_is_all_full(program.clone(), *x, *y, size))
        .unwrap()
}

cached_key! {
    TRACTOR_BEAM_IS_ACTIVE: UnboundCache<(usize, usize), bool> = UnboundCache::new();
    Key = { (x, y) };
    fn tractor_beam_is_active(program: IntcodeProgram, x: usize, y: usize) -> bool = {
        program
            .with_input(list![Intcode::from(x), Intcode::from(y)])
            .execute()
            == Ok(vector![Intcode::from(1)])

    }
}