summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--Cargo.lock16
-rw-r--r--Cargo.toml1
-rw-r--r--inputs/day_19.txt1
-rw-r--r--src/bin/day_18.rs1
-rw-r--r--src/bin/day_19.rs105
5 files changed, 123 insertions, 1 deletions
diff --git a/Cargo.lock b/Cargo.lock
index 16321a7..02e042e 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -13,6 +13,7 @@ name = "aoc2019"
version = "0.1.0"
dependencies = [
"archery 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "cached 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)",
"derive_more 0.99.2 (registry+https://github.com/rust-lang/crates.io-index)",
"im 14.0.0 (registry+https://github.com/rust-lang/crates.io-index)",
"num 0.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
@@ -57,6 +58,14 @@ dependencies = [
]
[[package]]
+name = "cached"
+version = "0.11.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "once_cell 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
name = "cfg-if"
version = "0.1.10"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -257,6 +266,11 @@ dependencies = [
]
[[package]]
+name = "once_cell"
+version = "1.2.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
name = "proc-macro-error"
version = "0.2.6"
source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -465,6 +479,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
"checksum autocfg 0.1.7 (registry+https://github.com/rust-lang/crates.io-index)" = "1d49d90015b3c36167a20fe2810c5cd875ad504b39cff3d4eae7977e6b7c1cb2"
"checksum bitflags 1.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cf1de2fe8c75bc145a2f577add951f8134889b4795d47466a54a5c846d691693"
"checksum bitmaps 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "81e039a80914325b37fde728ef7693c212f0ac913d5599607d7b95a9484aae0b"
+"checksum cached 0.11.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7b052fd10f32987c3bd028d91ef86190b36fba5c8fccb5515d42083f061e6104"
"checksum cfg-if 0.1.10 (registry+https://github.com/rust-lang/crates.io-index)" = "4785bdd1c96b2a846b2bd7cc02e86b6b3dbf14e7e53446c4f54c92a361040822"
"checksum clap 2.33.0 (registry+https://github.com/rust-lang/crates.io-index)" = "5067f5bb2d80ef5d68b4c87db81601f0b75bca627bc2ef76b141d7b846a3c6d9"
"checksum crossbeam-deque 0.7.2 (registry+https://github.com/rust-lang/crates.io-index)" = "c3aa945d63861bfe624b55d153a39684da1e8c0bc8fba932f7ee3a3c16cea3ca"
@@ -487,6 +502,7 @@ source = "registry+https://github.com/rust-lang/crates.io-index"
"checksum num-rational 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "f2885278d5fe2adc2f75ced642d52d879bffaceb5a2e0b1d4309ffdfb239b454"
"checksum num-traits 0.2.10 (registry+https://github.com/rust-lang/crates.io-index)" = "d4c81ffc11c212fa327657cb19dd85eb7419e163b5b076bede2bdb5c974c07e4"
"checksum num_cpus 1.11.1 (registry+https://github.com/rust-lang/crates.io-index)" = "76dac5ed2a876980778b8b85f75a71b6cbf0db0b1232ee12f826bccb00d09d72"
+"checksum once_cell 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "891f486f630e5c5a4916c7e16c4b24a53e78c860b646e9f8e005e4f16847bfed"
"checksum proc-macro-error 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "aeccfe4d5d8ea175d5f0e4a2ad0637e0f4121d63bd99d356fb1f39ab2e7c6097"
"checksum proc-macro2 1.0.6 (registry+https://github.com/rust-lang/crates.io-index)" = "9c9e470a8dc4aeae2dee2f335e8f533e2d4b347e1434e5671afc49b054592f27"
"checksum quote 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "053a8c8bcc71fcce321828dc897a98ab9760bef03a4fc36693c231e5b3216cfe"
diff --git a/Cargo.toml b/Cargo.toml
index 0b84c43..a5c6e6a 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -12,6 +12,7 @@ rpds = "0.7.0"
archery = "0.3.0"
num = "0.2"
rayon = "1.3.0"
+cached = "0.11.0"
[profile.release]
debug = true
diff --git a/inputs/day_19.txt b/inputs/day_19.txt
new file mode 100644
index 0000000..e85881e
--- /dev/null
+++ b/inputs/day_19.txt
@@ -0,0 +1 @@
+109,424,203,1,21102,11,1,0,1106,0,282,21101,0,18,0,1106,0,259,1201,1,0,221,203,1,21102,1,31,0,1106,0,282,21101,0,38,0,1106,0,259,20102,1,23,2,21202,1,1,3,21101,1,0,1,21101,0,57,0,1105,1,303,2101,0,1,222,20101,0,221,3,21001,221,0,2,21102,1,259,1,21101,0,80,0,1105,1,225,21101,185,0,2,21102,91,1,0,1106,0,303,1202,1,1,223,21001,222,0,4,21102,259,1,3,21101,225,0,2,21102,1,225,1,21101,0,118,0,1106,0,225,20102,1,222,3,21102,1,131,2,21101,133,0,0,1106,0,303,21202,1,-1,1,22001,223,1,1,21101,148,0,0,1105,1,259,2101,0,1,223,21002,221,1,4,21002,222,1,3,21101,0,16,2,1001,132,-2,224,1002,224,2,224,1001,224,3,224,1002,132,-1,132,1,224,132,224,21001,224,1,1,21101,0,195,0,106,0,109,20207,1,223,2,20101,0,23,1,21102,1,-1,3,21101,0,214,0,1105,1,303,22101,1,1,1,204,1,99,0,0,0,0,109,5,1201,-4,0,249,22101,0,-3,1,22101,0,-2,2,21201,-1,0,3,21101,0,250,0,1106,0,225,21201,1,0,-4,109,-5,2106,0,0,109,3,22107,0,-2,-1,21202,-1,2,-1,21201,-1,-1,-1,22202,-1,-2,-2,109,-3,2106,0,0,109,3,21207,-2,0,-1,1206,-1,294,104,0,99,22102,1,-2,-2,109,-3,2105,1,0,109,5,22207,-3,-4,-1,1206,-1,346,22201,-4,-3,-4,21202,-3,-1,-1,22201,-4,-1,2,21202,2,-1,-1,22201,-4,-1,1,21201,-2,0,3,21101,343,0,0,1106,0,303,1105,1,415,22207,-2,-3,-1,1206,-1,387,22201,-3,-2,-3,21202,-2,-1,-1,22201,-3,-1,3,21202,3,-1,-1,22201,-3,-1,2,22101,0,-4,1,21102,384,1,0,1106,0,303,1105,1,415,21202,-4,-1,-4,22201,-4,-3,-4,22202,-3,-2,-2,22202,-2,-4,-4,22202,-3,-2,-3,21202,-4,-1,-2,22201,-3,-2,1,21201,1,0,-4,109,-5,2106,0,0
diff --git a/src/bin/day_18.rs b/src/bin/day_18.rs
index 8714e4f..34db7f9 100644
--- a/src/bin/day_18.rs
+++ b/src/bin/day_18.rs
@@ -1,4 +1,3 @@
-use rayon::prelude::*;
use rpds::rbt_set;
use rpds::vector;
use rpds::vector::Vector;
diff --git a/src/bin/day_19.rs b/src/bin/day_19.rs
new file mode 100644
index 0000000..d5ee7f2
--- /dev/null
+++ b/src/bin/day_19.rs
@@ -0,0 +1,105 @@
+use aoc2019::*;
+use cached::cached_key;
+use cached::UnboundCache;
+use rpds::list;
+use rpds::list::List;
+use rpds::vector;
+use rpds::vector::Vector;
+use std::collections::HashMap;
+use std::io;
+use std::io::prelude::*;
+use std::iter;
+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)])
+
+ }
+}