diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | 15/src/main.rs.bak | 181 | ||||
| -rw-r--r-- | 15/tests/main.rs | 2 | ||||
| -rw-r--r-- | 16/Cargo.toml | 11 | ||||
| -rw-r--r-- | 16/input | 1 | ||||
| -rw-r--r-- | 16/src/main.rs | 219 | ||||
| -rw-r--r-- | 16/tests/main.rs | 18 | ||||
| -rw-r--r-- | Cargo.lock | 8 | ||||
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | lib/src/error.rs | 2 |
10 files changed, 262 insertions, 182 deletions
diff --git a/.gitignore b/.gitignore index 31158d2..3c3194f 100644 --- a/.gitignore +++ b/.gitignore @@ -3,3 +3,4 @@ /result-* **/*.rs.bk *.swp +*.swo diff --git a/15/src/main.rs.bak b/15/src/main.rs.bak deleted file mode 100644 index 33f76e3..0000000 --- a/15/src/main.rs.bak +++ /dev/null @@ -1,181 +0,0 @@ -use advent_lib::prelude::*; - - -fn main() -> Result<()> { - let mut args = std::env::args(); - if args.len() != 2 { - eprintln!("Usage: advent input"); - } - let _ = args.next(); - let filename = args.next().unwrap(); - - let input = advent_lib::read_lines_file(&filename)?; - - let mut value_grid = Vec::new(); - let mut risk_grid: Vec<Vec<Option<i64>>> = Vec::new(); - for line in &input{ - let mut value_row = Vec::new(); - let mut risk_row = Vec::new(); - for c in line.chars() { - let value = c.to_digit(10).unwrap() as i64; - value_row.push(value); - risk_row.push(None); - } - value_grid.push(value_row); - risk_grid.push(risk_row); - } - - let height = value_grid.len(); - let width = value_grid[0].len(); - - /* - risk_grid[0][0] = Some(0); - find_path(0, 0, &value_grid, &mut risk_grid, false); - let risk = risk_grid[height - 1][width - 1].unwrap(); - println!("{}", risk); - */ - - let mut big_risk_grid = Vec::new(); - for _ in 0 .. height * 5 { - let mut big_risk_grid_row = Vec::new(); - for _ in 0 .. width * 5 { - big_risk_grid_row.push(None); - } - big_risk_grid.push(big_risk_grid_row); - } - big_risk_grid[0][0] = Some(0); - find_path(0, 0, &value_grid, &mut big_risk_grid, true); - let big_risk = big_risk_grid[height * 5 - 1][width * 5 - 1].unwrap(); - println!("{}", big_risk); - - Ok(()) -} - - -#[allow(dead_code)] -fn debug_risk_grid(risk_grid: &Vec<Vec<Option<i64>>>) { - for row in risk_grid { - for cell in row { - match cell { - None => { print!(" ."); } - Some(n) => { print!(" {}", n); } - } - } - println!(""); - } - println!(""); -} - - -fn find_path(x: usize, y: usize, value_grid: &Vec<Vec<i64>>, - risk_grid: &mut Vec<Vec<Option<i64>>>, repeat: bool) -{ - let mut height = value_grid.len(); - let mut width = value_grid[0].len(); - if repeat { - width *= 5; - height *= 5; - } - - let mut exploration_stack = Vec::new(); - exploration_stack.push((x, y)); - - let mut counter = 0; - - loop { - let (x, y) = match exploration_stack.pop() { - None => { return; } - Some(value) => { value } - }; - let risk_so_far = risk_grid[y][x].unwrap(); - counter += 1; - if counter % 100000 == 0 { - print!(" [{},{} {}]", x, y, risk_so_far); - } - - if x > 0 { - let value_left = get_value(x - 1, y, value_grid); - let new_risk_left = risk_so_far + value_left; - - let risk_left = risk_grid[y][x-1]; - let should_move = match risk_left { - None => true, - Some(prior_best_risk) => { - new_risk_left < prior_best_risk - } - }; - if should_move { - risk_grid[y][x-1] = Some(new_risk_left); - - exploration_stack.push((x - 1, y)); - } - } - - if y > 0 { - let value_up = get_value(x, y - 1, value_grid); - let new_risk_up = risk_so_far + value_up; - - let risk_up = risk_grid[y-1][x]; - let should_move = match risk_up { - None => true, - Some(prior_best_risk) => { - new_risk_up < prior_best_risk - } - }; - if should_move { - risk_grid[y-1][x] = Some(new_risk_up); - - exploration_stack.push((x, y - 1)); - } - } - - if x + 1 < width { - let value_right = get_value(x + 1, y, value_grid); - let new_risk_right = risk_so_far + value_right; - - let risk_right = risk_grid[y][x+1]; - let should_move = match risk_right { - None => true, - Some(prior_best_risk) => { - new_risk_right < prior_best_risk - } - }; - if should_move { - risk_grid[y][x+1] = Some(new_risk_right); - - exploration_stack.push((x + 1, y)); - } - } - - if y + 1 < height { - let value_down = get_value(x, y + 1, value_grid); - let new_risk_down = risk_so_far + value_down; - - let risk_down = risk_grid[y+1][x]; - let should_move = match risk_down { - None => true, - Some(prior_best_risk) => { - new_risk_down < prior_best_risk - } - }; - if should_move { - risk_grid[y+1][x] = Some(new_risk_down); - - exploration_stack.push((x, y + 1)); - } - } - } -} - - -fn get_value(x: usize, y: usize, value_grid: &Vec<Vec<i64>>) -> i64 { - let height = value_grid.len(); - let width = value_grid[0].len(); - - let tile_x = x / width; - let tile_y = y / height; - let increment: i64 = (tile_x + tile_y) as i64; - let raw_value = value_grid[y % height][x % width]; - (raw_value + increment - 1) % 9 + 1 -} - diff --git a/15/tests/main.rs b/15/tests/main.rs index 3e205b0..09dddae 100644 --- a/15/tests/main.rs +++ b/15/tests/main.rs @@ -5,7 +5,7 @@ use std::process::Command; #[test] fn personal_input() -> Result<(), Box<dyn std::error::Error>> { - let mut command = Command::cargo_bin("advent_14")?; + let mut command = Command::cargo_bin("advent_15")?; command.arg("input"); command.assert().success().stdout( diff --git a/16/Cargo.toml b/16/Cargo.toml new file mode 100644 index 0000000..a8b1866 --- /dev/null +++ b/16/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "advent_16" +version = "0.1.0" +authors = ["Irene Knapp <ireneista@gmail.com>"] +edition = "2018" + +[dependencies] +advent_lib = { path = "../lib" } + +[dev-dependencies] +assert_cmd = "0.10" diff --git a/16/input b/16/input new file mode 100644 index 0000000..019f19b --- /dev/null +++ b/16/input @@ -0,0 +1 @@ +220D790065B2745FF004672D99A34E5B33439D96CEC80373C0068663101A98C406A5E7395DC1804678BF25A4093BFBDB886CA6E11FDE6D93D16A100325E5597A118F6640600ACF7274E6A5829B00526C167F9C089F15973C4002AA4B22E800FDCFD72B9351359601300424B8C9A00BCBC8EE069802D2D0B945002AB2D7D583E3F00016B05E0E9802BA00B4F29CD4E961491CCB44C6008E80273C393C333F92020134B003530004221347F83A200D47F89913A66FB6620016E24A007853BE5E944297AB64E66D6669FCEA0112AE06009CAA57006A0200EC258FB0440010A8A716A321009DE200D44C8E31F00010887B146188803317A3FC5F30056C0150004321244E88C000874468A91D2291802B25EB875802B28D13550030056C0169FB5B7ECE2C6B2EF3296D6FD5F54858015B8D730BB24E32569049009BF801980803B05A3B41F1007625C1C821256D7C848025DE0040E5016717247E18001BAC37930E9FA6AE3B358B5D4A7A6EA200D4E463EA364EDE9F852FF1B9C8731869300BE684649F6446E584E61DE61CD4021998DB4C334E72B78BA49C126722B4E009C6295F879002093EF32A64C018ECDFAF605989D4BA7B396D9B0C200C9F0017C98C72FD2C8932B7EE0EA6ADB0F1006C8010E89B15A2A90021713610C202004263E46D82AC06498017C6E007901542C04F9A0128880449A8014403AA38014C030B08012C0269A8018E007A801620058003C64009810010722EC8010ECFFF9AAC32373F6583007A48CA587E55367227A40118C2AC004AE79FE77E28C007F4E42500D10096779D728EB1066B57F698C802139708B004A5C5E5C44C01698D490E800B584F09C8049593A6C66C017100721647E8E0200CC6985F11E634EA6008CB207002593785497652008065992443E7872714 diff --git a/16/src/main.rs b/16/src/main.rs new file mode 100644 index 0000000..f4f6253 --- /dev/null +++ b/16/src/main.rs @@ -0,0 +1,219 @@ +use advent_lib::prelude::*; + +#[derive(Debug)] +struct Packet { + version: u8, + type_id: u8, + content: Vec<u8>, + subpackets: Vec<Packet>, +} + + +fn main() -> Result<()> { + let mut args = std::env::args(); + if args.len() != 2 { + eprintln!("Usage: advent input"); + } + let _ = args.next(); + let filename = args.next().unwrap(); + + let input = advent_lib::read_lines_file(&filename)?; + + let mut bit_string: Vec<u8> = Vec::new(); + for c in input[0].chars() { + let value = c.to_digit(16).unwrap() as u8; + for i in 0 .. 4 { + let bit = (value >> (3 - i)) & 1; + bit_string.push(bit); + } + } + + let mut iter = bit_string.iter().peekable(); + let (version_total, _top_packet, result) = read_packet(&mut iter).unwrap(); + println!("{}", version_total); + println!("{}", result); + + Ok(()) +} + + +fn read_packet<'a>(iter: &mut impl Iterator<Item=&'a u8>) -> Result<(u64, Packet, u128)> +{ + let mut version_total: u64 = 0; + + let version = bits_to_u8(take_bits(iter, 3)?); + let type_id = bits_to_u8(take_bits(iter, 3)?); + + version_total += version as u64; + + if type_id == 4 { + let mut result = 0; + loop { + let bits = take_bits(iter, 5)?; + + let bits_value = bits_to_u128(bits[1..].to_vec()); + result = result << 4; + result += bits_value; + + if bits[0] == 0 { + break; + } + } + + Ok((version_total, Packet { + version, + type_id, + content: Vec::new(), + subpackets: Vec::new(), + }, result)) + } else { + let mut subpackets = Vec::new(); + let mut parameters = Vec::new(); + + let length_type_id = bits_to_u8(take_bits(iter, 1)?); + if length_type_id == 0 { + let length_in_bits = bits_to_u64(take_bits(iter, 15)?); + + let mut content_bits: Vec<u8> = Vec::new(); + for bit in iter.take(length_in_bits as usize) { + content_bits.push(*bit); + } + + let mut content_bits = content_bits.iter().peekable(); + + loop { + match read_packet(&mut content_bits) { + Err(_) => { + break; + } + Ok((sub_version_total, subpacket, value)) => { + version_total += sub_version_total; + subpackets.push(subpacket); + parameters.push(value); + } + } + } + } else { + let n_subpackets = bits_to_u64(take_bits(iter, 11)?); + + for _ in 0 .. n_subpackets { + match read_packet(iter) { + Err(_) => { + return Err(advent_lib::error::Error::Unspecified); + } + Ok((sub_version_total, subpacket, value)) => { + version_total += sub_version_total; + subpackets.push(subpacket); + parameters.push(value); + } + } + } + } + + let mut result = 0; + match type_id { + 0 => { + result = 0; + for parameter in ¶meters { + result += parameter; + } + } + 1 => { + result = 1; + for parameter in ¶meters { + result *= parameter; + } + } + 2 => { + result = parameters[0]; + for parameter in ¶meters { + if *parameter < result { + result = *parameter; + } + } + } + 3 => { + result = parameters[0]; + for parameter in ¶meters { + if *parameter > result { + result = *parameter; + } + } + } + 5 => { + result = if parameters[0] > parameters[1] { 1 } else { 0 }; + } + 6 => { + result = if parameters[0] < parameters[1] { 1 } else { 0 }; + } + 7 => { + result = if parameters[0] == parameters[1] { 1 } else { 0 }; + } + _ => { } + } + + Ok((version_total, Packet { + version, + type_id, + content: Vec::new(), + subpackets: subpackets, + }, result)) + } +} + + +fn take_bits<'a>(iter: &mut impl Iterator<Item=&'a u8>, count: usize) + -> Result<Vec<u8>> +{ + let mut result: Vec<u8> = Vec::new(); + + for _ in 0 .. count { + match iter.next() { + None => { + return Err(advent_lib::error::Error::Unspecified); + } + Some(bit) => { + result.push(*bit); + } + } + } + + Ok(result) +} + + +fn bits_to_u8(bits: Vec<u8>) -> u8 { + let mut result = 0; + + for bit in &bits { + result *= 2; + result += bit; + } + + result +} + + +fn bits_to_u64(bits: Vec<u8>) -> u64 { + let mut result = 0; + + for bit in &bits { + result *= 2; + result += *bit as u64; + } + + result +} + + +fn bits_to_u128(bits: Vec<u8>) -> u128 { + let mut result = 0; + + for bit in &bits { + result *= 2; + result += *bit as u128; + } + + result +} + diff --git a/16/tests/main.rs b/16/tests/main.rs new file mode 100644 index 0000000..ba7a189 --- /dev/null +++ b/16/tests/main.rs @@ -0,0 +1,18 @@ +use assert_cmd::prelude::*; +//use predicates::prelude::*; +use std::process::Command; + + +#[test] +fn personal_input() -> Result<(), Box<dyn std::error::Error>> { + let mut command = Command::cargo_bin("advent_16")?; + + command.arg("input"); + command.assert().success().stdout( + "989\n\ + 7936430475134\n"); + + + Ok(()) +} + diff --git a/Cargo.lock b/Cargo.lock index 751fe79..2c1fbd4 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -121,6 +121,14 @@ dependencies = [ ] [[package]] +name = "advent_16" +version = "0.1.0" +dependencies = [ + "advent_lib", + "assert_cmd", +] + +[[package]] name = "advent_lib" version = "0.1.0" dependencies = [ diff --git a/Cargo.toml b/Cargo.toml index d8cc993..4a97c58 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -16,4 +16,5 @@ members = [ "13", "14", "15", + "16", ] diff --git a/lib/src/error.rs b/lib/src/error.rs index 4f594b7..ccf01ee 100644 --- a/lib/src/error.rs +++ b/lib/src/error.rs @@ -2,6 +2,7 @@ pub enum Error { IO(std::io::Error), Parse, + Unspecified, } impl std::error::Error for Error { } @@ -11,6 +12,7 @@ impl std::fmt::Display for Error { match self { Error::IO(e) => e.fmt(f), Error::Parse => f.write_str("Parse error"), + Error::Unspecified => f.write_str("Unspecified error (bad luck!)"), } } } |