#[cfg(test)]
mod tests_aoc {
const PUZZLE_INPUT: &str = "[..##.##.#] (2,3,5,6,8) (0,3,7) (1,4,8) (0,1,6) (3,4,5,8) (2,3,7,8) (0,2,3,8) {21,15,27,149,126,127,16,12,153}
[#####..#] (0,1,4,5,6) (0,1,2,4,5,6) (1,2) (2,3) (2) (5) (0,4,5,7) {33,29,57,14,33,47,20,13}
[#.###] (0,1,3) (0,1,4) (0,2,3,4) (1,2) {20,29,13,6,16}
[#.###] (0,2) (1,2,4) (1,2,3) (0,2,4) {9,180,189,163,21}
[.#.#####..] (0,1,4,9) (0,2,3,4) (0,6,9) (0,2,4,6,8,9) (0,1,2,3,4,7,8) (0,1,2,4,5,6,8,9) (0,5,6,9) (0,3,8,9) (3,5,6,8) (1,2) (0,1,4,5,6) (0,3,7) (0,1,4,5,6,9) {184,136,19,48,143,50,68,3,53,165}
[.###..##.] (3,5,6,8) (0,1,3,4,5,7) (0,3,4,5,6,8) (3,8) (1,2,3,5,6,7) (0,1,2,3,4,5,8) (1,2,5,6,7) (1,2,3,4,5,6) (0,2,3,5) (7,8) {35,40,50,101,38,87,67,25,57}
[.####.#..#] (0,1,4,5,7,8,9) (1,7) (1,3,5,6,7,8,9) (0,1,4,6,7,8,9) (0,1,2,4,5,6,8,9) (0,1,2,3,5,6,8) (3,9) (1,2,3,5,6,7,9) (3,5,7) (1,2,3,4,5,6) {53,106,42,61,48,70,79,69,70,59}
[#.###....] (0,1,2,4,8) (0,1,3,4,6,7,8) (0,1,4,7,8) (1,2,3,5,6) (1,2,5) (3,4,5,7,8) (1,6,8) {40,72,30,24,48,22,34,32,66}
[###.#.#] (0,1,5) (2,4) (0,3,6) (5) (0,3) (4,5,6) {31,8,1,23,19,45,26}
[..##.] (2,3,4) (0,3,4) (0,2,4) (3,4) (1,2) {25,14,42,38,46}
[#####..##] (0,3,4,6,8) (4,5) (2,5,7,8) (1,2,5) (0,1,2,3,4,6,7) (0,4) (0,1,3,5,7,8) (1,2,3,4,6,8) (5,6,7,8) (0,1,2,3,6,7) (1,3,5,6,7,8) {83,74,47,84,58,71,81,83,83}
[...#.###] (1,4,5,6) (1,2,4,7) (0,1,2,3,4,5) (1,5,6) (3,4,5,7) (0,1,2,4,6,7) (0,1,2,6) (7) {14,36,21,14,27,29,25,23}
[..###....] (1,2,6) (0,3,5,6,7,8) (2) (0,1,3,6,8) (2,4,5,6,7,8) (1,3,5,7,8) (2,4,8) (0,1,2,7,8) (1,2,3,4,6) (0,1,2,3,4,5,6,8) (2,3,4,5,6,7) {34,56,81,54,41,49,57,41,71}
[####.#.] (0,1,4,5,6) (0,2,3,5) (0,2,5) (1,6) (0,2,4,5,6) (0,1,2,3,5) (1,2,4,5,6) {182,161,37,15,162,189,162}
[##.#] (0,1,2) (0,3) (1) {31,26,19,12}
[#..#] (2) (0,3) (0,1) (0) {33,13,17,11}
[#.#...#.] (0,5) (1,2,3,6) (3,6) (0,2,3,5,6,7) (1,2,3,5,7) (1,2,3,4,6,7) (0,1,3,4,5,6,7) {24,26,25,33,13,24,33,19}
[###..] (1,2,3,4) (1,2,4) (0,3,4) {0,15,15,4,15}
[.#..#.] (0,2,4) (0) (0,1,4) (2,3,5) (1,2,3,5) (0,2,5) (0,2,4,5) (0,3,4,5) {87,37,54,40,61,65}
[.#..#.####] (3,7) (0,3,4,6,7,8,9) (1,4,5,7,8,9) (0,1,2,8,9) (4,5,6,7) (0,4,8) (2,9) (3,8) {36,23,9,39,70,37,36,71,61,48}
[#.##..#..] (0,1,3,4,5,7,8) (0,6) (0,1,2,4,5,7,8) (3,6) (0,1,4,7,8) (1,2,3,4,5,6,7,8) (0,2,5,6) (0,2,4,7,8) (0,4) (2,6) {89,38,43,34,62,50,56,43,43}
[.#.#] (0,2) (1,3) {6,2,6,2}
[##.#] (0,3) (0,1,3) (1,2,3) {24,192,187,211}
[.###.] (0,2,4) (0,3,4) (0,3) (4) (1,2,4) (0,1,2) (1,2) {32,38,51,8,43}
[##.##...] (1) (1,5) (0,1,5,6) (5,7) (2,4,6) (0,1,3,5,6) (0,1,3,4,7) (2,3,4,5) (0,1,2,3,4,6) {48,64,39,51,43,59,55,7}
[..#..#] (2,4,5) (0,2,4,5) (1,2,3,4) (2,4) (0,3,5) (0,4) (2,3,4,5) {55,8,64,47,84,60}
[.#.#..] (1,2,3,4,5) (1,2,4,5) (1) (1,3,4) (0,1,3,4) (2,3) (0,1,3,5) {26,70,29,50,40,37}
[..###..#] (0,1,2,3) (0,1,4,5,7) (0,2,5,7) (1) (0,1,3,4,5,6,7) (0,1,2,3,4,6) (0,4,7) (2,5) {58,40,58,29,19,49,10,38}
[##.###.##] (3,6,8) (0,1,2,3,4,6) (0,1,5,6,7) (0,5) (0,2,3,4,6,7) (0,1,4,5,7,8) (0,1,2,3,5,6) (0,1,2,3,4,6,7) (6,7,8) {69,56,47,61,44,32,85,49,39}
[###..#.] (0,1,4,6) (2,4,5,6) (6) (2,5) (4,6) (0,4,5,6) (3,5) (5,6) {20,5,19,6,45,52,71}
[#..###.##] (0,5,6,7) (0,1,3,4,5,6,8) (0,1,2,4,5,7) (3,5) (4,5) (1,2,3,6) (1,4,7) (0,3,4,5,7,8) {36,28,20,157,43,167,25,30,24}
[#....#.] (1,5) (2,5,6) (0,2,3,5) (2) (4,5) (0,3,4,5) (0,1,3,4,5) (0,2,4,5,6) {50,32,34,45,201,236,17}
[#.###] (0,1,3) (0,1,4) (1) (0,2) {41,32,18,4,19}
[#.##..#] (2,3) (0,2,3,6) (3,6) (0,1,3,4,5) (1,2,5,6) (1,2,4,5,6) {35,173,174,45,18,173,184}
[..#.#] (0,1,4) (0,1,3,4) (2,3,4) (0,1) {43,43,1,9,26}
[#..#] (2,3) (0,3) (0,1) {187,170,11,28}
[####..##.] (5,6) (0,1,2,3,5,7,8) (6,7,8) (1,2,4,5,6,7) (1,2,4,5,7,8) (0,1,2,3,5,6,8) (0,1,3,6,7,8) (2,4,5,6,7) {32,42,46,32,14,59,53,45,55}
[.###.###.] (3,4) (0,1,2,3,8) (5) (1,6) (0,1,3,4,7,8) (0,2,4,5,6,8) (0,1,4,6,7,8) (0,3,4,6,8) {48,52,4,38,59,21,51,33,48}
[....###.] (0,3,5) (0,3,4,5,6,7) (1,6) (0,1,3,4,5,6,7) (0,2) (2,3,5,6,7) (2,3,7) (2,7) (0,2,3,6,7) (0,1,2,3,7) {190,148,186,176,22,25,41,190}
[..###...] (0,1,2,5,6,7) (0,1,2) (0,1,2,4,5,6,7) (0,1,3,4,5,7) (0,2,7) (0,3,4,5,6) (1,2,4,5,6,7) {80,58,52,28,48,58,48,44}
[#..##..#.] (2,3,4,5,6,8) (0,1,4,5,6,7,8) (0,2,3,4,5,6) (0,2,3,7,8) (0,1,3,4,5,6) (0,4,5) (0,3) (2,3,4,7) (0,2,5,6,7,8) {66,15,56,66,53,53,46,33,36}
[...#.#] (0,1,2,4) (3,5) (0,1) (4) (0,3,4,5) (0,1,2,3,5) (0,3,5) {70,38,20,40,38,40}
[#..###.#] (0,2,3,4,5,7) (0,2,3,4,5,6) (4,6,7) (1,2,3,4,6) (1,6,7) (2,6,7) (0,1,4) (0,1,2,4,6,7) (0,4) (0,2,5,6,7) {208,38,30,13,211,10,43,38}
[###.#] (3,4) (0,1,2) (1,3) (0,1,4) (1,3,4) {9,14,6,8,8}
[##.####] (1,2,4,5) (2,3,4,6) (1,4,6) (0,1,2,5) (2,6) {16,39,144,4,27,22,139}
[#.#..#] (0,2) (1,2,4) (1,4) (1,2,3,4,5) (1,2,5) (0,2,4,5) (3,4) (0,2,5) {44,55,80,25,65,53}
[..####..] (1,3,4,5,6) (2,4) (0,1,5,7) (0,1,2,6) (3,6) (1,2,3,5,6) (0,1,2,6,7) (7) (2,4,5,6,7) {49,72,79,24,27,43,65,59}
[#####.#.] (0,1,2,3,4,6) (0,1,4,7) (0,1,5,6,7) (2,3) (0,1,2,4) (0,1,3,4,6) (1,2,3,5,6) (2,3,4,5) (0,1,3,5,6,7) {84,104,73,75,85,37,66,26}
[.#..##] (0,1,2,4,5) (0,3,4) (1,2,3,5) (0,1,3,5) {19,17,9,26,11,17}
[...#...] (0,1,3,4,6) (2,4,5,6) (0,1,3,5) (0,1,2,4,5,6) (0,1,2,4,6) (0,1,2,3,5) (0,1,2,6) {88,88,82,33,43,59,63}
[####] (0,3) (2) (3) (0,1) {31,12,19,31}
[#..#..] (0,1,2,4) (4,5) (3,5) (1,2) (0,1,3,5) {9,26,19,15,5,18}
[##.#..###] (0,3,4,6,7,8) (2,5,8) (1,2,3,4) (0,1,2,4,5,8) (0,3,4,6) (0,7) (0,2,3,4,5,6,7) (1,2,3,4,5) (3,5,7) {64,21,35,63,58,54,37,55,26}
[.#.##.#] (2,6) (0,3,4,6) (0,1,3,4,5) (0,6) (0,3,5) (0,2,6) (0,2,3,4,6) (0,1,2,3,4) (0,1,2,4,6) {75,47,38,52,65,14,44}
[...##] (0,2) (3,4) (0,1,4) (0,1,3,4) (2,3) (0,2,4) (0,3,4) {51,17,26,33,44}
[#####.] (0,1,2,3,4) (1,2,4,5) (0,2) (0,1,2,3,5) {24,26,34,16,22,14}
[...####.#.] (0,3,5,8,9) (3,4,5,6,8) (0,1,2,3,5,6) (0,1,2,3,4,5,6,7,9) (0,1,2,4,5,6,7,8,9) (1,3,7,8,9) (6,7) (5,7) {31,40,28,30,17,209,36,209,32,30}
[.#..#.] (1,2,3,4) (0,2,3,5) (0,1,3,4) (3,4) (1,4) {6,14,7,21,27,5}
[##.......#] (1,2,4,6) (1,5) (2,3,6,8) (1,2,3,4,7,8) (0,1,2,4,5,6,7,9) (1,6,7,9) (0,3,8) (1,2,3,6) {18,46,44,43,24,17,41,19,40,10}
[#.######] (0,1,2,3,5,7) (0,2,5,6,7) (0,2,3,4,7) (1,6,7) (3,4) (0,1,2,3,5,6,7) {35,28,35,36,27,19,35,54}
[#.###] (0,2,3,4) (0,1,3,4) (3) (1,3) (0,2,4) {28,186,21,204,28}
[..#####..#] (0,1,2,3,5,6,8) (1,3,4,6,7,8,9) (0,1,2,3,4,7,8,9) (0,1,2,3,4,5,6,7,9) (0,3,4,5,6,7,8,9) (1,2,4,6,9) (3,4,5,6,8) (2,8,9) (0,1,2,3,4,5,6,8,9) {59,72,260,84,88,75,96,35,260,263}
[.#.#...###] (0,3,8,9) (1,2,3,4,5,6,7,9) (0,1,2,5,6,8) (3,8) (2,6) (1,2,7) (4,5,8) (0,1,2,3,4,5,6,8,9) (3,4,5,7) (0,1,3,4,5,8) (1,4,5,8,9) {63,99,72,88,97,117,57,48,105,53}
[#.#..] (1,3,4) (0,2) (0,3) (1) (0,2,4) (1,2,3) {212,34,204,48,201}
[#####] (2,3) (0,1,3) (0,1,4) {21,21,166,180,7}
[#.######] (3,4,6) (0,3,4,5) (0,1,2,3,4,6,7) (1,3,4,5,7) (2,6,7) (0,3,6) {39,34,19,254,245,34,224,38}
[##...] (1,2) (0,2,3,4) (0,1) (1,4) (1,2,3,4) (0,4) (1,3,4) {44,48,12,26,56}
[##....##.] (0,1,2,3,4,5,6,8) (2,5,6) (3,7,8) (0,1,2,4,6) (0,1,2) (3,6,8) (1,2,3,6,7) (0,2,3,4,5) {50,49,57,31,41,22,40,9,16}
[...#..#.] (1,2,3,4,7) (0,1,4,6) (3,4,5,6) (1,3,4,5,6) (1,4,6,7) (1,2) {6,36,14,39,48,32,41,10}
[##.#] (0,1,3) (0,2) {26,20,6,20}
[#.####....] (1,2,3,5,6,9) (3,4,5,6,9) (1,2) (0,1,4,5,6,9) (0,6) (1,3,4,6,7,8,9) (0,4,7) (3,8) (0,1,2,3,4,5,6,8) (2,4,5,7,8,9) {31,223,214,35,46,31,43,32,41,42}
[#.#.#] (0,1,2) (0,2,4) (1,2,3,4) (0) (2,3) (1,3) {174,35,35,41,19}
[.#.#] (1,2) (1,3) (0,2) (1) (0,1,3) {1,174,11,6}
[#.##.#.] (0,4,6) (1,3,5) (1,2,3,4,5) (1,6) (6) (2,4) (0,2,3,6) {17,35,37,34,34,24,165}
[##.#.#.] (1,2,4,6) (0,1,3,5) (1,2,3,5,6) (1,2,4) (2,3,4) (3,4,6) (0,3,4,5) {11,50,46,36,46,24,34}
[....##....] (0,1,2,4,5,8,9) (0,2,4,5,6,7,9) (6) (1,2,3,4,6,7,8,9) (1,4,6,7,9) (1,2,3,4,5,6,7,9) (0,2,6,7,9) (1,4,7,9) (1,2,3,4,5,6,8,9) (1,3,4,7) (4,5) {157,83,207,58,112,68,223,214,37,226}
[.#.#...] (0,3,6) (0,2) (1,5) (1,3) (1,2,4,6) (1,5,6) {31,35,31,19,15,16,33}
[#.#..] (0,3) (0,2,3) (0,3,4) (0,1,2,3) (0,1,3) (0,1) (0,2,4) {238,207,29,206,21}
[######.] (3,5) (0,1,4,6) (0,3,6) (2,4) (1,3,4) (2,5,6) (4,5) (0,1,4,5,6) (0,1,3) {172,171,18,11,186,194,182}
[##..##..#.] (2,5) (0,3,5,8) (2,3,4,5,7,8,9) (0,1,2,3,4,5,7,9) (0,1,2,4,5,7,8) (1,5,8) (1,2,4,5,7,8,9) (0,1,2,3,5,7,9) (0,1,3,4,5,8,9) (0,2,3,6) (4,6,9) (0,1,2,3,4,7,8,9) (1,3,4,6,8) {70,83,90,107,83,80,36,66,79,71}
[.##.] (0,1,2) (2,3) (1,3) (0) (0,3) (2) {42,28,138,48}
[.##..] (0,4) (2,3) (1,4) (0,1,4) (0,3) (0,1,3,4) {44,53,13,33,57}
[#..#.#..#.] (0,1,3,4,5,6,7,8,9) (0,1,2,7) (2,3,5,6,7,8) (0,3,4,6) (0,1,2,3,5,7,8,9) (1,2,3,4,6,8,9) (1,3,7,9) (0,2,3,4,5,9) (0,1,2,4,5,6,9) (0,6,7,9) {184,188,169,52,162,172,174,57,25,200}
[#####.#.] (2,3,7) (0,2,3,4,5) (2,6,7) (1,3,4,5,6) (0,1,2,3,4,6) (2,5,6) (0,1,3,4,6,7) (0,4,5) (3,6) (0,2,3,4,6) {71,36,71,89,77,29,73,25}
[..#.#] (1,3,4) (1,2) (2,4) (0,1,2) (0,4) (0,3,4) {38,37,38,17,52}
[###.#....] (2,3,6) (1,2,4,6) (0,3,5,6,7) (0,3,4,5,7,8) (4,6) (1,2,3,4,5,7,8) (0,5,8) (3,7) {47,33,46,76,60,63,59,63,43}
[##...###] (2,3) (1,2,3,5) (0,2,3,5) (2,5,6) (2,6) (2,4,5) (2,4) (0,1,4) (2,3,4,5,7) {36,37,213,198,42,58,4,14}
[.###.#.] (0,1,3,5,6) (1,2,3,4,6) (1) (1,3,5,6) (2,5) (0,1,3,4,6) (0,3,5) {22,43,28,48,25,31,42}
[...#...] (0,1,3,6) (0,1,3,4,6) (0,2,3,4,5) (2,3) (2,3,4,5,6) (0,1,5) {39,29,21,33,19,33,18}
[#.#.###..#] (1,2,3,4,5,6,7,8) (0,7,9) (1,2,3,4,7,8,9) (1,2,8,9) (0,1,2,7,9) (0,2,4,5,6,7,9) (6,7) (1,5,6,7,8) (0,2,4,6,9) (0,1,2,4,7,9) (0,9) {65,68,78,25,70,39,69,95,51,92}
[.###..#.] (3,4,6,7) (4,7) (0,1,2,5) (1,2,4,5,6,7) (1,3,7) (0,1,2,4,6,7) {31,43,41,4,44,27,26,46}
[#...##.#.#] (1,2,3,4,7,9) (0,6) (1,2,3,4,5,6,8,9) (0,1,2,4,5,6,7,8) (0,1,2,4,7) (1,3,4,5,6,7,8,9) (0,1,2,3,4,6,7,9) (2,3,4,5,6,7) (0,5,6,7,9) (0,2,3,4,5,6,7,8) (1,7) (1,2,3,6,7,8,9) (2,3,7,8) {73,231,221,196,225,191,212,127,168,195}
[.#.#] (0,1,2,3) (1,3) {9,16,9,16}
[..#..#..#] (2,3,4,5,8) (0,1,4,7,8) (1,6,7,8) (1,3,5,7) (2,4) (1,2,3,7,8) (0,2,3,4,6,7) {10,24,28,35,27,24,21,33,30}
[####] (2) (3) (1,2) (0,1) {7,11,157,4}
[##..#..] (1,2) (0,1,3,4,6) (1,2,4,5) (0,4) (0,3,5,6) (0,1,2,3,4,6) {48,41,29,39,42,28,39}
[#.#.##.#.#] (0,1,6) (0,1,2,3,4,6,8) (0,7,8) (1,2,3,4,5,6,7,8,9) (1,2,4,9) (0,3,4,5,6) (0,3,5,6,7) (0,3,4,5,7,8,9) {50,25,17,39,33,30,42,27,27,13}
[..#.#.#...] (1,2,4,6,7,9) (0,3,7,9) (1,2,4,5,6,8,9) (4,7) (0,3,4,5,7) (1,4,9) (3) (0,1,2,4,6,7,8,9) (0,3,4) (0,1,4,5,9) (0,2,3,6,8,9) (2,3,5,6,7,9) {76,43,51,73,71,54,51,48,29,81}
[.###..#] (1,5) (0,6) (1,2,3,5,6) (0,1,2,4,5) (1,2,3,4,6) (2,3,5,6) (3) {20,28,42,216,22,25,58}
[..#.##...#] (0,3,6,7,8,9) (0,1,4,6) (0,8) (0,1,7,8) (1,3,4,6,7,9) (0,1,2,3,4,5,6,8) (0,3,5,7,9) (2,4,6,7) (1,2,5,7) (0,2,4,5,6) {97,79,65,48,78,65,78,81,47,28}
[###.] (0,1,2) (0,3) (0,2,3) (0,1) (2,3) (1) {20,23,19,20}
[.###] (0,1,2) (1,2) (2,3) (0,3) (0,1) {48,42,36,23}
[..#.....#] (0,2,3,4,5,6,7) (0,1,4,5,6,7) (1,2,3,4,6) (1) (1,3,5,7,8) (0,1,2,4,5,6,7,8) (2,4,6,7) (0,2,3,6,7) (7,8) (0,5,7) (3,4,5,6,7,8) {62,49,36,54,51,73,68,118,50}
[#.###.] (2) (0,1,4,5) (1,2,3,5) (0,1,3,4,5) (1,3,4,5) (1,2,5) (0,1,2,3,5) {25,233,199,219,36,233}
[.....#.###] (0,2,4,5,6,7,8,9) (1,2,3,5,7) (2,3,4,5,6,7,8) (2,3,4,5,6,8) (1,7,8) (1,2,4,6,7,8,9) (4,5,6,7,9) (0,2,4,5,6,7,8) (0,1,2,3,4,5,7,8) (0,1,2,9) (2,5,6) (1,4) {38,54,66,23,52,43,42,54,53,47}
[..##] (0,2) (1,2) (2,3) (1,2,3) {2,30,48,32}
[##..#] (0,1,2) (0,3) (1,3,4) {3,16,0,19,16}
[#..#] (0,3) (2,3) (0,1) {15,0,2,17}
[.####.#] (1,2,4,5,6) (0,1,2) (0,2,3,4,5,6) (0,3,4) (1,2,3,4,6) (2,3,5) (1,3,6) {50,48,65,48,62,34,44}
[#..#.##] (0,1,2,3,4) (0,1,2,5,6) (2,4,6) (0,2,3,6) (0,2,4,5,6) (0,2,3,5,6) (1,5) (1,3,4,6) {46,216,54,44,39,192,53}
[##.....#.#] (0,1,2,4,6,7,8,9) (0,1,2,3,5,8,9) (0,4,9) (0,2,5,6,9) (1,2,4,5,6,7,8,9) (6,7,8) (3,5,6,7,9) (2,5,6,7,9) (4,7) (1,4,7) (0,1,2,4,5,6,7,8) (4) (0,1,3,5,8,9) {68,67,74,42,163,102,98,105,76,93}
[..#.#..] (3,4,5,6) (0,2) (0,1,4,5,6) (0,3,6) (0,1,3,4,5) (0,1,5,6) {49,25,5,36,20,28,33}
[##..#.] (0,1,3,5) (0,3,4) (1,2,3) (0,1,2,3,5) (0,1,2,3,4) (0,1,4) (1,5) {55,41,21,49,37,22}
[####..] (2,4) (3) (0,3,4,5) (1,2,5) (0,5) {23,5,25,17,36,28}
[..#.##.] (0,1,4,5,6) (0,2,3,4,6) (1,5) (2,4) (3,5) (1,6) (2) (0,1,4) {36,57,20,10,37,46,17}
[..#.] (0,2,3) (0,1) (3) (1,2,3) (1) (0,3) {34,42,24,32}
[..##..##..] (0,1,2,5,6,8,9) (1,2,3,4,5,6,7,8) (0,5,7,9) (1,5,6) (0,1,2,3,6,7,9) (1,6,7,8) (0,1,2,3,6,7) (1,2,3,4,8,9) (1,4,5,6,9) (1,2,3,4,5,6,7) {48,271,246,239,212,238,266,242,205,45}
[.#.#.#.] (1,2,4,5,6) (2,3,4,6) (0,1,2,3,4,5,6) (0,1,2,3,5,6) (2,3,4,5) {174,188,202,188,189,189,201}
[..#.##.] (4,5) (0,1,3,5,6) (0,3,4,6) (0,1,2,3,5,6) (0,2,5,6) {40,34,17,37,7,41,40}
[##..] (0,2,3) (0,1) (1,2) (3) (0) (0,1,2) {15,15,20,28}
[.###] (1,2,3) (0,2,3) {4,7,11,11}
[##..] (3) (1,2) (1,3) (0,1,3) (1,2,3) (2,3) {14,45,23,56}
[#.###] (0,2) (0,2,3,4) (1,2,3) (0,1,4) {22,176,182,168,8}
[#..#] (0,1) (1,2,3) (0,3) {27,18,10,29}
[.#..] (0,1,2) (1) (2,3) (2) (0,1) {33,36,34,8}
[#####..#] (1,4,6,7) (0,1,2,3,4,7) (0,1,3,4,5) (0,2,3,5,7) (0,1,4) (0,2,5,7) (0,1,2,5,6) (1,3,4,5,7) {45,58,18,19,47,29,26,23}
[##.#.###] (0,1,2,7) (1,3,4,5) (2) (0,1,6,7) (0,1,3,4,5,6) (0,1,5,6,7) (0,4,5,7) (0,1,2,3,4,5) {29,36,12,29,33,33,23,11}
[.#####..] (3,4) (0,2,5,6) (1,2,3,7) (0,4,5,6,7) (2) (6,7) (1,2,4) (2,5,7) (1,7) {20,17,39,21,25,27,35,51}
[.#####.] (3,4) (0,1,3,4,5,6) (3) (1,5) (2,4,6) (0,1,6) (0,1,3,4) (0,1,2,4,5,6) (0,1,2,3,5,6) {67,74,52,41,54,50,77}
[#...#....] (0,1,8) (3) (0,1,2,3,4,5,8) (0,1,2,3,6,8) (2,3,4,6,7,8) (0,1,2,4,5,6,7,8) (3,4,8) (0,2,3,4,6,7,8) (1,2,5) (0,1,2,3,5,6,8) (1,2,3,4,5,6,7) {62,91,92,90,54,66,68,34,86}
[..##.] (2,3,4) (0,1) (1,3,4) (0,1,4) (1,2,3,4) {12,17,5,7,8}
[..###..#..] (0,2,3,5,6,7,8,9) (5,6,9) (0,2,7,8) (0,1,2,3,4,5,7,8,9) (2,4) (0,2,8) (0,1,5,6,7,9) (0,1,2,4,5,6,7,8,9) {27,15,31,12,19,35,33,26,27,35}
[.##...#.#] (0,1,2,3,4,5,7,8) (0,1,3,4,5,6) (1,7,8) (1,2,6,7) (1,2,3,4,6,7,8) (1,5) (0,3,4,6,7,8) {21,193,12,24,24,23,17,187,186}
[.###.] (0,2,3) (0,1,3,4) (0,2,4) {152,131,21,142,141}
[.##..#] (0,1,4) (0,4,5) (2,4,5) (1,2,3) (1,2,5) (0,2) {43,20,35,7,26,27}
[###...] (0,1,2,5) (1,3) (0,4) (3,5) (0,1,4) (0,2,4) {47,21,31,18,33,27}
[###.#.#.] (0,1,2,5,6) (0,3,4,5) (0,1,3,4,7) (0,2,7) (0,3) (0,3,4,5,6) {70,15,26,44,31,30,13,27}
[###.#...#] (1,2,3,5,7) (0,1,2,5,7,8) (1,2,3,5,6,8) (0,2,3,5,6,7) (0,1,2,3,5,8) (0) (0,4,5) (0,1,4,8) (0,1,2,3,4,5,8) {93,57,60,41,35,78,27,44,51}
[#.#.] (2,3) (0,2) (2) (0) (1) (1,3) {19,12,31,21}
[##.#] (0,1,2) (0,2,3) (1,2) (0,1,3) {45,39,40,37}
[...##.#.#] (3,7) (5,7) (0,1,3,4,5,6,7,8) (0,1,2,3,4,5,8) (2,4,8) (2,6,7) (0,1,2,3,4,7,8) {43,43,70,60,58,27,26,61,58}
[.#.#] (1,3) (0,3) (0,1,2) (0,2) {196,186,187,23}
[...#.] (0,1,2) (3) (0,1,4) (2) (2,3) (1,2,4) (0,2,4) {154,163,53,18,155}
[.#.#####..] (0,4,5,7,9) (0,3,4,5,6,9) (0,1,3,5,7,8,9) (0,1,2,6,8,9) (1,9) (0,1,8) (2,4,5) (0,3,6) {197,35,19,168,47,63,158,34,27,64}
[..#..] (2,3,4) (0,2,3) (1,2,3) (0,1,4) (0,3) (3) {32,14,39,55,14}
[###.###.] (0,1,2,5,6,7) (1,2,3,4,5,7) (4,5,6) (0,2,4,5,7) (1,6,7) (0,1,3,4,7) (0,3,7) {30,42,39,29,42,59,42,53}
[##..#..#..] (1,2,3,7) (0,2,3,4,5,6,7,8) (1,2,3,4,5,6,7,8,9) (0,1,2,4,5,6,7,8,9) (0,1,3,4,5,6,7) (0,3,5,6,7,9) (5,9) (2,4,6,7,8) (0,3,8) {177,191,192,56,190,208,191,203,185,188}
[.####..] (0,2,3,5) (1,2,3,4) (0,1,2,3) (0,1,3,5,6) (0,1,2,3,4,6) (0,4) (4,5,6) {47,34,30,45,24,30,19}
[##.##.#...] (0,1,4,5,7,9) (1,2) (0,1,2,4,6,8,9) (0,3,4,6,7,8) (0,1,2,4,5,7,8,9) (3,5,7) (0,1,3,4,6,7,8) (1,5,6,7,8,9) (1,3,5,6,7,8,9) {61,84,22,50,61,70,63,97,76,65}
[####.##.##] (4,6,7,8) (8,9) (0,1,2,3,4,5,8) (1,2,4,7,9) (3,5,6,7,8) (1,2,7) (5,7,8,9) (0,1,3,4,5,8,9) (1,3,6) {30,67,33,52,44,41,25,35,52,42}
[.#.#####.#] (0,2,3,4,5,7,8) (0,2,4,9) (1,2,4,6,7,8,9) (2,3,9) (0,7) (0,2,5,6,8) (0,2,6,9) (0,1,2,4,5,6,8,9) (2,3,4,8) (1,6,8) (0,1,3,4,5,6,9) {59,37,76,28,45,35,56,19,41,72}
[...####..#] (0,3,4,7,8) (0,1) (1,3,5) (5,6,7,9) (5,9) (0,3,4,5,6,8) (0,3,4,5,6) (0,1,2,3,7,8,9) (0,1,3,7,9) (0,1,3,4,5,6,8,9) (3) (1,2) {62,44,26,82,47,46,34,32,37,21}
[.##..#] (4,5) (1,3) (0,1,3) (0,2,3) (0,1,2,3) (4) (0,2,4,5) {40,49,27,52,34,16}
[.#.#..#.] (2,3,6) (0,3,4,6) (0,4,5,6) (1,3,4,5,6,7) (1,4) (2,3) (0,2,4,6) (0,1,4,6,7) {64,22,233,236,76,21,268,14}
[#######] (0,1,2,4,5) (0,1,2,3,6) (0,3,5) (0,1,2,6) (2,5,6) (0,1,2,5) (0,3,4,5,6) (1,3) (1,2,3,5,6) {81,71,68,53,28,61,50}
[#.##....#] (6,8) (0,1,2,4,5,6,8) (0,3,8) (1,2,6,7,8) (0,1,7,8) (0,2,3,5,6) (0,3,5,7,8) (2,4) (2,3,5) (4,5) {33,24,45,33,122,136,37,25,54}
[##..#] (2,3) (1,3) (2) (4) (1,2,4) (0,3,4) (1,2,3,4) {12,10,14,28,28}
[..#.#..] (1,6) (0,1,3,5,6) (4,6) (1,3,4,5) (2,4) {10,16,12,16,23,16,15}
[##...#.#] (0,1,2,3,4,5) (0,1,3) (0,2,4) (2,4,5) (1,2,4,5,6,7) (6) (1,2,4,6,7) (1) (0,3) {39,52,67,29,67,42,31,31}
[...#] (2) (1,3) (2,3) (0) {7,2,29,19}
[##...###.] (1,6) (1,3,5,6,7,8) (0,1,2,3,4,5,7,8) (0,7,8) (0,2,3,4,5,7,8) (1,5,6,7,8) (1,4,5,8) (0,1,2,4,8) (1,2,3,4,5,6) (2,4,6,8) {37,63,53,42,57,59,56,53,77}
[#.##] (0,2,3) (1,3) {8,1,8,9}
[.#..##] (1,2,3,4,5) (3,5) (0,2,3,4) (2,5) {4,0,10,19,4,21}
[#.#.#..#] (0,1,2,5,7) (0,1,3,6,7) (1,2,4,5,7) (3,4) (2,3,5,6,7) (1,2,6) (0,3,4,5,6,7) {19,29,28,138,131,24,35,31}
[##..#..###] (0,1,3,5,6,7,8) (1,2,4,5,8,9) (0,3,5,8,9) (0,5,6,7,9) (1,4,6) (0,5,8) (0,2,3,5,8) (1,2,3,5,6,7,9) (1,2,5,9) (1,2,3,6,8,9) (0,1,2,4) {59,208,199,187,27,224,179,159,85,210}
[#..#.##.#] (2,8) (0,1,4,6,8) (0,1,2,4,5,6,7) (0,5,8) (1,2,4,5,6,7,8) (0,3,5,6,7,8) (0,3,4,5,7) (3,4,5) (1,2) (3,6) {232,208,198,46,229,227,221,215,43}
[.#..#.] (2,3,4) (3,5) (1,2) (0,2,3,4) (0,2) (3) {13,12,32,212,11,18}
[.#.###] (0,3,5) (1,3,4) (0,5) (2,4,5) (0,2,3,5) (0) (1,3) (0,1) {162,21,118,146,11,146}
[.#..] (1,2,3) (1) (0,1,3) {19,47,14,33}
[..#...] (0,1,2,5) (2,3,4,5) (2,4) (0,1,2) (1,2,3,5) (0,3,4) (0,1,2,3,4) (2) {39,34,42,28,30,8}
[#.####] (0,3,4) (1,5) (0,2,3,4,5) (3,4) {18,20,4,18,18,24}
[......#] (0,2,5) (0,1,2,3,6) (1,2,4,5,6) (6) (0,1) (0,1,3) (0,6) (0,1,2,4,5,6) {53,29,35,11,12,32,33}
[##.#..] (2,4) (0) (1,3,4) (4,5) (2,3) (0,1,3) (1,2,3) (0,1,2,4) {193,207,208,45,209,14}
[###.] (0) (1) (0,1,2) (1,3) (0,2) (1,2) {19,35,18,19}
[..#.#...#] (1,4,6,8) (0,2,4,5,6,8) (1,4) (1,2,3,4,6,8) (1,3,4,5,6,7,8) (2,3,8) (1,6) (7,8) (0,5,7,8) (0,5,6) (0,1,2,4,5,6,8) {36,57,31,15,70,40,53,21,68}
[..#.#....] (0,4,7,8) (0,3,4,5,6) (1,2,3,4,5,6) (1,6) (1,4,5,7) (2,3,4,5,7) (0,2,4) (0,1,6) (2,3,4,5,6,7,8) {62,44,45,36,84,50,46,47,19}
[.###..###.] (2,4,6,9) (1,2,3,4,6,7,8,9) (0,4,5,7) (0,7,9) (1,3,4,5,8) (2,4,6,7,8,9) (3,5,6,7,9) (0,1,2,3,4,5,8,9) (0,2,3,4,5,6,7,8) (0,2,3,4,7) {54,29,149,57,172,61,143,162,134,168}
[##..##] (1,5) (0,1,2,3,5) (0,4) (1,2,4) (0,1,3,4) (0,2,4,5) (1,2,3,4,5) {35,40,39,35,32,38}
[...#] (0,2,3) (0,2) (2,3) (0,1) (0) {51,15,37,26}
[....#.] (0,2,3,4,5) (0,2,4) (1,2,3) (1,5) (0,1,2,5) {50,157,192,159,35,32}
[#..#.#] (2,3,5) (0,3) (0,1,5) (0,1,4) (0,1,2,3) (2,3,4,5) {34,29,12,17,20,22}
[#......#] (1,2,3,4,5,7) (0,2,5) (0,1,2,4,5,7) (0,2,4,5,7) (0,1,2,3,5,7) (0,3) (4,7) (2,3,4,6) (0,1,4,6,7) (1,7) {46,41,51,37,53,40,16,54}
[.#.#.#] (0,3,5) (1,3,4,5) (1,3,5) (2,3,4,5) (0,2,5) (0,1,3,4,5) {35,19,36,51,35,69}
[#.##.###] (0,2,3,4,5,6,7) (1,5,7) (1,2) (0,4,6) (0,1,3,4,5,6) (1,2,4) {11,13,12,11,12,21,11,20}
[..##.....] (0,1,2,3,4,8) (7) (1,3,4,8) (2,3,5,6,8) (2,3,4,5,7) (3,7,8) (0,1,2,7,8) (0,1,2,6,8) (3,5) (0,1,2,4,5,7) {44,46,229,231,198,210,15,235,59}
[...###.#] (0,1,3,5,6) (3,5) (3,6) (1,3,4,7) (2,3,7) (0,1,4,5,7) {12,30,10,30,30,12,2,40}
[.##.###.##] (0,1,2,3,4,6,7,9) (1,4,5,7) (0,2,5,6,8,9) (0,1,2,4,5,6,7,9) (1,3,4,6,7,9) (1,2,4,5,6,8) (0,3,4,5,6,8,9) (6) (0,4,6,8,9) (9) (3) {35,51,25,24,64,34,59,48,19,61}
[##..#..] (1,3,5) (1,2,5) (0,6) (0,2,3,4,5) (1,2,3,4,6) (3,4,5) (1,6) (0,1,2,3,5,6) {27,30,36,35,19,36,22}
[...#..##.#] (1,3,4,5,6,7,8) (0,1,3,4,5,8,9) (3,4,5,8) (0,4,6,7,8,9) (1,2,3,5,6,8) (4) (0,2,5,6,7) (1,2,3,5,8,9) (2,5,6) (1) (4,6) (0,1,2,7,8) {32,47,47,38,57,57,62,37,52,12}
[.##.#..] (1,3,6) (2,3,4,5) (0,4,5) (0,2,3,5,6) (1,2,3,4,6) {26,24,15,33,27,28,31}
[.....####.] (0,2,5,6,7,8) (0,2,3,4,5,7,9) (0,1,3,5,6,8,9) (0,3,4,5,6,7) (0,2,4,5,6,8) (0,2,3,5,7) (0,1,3) (0,4) (1,2,3,4,6,7,8) {67,32,54,58,47,51,47,49,40,14}
[#.#..###.] (2,4,5,6,7,8) (1,2,4,7,8) (1,3,4,5,7) (0,1,2,3,4,5,6,8) (1,2) (1,3,4,5,6,8) (0,1,3,4,5,7) (0,1,2,4,6,7,8) (7,8) (1,2,3,4,5,7,8) {51,90,66,62,103,76,71,81,100}
[.##.#.#.##] (3,4) (1,2,3,4,6,7,9) (0,1,3,5,7,8) (1,6,7) (1,4,5,6) (0,1,4,8) (0,1,8) (2,3) (0,1,3,4,8) (2,7,8,9) (0,2,3,7) (5,6,9) {59,79,35,70,76,37,46,39,61,43}
[###....#..] (0,1,2,3,4,5) (0,2,3,6,7,8,9) (0,2,3,5,7,8,9) (0,1,3,4,5,6,7,9) (1,2,3,6,7,9) (0,2,3,4,5,6,8) (1,5) (0,1,2,3,4,5,7,9) (0,4,6,7) (0,3,4,5,8) {89,64,88,99,61,65,65,83,40,74}
[..#..#.#..] (1,2,3,5,7,8) (1,3,5,6,7,9) (0,3,5,6,8,9) (1,2,3,4,5,6,8,9) (0,2,3,5,6,7,8,9) (1,2,7,9) (0,1,2,3,5,9) (2,3,4,5,6,7,8,9) (4,5,8) (1,6) (4,6,8) (2) (2,3,4) {38,63,75,100,59,103,81,55,82,84}
[####..] (0,1,2,5) (1,4,5) (0,2,3,4,5) (2,3,4) (0,3,4,5) {196,20,187,205,223,214}
[###.] (0,1) (2) (2,3) (0,1,2) (0,3) {44,34,29,17}
[.#.#.#..##] (0,1,2,4,5,6,7,8,9) (2,8) (0,1,4,5,6,7,8,9) (4,5,6,8,9) (0,1,7,8) (0,1,2,3) (0,3,4,6,7,8,9) (0,3,5,6,7,8) (1,2,3,5,9) (0,4,6,9) {62,49,33,39,52,41,53,34,54,71}";
const SAMPLE_INPUT: &str = "[.##.] (3) (1,3) (2) (2,3) (0,2) (0,1) {3,5,4,7}
[...#.] (0,2,3,4) (2,3) (0,4) (0,1,2) (1,2,3,4) {7,5,12,7,2}
[.###.#] (0,1,2,3,4) (0,3,4) (0,1,2,4,5) (1,2) {10,11,11,5,10,5}";
use crate::{ComparisonOp, OptimizationDirection, Problem, Variable};
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Machine {
indicators: Indicators,
button_wirings: Vec<ButtonWiring>,
joltage_requirements: Vec<i64>,
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Indicators(Vec<bool>);
impl FromIterator<bool> for Indicators {
fn from_iter<T: IntoIterator<Item = bool>>(iter: T) -> Self {
Self(iter.into_iter().collect())
}
}
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct ButtonWiring(Vec<usize>);
impl FromIterator<usize> for ButtonWiring {
fn from_iter<T: IntoIterator<Item = usize>>(iter: T) -> Self {
Self(iter.into_iter().collect())
}
}
fn parse_machines(input: &str) -> Vec<Machine> {
input.lines().map(parse_machine).collect()
}
fn parse_machine(line: &str) -> Machine {
let mut parts = line.split_whitespace().peekable();
let indicators: Indicators = parts
.next()
.unwrap()
.chars()
.flat_map(|c| match c {
'[' | ']' => None,
'.' => Some(false),
'#' => Some(true),
_ => unreachable!("Invalid indicator character"),
})
.collect();
let mut button_wirings = Vec::new();
while parts.peek().unwrap().starts_with('(') {
let button_wiring_str = parts.next().unwrap();
let button_wiring: ButtonWiring = button_wiring_str[1..button_wiring_str.len() - 1]
.split(',')
.map(|s| s.parse::<usize>().unwrap())
.collect();
button_wirings.push(button_wiring);
}
let joltage_requirement_str = parts.next().unwrap();
let joltage_requirements = joltage_requirement_str[1..joltage_requirement_str.len() - 1]
.split(',')
.map(|s| s.parse().unwrap())
.collect();
Machine {
indicators,
button_wirings,
joltage_requirements,
}
}
fn get_least_presses_joltage_microlp(machine: &Machine) -> i64 {
let counter_count = machine.joltage_requirements.len();
let button_count = machine.button_wirings.len();
let mut problem = Problem::new(OptimizationDirection::Minimize);
let vars: Vec<Variable> = (0..button_count)
.map(|_| problem.add_integer_var(1.0, (0, i32::MAX)))
.collect();
let mut counter_changing_button_indices = vec![Vec::new(); counter_count];
for (index, button_wiring) in machine.button_wirings.iter().enumerate() {
for &button in &button_wiring.0 {
counter_changing_button_indices[button].push(index);
}
}
for (counter_index, button_indices) in counter_changing_button_indices.iter().enumerate() {
let expr: Vec<_> = button_indices
.iter()
.map(|&index| (vars[index], 1.0))
.collect();
problem.add_constraint(
expr,
ComparisonOp::Eq,
machine.joltage_requirements[counter_index] as f64,
);
}
let solution = problem.solve().expect("microlp solve failed");
vars.iter().map(|&var| solution.var_value(var) as i64).sum()
}
fn part_2_microlp(input: &str) -> i64 {
parse_machines(input)
.iter()
.map(get_least_presses_joltage_microlp)
.sum()
}
#[test]
fn test_aoc_part_2_microlp_puzzle() {
let total = part_2_microlp(PUZZLE_INPUT);
assert_eq!(total, 21696);
}
#[test]
fn test_aoc_part_2_microlp_sample() {
let total = part_2_microlp(SAMPLE_INPUT);
assert_eq!(total, 33);
}
}