From 6ace94fc43d95b7bedbd6fdcc207572385479f58 Mon Sep 17 00:00:00 2001 From: Irene Knapp Date: Sun, 20 Dec 2020 01:20:16 -0800 Subject: 20 --- 20/Cargo.toml | 11 + 20/input | 1728 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 20/input.small | 107 ++++ 20/src/main.rs | 655 +++++++++++++++++++++ 20/tests/main.rs | 14 + Cargo.lock | 8 + Cargo.toml | 1 + 7 files changed, 2524 insertions(+) create mode 100644 20/Cargo.toml create mode 100644 20/input create mode 100644 20/input.small create mode 100644 20/src/main.rs create mode 100644 20/tests/main.rs diff --git a/20/Cargo.toml b/20/Cargo.toml new file mode 100644 index 0000000..21adb16 --- /dev/null +++ b/20/Cargo.toml @@ -0,0 +1,11 @@ +[package] +name = "advent_20" +version = "0.1.0" +authors = ["Irene Knapp "] +edition = "2018" + +[dependencies] +advent_lib = { path = "../lib" } + +[dev-dependencies] +assert_cmd = "0.10" diff --git a/20/input b/20/input new file mode 100644 index 0000000..2cb7a6f --- /dev/null +++ b/20/input @@ -0,0 +1,1728 @@ +Tile 3391: +#.......## +#..#.....# +..#....#.# +##...##.## +#.##.#.... +.#.......# +.#.......# +#..#..#..# +.......#.# +.##.#.#### + +Tile 2549: +.#...##... +##.#...... +....####.. +######..## +...##..#.# +......##.. +.##..#...# +...#....## +..#....#.. +.#.#..##.. + +Tile 1109: +.#.###..#. +##..#.#... +#...###..# +#...#..#.# +.......### +#.#....#.# +.#.#.#.### +.#.#.#.... +.#....#... +..###.#... + +Tile 3023: +##.#.#.##. +...#..#### +.##.#...## +#.##.....# +###.##...# +.......#.. +...##..##. +##.....#.. +###....#.# +.#...#.##. + +Tile 2833: +.#...##### +....#...## +....##...# +#...###... +#...###... +..#.#..#.# +##.....#.# +..#....... +##..##...# +###....##. + +Tile 2347: +#...###.## +#..##.##.# +.#..#.###. +....##..#. +.......#.# +#........# +##..#...## +..#......# +#...#..... +#....####. + +Tile 2311: +####..##.. +#......##. +##..#..... +#..#..#..# +###.#..### +.#...#...# +....#..... +##...##..# +#....##... +.#...####. + +Tile 3137: +...#....#. +#..#.##... +#..#.....# +...#....#. +#..###.##. +..#..#.#.# +#........# +#......... +#.##....#. +#.#.#.#.#. + +Tile 2333: +#.###..#.# +.#....#..# +#....##..# +##....#.## +#..##.##.. +.##..##### +#.....#..# +#.......#. +.#..#.###. +...#....## + +Tile 1439: +..###....# +##.#...#.. +..##.#...# +.##....#.. +#...#..... +#.#.#..... +.#.#....## +.......##. +....#..... +##.##.#..# + +Tile 1999: +....#.#.#. +.....#.... +#...###... +...#..#... +....##.#.. +#.....#... +.....#.... +#..#.##... +##.......# +#.#....### + +Tile 2351: +#..#.###.# +##..##..## +#...#..... +.......### +#....#...# +##....#.#. +#...#..... +.#...#...# +#..#...#.# +##.#..#..# + +Tile 3547: +...#.#...# +###...#..# +.........# +#.#...#... +#.#..##..# +.#.####.#. +#..#.#.#.# +.##......# +#......#.. +.###...### + +Tile 3877: +..##...##. +..#.....## +.#..#....# +##...#...# +##.#..#..# +.#..#....# +..##.#.#.# +......#.#. +#.....##.. +####..#.## + +Tile 2309: +.##.#..#.. +....#..#.# +..#.....## +.........# +#..#...... +#........# +..##.#.... +......#... +........## +#.##.###.. + +Tile 1303: +#.##.####. +.......#.. +...####... +.....#.... +#......#.# +......#... +.#.#.....# +#........# +#.#..#.#.# +##.##.#### + +Tile 3797: +.#.###..#. +#...##.... +#.##.##... +#.##.....# +........## +#.#....... +#...##.... +.......... +.....#..## +#..##..... + +Tile 2161: +.#....##.. +...#.....# +#.....#..# +#..#.#.#.# +.......... +....#..#.# +##...#...# +.#..#....# +......#... +#.#..#.#.. + +Tile 3463: +##.##..### +##.#..##.. +.##..#.##. +.......... +#.#...#..# +....#...## +#..#.....# +#......... +.......#.. +#.#.#.#### + +Tile 1657: +#.##.##.## +.....#.... +.#.....#.# +.#......#. +#...##...# +##.####... +#.#...#... +#..##..... +#..###.... +###.##...# + +Tile 2647: +##.##..##. +#..#...... +##....#### +#......#.. +.#.#...#.. +.#..##.#.. +##...##... +#.##...#.. +..#....#.. +###...###. + +Tile 2557: +.###.#.#.. +#.#...#.#. +#####....# +#..#.....# +..#.....#. +...#...... +#....#.... +.#..#....# +........#. +.#.#.#.##. + +Tile 2113: +###.#..... +.####..... +.....#...# +.#......#. +........#. +...#...... +......#.#. +.......... +.......... +..#.#.#### + +Tile 2729: +###...##.. +...#....#. +#.#....... +....###.## +#..#..##.. +..##..#### +##....#### +#...#.#..# +##...##..# +###.#.#..# + +Tile 2741: +.####..### +.#.#.#.#.. +.##..##.## +#.##...#.. +#..#.#.#.. +#...#....# +#......... +##...#.... +.......... +#####.#... + +Tile 1901: +#.#..##..# +...#.#.... +.##...#... +##........ +..#.#..#.. +...#.##..# +..#..###.. +..##...... +.#.#.....# +#.###.#..# + +Tile 2843: +#...##..## +.........# +##.###.#.. +.........# +#..###.... +..##...... +##......## +..#..##### +##....##.# +##.##...## + +Tile 3229: +#...###.#. +.......#.. +###...#.#. +#.......## +...#.#...# +#.##...#.. +##.###...# +..#....... +....#..... +#....####. + +Tile 1289: +..#.###.## +......#.## +..##...#.. +#......... +#..##..... +###....#.. +.........# +...##..##. +.#...#.... +.#.###...# + +Tile 2953: +..#..##... +...#.#..#. +........#. +#.#......# +###..#.##. +...##.#..# +#...#..##. +.......#.# +.........# +#.#.#.##.# + +Tile 1579: +..##...... +.....#.... +#..#.##..# +.#........ +.....#.... +#.......## +#..#...... +#......... +...#..#.## +##....##.# + +Tile 3359: +.##..####. +.......#.# +....##...# +.........# +.......... +....#....# +....#....# +.#.#.#..#. +...#.#.... +#######... + +Tile 1823: +####..##.# +.........# +...##..... +..#....... +.#...##... +#..#...... +.......... +#....#...# +#...#.#..# +#.#.##.... + +Tile 2659: +##.#.###.# +#......##. +..#.#....# +##...##... +#.#..#..## +#...#..... +...#.#.... +.......#.# +.#..#..#.. +....###..# + +Tile 1097: +.#.#.#.... +##..#...## +###.....#. +.#.....### +##...##..# +...#.##... +.....#..## +#..#.#.... +.#...#..## +.#.##..##. + +Tile 2341: +####.#...# +....#...## +#.##.....# +..#..###.# +...#.#.### +#...#....# +.##......# +#....#.... +##....#.#. +#..#....#. + +Tile 2089: +#.###..##. +#..#####.. +....##.... +#.....#.## +.....###.# +.#..#.#..# +....#.#.## +#.......#. +###......# +###..####. + +Tile 1583: +#.#...#... +#....#.#.# +.........# +#.....#... +...#...... +#........# +#......#.. +.......#.. +.........# +####...#.# + +Tile 3011: +##.####... +.##......# +...#.....# +#.......## +#..#...... +##........ +##..#...#. +##..#..... +#...##..#. +.###.#.#.# + +Tile 1481: +###.#.##.. +..###...## +....##.#.# +..#......# +..#.#..... +..##...... +#........# +......#... +#..#..#..# +#.#.###### + +Tile 2927: +##..##.### +#.##.#...# +....#..#.# +.#....#.## +#...#.#.## +#.#....... +#......... +......#..# +.#.#.#...# +###...#.#. + +Tile 2633: +.##..##.#. +.#..#.#### +..#..##..# +..#.#....# +.........# +..#.....## +........#. +##....#.## +.......##. +....#####. + +Tile 2371: +#..#.####. +....#.#... +..#...#..# +......#... +..#.##.#.. +.#..##.#.. +....#....# +.#.......# +#.#....... +#.##.#.#.. + +Tile 1733: +#.######## +.#.##..#.# +#.#..#.... +..###.##.. +#..##..##. +.##.#..... +#...#.#... +#..##..### +#........# +..#....#.# + +Tile 3583: +#.#.#..... +....#....# +...#.#.... +....#..... +#........# +#.#..##..# +.........# +#....#.... +#.....#... +...#..###. + +Tile 1291: +.##.###.## +#...#.#.#. +#.##.#.##. +....#..#.# +#.##.###.. +#.##...#.# +....#.#.#. +.###.#...# +.#.#.....# +##..#..### + +Tile 3067: +#.#...##.# +#........# +...##.#.#. +#.##.....# +..#....... +#..#...#.# +#....#.... +#.#...#... +.......... +########.# + +Tile 1621: +.#..#.#..# +#...#..#.. +..#.#.#..# +##..##...# +#.#....... +...#..#..# +##.#.....# +..#.#..#.. +...##.##.# +#....#.... + +Tile 3719: +#..###.... +...##..##. +..###..... +.....#.### +##...#..## +#........# +.....#...# +#...#...#. +#.###.#... +#..#.#..## + +Tile 1217: +#.##..#.## +#.....#... +...#.#.... +.#..#.##.. +...##.#.## +#.#.#..#.. +.......... +#.......## +.........# +######..#. + +Tile 2503: +..##.#.#.. +#....#.... +#......... +.#...#.##. +...#.#.... +.........# +..##...... +.##.....#. +.#.....#.. +###.##..#. + +Tile 2971: +#...###..# +#...#.#.## +#........# +#.#....#.. +##........ +#.....#..# +.#........ +.#........ +.#.###..## +.##...#..# + +Tile 2593: +#..#.####. +....#...#. +#.##.#.... +......#.#. +........## +#......... +##.#...... +#...#.#..# +..##...#.. +...####.#. + +Tile 2711: +##..##...# +#....#...# +.........# +##....#.## +##......## +######.... +#...#...## +.....#.... +....#.#.#. +....##.#.# + +Tile 3929: +#.#.#..### +..#.###.#. +.....#...# +.....##.## +..#.#..##. +#........# +#.###..### +..#..#.#.. +.##.....#. +#.#.#.#.## + +Tile 2473: +###....#.. +..##...##. +.#...#...# +.#..#...#. +##......## +#......... +#....#..#. +##........ +..##...... +..#..#..## + +Tile 1103: +.#######.. +#....#.... +.......#.. +.......#.. +##.#.....# +.......#.# +#.....#... +#......#.# +#..#..#... +######..#. + +Tile 1907: +#..##.#..# +#..##.#..# +.##.#.#.#. +########## +....####.. +##...#.... +..##.#.... +#...#....# +..#.####.. +.#.##..### + +Tile 1553: +###.#...#. +#....#.#.# +..#......# +....##...# +......#..# +###...#.## +##...#.... +.......... +..#....... +###.#####. + +Tile 1637: +#####.##.# +.......#.. +...#.#.... +#......##. +#.###...## +.......... +..#.###.#. +#....##..# +#..#.....# +#..##.#... + +Tile 2789: +##..####.# +..#....... +#......... +.......#.. +.#........ +.......... +#....##... +####.....# +...##..#.# +.#.###.#.. + +Tile 3301: +#.#....#.. +.#.....### +##......## +.#.#...... +#..#...#.. +...#...... +.#.....#.# +#........# +#.....#.#. +.###.#.... + +Tile 2957: +#.#.##..#. +#..#...... +.##...#.#. +..#....... +####...... +.....#.#.. +#.#......# +#...###... +#..#..##.. +###..#.#.. + +Tile 2389: +##.#..#... +.#.......# +..#....... +###....#.# +.#....#... +....#..... +....#..#.# +#......#.# +..#.##.##. +...###.##. + +Tile 1087: +##..##.### +#...#....# +.#.##.#.#. +.#.......# +#.#..#...# +.#..##...# +##.#..#.## +.#...#.#.. +#........# +#..#...#.. + +Tile 2251: +#..####... +#..##..#.. +#..#.##... +.#.#.....# +.##.#.#... +#.##.....# +....##.... +.........# +...#.....# +##.#.#..#. + +Tile 2969: +####.##..# +##........ +...#...#.# +.......#.. +###.###### +..#..#.... +...###...# +#......### +.#........ +#.###...## + +Tile 1669: +.#...#.##. +#.##...#.# +#...#..... +#...##.#.# +#.....#... +...#.#.#.. +...#.#.... +..#.#.#..# +#.#.#.##.# +#..#.##..# + +Tile 2713: +#...#.#.## +...##..#.# +.#..#..### +..#.#..... +..#....#.# +..#...#... +#..#....## +##.....#.# +#....#.... +.##.....## + +Tile 3659: +...#....#. +#......... +#..#.#.#.# +#..#..#.## +.#.#.#..## +#....#..## +..#......# +..#.....#. +.##.##.#.. +####..#..# + +Tile 1609: +...#...... +.......#.. +##.....#.# +#...#..#.. +....#..... +#.......## +#...##.... +#..#..##.# +#####.###. +..##...... + +Tile 1979: +#..#.##### +.....#.#.. +.#....#.#. +###.###..# +..#....#.# +..#....#.. +#....#.##. +....#..#.. +....#..... +.#.#..#.## + +Tile 3457: +##.#.#..#. +.#......## +#.##..#..# +#.#..#.... +..#..#.... +##..#..#.. +.........# +.......#.# +.........# +###.##.#.. + +Tile 2531: +#..##...## +##....#..# +#......... +.....####. +.#.####..# +##..##.#.# +#.....#..# +#.....#..# +.....#.##. +#..#..##.# + +Tile 2267: +###..##..# +..#......# +.#..#....# +#..#...#.. +......#..# +...#...... +##.....#.# +##.#....## +.#.....#.. +###.##..#. + +Tile 3853: +##.##.##.# +.....#..## +....#..#.. +.#...#.... +.........# +....#..... +#...#....# +#......... +#........# +#.#..####. + +Tile 3433: +#...#.#... +....#.##.. +###..##.## +##.#...#.. +.#.#.##.#. +......#..# +...##..##. +##....#..# +..#..##..# +###...#### + +Tile 3109: +###.####.# +.#.#....## +.#...#.... +..#...#..# +.#.#...#.. +#......... +...#.##.#. +.......#.. +..#..#.... +#.##.##### + +Tile 2399: +####.##.## +...#.....# +..#.#..... +.#.##..... +...#.#...# +..#..#..#. +...#..#..# +#....#..#. +.......... +#....##### + +Tile 2141: +#.#...#... +#........# +.#.#.##.#. +..#...##.# +..#......# +.........# +#...#...#. +.#.####..# +..#.....## +###..#.#.# + +Tile 3187: +.##.##.#.# +...#.##.## +##...#...# +......#..# +.##.#...## +..##...#.. +#......#.# +...#..###. +#.#....#.# +.#..##.#.# + +Tile 3329: +.#.##..#.. +.#........ +#..#.....# +#.###..#.# +..#.#..... +.#..###..# +..#.....## +#.#..#.### +##.##..#.# +##..##.##. + +Tile 2693: +#..#####.# +.........# +##.#....## +#..#.....# +####.#.... +..####.#.# +....##...# +##.#.....# +#.......#. +.....##### + +Tile 2357: +.#..##...# +......#.## +....#.##.. +#.##.....# +..#.#...## +#........# +#..#...... +#......... +....#..... +...##...## + +Tile 1381: +.#.....#.# +#.....#### +#......... +.#.###.#.. +##....#... +.......... +#.#.#.#..# +.#####.#.# +#.......## +#.####.... + +Tile 3761: +#....##... +#......#.. +#...#...## +.........# +.......... +.#.##.#.#. +...#....## +#...#...#. +#....#.... +.###..#### + +Tile 1889: +..#.#....# +..#..#.... +.#..#....# +.......... +..##..#.#. +.......... +.....#.##. +#..#...... +#......#.. +.#...#..#. + +Tile 3511: +..##.....# +.#....#... +####.....# +.#...#...# +#..##.##.. +#.#.....#. +.#.#...... +#...#..... +#.#....... +###.###..# + +Tile 1619: +...###.##. +#...#.##.# +###....... +..#..##.## +..#.##.... +..###....# +#......### +....###.## +..#....### +..##.##.## + +Tile 1721: +###....#.. +......#.## +.#.....#.# +##.##..### +.#....#... +#...#..#.# +#.#.#....# +...#..#... +#.......## +.######.## + +Tile 3539: +.#.....#.# +...##...## +#.#...#... +..#.#....# +#..#....## +#.#..##..# +##..#..#.# +.....#.#.# +.#..#.#.## +..#...###. + +Tile 3847: +##..###..# +#..##..#.# +.......##. +.#.#.....# +###...#... +.##.##...# +....#.#... +..#..##..# +#......#.. +####..###. + +Tile 3257: +.##.#.#... +###...#.#. +.......... +.......... +..#...#..# +.........# +#.....#..# +...#....#. +#..##.#.## +####...### + +Tile 3851: +#.#.####.. +#.#....#.# +#......... +####.#...# +.###.....# +##..#..#.# +.#.###.... +.........# +####.....# +.#.#..#.## + +Tile 3881: +....#..#.# +#......#.. +.......... +#....#.... +#.#.#.#..# +....#..#.. +.....#..## +#.#...#.#. +....#..... +..#.#..### + +Tile 2539: +#.####.#.# +...#.###.# +####...#.. +#..#...### +......#.#. +#..#.....# +#....#..## +...#...#.. +#.#....#.# +.##.##.#.# + +Tile 1301: +##.##..#.# +.......#.. +#..#.#.#.# +#...#..... +#####.#... +...#.#.... +..#....#.# +...#..#..# +#...#...## +.###.###.. + +Tile 2027: +##..###.#. +##..#..... +#.#..#.... +.##...#... +..##.....# +#......#.# +#.#.....#. +##..#....# +.......... +#..##.#... + +Tile 3001: +.#...#...# +..#.#...#. +...#.##... +#......... +.#...#.... +#.......## +##....##.# +##.#....## +...#.....# +#...###### + +Tile 3767: +#..#.#...# +##..#....# +...###...# +.....#.#.. +........#. +.#...#.... +#..##....# +.......... +##..#..#.# +.#......## + +Tile 1433: +.##.#.##.# +#...#..... +......##.# +##.#....#. +.#.##...## +#..#.##..# +.#.##...## +#...##.#.# +...#...#.# +..#.....#. + +Tile 1931: +##.####.#. +#.##..#..# +#....#...# +#....#.... +...####... +...#...... +#........# +####..#... +...###.... +.#..#.#... + +Tile 3491: +.##..#.#.# +##...#...# +#..#...... +#.#.#....# +........#. +#.#......# +##........ +.#.......# +.##......# +####.....# + +Tile 2683: +...#....## +...#.##.#. +..##.#.... +....##...# +..#.##..#. +...##.#.## +#..#.#...# +..#..#.... +#...#..#.. +#..#####.. + +Tile 3323: +.....#.#.# +###....... +....#.#... +..#......# +.##..#.... +#.....###. +.#....##.. +.....#...# +....#..#.# +.....###.. + +Tile 1061: +#....###.. +#.#.#.#... +#......#.. +#...##...# +#........# +.....#.### +##....#..# +....###..# +###....#.. +..##.##... + +Tile 1163: +####.###.# +#..#.....# +#........# +#...##...# +.##..#.#.. +..#.#.#... +.....#.#.# +##........ +.#....#.#. +###..##### + +Tile 3779: +.#####.#.. +####.##.#. +##...##..# +#.###...#. +..#....... +#........# +...#...#.# +.#.#...... +#...#.#... +.#.#..##.# + +Tile 1993: +#..##.#.## +.#...#...# +#..###.... +#.##.....# +#.....##.# +#...#.#..# +#.#.#..... +.#.#.#...# +....#.#.#. +##......#. + +Tile 1213: +#..##..#.. +..##..#..# +#......... +.##.....#. +#......... +........## +........#. +..#.###..# +##.......# +..##...#.# + +Tile 3373: +#.##..#.## +#......... +.....#.... +#...#..... +#...##...# +..#..#.... +#......... +.......... +#...##..#. +..##.###.# + +Tile 2017: +#...#.##.# +#...##.... +........## +...#...#.# +.......... +##...##..# +.....#...# +#....#.#.# +#........# +#.##...#.. + +Tile 1367: +..###.#### +#..#.#..#. +#...##..#. +.#.....#.# +##......## +.#.#.....# +.....#.... +........## +#...##...# +###.#...## + +Tile 2417: +.#.#.#.#.. +#.##..#.## +#.#......# +###....... +#..#.....# +...#.....# +..#....... +#.#.#....# +.#...#.... +#..##..... + +Tile 1871: +##..#.##.# +.#.#..#### +..#...###. +.##....... +....##..## +..#....#.# +###....... +.#....#.## +.#.#...#.# +#.###..#.. + +Tile 1601: +#####..... +.....#.... +......#..# +.#..###### +#..#.##..# +....#.#... +#.#....... +#.#..##..# +#..##.#.#. +..#..##.## + +Tile 1471: +.#######.. +..#..#...# +.##..#...# +##..#.#..# +......#..# +.#...#.... +#........# +..#......# +.....##..# +###.#....# + +Tile 2521: +###.....## +###.##.##. +......##.# +#...#.#... +........## +##.####... +...###.... +#..#.#...# +#..####... +#.#.#....# + +Tile 1279: +##..#..#.# +.#...#.#.# +#.......#. +#.#.#..#.. +#.#......# +#......### +#..#..#..# +#.#.#...#. +#...#....# +..#......# + +Tile 1069: +#.#.#...## +......#.## +#....#.##. +......#..# +##.#.#...# +#.#.#.#.## +#.......#. +##..#....# +......#... +.##..#..## + +Tile 2143: +#.#...#.#. +#......... +..#...#... +.#..##.... +#......#.# +.....##..# +#.#.....## +#......... +#....#.... +##....#.#. + +Tile 3517: +####.#...# +#.#..#...# +#......#.# +#..#...... +##....#..# +#......#.. +..#...#... +#.....#... +....#.###. +##...#.#.. + +Tile 2543: +.#######.# +.....#.... +#.#.#....# +........#. +##...#.... +..#.....## +..#.#.##.# +........## +#.......#. +#.####.### + +Tile 1567: +...#.##... +...#...### +.....#.... +....#....# +#.....#.#. +.###....#. +#.##..###. +........## +........#. +#####.#.## + +Tile 1459: +..#...###. +##..##...# +.##....... +..###.#... +##.......# +....#..##. +##....#.## +......#... +....#..... +.#.#.#.### + +Tile 1153: +.##...###. +#.#..#.#.. +.......... +.......... +...#.#..#. +..#......# +#.#..##... +..##....#. +#......... +#.#....### + +Tile 1811: +###.#..#.# +#..##....# +#.##..#... +...#...### +......#... +..#....##. +##.......# +..#......# +.....#...# +.....#.... + +Tile 1667: +.#.#.##.## +.....#.#.# +....##.... +....#....# +.###..#..# +.#.####.## +#..##..... +......##.# +#.#...##.. +#####..### + +Tile 2677: +.###...#.# +#..###...# +#....###.. +.......... +##.......# +##.#....#. +###..##.#. +#.#....... +.#......#. +##.#..#... + +Tile 2707: +#..#.#.##. +#.....#### +....#...#. +##..#..... +##........ +..#...#... +....#..... +#....#.#.# +..#..#.#.. +####...#.. + +Tile 1699: +.###....## +..#..#...# +.###...... +.....#...# +#.#.....## +#.##..#... +.#.......# +#......#.# +###.....## +.##....... + +Tile 3919: +..#.#..#.# +#.#...#..# +##.#..#.#. +.#..#..#.. +#.#.#.#.#. +#...##...# +#...##.... +#...#.#... +...#...### +##.#.#..## + +Tile 1019: +#..#..#.## +#....#..## +#......##. +#.#....#.. +##....#... +#....##..# +....#..... +.#..#.#... +......##.. +...#...#.. + +Tile 3319: +..#...#.#. +.##....... +...#.#...# +........#. +#.....##.. +...##....# +..##...##. +.....#..## +..###..... +#...####.. + +Tile 3041: +##..#####. +......#..# +..#..##..# +.......... +#.....#.## +#......#.. +.....#..#. +..##.....# +.#.......# +........## + +Tile 3313: +.##.#..### +#.#..###.. +#....#.#.. +##........ +...#.....# +#......... +.#.....#.. +#.....#... +#.#.#...#. +#.....##.. + +Tile 3541: +#.#....... +.##......# +#......... +##.......# +.#......## +..#..#.... +....#.#.## +.#.......# +##.......# +#.#..##..# + +Tile 1319: +#.#...#..# +#......##. +..#.#.#### +#......... +#..#.....# +..#...##.# +#...#.##.# +#..#....## +....##.... +.#.#.#.### + +Tile 1499: +####...#.. +#...#....# +.....#...# +.......#.. +#.###....# +.......### +.......##. +.......#.# +..#.#...#. +......#.#. + +Tile 2239: +..#....##. +.####....# +...#.....# +......#... +.....#..#. +#..#.....# +#.#.####.. +###.##.... +.........# +...#...#.. + +Tile 3769: +####.####. +#....#.#.# +.##....... +###.....## +##.#...#.# +....#.#..# +.......... +#.#.#..... +##.......# +.#####.### + +Tile 1187: +#..#.#.... +#.......#. +...#....## +#..##....# +#.....#.## +...##.#### +#....#.... +.....#.#.. +#.##.#...# +#..#.##.## + +Tile 1913: +#.##.#.##. +##.#...#.# +#.#...#... +##.#.....# +#.##...... +#.###....# +..#..#.##. +#......... +#.#......# +...#.###.# + +Tile 1753: +..#..#.... +.......#.# +...#.#.#.# +#.#....#.. +#......#.# +##...#.... +#.#.....## +#..#...##. +.##.#.#..# +##.###.##. + diff --git a/20/input.small b/20/input.small new file mode 100644 index 0000000..b07aa4b --- /dev/null +++ b/20/input.small @@ -0,0 +1,107 @@ +Tile 2311: +..##.#..#. +##..#..... +#...##..#. +####.#...# +##.##.###. +##...#.### +.#.#.#..## +..#....#.. +###...#.#. +..###..### + +Tile 1951: +#.##...##. +#.####...# +.....#..## +#...###### +.##.#....# +.###.##### +###.##.##. +.###....#. +..#.#..#.# +#...##.#.. + +Tile 1171: +####...##. +#..##.#..# +##.#..#.#. +.###.####. +..###.#### +.##....##. +.#...####. +#.##.####. +####..#... +.....##... + +Tile 1427: +###.##.#.. +.#..#.##.. +.#.##.#..# +#.#.#.##.# +....#...## +...##..##. +...#.##### +.#.####.#. +..#..###.# +..##.#..#. + +Tile 1489: +##.#.#.... +..##...#.. +.##..##... +..#...#... +#####...#. +#..#.#.#.# +...#.#.#.. +##.#...##. +..##.##.## +###.##.#.. + +Tile 2473: +#....####. +#..#.##... +#.##..#... +######.#.# +.#...#.#.# +.######### +.###.#..#. +########.# +##...##.#. +..###.#.#. + +Tile 2971: +..#.#....# +#...###... +#.#.###... +##.##..#.. +.#####..## +.#..####.# +#..#.#..#. +..####.### +..#.#.###. +...#.#.#.# + +Tile 2729: +...#.#.#.# +####.#.... +..#.#..... +....#..#.# +.##..##.#. +.#.####... +####.#.#.. +##.####... +##..#.##.. +#.##...##. + +Tile 3079: +#.#.#####. +.#..###### +..#....... +######.... +####.#..#. +.#...#.##. +#.#####.## +..#.###... +..#....... +..#.###... diff --git a/20/src/main.rs b/20/src/main.rs new file mode 100644 index 0000000..12c3dea --- /dev/null +++ b/20/src/main.rs @@ -0,0 +1,655 @@ +use advent_lib::prelude::*; + +use std::collections::BTreeMap; +use std::collections::BTreeSet; + +#[derive(Clone,Copy,Debug,Eq,Ord,PartialOrd,PartialEq)] +pub enum Edge { + Top, + Bottom, + Left, + Right, +} + +#[derive(Clone,Copy,Debug,Eq,Ord,PartialOrd,PartialEq)] +pub struct Orientation { + edge_at_top: Edge, // rotation occurs *after* flipping + is_flipped: bool, // flips occur around the y axis +} + + +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 input = advent_lib::group_lines_by_blanks(input); + + let mut tiles: BTreeMap>> = BTreeMap::new(); + for tile_input in &input { + let mut lines = tile_input.iter(); + + let rest = lines.next().unwrap(); + let (_, rest) = rest.split_at(5); + let colon_point = rest.find(':').unwrap(); + let (tile_id, _) = rest.split_at(colon_point); + let tile_id = tile_id.parse::().unwrap(); + + let mut tile = Vec::new(); + for line in lines { + let mut row = Vec::new(); + for c in line.chars() { + row.push(c == '#'); + } + tile.push(row); + } + + tiles.insert(tile_id, tile); + } + + let mut tile_edges: BTreeMap<(i64,Edge),u64> = BTreeMap::new(); + for (tile_id, tile) in tiles.iter() { + let top = extract_top(tile); + let bottom = extract_bottom(tile); + let left = extract_left(tile); + let right = extract_right(tile); + tile_edges.insert((*tile_id, Edge::Top), top); + tile_edges.insert((*tile_id, Edge::Bottom), bottom); + tile_edges.insert((*tile_id, Edge::Left), left); + tile_edges.insert((*tile_id, Edge::Right), right); + } + + let tile_count = tiles.keys().len() as f64; + let grid_size = tile_count.sqrt().floor() as i64; + + let mut grid: Vec>> = Vec::new(); + for _ in 0 .. grid_size { + let mut grid_row = Vec::new(); + for _ in 0 .. grid_size { + grid_row.push(None); + } + grid.push(grid_row); + } + + let mut tile_ids = BTreeSet::new(); + for tile_id in tiles.keys() { + tile_ids.insert(*tile_id); + } + + let grid = fill_grid(&grid, &tiles, &tile_edges, &tile_ids).unwrap(); + let summary = summarize_grid(&grid); + println!("{}", summary); + + let image = assemble_grid(&grid, &tiles); + let sea_serpent_count = count_sea_serpents(&image); + println!("{}", sea_serpent_count); + + Ok(()) +} + + +fn fill_grid(grid: &Vec>>, + tiles: &BTreeMap>>, + tile_edges: &BTreeMap<(i64,Edge),u64>, + available_tiles: &BTreeSet) + -> Option>>> +{ + match find_empty_cell(grid) { + Some((empty_x, empty_y)) => { + for tile_id in available_tiles { + let mut value_to_match_top = None; + if empty_y > 0 { + let (tile_id_above, orientation_above) = + grid[empty_y - 1][empty_x].unwrap(); + let edge_above = edge_at(orientation_above, Edge::Bottom); + let mut edge_value_above = + *tile_edges.get(&(tile_id_above, edge_above)).unwrap(); + if !orientation_above.is_flipped { + edge_value_above = reverse_edge(edge_value_above); + } + value_to_match_top = Some(edge_value_above); + } + + let mut value_to_match_left = None; + if empty_x > 0 { + let (tile_id_left, orientation_left) = + grid[empty_y][empty_x - 1].unwrap(); + let edge_left = edge_at(orientation_left, Edge::Right); + let mut edge_value_left = + *tile_edges.get(&(tile_id_left, edge_left)).unwrap(); + if !orientation_left.is_flipped { + edge_value_left = reverse_edge(edge_value_left); + } + value_to_match_left = Some(edge_value_left); + } + + for edge_at_top in &[Edge::Top, Edge::Right, Edge::Bottom, Edge::Left] { + for is_flipped in &[false, true] { + let orientation = Orientation { + edge_at_top: *edge_at_top, + is_flipped: *is_flipped, + }; + + match value_to_match_top { + Some(to_match) => { + let edge_top = edge_at(orientation, Edge::Top); + let mut value_top = + *tile_edges.get(&(*tile_id, edge_top)).unwrap(); + if *is_flipped { + value_top = reverse_edge(value_top); + } + + if value_top != to_match { + continue; + } + }, + None => { }, + } + + match value_to_match_left { + Some(to_match) => { + let edge_left = edge_at(orientation, Edge::Left); + let mut value_left = + *tile_edges.get(&(*tile_id, edge_left)).unwrap(); + if *is_flipped { + value_left = reverse_edge(value_left); + } + + if value_left != to_match { + continue; + } + }, + None => { }, + } + + let mut modified_grid = Vec::new(); + for y in 0 .. grid.len() { + let mut modified_row = Vec::new(); + for x in 0 .. grid[y].len() { + if y == empty_y && x == empty_x { + modified_row.push(Some((*tile_id, orientation))); + } else { + modified_row.push(grid[y][x]); + } + } + modified_grid.push(modified_row); + } + + let mut modified_available_tiles = available_tiles.clone(); + modified_available_tiles.remove(tile_id); + + if modified_available_tiles.iter().count() == 0 { + return Some(modified_grid); + } else { + let result = fill_grid(&modified_grid, tiles, + tile_edges, &modified_available_tiles); + if result.is_some() { + return result; + } + } + } + } + } + + None + }, + None => { + Some(grid.clone()) + }, + } +} + + +fn find_empty_cell(grid: &Vec>>) + -> Option<(usize, usize)> +{ + let mut found_empty_cell = false; + let mut empty_y = 0; + let mut empty_x = 0; + + for y in 0 .. grid.len() { + for x in 0 .. grid[y].len() { + match grid[y][x] { + None => { + empty_x = x; + empty_y = y; + found_empty_cell = true; + break; + }, + _ => { }, + } + } + if found_empty_cell { + break; + } + } + + if found_empty_cell { + Some((empty_x, empty_y)) + } else { + None + } +} + + +fn extract_top(tile: &Vec>) -> u64 { + let mut result = 0; + let y = 0; + for x in 0 .. tile[y].len() { + result *= 2; + if tile[y][x] { + result += 1; + } + } + result +} + + +fn extract_bottom(tile: &Vec>) -> u64 { + let mut result = 0; + let y = tile.len() - 1; + let width = tile[y].len(); + for x_reversed in 0 .. width { + let x = width - x_reversed - 1; + result *= 2; + if tile[y][x] { + result += 1; + } + } + result +} + + +fn extract_left(tile: &Vec>) -> u64 { + let mut result = 0; + let x = 0; + let height = tile.len(); + for y_reversed in 0 .. height { + let y = height - y_reversed - 1; + result *= 2; + if tile[y][x] { + result += 1; + } + } + result +} + + +fn extract_right(tile: &Vec>) -> u64 { + let mut result = 0; + let x = tile[0].len() - 1; + for y in 0 .. tile.len() { + result *= 2; + if tile[y][x] { + result += 1; + } + } + result +} + + +fn reverse_edge(input: u64) -> u64 { + let mut input = input; + let mut result = 0; + for _ in 0 .. 10 { + result *= 2; + if input & 1 != 0 { + result += 1; + } + input /= 2; + } + result +} + + +fn edge_clockwise(edge: Edge) -> Edge { + match edge { + Edge::Top => Edge::Right, + Edge::Right => Edge::Bottom, + Edge::Bottom => Edge::Left, + Edge::Left => Edge::Top, + } +} + + +fn edge_counterclockwise(edge: Edge) -> Edge { + match edge { + Edge::Top => Edge::Left, + Edge::Left => Edge::Bottom, + Edge::Bottom => Edge::Right, + Edge::Right => Edge::Top, + } +} + + +fn edge_at(orientation: Orientation, edge_as_placed: Edge) -> Edge { + if !orientation.is_flipped { + let n_clockwise_from_top = match edge_as_placed { + Edge::Top => 0, + Edge::Right => 1, + Edge::Bottom => 2, + Edge::Left => 3, + }; + + let mut rotated_edge = orientation.edge_at_top; + for _ in 0 .. n_clockwise_from_top { + rotated_edge = edge_clockwise(rotated_edge); + } + + rotated_edge + } else { + let n_counterclockwise_from_top = match edge_as_placed { + Edge::Top => 0, + Edge::Right => 1, + Edge::Bottom => 2, + Edge::Left => 3, + }; + + let mut rotated_edge = orientation.edge_at_top; + for _ in 0 .. n_counterclockwise_from_top { + rotated_edge = edge_counterclockwise(rotated_edge); + } + + rotated_edge + } +} + + +fn summarize_grid(grid: &Vec>>) -> i64 { + let mut summary = 1; + let height = grid.len(); + let width = grid[0].len(); + summary *= match grid[0][0] { + Some((tile_id, _)) => { tile_id }, + _ => 0, + }; + summary *= match grid[height - 1][0] { + Some((tile_id, _)) => { tile_id }, + _ => 0, + }; + summary *= match grid[0][width - 1] { + Some((tile_id, _)) => { tile_id }, + _ => 0, + }; + summary *= match grid[height - 1][width - 1] { + Some((tile_id, _)) => { tile_id }, + _ => 0, + }; + summary +} + + +fn assemble_grid(grid: &Vec>>, + tiles: &BTreeMap>>) + -> Vec> +{ + let mut image: Vec> = Vec::new(); + + let grid_size = grid.len(); + let (sample_tile_id, _) = grid[0][0].unwrap(); + let sample_tile = tiles.get(&sample_tile_id).unwrap(); + let tile_size = sample_tile.len(); + + for outer_y in 0 .. grid_size { + for inner_y_shifted in 0 .. tile_size - 2 { + let mut image_row = Vec::new(); + + let inner_y = inner_y_shifted + 1; + + for outer_x in 0 .. grid_size { + let (tile_id, orientation) = grid[outer_y][outer_x].unwrap(); + let tile = tiles.get(&tile_id).unwrap(); + + for inner_x_shifted in 0 .. tile_size - 2 { + let inner_x = inner_x_shifted + 1; + let (tile_x, tile_y) = transform_placed_coordinates_to_tile( + orientation, tile_size, inner_x, inner_y); + let cell = tile[tile_y][tile_x]; + image_row.push(cell); + } + } + + image.push(image_row); + } + } + + image +} + + +pub fn debug_grid(grid: &Vec>>, + tiles: &BTreeMap>>) +{ + let mut debug_output = String::new(); + + let grid_size = grid.len(); + let (sample_tile_id, _) = grid[0][0].unwrap(); + let sample_tile = tiles.get(&sample_tile_id).unwrap(); + let tile_size = sample_tile.len(); + + for outer_y in 0 .. grid_size { + if outer_y > 0 { + debug_output.push_str("\n"); + } + + for inner_y in 0 .. tile_size { + for outer_x in 0 .. grid_size { + debug_output.push_str(" "); + + let (tile_id, orientation) = grid[outer_y][outer_x].unwrap(); + let tile = tiles.get(&tile_id).unwrap(); + + for inner_x in 0 .. tile_size { + let (tile_x, tile_y) = transform_placed_coordinates_to_tile( + orientation, tile_size, inner_x, inner_y); + let cell = tile[tile_y][tile_x]; + + if cell { + debug_output.push_str("#"); + } else { + debug_output.push_str("."); + } + } + } + + debug_output.push_str("\n"); + } + } + + println!("{}", debug_output); +} + + +pub fn debug_image(image: &Vec>) { + let mut output = String::new(); + + for row in image { + for cell in row { + if *cell { + output.push_str("#"); + } else { + output.push_str("."); + } + } + output.push_str("\n"); + } + println!("{}", output); +} + + +pub fn debug_map(image: &Vec>, map: &Vec>) { + let mut output = String::new(); + let image_size = image.len(); + + for y in 0 .. image_size { + for x in 0 .. image_size { + if map[y][x] { + if image[y][x] { + output.push_str("O"); + } else { + output.push_str("@"); + } + } else { + if image[y][x] { + output.push_str("#"); + } else { + output.push_str("."); + } + } + } + output.push_str("\n"); + } + println!("{}", output); +} + + +fn transform_placed_coordinates_to_tile( + orientation: Orientation, tile_size: usize, placed_x: usize, placed_y: usize) + -> (usize, usize) +{ + /* + * at top TOP RIGHT BOTTOM LEFT + * + * normal A. .2 2+ +A + * +2 A+ .A 2. + * + * flipped .A 2. +2 A+ + * 2+ +A A. .2 + */ + + if !orientation.is_flipped { + match orientation.edge_at_top { + Edge::Top => { (placed_x, placed_y) }, + Edge::Left => { (placed_y, tile_size - placed_x - 1) }, + Edge::Bottom => { (tile_size - placed_x - 1, tile_size - placed_y - 1) }, + Edge::Right => { (tile_size - placed_y - 1, placed_x) }, + } + } else { + match orientation.edge_at_top { + Edge::Top => { (tile_size - placed_x - 1, placed_y) }, + Edge::Left => { (placed_y, placed_x) }, + Edge::Bottom => { (placed_x, tile_size - placed_y - 1) }, + Edge::Right => { (tile_size - placed_y - 1, tile_size - placed_x - 1) }, + } + } +} + + +fn transform_image(input_image: &Vec>, orientation: Orientation) + -> Vec> +{ + let image_size = input_image.len(); + + let mut output_image = Vec::new(); + for y_as_placed in 0 .. image_size { + let mut output_row = Vec::new(); + for x_as_placed in 0 .. image_size { + let (x_in_input, y_in_input) = transform_placed_coordinates_to_tile( + orientation, image_size, x_as_placed, y_as_placed); + if input_image[y_in_input][x_in_input] { + output_row.push(true); + } else { + output_row.push(false); + } + } + output_image.push(output_row); + } + + output_image +} + + +fn count_sea_serpents(image: &Vec>) -> usize { + let mut sea_serpent: Vec> = Vec::new(); + for line in &[" # ", + "# ## ## ###", + " # # # # # # "] + { + let mut sea_serpent_row = Vec::new(); + for c in line.chars() { + sea_serpent_row.push(c == '#'); + } + sea_serpent.push(sea_serpent_row); + } + let sea_serpent_height = sea_serpent.len(); + let sea_serpent_width = sea_serpent[0].len(); + let image_size = image.len(); + + let mut sea_serpent_map: Vec> = Vec::new(); + for _ in 0 .. image_size { + let mut map_row = Vec::new(); + for _ in 0 .. image_size { + map_row.push(false); + } + sea_serpent_map.push(map_row); + } + + for edge_at_top in &[Edge::Top, Edge::Right, Edge::Bottom, Edge::Left] { + for is_flipped in &[false, true] { + let orientation = Orientation { + edge_at_top: *edge_at_top, + is_flipped: *is_flipped, + }; + + let transformed_image = transform_image(image, orientation); + let mut sea_serpent_count = 0; + + for image_y in 0 .. image_size - sea_serpent_height + 1 { + for image_x in 0 .. image_size - sea_serpent_width + 1 { + let mut possible_sea_serpent = true; + + for sea_serpent_y in 0 .. sea_serpent_height { + for sea_serpent_x in 0 .. sea_serpent_width { + if sea_serpent[sea_serpent_y][sea_serpent_x] { + let cell_x = image_x + sea_serpent_x; + let cell_y = image_y + sea_serpent_y; + let cell = transformed_image[cell_y][cell_x]; + if !cell { + possible_sea_serpent = false; + break; + } + } + } + if !possible_sea_serpent { + break; + } + } + + if possible_sea_serpent { + sea_serpent_count += 1; + + for sea_serpent_y in 0 .. sea_serpent_height { + for sea_serpent_x in 0 .. sea_serpent_width { + if sea_serpent[sea_serpent_y][sea_serpent_x] { + let map_x = image_x + sea_serpent_x; + let map_y = image_y + sea_serpent_y; + sea_serpent_map[map_y][map_x] = true; + } + } + } + } + } + } + + if sea_serpent_count > 0 { + let mut roughness = 0; + for y in 0 .. image_size { + for x in 0 .. image_size { + if transformed_image[y][x] && !sea_serpent_map[y][x] { + roughness += 1; + } + } + } + + return roughness; + } + } + } + + 0 +} + diff --git a/20/tests/main.rs b/20/tests/main.rs new file mode 100644 index 0000000..feb9fe3 --- /dev/null +++ b/20/tests/main.rs @@ -0,0 +1,14 @@ +use assert_cmd::prelude::*; +use std::process::Command; + + +#[test] +fn personal_input() -> Result<(), Box> { + let mut command = Command::cargo_bin("advent_20")?; + + command.arg("input"); + command.assert().success().stdout("29125888761511\n2219\n"); + + Ok(()) +} + diff --git a/Cargo.lock b/Cargo.lock index 6047458..1a72d14 100644 --- a/Cargo.lock +++ b/Cargo.lock @@ -156,6 +156,14 @@ dependencies = [ "assert_cmd", ] +[[package]] +name = "advent_20" +version = "0.1.0" +dependencies = [ + "advent_lib", + "assert_cmd", +] + [[package]] name = "advent_lib" version = "0.1.0" diff --git a/Cargo.toml b/Cargo.toml index 8e0da29..154b354 100644 --- a/Cargo.toml +++ b/Cargo.toml @@ -20,4 +20,5 @@ members = [ "17", "18", "19", + "20", ] -- cgit 1.4.1