diff options
author | Jesse Luehrs <doy@tozt.net> | 2021-12-23 03:39:41 -0500 |
---|---|---|
committer | Jesse Luehrs <doy@tozt.net> | 2021-12-23 03:39:41 -0500 |
commit | 01197254cc1283ecdd44eac84975925919afd235 (patch) | |
tree | d35f1d668eaad7e700d1808f41c1e87f48b62023 | |
parent | 19c9b9511a03467ae968a41be7f9ba607cb1b771 (diff) | |
download | advent-of-code-01197254cc1283ecdd44eac84975925919afd235.tar.gz advent-of-code-01197254cc1283ecdd44eac84975925919afd235.zip |
day 23
-rw-r--r-- | data/2021/23.txt | 5 | ||||
-rw-r--r-- | examples/2021_23_generate_connectivity.rs | 122 | ||||
-rw-r--r-- | src/2021/23/mod.rs | 1762 | ||||
-rw-r--r-- | src/2021/mod.rs | 4 |
4 files changed, 1893 insertions, 0 deletions
diff --git a/data/2021/23.txt b/data/2021/23.txt new file mode 100644 index 0000000..3d20443 --- /dev/null +++ b/data/2021/23.txt @@ -0,0 +1,5 @@ +############# +#...........# +###B#B#D#D### + #C#A#A#C# + ######### diff --git a/examples/2021_23_generate_connectivity.rs b/examples/2021_23_generate_connectivity.rs new file mode 100644 index 0000000..6f02da6 --- /dev/null +++ b/examples/2021_23_generate_connectivity.rs @@ -0,0 +1,122 @@ +// ############# +// #abcdefghijk# +// ###l#m#n#o### +// #p#q#r#s# +// ######### +static NEIGHBORS1: &[&[usize]] = &[ + &[1], + &[0, 2], + &[1, 3, 11], + &[2, 4], + &[3, 5, 12], + &[4, 6], + &[5, 7, 13], + &[6, 8], + &[7, 9, 14], + &[8, 10], + &[9], + &[2, 15], + &[4, 16], + &[6, 17], + &[8, 18], + &[11], + &[12], + &[13], + &[14], +]; + +// ############# +// #abcdefghijk# +// ###l#m#n#o### +// #p#q#r#s# +// #t#u#v#w# +// #x#y#z#!# +// ######### +static NEIGHBORS2: &[&[usize]] = &[ + &[1], + &[0, 2], + &[1, 3, 11], + &[2, 4], + &[3, 5, 12], + &[4, 6], + &[5, 7, 13], + &[6, 8], + &[7, 9, 14], + &[8, 10], + &[9], + &[2, 15], + &[4, 16], + &[6, 17], + &[8, 18], + &[11, 19], + &[12, 20], + &[13, 21], + &[14, 22], + &[15, 23], + &[16, 24], + &[17, 25], + &[18, 26], + &[19], + &[20], + &[21], + &[22], +]; + +fn path_rec( + neighbors: &[&[usize]], + from: usize, + to: usize, + path: &mut Vec<usize>, +) -> bool { + if from == to { + return true; + } + for neighbor in neighbors[from] { + if path.contains(neighbor) { + continue; + } + path.push(*neighbor); + if path_rec(neighbors, *neighbor, to, path) { + return true; + } + path.pop(); + } + false +} + +fn path(neighbors: &[&[usize]], from: usize, to: usize) -> Vec<usize> { + let mut path = vec![from]; + if !path_rec(neighbors, from, to, &mut path) { + panic!("no path found from {} to {}", from, to); + } + path.remove(0); + path +} + +fn main() { + println!("static CONNECTIVITY1: &[&[&[usize]]] = &["); + for from in 0..19 { + println!(" &["); + for to in 0..19 { + let path = path(NEIGHBORS1, from, to); + let path_strs: Vec<_> = + path.iter().map(|i| i.to_string()).collect(); + println!(" &[{}],", path_strs.join(", ")); + } + println!(" ],"); + } + println!("];"); + println!(); + println!("static CONNECTIVITY2: &[&[&[usize]]] = &["); + for from in 0..27 { + println!(" &["); + for to in 0..27 { + let path = path(NEIGHBORS2, from, to); + let path_strs: Vec<_> = + path.iter().map(|i| i.to_string()).collect(); + println!(" &[{}],", path_strs.join(", ")); + } + println!(" ],"); + } + println!("];"); +} diff --git a/src/2021/23/mod.rs b/src/2021/23/mod.rs new file mode 100644 index 0000000..f5b64a0 --- /dev/null +++ b/src/2021/23/mod.rs @@ -0,0 +1,1762 @@ +use crate::prelude::*; + +static CONNECTIVITY1: &[&[&[usize]]] = &[ + &[ + &[], + &[1], + &[1, 2], + &[1, 2, 3], + &[1, 2, 3, 4], + &[1, 2, 3, 4, 5], + &[1, 2, 3, 4, 5, 6], + &[1, 2, 3, 4, 5, 6, 7], + &[1, 2, 3, 4, 5, 6, 7, 8], + &[1, 2, 3, 4, 5, 6, 7, 8, 9], + &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[1, 2, 11], + &[1, 2, 3, 4, 12], + &[1, 2, 3, 4, 5, 6, 13], + &[1, 2, 3, 4, 5, 6, 7, 8, 14], + &[1, 2, 11, 15], + &[1, 2, 3, 4, 12, 16], + &[1, 2, 3, 4, 5, 6, 13, 17], + &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[0], + &[], + &[2], + &[2, 3], + &[2, 3, 4], + &[2, 3, 4, 5], + &[2, 3, 4, 5, 6], + &[2, 3, 4, 5, 6, 7], + &[2, 3, 4, 5, 6, 7, 8], + &[2, 3, 4, 5, 6, 7, 8, 9], + &[2, 3, 4, 5, 6, 7, 8, 9, 10], + &[2, 11], + &[2, 3, 4, 12], + &[2, 3, 4, 5, 6, 13], + &[2, 3, 4, 5, 6, 7, 8, 14], + &[2, 11, 15], + &[2, 3, 4, 12, 16], + &[2, 3, 4, 5, 6, 13, 17], + &[2, 3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[1, 0], + &[1], + &[], + &[3], + &[3, 4], + &[3, 4, 5], + &[3, 4, 5, 6], + &[3, 4, 5, 6, 7], + &[3, 4, 5, 6, 7, 8], + &[3, 4, 5, 6, 7, 8, 9], + &[3, 4, 5, 6, 7, 8, 9, 10], + &[11], + &[3, 4, 12], + &[3, 4, 5, 6, 13], + &[3, 4, 5, 6, 7, 8, 14], + &[11, 15], + &[3, 4, 12, 16], + &[3, 4, 5, 6, 13, 17], + &[3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[2, 1, 0], + &[2, 1], + &[2], + &[], + &[4], + &[4, 5], + &[4, 5, 6], + &[4, 5, 6, 7], + &[4, 5, 6, 7, 8], + &[4, 5, 6, 7, 8, 9], + &[4, 5, 6, 7, 8, 9, 10], + &[2, 11], + &[4, 12], + &[4, 5, 6, 13], + &[4, 5, 6, 7, 8, 14], + &[2, 11, 15], + &[4, 12, 16], + &[4, 5, 6, 13, 17], + &[4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[3, 2, 1, 0], + &[3, 2, 1], + &[3, 2], + &[3], + &[], + &[5], + &[5, 6], + &[5, 6, 7], + &[5, 6, 7, 8], + &[5, 6, 7, 8, 9], + &[5, 6, 7, 8, 9, 10], + &[3, 2, 11], + &[12], + &[5, 6, 13], + &[5, 6, 7, 8, 14], + &[3, 2, 11, 15], + &[12, 16], + &[5, 6, 13, 17], + &[5, 6, 7, 8, 14, 18], + ], + &[ + &[4, 3, 2, 1, 0], + &[4, 3, 2, 1], + &[4, 3, 2], + &[4, 3], + &[4], + &[], + &[6], + &[6, 7], + &[6, 7, 8], + &[6, 7, 8, 9], + &[6, 7, 8, 9, 10], + &[4, 3, 2, 11], + &[4, 12], + &[6, 13], + &[6, 7, 8, 14], + &[4, 3, 2, 11, 15], + &[4, 12, 16], + &[6, 13, 17], + &[6, 7, 8, 14, 18], + ], + &[ + &[5, 4, 3, 2, 1, 0], + &[5, 4, 3, 2, 1], + &[5, 4, 3, 2], + &[5, 4, 3], + &[5, 4], + &[5], + &[], + &[7], + &[7, 8], + &[7, 8, 9], + &[7, 8, 9, 10], + &[5, 4, 3, 2, 11], + &[5, 4, 12], + &[13], + &[7, 8, 14], + &[5, 4, 3, 2, 11, 15], + &[5, 4, 12, 16], + &[13, 17], + &[7, 8, 14, 18], + ], + &[ + &[6, 5, 4, 3, 2, 1, 0], + &[6, 5, 4, 3, 2, 1], + &[6, 5, 4, 3, 2], + &[6, 5, 4, 3], + &[6, 5, 4], + &[6, 5], + &[6], + &[], + &[8], + &[8, 9], + &[8, 9, 10], + &[6, 5, 4, 3, 2, 11], + &[6, 5, 4, 12], + &[6, 13], + &[8, 14], + &[6, 5, 4, 3, 2, 11, 15], + &[6, 5, 4, 12, 16], + &[6, 13, 17], + &[8, 14, 18], + ], + &[ + &[7, 6, 5, 4, 3, 2, 1, 0], + &[7, 6, 5, 4, 3, 2, 1], + &[7, 6, 5, 4, 3, 2], + &[7, 6, 5, 4, 3], + &[7, 6, 5, 4], + &[7, 6, 5], + &[7, 6], + &[7], + &[], + &[9], + &[9, 10], + &[7, 6, 5, 4, 3, 2, 11], + &[7, 6, 5, 4, 12], + &[7, 6, 13], + &[14], + &[7, 6, 5, 4, 3, 2, 11, 15], + &[7, 6, 5, 4, 12, 16], + &[7, 6, 13, 17], + &[14, 18], + ], + &[ + &[8, 7, 6, 5, 4, 3, 2, 1, 0], + &[8, 7, 6, 5, 4, 3, 2, 1], + &[8, 7, 6, 5, 4, 3, 2], + &[8, 7, 6, 5, 4, 3], + &[8, 7, 6, 5, 4], + &[8, 7, 6, 5], + &[8, 7, 6], + &[8, 7], + &[8], + &[], + &[10], + &[8, 7, 6, 5, 4, 3, 2, 11], + &[8, 7, 6, 5, 4, 12], + &[8, 7, 6, 13], + &[8, 14], + &[8, 7, 6, 5, 4, 3, 2, 11, 15], + &[8, 7, 6, 5, 4, 12, 16], + &[8, 7, 6, 13, 17], + &[8, 14, 18], + ], + &[ + &[9, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[9, 8, 7, 6, 5, 4, 3, 2, 1], + &[9, 8, 7, 6, 5, 4, 3, 2], + &[9, 8, 7, 6, 5, 4, 3], + &[9, 8, 7, 6, 5, 4], + &[9, 8, 7, 6, 5], + &[9, 8, 7, 6], + &[9, 8, 7], + &[9, 8], + &[9], + &[], + &[9, 8, 7, 6, 5, 4, 3, 2, 11], + &[9, 8, 7, 6, 5, 4, 12], + &[9, 8, 7, 6, 13], + &[9, 8, 14], + &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[9, 8, 7, 6, 5, 4, 12, 16], + &[9, 8, 7, 6, 13, 17], + &[9, 8, 14, 18], + ], + &[ + &[2, 1, 0], + &[2, 1], + &[2], + &[2, 3], + &[2, 3, 4], + &[2, 3, 4, 5], + &[2, 3, 4, 5, 6], + &[2, 3, 4, 5, 6, 7], + &[2, 3, 4, 5, 6, 7, 8], + &[2, 3, 4, 5, 6, 7, 8, 9], + &[2, 3, 4, 5, 6, 7, 8, 9, 10], + &[], + &[2, 3, 4, 12], + &[2, 3, 4, 5, 6, 13], + &[2, 3, 4, 5, 6, 7, 8, 14], + &[15], + &[2, 3, 4, 12, 16], + &[2, 3, 4, 5, 6, 13, 17], + &[2, 3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[4, 3, 2, 1, 0], + &[4, 3, 2, 1], + &[4, 3, 2], + &[4, 3], + &[4], + &[4, 5], + &[4, 5, 6], + &[4, 5, 6, 7], + &[4, 5, 6, 7, 8], + &[4, 5, 6, 7, 8, 9], + &[4, 5, 6, 7, 8, 9, 10], + &[4, 3, 2, 11], + &[], + &[4, 5, 6, 13], + &[4, 5, 6, 7, 8, 14], + &[4, 3, 2, 11, 15], + &[16], + &[4, 5, 6, 13, 17], + &[4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[6, 5, 4, 3, 2, 1, 0], + &[6, 5, 4, 3, 2, 1], + &[6, 5, 4, 3, 2], + &[6, 5, 4, 3], + &[6, 5, 4], + &[6, 5], + &[6], + &[6, 7], + &[6, 7, 8], + &[6, 7, 8, 9], + &[6, 7, 8, 9, 10], + &[6, 5, 4, 3, 2, 11], + &[6, 5, 4, 12], + &[], + &[6, 7, 8, 14], + &[6, 5, 4, 3, 2, 11, 15], + &[6, 5, 4, 12, 16], + &[17], + &[6, 7, 8, 14, 18], + ], + &[ + &[8, 7, 6, 5, 4, 3, 2, 1, 0], + &[8, 7, 6, 5, 4, 3, 2, 1], + &[8, 7, 6, 5, 4, 3, 2], + &[8, 7, 6, 5, 4, 3], + &[8, 7, 6, 5, 4], + &[8, 7, 6, 5], + &[8, 7, 6], + &[8, 7], + &[8], + &[8, 9], + &[8, 9, 10], + &[8, 7, 6, 5, 4, 3, 2, 11], + &[8, 7, 6, 5, 4, 12], + &[8, 7, 6, 13], + &[], + &[8, 7, 6, 5, 4, 3, 2, 11, 15], + &[8, 7, 6, 5, 4, 12, 16], + &[8, 7, 6, 13, 17], + &[18], + ], + &[ + &[11, 2, 1, 0], + &[11, 2, 1], + &[11, 2], + &[11, 2, 3], + &[11, 2, 3, 4], + &[11, 2, 3, 4, 5], + &[11, 2, 3, 4, 5, 6], + &[11, 2, 3, 4, 5, 6, 7], + &[11, 2, 3, 4, 5, 6, 7, 8], + &[11, 2, 3, 4, 5, 6, 7, 8, 9], + &[11, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[11], + &[11, 2, 3, 4, 12], + &[11, 2, 3, 4, 5, 6, 13], + &[11, 2, 3, 4, 5, 6, 7, 8, 14], + &[], + &[11, 2, 3, 4, 12, 16], + &[11, 2, 3, 4, 5, 6, 13, 17], + &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[12, 4, 3, 2, 1, 0], + &[12, 4, 3, 2, 1], + &[12, 4, 3, 2], + &[12, 4, 3], + &[12, 4], + &[12, 4, 5], + &[12, 4, 5, 6], + &[12, 4, 5, 6, 7], + &[12, 4, 5, 6, 7, 8], + &[12, 4, 5, 6, 7, 8, 9], + &[12, 4, 5, 6, 7, 8, 9, 10], + &[12, 4, 3, 2, 11], + &[12], + &[12, 4, 5, 6, 13], + &[12, 4, 5, 6, 7, 8, 14], + &[12, 4, 3, 2, 11, 15], + &[], + &[12, 4, 5, 6, 13, 17], + &[12, 4, 5, 6, 7, 8, 14, 18], + ], + &[ + &[13, 6, 5, 4, 3, 2, 1, 0], + &[13, 6, 5, 4, 3, 2, 1], + &[13, 6, 5, 4, 3, 2], + &[13, 6, 5, 4, 3], + &[13, 6, 5, 4], + &[13, 6, 5], + &[13, 6], + &[13, 6, 7], + &[13, 6, 7, 8], + &[13, 6, 7, 8, 9], + &[13, 6, 7, 8, 9, 10], + &[13, 6, 5, 4, 3, 2, 11], + &[13, 6, 5, 4, 12], + &[13], + &[13, 6, 7, 8, 14], + &[13, 6, 5, 4, 3, 2, 11, 15], + &[13, 6, 5, 4, 12, 16], + &[], + &[13, 6, 7, 8, 14, 18], + ], + &[ + &[14, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[14, 8, 7, 6, 5, 4, 3, 2, 1], + &[14, 8, 7, 6, 5, 4, 3, 2], + &[14, 8, 7, 6, 5, 4, 3], + &[14, 8, 7, 6, 5, 4], + &[14, 8, 7, 6, 5], + &[14, 8, 7, 6], + &[14, 8, 7], + &[14, 8], + &[14, 8, 9], + &[14, 8, 9, 10], + &[14, 8, 7, 6, 5, 4, 3, 2, 11], + &[14, 8, 7, 6, 5, 4, 12], + &[14, 8, 7, 6, 13], + &[14], + &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[14, 8, 7, 6, 5, 4, 12, 16], + &[14, 8, 7, 6, 13, 17], + &[], + ], +]; + +static CONNECTIVITY2: &[&[&[usize]]] = &[ + &[ + &[], + &[1], + &[1, 2], + &[1, 2, 3], + &[1, 2, 3, 4], + &[1, 2, 3, 4, 5], + &[1, 2, 3, 4, 5, 6], + &[1, 2, 3, 4, 5, 6, 7], + &[1, 2, 3, 4, 5, 6, 7, 8], + &[1, 2, 3, 4, 5, 6, 7, 8, 9], + &[1, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[1, 2, 11], + &[1, 2, 3, 4, 12], + &[1, 2, 3, 4, 5, 6, 13], + &[1, 2, 3, 4, 5, 6, 7, 8, 14], + &[1, 2, 11, 15], + &[1, 2, 3, 4, 12, 16], + &[1, 2, 3, 4, 5, 6, 13, 17], + &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18], + &[1, 2, 11, 15, 19], + &[1, 2, 3, 4, 12, 16, 20], + &[1, 2, 3, 4, 5, 6, 13, 17, 21], + &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[1, 2, 11, 15, 19, 23], + &[1, 2, 3, 4, 12, 16, 20, 24], + &[1, 2, 3, 4, 5, 6, 13, 17, 21, 25], + &[1, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[0], + &[], + &[2], + &[2, 3], + &[2, 3, 4], + &[2, 3, 4, 5], + &[2, 3, 4, 5, 6], + &[2, 3, 4, 5, 6, 7], + &[2, 3, 4, 5, 6, 7, 8], + &[2, 3, 4, 5, 6, 7, 8, 9], + &[2, 3, 4, 5, 6, 7, 8, 9, 10], + &[2, 11], + &[2, 3, 4, 12], + &[2, 3, 4, 5, 6, 13], + &[2, 3, 4, 5, 6, 7, 8, 14], + &[2, 11, 15], + &[2, 3, 4, 12, 16], + &[2, 3, 4, 5, 6, 13, 17], + &[2, 3, 4, 5, 6, 7, 8, 14, 18], + &[2, 11, 15, 19], + &[2, 3, 4, 12, 16, 20], + &[2, 3, 4, 5, 6, 13, 17, 21], + &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[2, 11, 15, 19, 23], + &[2, 3, 4, 12, 16, 20, 24], + &[2, 3, 4, 5, 6, 13, 17, 21, 25], + &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[1, 0], + &[1], + &[], + &[3], + &[3, 4], + &[3, 4, 5], + &[3, 4, 5, 6], + &[3, 4, 5, 6, 7], + &[3, 4, 5, 6, 7, 8], + &[3, 4, 5, 6, 7, 8, 9], + &[3, 4, 5, 6, 7, 8, 9, 10], + &[11], + &[3, 4, 12], + &[3, 4, 5, 6, 13], + &[3, 4, 5, 6, 7, 8, 14], + &[11, 15], + &[3, 4, 12, 16], + &[3, 4, 5, 6, 13, 17], + &[3, 4, 5, 6, 7, 8, 14, 18], + &[11, 15, 19], + &[3, 4, 12, 16, 20], + &[3, 4, 5, 6, 13, 17, 21], + &[3, 4, 5, 6, 7, 8, 14, 18, 22], + &[11, 15, 19, 23], + &[3, 4, 12, 16, 20, 24], + &[3, 4, 5, 6, 13, 17, 21, 25], + &[3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[2, 1, 0], + &[2, 1], + &[2], + &[], + &[4], + &[4, 5], + &[4, 5, 6], + &[4, 5, 6, 7], + &[4, 5, 6, 7, 8], + &[4, 5, 6, 7, 8, 9], + &[4, 5, 6, 7, 8, 9, 10], + &[2, 11], + &[4, 12], + &[4, 5, 6, 13], + &[4, 5, 6, 7, 8, 14], + &[2, 11, 15], + &[4, 12, 16], + &[4, 5, 6, 13, 17], + &[4, 5, 6, 7, 8, 14, 18], + &[2, 11, 15, 19], + &[4, 12, 16, 20], + &[4, 5, 6, 13, 17, 21], + &[4, 5, 6, 7, 8, 14, 18, 22], + &[2, 11, 15, 19, 23], + &[4, 12, 16, 20, 24], + &[4, 5, 6, 13, 17, 21, 25], + &[4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[3, 2, 1, 0], + &[3, 2, 1], + &[3, 2], + &[3], + &[], + &[5], + &[5, 6], + &[5, 6, 7], + &[5, 6, 7, 8], + &[5, 6, 7, 8, 9], + &[5, 6, 7, 8, 9, 10], + &[3, 2, 11], + &[12], + &[5, 6, 13], + &[5, 6, 7, 8, 14], + &[3, 2, 11, 15], + &[12, 16], + &[5, 6, 13, 17], + &[5, 6, 7, 8, 14, 18], + &[3, 2, 11, 15, 19], + &[12, 16, 20], + &[5, 6, 13, 17, 21], + &[5, 6, 7, 8, 14, 18, 22], + &[3, 2, 11, 15, 19, 23], + &[12, 16, 20, 24], + &[5, 6, 13, 17, 21, 25], + &[5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[4, 3, 2, 1, 0], + &[4, 3, 2, 1], + &[4, 3, 2], + &[4, 3], + &[4], + &[], + &[6], + &[6, 7], + &[6, 7, 8], + &[6, 7, 8, 9], + &[6, 7, 8, 9, 10], + &[4, 3, 2, 11], + &[4, 12], + &[6, 13], + &[6, 7, 8, 14], + &[4, 3, 2, 11, 15], + &[4, 12, 16], + &[6, 13, 17], + &[6, 7, 8, 14, 18], + &[4, 3, 2, 11, 15, 19], + &[4, 12, 16, 20], + &[6, 13, 17, 21], + &[6, 7, 8, 14, 18, 22], + &[4, 3, 2, 11, 15, 19, 23], + &[4, 12, 16, 20, 24], + &[6, 13, 17, 21, 25], + &[6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[5, 4, 3, 2, 1, 0], + &[5, 4, 3, 2, 1], + &[5, 4, 3, 2], + &[5, 4, 3], + &[5, 4], + &[5], + &[], + &[7], + &[7, 8], + &[7, 8, 9], + &[7, 8, 9, 10], + &[5, 4, 3, 2, 11], + &[5, 4, 12], + &[13], + &[7, 8, 14], + &[5, 4, 3, 2, 11, 15], + &[5, 4, 12, 16], + &[13, 17], + &[7, 8, 14, 18], + &[5, 4, 3, 2, 11, 15, 19], + &[5, 4, 12, 16, 20], + &[13, 17, 21], + &[7, 8, 14, 18, 22], + &[5, 4, 3, 2, 11, 15, 19, 23], + &[5, 4, 12, 16, 20, 24], + &[13, 17, 21, 25], + &[7, 8, 14, 18, 22, 26], + ], + &[ + &[6, 5, 4, 3, 2, 1, 0], + &[6, 5, 4, 3, 2, 1], + &[6, 5, 4, 3, 2], + &[6, 5, 4, 3], + &[6, 5, 4], + &[6, 5], + &[6], + &[], + &[8], + &[8, 9], + &[8, 9, 10], + &[6, 5, 4, 3, 2, 11], + &[6, 5, 4, 12], + &[6, 13], + &[8, 14], + &[6, 5, 4, 3, 2, 11, 15], + &[6, 5, 4, 12, 16], + &[6, 13, 17], + &[8, 14, 18], + &[6, 5, 4, 3, 2, 11, 15, 19], + &[6, 5, 4, 12, 16, 20], + &[6, 13, 17, 21], + &[8, 14, 18, 22], + &[6, 5, 4, 3, 2, 11, 15, 19, 23], + &[6, 5, 4, 12, 16, 20, 24], + &[6, 13, 17, 21, 25], + &[8, 14, 18, 22, 26], + ], + &[ + &[7, 6, 5, 4, 3, 2, 1, 0], + &[7, 6, 5, 4, 3, 2, 1], + &[7, 6, 5, 4, 3, 2], + &[7, 6, 5, 4, 3], + &[7, 6, 5, 4], + &[7, 6, 5], + &[7, 6], + &[7], + &[], + &[9], + &[9, 10], + &[7, 6, 5, 4, 3, 2, 11], + &[7, 6, 5, 4, 12], + &[7, 6, 13], + &[14], + &[7, 6, 5, 4, 3, 2, 11, 15], + &[7, 6, 5, 4, 12, 16], + &[7, 6, 13, 17], + &[14, 18], + &[7, 6, 5, 4, 3, 2, 11, 15, 19], + &[7, 6, 5, 4, 12, 16, 20], + &[7, 6, 13, 17, 21], + &[14, 18, 22], + &[7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[7, 6, 5, 4, 12, 16, 20, 24], + &[7, 6, 13, 17, 21, 25], + &[14, 18, 22, 26], + ], + &[ + &[8, 7, 6, 5, 4, 3, 2, 1, 0], + &[8, 7, 6, 5, 4, 3, 2, 1], + &[8, 7, 6, 5, 4, 3, 2], + &[8, 7, 6, 5, 4, 3], + &[8, 7, 6, 5, 4], + &[8, 7, 6, 5], + &[8, 7, 6], + &[8, 7], + &[8], + &[], + &[10], + &[8, 7, 6, 5, 4, 3, 2, 11], + &[8, 7, 6, 5, 4, 12], + &[8, 7, 6, 13], + &[8, 14], + &[8, 7, 6, 5, 4, 3, 2, 11, 15], + &[8, 7, 6, 5, 4, 12, 16], + &[8, 7, 6, 13, 17], + &[8, 14, 18], + &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[8, 7, 6, 5, 4, 12, 16, 20], + &[8, 7, 6, 13, 17, 21], + &[8, 14, 18, 22], + &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[8, 7, 6, 5, 4, 12, 16, 20, 24], + &[8, 7, 6, 13, 17, 21, 25], + &[8, 14, 18, 22, 26], + ], + &[ + &[9, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[9, 8, 7, 6, 5, 4, 3, 2, 1], + &[9, 8, 7, 6, 5, 4, 3, 2], + &[9, 8, 7, 6, 5, 4, 3], + &[9, 8, 7, 6, 5, 4], + &[9, 8, 7, 6, 5], + &[9, 8, 7, 6], + &[9, 8, 7], + &[9, 8], + &[9], + &[], + &[9, 8, 7, 6, 5, 4, 3, 2, 11], + &[9, 8, 7, 6, 5, 4, 12], + &[9, 8, 7, 6, 13], + &[9, 8, 14], + &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[9, 8, 7, 6, 5, 4, 12, 16], + &[9, 8, 7, 6, 13, 17], + &[9, 8, 14, 18], + &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[9, 8, 7, 6, 5, 4, 12, 16, 20], + &[9, 8, 7, 6, 13, 17, 21], + &[9, 8, 14, 18, 22], + &[9, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[9, 8, 7, 6, 5, 4, 12, 16, 20, 24], + &[9, 8, 7, 6, 13, 17, 21, 25], + &[9, 8, 14, 18, 22, 26], + ], + &[ + &[2, 1, 0], + &[2, 1], + &[2], + &[2, 3], + &[2, 3, 4], + &[2, 3, 4, 5], + &[2, 3, 4, 5, 6], + &[2, 3, 4, 5, 6, 7], + &[2, 3, 4, 5, 6, 7, 8], + &[2, 3, 4, 5, 6, 7, 8, 9], + &[2, 3, 4, 5, 6, 7, 8, 9, 10], + &[], + &[2, 3, 4, 12], + &[2, 3, 4, 5, 6, 13], + &[2, 3, 4, 5, 6, 7, 8, 14], + &[15], + &[2, 3, 4, 12, 16], + &[2, 3, 4, 5, 6, 13, 17], + &[2, 3, 4, 5, 6, 7, 8, 14, 18], + &[15, 19], + &[2, 3, 4, 12, 16, 20], + &[2, 3, 4, 5, 6, 13, 17, 21], + &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[15, 19, 23], + &[2, 3, 4, 12, 16, 20, 24], + &[2, 3, 4, 5, 6, 13, 17, 21, 25], + &[2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[4, 3, 2, 1, 0], + &[4, 3, 2, 1], + &[4, 3, 2], + &[4, 3], + &[4], + &[4, 5], + &[4, 5, 6], + &[4, 5, 6, 7], + &[4, 5, 6, 7, 8], + &[4, 5, 6, 7, 8, 9], + &[4, 5, 6, 7, 8, 9, 10], + &[4, 3, 2, 11], + &[], + &[4, 5, 6, 13], + &[4, 5, 6, 7, 8, 14], + &[4, 3, 2, 11, 15], + &[16], + &[4, 5, 6, 13, 17], + &[4, 5, 6, 7, 8, 14, 18], + &[4, 3, 2, 11, 15, 19], + &[16, 20], + &[4, 5, 6, 13, 17, 21], + &[4, 5, 6, 7, 8, 14, 18, 22], + &[4, 3, 2, 11, 15, 19, 23], + &[16, 20, 24], + &[4, 5, 6, 13, 17, 21, 25], + &[4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[6, 5, 4, 3, 2, 1, 0], + &[6, 5, 4, 3, 2, 1], + &[6, 5, 4, 3, 2], + &[6, 5, 4, 3], + &[6, 5, 4], + &[6, 5], + &[6], + &[6, 7], + &[6, 7, 8], + &[6, 7, 8, 9], + &[6, 7, 8, 9, 10], + &[6, 5, 4, 3, 2, 11], + &[6, 5, 4, 12], + &[], + &[6, 7, 8, 14], + &[6, 5, 4, 3, 2, 11, 15], + &[6, 5, 4, 12, 16], + &[17], + &[6, 7, 8, 14, 18], + &[6, 5, 4, 3, 2, 11, 15, 19], + &[6, 5, 4, 12, 16, 20], + &[17, 21], + &[6, 7, 8, 14, 18, 22], + &[6, 5, 4, 3, 2, 11, 15, 19, 23], + &[6, 5, 4, 12, 16, 20, 24], + &[17, 21, 25], + &[6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[8, 7, 6, 5, 4, 3, 2, 1, 0], + &[8, 7, 6, 5, 4, 3, 2, 1], + &[8, 7, 6, 5, 4, 3, 2], + &[8, 7, 6, 5, 4, 3], + &[8, 7, 6, 5, 4], + &[8, 7, 6, 5], + &[8, 7, 6], + &[8, 7], + &[8], + &[8, 9], + &[8, 9, 10], + &[8, 7, 6, 5, 4, 3, 2, 11], + &[8, 7, 6, 5, 4, 12], + &[8, 7, 6, 13], + &[], + &[8, 7, 6, 5, 4, 3, 2, 11, 15], + &[8, 7, 6, 5, 4, 12, 16], + &[8, 7, 6, 13, 17], + &[18], + &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[8, 7, 6, 5, 4, 12, 16, 20], + &[8, 7, 6, 13, 17, 21], + &[18, 22], + &[8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[8, 7, 6, 5, 4, 12, 16, 20, 24], + &[8, 7, 6, 13, 17, 21, 25], + &[18, 22, 26], + ], + &[ + &[11, 2, 1, 0], + &[11, 2, 1], + &[11, 2], + &[11, 2, 3], + &[11, 2, 3, 4], + &[11, 2, 3, 4, 5], + &[11, 2, 3, 4, 5, 6], + &[11, 2, 3, 4, 5, 6, 7], + &[11, 2, 3, 4, 5, 6, 7, 8], + &[11, 2, 3, 4, 5, 6, 7, 8, 9], + &[11, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[11], + &[11, 2, 3, 4, 12], + &[11, 2, 3, 4, 5, 6, 13], + &[11, 2, 3, 4, 5, 6, 7, 8, 14], + &[], + &[11, 2, 3, 4, 12, 16], + &[11, 2, 3, 4, 5, 6, 13, 17], + &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18], + &[19], + &[11, 2, 3, 4, 12, 16, 20], + &[11, 2, 3, 4, 5, 6, 13, 17, 21], + &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[19, 23], + &[11, 2, 3, 4, 12, 16, 20, 24], + &[11, 2, 3, 4, 5, 6, 13, 17, 21, 25], + &[11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[12, 4, 3, 2, 1, 0], + &[12, 4, 3, 2, 1], + &[12, 4, 3, 2], + &[12, 4, 3], + &[12, 4], + &[12, 4, 5], + &[12, 4, 5, 6], + &[12, 4, 5, 6, 7], + &[12, 4, 5, 6, 7, 8], + &[12, 4, 5, 6, 7, 8, 9], + &[12, 4, 5, 6, 7, 8, 9, 10], + &[12, 4, 3, 2, 11], + &[12], + &[12, 4, 5, 6, 13], + &[12, 4, 5, 6, 7, 8, 14], + &[12, 4, 3, 2, 11, 15], + &[], + &[12, 4, 5, 6, 13, 17], + &[12, 4, 5, 6, 7, 8, 14, 18], + &[12, 4, 3, 2, 11, 15, 19], + &[20], + &[12, 4, 5, 6, 13, 17, 21], + &[12, 4, 5, 6, 7, 8, 14, 18, 22], + &[12, 4, 3, 2, 11, 15, 19, 23], + &[20, 24], + &[12, 4, 5, 6, 13, 17, 21, 25], + &[12, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[13, 6, 5, 4, 3, 2, 1, 0], + &[13, 6, 5, 4, 3, 2, 1], + &[13, 6, 5, 4, 3, 2], + &[13, 6, 5, 4, 3], + &[13, 6, 5, 4], + &[13, 6, 5], + &[13, 6], + &[13, 6, 7], + &[13, 6, 7, 8], + &[13, 6, 7, 8, 9], + &[13, 6, 7, 8, 9, 10], + &[13, 6, 5, 4, 3, 2, 11], + &[13, 6, 5, 4, 12], + &[13], + &[13, 6, 7, 8, 14], + &[13, 6, 5, 4, 3, 2, 11, 15], + &[13, 6, 5, 4, 12, 16], + &[], + &[13, 6, 7, 8, 14, 18], + &[13, 6, 5, 4, 3, 2, 11, 15, 19], + &[13, 6, 5, 4, 12, 16, 20], + &[21], + &[13, 6, 7, 8, 14, 18, 22], + &[13, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[13, 6, 5, 4, 12, 16, 20, 24], + &[21, 25], + &[13, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[14, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[14, 8, 7, 6, 5, 4, 3, 2, 1], + &[14, 8, 7, 6, 5, 4, 3, 2], + &[14, 8, 7, 6, 5, 4, 3], + &[14, 8, 7, 6, 5, 4], + &[14, 8, 7, 6, 5], + &[14, 8, 7, 6], + &[14, 8, 7], + &[14, 8], + &[14, 8, 9], + &[14, 8, 9, 10], + &[14, 8, 7, 6, 5, 4, 3, 2, 11], + &[14, 8, 7, 6, 5, 4, 12], + &[14, 8, 7, 6, 13], + &[14], + &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[14, 8, 7, 6, 5, 4, 12, 16], + &[14, 8, 7, 6, 13, 17], + &[], + &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[14, 8, 7, 6, 5, 4, 12, 16, 20], + &[14, 8, 7, 6, 13, 17, 21], + &[22], + &[14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[14, 8, 7, 6, 5, 4, 12, 16, 20, 24], + &[14, 8, 7, 6, 13, 17, 21, 25], + &[22, 26], + ], + &[ + &[15, 11, 2, 1, 0], + &[15, 11, 2, 1], + &[15, 11, 2], + &[15, 11, 2, 3], + &[15, 11, 2, 3, 4], + &[15, 11, 2, 3, 4, 5], + &[15, 11, 2, 3, 4, 5, 6], + &[15, 11, 2, 3, 4, 5, 6, 7], + &[15, 11, 2, 3, 4, 5, 6, 7, 8], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 9], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[15, 11], + &[15, 11, 2, 3, 4, 12], + &[15, 11, 2, 3, 4, 5, 6, 13], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14], + &[15], + &[15, 11, 2, 3, 4, 12, 16], + &[15, 11, 2, 3, 4, 5, 6, 13, 17], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18], + &[], + &[15, 11, 2, 3, 4, 12, 16, 20], + &[15, 11, 2, 3, 4, 5, 6, 13, 17, 21], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[23], + &[15, 11, 2, 3, 4, 12, 16, 20, 24], + &[15, 11, 2, 3, 4, 5, 6, 13, 17, 21, 25], + &[15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[16, 12, 4, 3, 2, 1, 0], + &[16, 12, 4, 3, 2, 1], + &[16, 12, 4, 3, 2], + &[16, 12, 4, 3], + &[16, 12, 4], + &[16, 12, 4, 5], + &[16, 12, 4, 5, 6], + &[16, 12, 4, 5, 6, 7], + &[16, 12, 4, 5, 6, 7, 8], + &[16, 12, 4, 5, 6, 7, 8, 9], + &[16, 12, 4, 5, 6, 7, 8, 9, 10], + &[16, 12, 4, 3, 2, 11], + &[16, 12], + &[16, 12, 4, 5, 6, 13], + &[16, 12, 4, 5, 6, 7, 8, 14], + &[16, 12, 4, 3, 2, 11, 15], + &[16], + &[16, 12, 4, 5, 6, 13, 17], + &[16, 12, 4, 5, 6, 7, 8, 14, 18], + &[16, 12, 4, 3, 2, 11, 15, 19], + &[], + &[16, 12, 4, 5, 6, 13, 17, 21], + &[16, 12, 4, 5, 6, 7, 8, 14, 18, 22], + &[16, 12, 4, 3, 2, 11, 15, 19, 23], + &[24], + &[16, 12, 4, 5, 6, 13, 17, 21, 25], + &[16, 12, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[17, 13, 6, 5, 4, 3, 2, 1, 0], + &[17, 13, 6, 5, 4, 3, 2, 1], + &[17, 13, 6, 5, 4, 3, 2], + &[17, 13, 6, 5, 4, 3], + &[17, 13, 6, 5, 4], + &[17, 13, 6, 5], + &[17, 13, 6], + &[17, 13, 6, 7], + &[17, 13, 6, 7, 8], + &[17, 13, 6, 7, 8, 9], + &[17, 13, 6, 7, 8, 9, 10], + &[17, 13, 6, 5, 4, 3, 2, 11], + &[17, 13, 6, 5, 4, 12], + &[17, 13], + &[17, 13, 6, 7, 8, 14], + &[17, 13, 6, 5, 4, 3, 2, 11, 15], + &[17, 13, 6, 5, 4, 12, 16], + &[17], + &[17, 13, 6, 7, 8, 14, 18], + &[17, 13, 6, 5, 4, 3, 2, 11, 15, 19], + &[17, 13, 6, 5, 4, 12, 16, 20], + &[], + &[17, 13, 6, 7, 8, 14, 18, 22], + &[17, 13, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[17, 13, 6, 5, 4, 12, 16, 20, 24], + &[25], + &[17, 13, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 1], + &[18, 14, 8, 7, 6, 5, 4, 3, 2], + &[18, 14, 8, 7, 6, 5, 4, 3], + &[18, 14, 8, 7, 6, 5, 4], + &[18, 14, 8, 7, 6, 5], + &[18, 14, 8, 7, 6], + &[18, 14, 8, 7], + &[18, 14, 8], + &[18, 14, 8, 9], + &[18, 14, 8, 9, 10], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11], + &[18, 14, 8, 7, 6, 5, 4, 12], + &[18, 14, 8, 7, 6, 13], + &[18, 14], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[18, 14, 8, 7, 6, 5, 4, 12, 16], + &[18, 14, 8, 7, 6, 13, 17], + &[18], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[18, 14, 8, 7, 6, 5, 4, 12, 16, 20], + &[18, 14, 8, 7, 6, 13, 17, 21], + &[], + &[18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[18, 14, 8, 7, 6, 5, 4, 12, 16, 20, 24], + &[18, 14, 8, 7, 6, 13, 17, 21, 25], + &[26], + ], + &[ + &[19, 15, 11, 2, 1, 0], + &[19, 15, 11, 2, 1], + &[19, 15, 11, 2], + &[19, 15, 11, 2, 3], + &[19, 15, 11, 2, 3, 4], + &[19, 15, 11, 2, 3, 4, 5], + &[19, 15, 11, 2, 3, 4, 5, 6], + &[19, 15, 11, 2, 3, 4, 5, 6, 7], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 9], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 9, 10], + &[19, 15, 11], + &[19, 15, 11, 2, 3, 4, 12], + &[19, 15, 11, 2, 3, 4, 5, 6, 13], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14], + &[19, 15], + &[19, 15, 11, 2, 3, 4, 12, 16], + &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18], + &[19], + &[19, 15, 11, 2, 3, 4, 12, 16, 20], + &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17, 21], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22], + &[], + &[19, 15, 11, 2, 3, 4, 12, 16, 20, 24], + &[19, 15, 11, 2, 3, 4, 5, 6, 13, 17, 21, 25], + &[19, 15, 11, 2, 3, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[20, 16, 12, 4, 3, 2, 1, 0], + &[20, 16, 12, 4, 3, 2, 1], + &[20, 16, 12, 4, 3, 2], + &[20, 16, 12, 4, 3], + &[20, 16, 12, 4], + &[20, 16, 12, 4, 5], + &[20, 16, 12, 4, 5, 6], + &[20, 16, 12, 4, 5, 6, 7], + &[20, 16, 12, 4, 5, 6, 7, 8], + &[20, 16, 12, 4, 5, 6, 7, 8, 9], + &[20, 16, 12, 4, 5, 6, 7, 8, 9, 10], + &[20, 16, 12, 4, 3, 2, 11], + &[20, 16, 12], + &[20, 16, 12, 4, 5, 6, 13], + &[20, 16, 12, 4, 5, 6, 7, 8, 14], + &[20, 16, 12, 4, 3, 2, 11, 15], + &[20, 16], + &[20, 16, 12, 4, 5, 6, 13, 17], + &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18], + &[20, 16, 12, 4, 3, 2, 11, 15, 19], + &[20], + &[20, 16, 12, 4, 5, 6, 13, 17, 21], + &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18, 22], + &[20, 16, 12, 4, 3, 2, 11, 15, 19, 23], + &[], + &[20, 16, 12, 4, 5, 6, 13, 17, 21, 25], + &[20, 16, 12, 4, 5, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[21, 17, 13, 6, 5, 4, 3, 2, 1, 0], + &[21, 17, 13, 6, 5, 4, 3, 2, 1], + &[21, 17, 13, 6, 5, 4, 3, 2], + &[21, 17, 13, 6, 5, 4, 3], + &[21, 17, 13, 6, 5, 4], + &[21, 17, 13, 6, 5], + &[21, 17, 13, 6], + &[21, 17, 13, 6, 7], + &[21, 17, 13, 6, 7, 8], + &[21, 17, 13, 6, 7, 8, 9], + &[21, 17, 13, 6, 7, 8, 9, 10], + &[21, 17, 13, 6, 5, 4, 3, 2, 11], + &[21, 17, 13, 6, 5, 4, 12], + &[21, 17, 13], + &[21, 17, 13, 6, 7, 8, 14], + &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15], + &[21, 17, 13, 6, 5, 4, 12, 16], + &[21, 17], + &[21, 17, 13, 6, 7, 8, 14, 18], + &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15, 19], + &[21, 17, 13, 6, 5, 4, 12, 16, 20], + &[21], + &[21, 17, 13, 6, 7, 8, 14, 18, 22], + &[21, 17, 13, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[21, 17, 13, 6, 5, 4, 12, 16, 20, 24], + &[], + &[21, 17, 13, 6, 7, 8, 14, 18, 22, 26], + ], + &[ + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 1, 0], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 1], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2], + &[22, 18, 14, 8, 7, 6, 5, 4, 3], + &[22, 18, 14, 8, 7, 6, 5, 4], + &[22, 18, 14, 8, 7, 6, 5], + &[22, 18, 14, 8, 7, 6], + &[22, 18, 14, 8, 7], + &[22, 18, 14, 8], + &[22, 18, 14, 8, 9], + &[22, 18, 14, 8, 9, 10], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11], + &[22, 18, 14, 8, 7, 6, 5, 4, 12], + &[22, 18, 14, 8, 7, 6, 13], + &[22, 18, 14], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15], + &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16], + &[22, 18, 14, 8, 7, 6, 13, 17], + &[22, 18], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19], + &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16, 20], + &[22, 18, 14, 8, 7, 6, 13, 17, 21], + &[22], + &[22, 18, 14, 8, 7, 6, 5, 4, 3, 2, 11, 15, 19, 23], + &[22, 18, 14, 8, 7, 6, 5, 4, 12, 16, 20, 24], + &[22, 18, 14, 8, 7, 6, 13, 17, 21, 25], + &[], + ], +]; + +#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)] +enum Amphipod { + A, + B, + C, + D, +} +use Amphipod::*; + +impl Amphipod { + fn step_cost(&self) -> i64 { + match self { + A => 1, + B => 10, + C => 100, + D => 1000, + } + } +} + +impl std::str::FromStr for Amphipod { + type Err = anyhow::Error; + fn from_str(s: &str) -> std::result::Result<Self, Self::Err> { + match s { + "A" => Ok(A), + "B" => Ok(B), + "C" => Ok(C), + "D" => Ok(D), + _ => Err(anyhow::anyhow!(s.to_string())), + } + } +} + +impl std::fmt::Display for Amphipod { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> std::result::Result<(), std::fmt::Error> { + match self { + A => write!(f, "A"), + B => write!(f, "B"), + C => write!(f, "C"), + D => write!(f, "D"), + } + } +} + +// ############# +// #abcdefghijk# +// ###l#m#n#o### +// #p#q#r#s# +// ######### +#[derive(Debug, Clone, Copy, Default, Hash, PartialEq, Eq)] +pub struct Burrow { + spaces: [Option<Amphipod>; 27], + big: bool, +} + +impl Burrow { + fn to_big(self) -> Self { + let mut big = self; + + big.spaces[23] = self.spaces[15]; + big.spaces[24] = self.spaces[16]; + big.spaces[25] = self.spaces[17]; + big.spaces[26] = self.spaces[18]; + + big.spaces[15] = Some(D); + big.spaces[16] = Some(C); + big.spaces[17] = Some(B); + big.spaces[18] = Some(A); + big.spaces[19] = Some(D); + big.spaces[20] = Some(B); + big.spaces[21] = Some(A); + big.spaces[22] = Some(C); + + big.big = true; + + big + } + + fn path(&self, from: usize, to: usize) -> &[usize] { + if self.big { + CONNECTIVITY2[from][to] + } else { + CONNECTIVITY1[from][to] + } + } + + fn done(&self) -> bool { + self.spaces[11] == Some(A) + && self.spaces[15] == Some(A) + && self.spaces[12] == Some(B) + && self.spaces[16] == Some(B) + && self.spaces[13] == Some(C) + && self.spaces[17] == Some(C) + && self.spaces[14] == Some(D) + && self.spaces[18] == Some(D) + && (!self.big + || (self.spaces[19] == Some(A) + && self.spaces[23] == Some(A) + && self.spaces[20] == Some(B) + && self.spaces[24] == Some(B) + && self.spaces[21] == Some(C) + && self.spaces[25] == Some(C) + && self.spaces[22] == Some(D) + && self.spaces[26] == Some(D))) + } + + fn move_cost(&self, mv: Move) -> i64 { + self.spaces[mv.from].unwrap().step_cost() + * i64::try_from(self.path(mv.from, mv.to).len()).unwrap() + } + + fn make_move(&self, mv: Move) -> Self { + let mut new = *self; + let a = new.spaces[mv.from].take().unwrap(); + assert!(new.spaces[mv.to].is_none()); + new.spaces[mv.to] = Some(a); + new + } + + fn legal_moves(&self) -> Vec<Move> { + let mut ret = vec![]; + let size = if self.big { 27 } else { 19 }; + for (from, space) in self.spaces.iter().enumerate().take(size) { + if let Some(a) = space { + for to in 0..size { + if self.can_move(*a, from, to) { + ret.push(Move::new(from, to)); + } + } + } + } + ret + } + + fn can_move(&self, a: Amphipod, from: usize, to: usize) -> bool { + if !self.big && (from >= 19 || to >= 19) { + return false; + } + + // Amphipods will never stop on the space immediately outside any + // room. + if to == 2 || to == 4 || to == 6 || to == 8 { + return false; + } + + // Amphipods will never move from the hallway into a room unless that + // room is their destination room and that room contains no amphipods + // which do not also have that room as their own destination. + match a { + A => { + if to == 12 + || to == 13 + || to == 14 + || to == 16 + || to == 17 + || to == 18 + || to == 20 + || to == 21 + || to == 22 + || to == 24 + || to == 25 + || to == 26 + { + return false; + } + if self.big { + if to == 11 + && (self.spaces[15] != Some(A) + || self.spaces[19] != Some(A) + || self.spaces[23] != Some(A)) + { + return false; + } + if to == 15 + && (self.spaces[19] != Some(A) + || self.spaces[23] != Some(A)) + { + return false; + } + if to == 19 && self.spaces[23] != Some(A) { + return false; + } + if from == 23 + || (from == 19 && self.spaces[23] == Some(A)) + || (from == 15 + && self.spaces[23] == Some(A) + && self.spaces[19] == Some(A)) + || (from == 11 + && self.spaces[23] == Some(A) + && self.spaces[19] == Some(A) + && self.spaces[15] == Some(A)) + { + return false; + } + } else { + if to == 11 && self.spaces[15] != Some(A) { + return false; + } + if from == 15 + || (from == 11 && self.spaces[15] == Some(A)) + { + return false; + } + } + } + B => { + if to == 11 + || to == 13 + || to == 14 + || to == 15 + || to == 17 + || to == 18 + || to == 19 + || to == 21 + || to == 22 + || to == 23 + || to == 25 + || to == 26 + { + return false; + } + if self.big { + if to == 12 + && (self.spaces[16] != Some(B) + || self.spaces[20] != Some(B) + || self.spaces[24] != Some(B)) + { + return false; + } + if to == 16 + && (self.spaces[20] != Some(B) + || self.spaces[24] != Some(B)) + { + return false; + } + if to == 20 && self.spaces[24] != Some(B) { + return false; + } + if from == 24 + || (from == 20 && self.spaces[24] == Some(B)) + || (from == 16 + && self.spaces[24] == Some(B) + && self.spaces[20] == Some(B)) + || (from == 12 + && self.spaces[24] == Some(B) + && self.spaces[20] == Some(B) + && self.spaces[16] == Some(B)) + { + return false; + } + } else { + if to == 12 && self.spaces[16] != Some(B) { + return false; + } + if from == 16 + || (from == 12 && self.spaces[16] == Some(B)) + { + return false; + } + } + } + C => { + if to == 11 + || to == 12 + || to == 14 + || to == 15 + || to == 16 + || to == 18 + || to == 19 + || to == 20 + || to == 22 + || to == 23 + || to == 24 + || to == 26 + { + return false; + } + if self.big { + if to == 13 + && (self.spaces[17] != Some(C) + || self.spaces[21] != Some(C) + || self.spaces[25] != Some(C)) + { + return false; + } + if to == 17 + && (self.spaces[21] != Some(C) + || self.spaces[25] != Some(C)) + { + return false; + } + if to == 21 && self.spaces[25] != Some(C) { + return false; + } + if from == 25 + || (from == 21 && self.spaces[25] == Some(C)) + || (from == 17 + && self.spaces[25] == Some(C) + && self.spaces[21] == Some(C)) + || (from == 13 + && self.spaces[25] == Some(C) + && self.spaces[21] == Some(C) + && self.spaces[17] == Some(C)) + { + return false; + } + } else { + if to == 13 && self.spaces[17] != Some(C) { + return false; + } + if from == 17 + || (from == 13 && self.spaces[17] == Some(C)) + { + return false; + } + } + } + D => { + if to == 11 + || to == 12 + || to == 13 + || to == 15 + || to == 16 + || to == 17 + || to == 19 + || to == 20 + || to == 21 + || to == 23 + || to == 24 + || to == 25 + { + return false; + } + if self.big { + if to == 14 + && (self.spaces[18] != Some(D) + || self.spaces[22] != Some(D) + || self.spaces[26] != Some(D)) + { + return false; + } + if to == 18 + && (self.spaces[22] != Some(D) + || self.spaces[26] != Some(D)) + { + return false; + } + if to == 22 && self.spaces[26] != Some(D) { + return false; + } + if from == 26 + || (from == 22 && self.spaces[26] == Some(D)) + || (from == 18 + && self.spaces[26] == Some(D) + && self.spaces[22] == Some(D)) + || (from == 14 + && self.spaces[26] == Some(D) + && self.spaces[22] == Some(D) + && self.spaces[18] == Some(D)) + { + return false; + } + } else { + if to == 14 && self.spaces[18] != Some(D) { + return false; + } + if from == 18 + || (from == 14 && self.spaces[18] == Some(D)) + { + return false; + } + } + } + } + + // Once an amphipod stops moving in the hallway, it will stay in that + // spot until it can move into a room. + if from < 11 && to < 11 { + return false; + } + + // not actually a move + if from == to { + return false; + } + + // we don't have an unblocked path + for space in self.path(from, to) { + if self.spaces[*space].is_some() { + return false; + } + } + + true + } +} + +impl std::fmt::Display for Burrow { + fn fmt( + &self, + f: &mut std::fmt::Formatter<'_>, + ) -> std::result::Result<(), std::fmt::Error> { + writeln!(f, "#############")?; + + write!(f, "#")?; + for i in 0..11 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}", a)?; + } else { + write!(f, ".")?; + } + } + writeln!(f, "#")?; + + write!(f, "###")?; + for i in 11..15 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}#", a)?; + } else { + write!(f, ".#")?; + } + } + writeln!(f, "##")?; + + write!(f, " #")?; + for i in 15..19 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}#", a)?; + } else { + write!(f, ".#")?; + } + } + writeln!(f)?; + + if self.big { + write!(f, " #")?; + for i in 19..23 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}#", a)?; + } else { + write!(f, ".#")?; + } + } + writeln!(f)?; + write!(f, " #")?; + for i in 23..27 { + if let Some(a) = &self.spaces[i] { + write!(f, "{}#", a)?; + } else { + write!(f, ".#")?; + } + } + writeln!(f)?; + } + + write!(f, " #########")?; + + Ok(()) + } +} + +#[derive(Debug, Clone, Copy, Hash, PartialEq, Eq)] +struct Move { + from: usize, + to: usize, +} + +impl Move { + fn new(from: usize, to: usize) -> Self { + Self { from, to } + } +} + +pub fn parse(fh: File) -> Result<Burrow> { + let mut burrow = Burrow::default(); + let lines: Vec<_> = parse::lines(fh).collect(); + + let captures = + regex_captures!(r"###(.)#(.)#(.)#(.)###", &lines[2]).unwrap(); + burrow.spaces[11] = Some(captures[1].parse()?); + burrow.spaces[12] = Some(captures[2].parse()?); + burrow.spaces[13] = Some(captures[3].parse()?); + burrow.spaces[14] = Some(captures[4].parse()?); + + let captures = + regex_captures!(r" #(.)#(.)#(.)#(.)#", &lines[3]).unwrap(); + burrow.spaces[15] = Some(captures[1].parse()?); + burrow.spaces[16] = Some(captures[2].parse()?); + burrow.spaces[17] = Some(captures[3].parse()?); + burrow.spaces[18] = Some(captures[4].parse()?); + + Ok(burrow) +} + +#[allow(dead_code)] +fn organize_recursive(burrow: Burrow, so_far: &mut Vec<Move>) -> bool { + if burrow.done() { + return true; + } + for mv in burrow.legal_moves() { + so_far.push(mv); + if organize_recursive(burrow.make_move(mv), so_far) { + return true; + } + so_far.pop(); + } + false +} + +fn organize_dijkstra(burrow: Burrow) -> (i64, Vec<Burrow>) { + let mut to_visit = priority_queue::PriorityQueue::new(); + let mut prev = HashMap::new(); + to_visit.push(burrow, std::cmp::Reverse(0)); + while let Some((burrow, std::cmp::Reverse(distance))) = to_visit.pop() { + if burrow.done() { + let mut path = vec![burrow]; + let mut cur = burrow; + while let Some(next) = prev.get(&cur) { + path.insert(0, *next); + cur = *next; + } + return (distance, path); + } + for mv in burrow.legal_moves() { + let next = burrow.make_move(mv); + prev.insert(next, burrow); + let new_distance = distance + burrow.move_cost(mv); + if to_visit.get(&next).is_some() { + if new_distance < to_visit.get_priority(&next).unwrap().0 { + to_visit.change_priority( + &next, + std::cmp::Reverse(new_distance), + ); + } + } else { + to_visit.push(next, std::cmp::Reverse(new_distance)); + } + } + } + unreachable!() +} + +pub fn part1(burrow: Burrow) -> Result<i64> { + let (cost, _path) = organize_dijkstra(burrow); + // for burrow in path { + // eprintln!("{}", burrow); + // } + Ok(cost) +} + +pub fn part2(burrow: Burrow) -> Result<i64> { + let (cost, _path) = organize_dijkstra(burrow.to_big()); + // for burrow in path { + // eprintln!("{}", burrow); + // } + Ok(cost) +} + +#[test] +fn test() { + assert_eq!( + part1(parse(parse::data(2021, 23).unwrap()).unwrap()).unwrap(), + 0 + ); + assert_eq!( + part2(parse(parse::data(2021, 23).unwrap()).unwrap()).unwrap(), + 0 + ); +} diff --git a/src/2021/mod.rs b/src/2021/mod.rs index 124ea71..7d2bdad 100644 --- a/src/2021/mod.rs +++ b/src/2021/mod.rs @@ -44,6 +44,8 @@ mod day20; mod day21; #[path = "22/mod.rs"] mod day22; +#[path = "23/mod.rs"] +mod day23; // NEXT MOD pub fn run(day: u8, puzzle: u8) -> Result<i64> { @@ -92,6 +94,8 @@ pub fn run(day: u8, puzzle: u8) -> Result<i64> { (21, 2) => day21::part2(day21::parse(parse::data(2021, 21)?)?), (22, 1) => day22::part1(day22::parse(parse::data(2021, 22)?)?), (22, 2) => day22::part2(day22::parse(parse::data(2021, 22)?)?), + (23, 1) => day23::part1(day23::parse(parse::data(2021, 23)?)?), + (23, 2) => day23::part2(day23::parse(parse::data(2021, 23)?)?), // NEXT PART _ => Err(anyhow!("unknown puzzle {}-{}", day, puzzle)), } |