heh
21 p1
| -rw-r--r-- | Cargo.toml | 1 | ||||
| -rw-r--r-- | src/inp.txt | 146 | ||||
| -rw-r--r-- | src/main.rs | 170 |
3 files changed, 136 insertions, 181 deletions
@@ -12,6 +12,7 @@ car = "0.1.1" itertools = "0.12.0" memchr = "2.6.4" pathfinding = "4.12.0" +rayon = "1.10.0" # radsort = "0.1.1" rustc-hash = { version = "2.1.0", features = ["nightly"] } [profile.release] diff --git a/src/inp.txt b/src/inp.txt index 64dfde1..5ed32e5 100644 --- a/src/inp.txt +++ b/src/inp.txt @@ -1,141 +1,5 @@ -############################################################################################################################################# -#...........#...#...#...#.....#...###...#...................#...#.....#.................#.......###...###.......###...###...................# -#.#########.#.#.#.#.#.#.#.###.#.#.###.#.#.#################.#.#.#.###.#.###############.#.#####.###.#.###.#####.###.#.###.#################.# -#.....#.....#.#...#...#.#...#...#.#...#.#.................#...#...#...#.......#.........#.#.....#...#...#.#.....#...#...#.....#.............# -#####.#.#####.#########.###.#####.#.###.#################.#########.#########.#.#########.#.#####.#####.#.#.#####.#####.#####.#.############# -###...#.....#.........#.###.....#.#...#.###.......#.....#...#.......#.......#.#.#.........#.....#.....#.#.#.#...#.....#.###...#.#...#...#...# -###.#######.#########.#.#######.#.###.#.###.#####.#.###.###.#.#######.#####.#.#.#.#############.#####.#.#.#.#.#.#####.#.###.###.#.#.#.#.#.#.# -#...#.......###...#...#.#.......#.....#...#.#.....#...#.....#.......#.....#.#.#.#.....#.........###...#.#.#...#.#...#.#...#...#...#...#...#.# -#.###.#########.#.#.###.#.###############.#.#.#######.#############.#####.#.#.#.#####.#.###########.###.#.#####.#.#.#.###.###.#############.# -#...#...###...#.#.#...#...#.............#.#.#.###...#.........#.....#...#.#.#.#...###.#.###...#...#...#.#.#.....#.#.#.#...#...#...#.........# -###.###.###.#.#.#.###.#####.###########.#.#.#.###.#.#########.#.#####.#.#.#.#.###.###.#.###.#.#.#.###.#.#.#.#####.#.#.#.###.###.#.#.######### -###...#...#.#...#.###.......#...#.....#.#.#.#...#.#...........#...###.#.#.#.#.#...#...#.....#.#.#.....#...#...#...#...#.....#...#...#.......# -#####.###.#.#####.###########.#.#.###.#.#.#.###.#.###############.###.#.#.#.#.#.###.#########.#.#############.#.#############.#######.#####.# -#...#.#...#.#.....#.......#...#.#...#.#.#...#...#.....#.....#...#...#.#.#.#.#.#.###...#...#...#.........#.....#.#.............#...#...#...#.# -#.#.#.#.###.#.#####.#####.#.###.###.#.#.#####.#######.#.###.#.#.###.#.#.#.#.#.#.#####.#.#.#.###########.#.#####.#.#############.#.#.###.#.#.# -#.#...#...#.#.....#.....#.#...#.#...#...#.....#...###...#...#.#.#...#.#.#.#...#.#...#.#.#...#####...#...#.#.....#...............#...#...#...# -#.#######.#.#####.#####.#.###.#.#.#######.#####.#.#######.###.#.#.###.#.#.#####.#.#.#.#.#########.#.#.###.#.#########################.####### -#.....#...#.#.....###...#...#.#.#.......#.#...#.#.....#...#...#.#.#...#.#.#.....#.#...#...#...#...#...#...#...#.......................###...# -#####.#.###.#.#######.#####.#.#.#######.#.#.#.#.#####.#.###.###.#.#.###.#.#.#####.#######.#.#.#.#######.#####.#.#########################.#.# -#.....#...#.#.......#.....#...#.....#...#...#.#...#...#.....#...#...#...#.#.#...#.#.......#.#.#.#.....#.###...#.....#...###...#.....#...#.#.# -#.#######.#.#######.#####.#########.#.#######.###.#.#########.#######.###.#.#.#.#.#.#######.#.#.#.###.#.###.#######.#.#.###.#.#.###.#.#.#.#.# -#.....#...#.#.......#...#.........#...#...#...#...#.#...#...#...#.....###.#.#.#...#...#...#.#.#...#...#...#...#...#...#.....#...#...#.#.#.#.# -#####.#.###.#.#######.#.#########.#####.#.#.###.###.#.#.#.#.###.#.#######.#.#.#######.#.#.#.#.#####.#####.###.#.#.###############.###.#.#.#.# -#.....#.###.#.#...#...#.#...#...#...#...#...###.#...#.#...#...#.#.......#.#.#...#.....#.#...#.#...#.....#.....#.#.#...............###.#.#.#.# -#.#####.###.#.#.#.#.###.#.#.#.#.###.#.#########.#.###.#######.#.#######.#.#.###.#.#####.#####.#.#.#####.#######.#.#.#################.#.#.#.# -#.....#.....#.#.#.#...#...#.#.#.....#.#...###...#.#...#....S#...#.......#.#.#...#.....#.#.....#.#.#.....#.......#.#.......#...........#.#.#.# -#####.#######.#.#.###.#####.#.#######.#.#.###.###.#.###.#########.#######.#.#.#######.#.#.#####.#.#.#####.#######.#######.#.###########.#.#.# -#...#.#.......#.#...#.....#.#.......#.#.#...#.#...#.....#####.....###...#.#...#.......#.#...#...#.#.....#.#.....#.........#.#...........#.#.# -#.#.#.#.#######.###.#####.#.#######.#.#.###.#.#.#############.#######.#.#.#####.#######.###.#.###.#####.#.#.###.###########.#.###########.#.# -#.#.#.#.......#.#...###...#.........#.#.#...#.#.......#######.###...#.#.#.....#.###...#.#...#.#...#...#.#.#.#...#...#...###.#.............#.# -#.#.#.#######.#.#.#####.#############.#.#.###.#######.#######.###.#.#.#.#####.#.###.#.#.#.###.#.###.#.#.#.#.#.###.#.#.#.###.###############.# -#.#...#.......#.#.#...#.............#...#...#.#...#...#######.#...#.#.#.#...#.#...#.#...#...#.#...#.#...#...#.....#.#.#...#.#.......#.....#.# -#.#####.#######.#.#.#.#############.#######.#.#.#.#.#########.#.###.#.#.#.#.#.###.#.#######.#.###.#.###############.#.###.#.#.#####.#.###.#.# -#.#...#...###...#...#.....#.......#.#.......#.#.#...#########.#...#.#.#.#.#.#.#...#.#.......#.#...#...#.............#.#...#.#.....#...###...# -#.#.#.###.###.###########.#.#####.#.#.#######.#.#############.###.#.#.#.#.#.#.#.###.#.#######.#.#####.#.#############.#.###.#####.########### -#...#...#...#...#...#.....#.....#...#...#...#.#.#...#########.#...#...#.#.#.#.#.#...#...#...#.#.#.....#.............#.#.....#.....#...###...# -#######.###.###.#.#.#.#########.#######.#.#.#.#.#.#.#########.#.#######.#.#.#.#.#.#####.#.#.#.#.#.#################.#.#######.#####.#.###.#.# -###...#.#...###...#.#.#...#.....#...#...#.#...#.#.#.#######...#.......#.#.#.#.#.#.....#...#...#.#...#...#.......#...#.#.....#.....#.#.#...#.# -###.#.#.#.#########.#.#.#.#.#####.#.#.###.#####.#.#.#######.#########.#.#.#.#.#.#####.#########.###.#.#.#.#####.#.###.#.###.#####.#.#.#.###.# -#...#...#.....#...#.#.#.#.#.......#.#...#.....#.#.#.#######...#...#...#.#.#.#.#.#.....#.........#...#.#...#...#...#...#...#.......#.#.#.#...# -#.###########.#.#.#.#.#.#.#########.###.#####.#.#.#.#########.#.#.#.###.#.#.#.#.#.#####.#########.###.#####.#.#####.#####.#########.#.#.#.### -#.#.......#...#.#...#...#...#...#...#...#...#.#.#.#.#########.#.#...#...#.#...#.#.....#.#...#...#.###.......#...#...#.....#.........#...#...# -#.#.#####.#.###.###########.#.#.#.###.###.#.#.#.#.#.#########.#.#####.###.#####.#####.#.#.#.#.#.#.#############.#.###.#####.###############.# -#.#.#...#.#.....#...#...#...#.#.#...#.....#...#...#.###.......#...###...#.#.....#...#.#.#.#...#.#.#...#.........#...#.......#.......#.....#.# -#.#.#.#.#.#######.#.#.#.#.###.#.###.###############.###.#########.#####.#.#.#####.#.#.#.#.#####.#.#.#.#.###########.#########.#####.#.###.#.# -#...#.#...#.....#.#...#.#.....#...#.............###.###...#.....#.#...#...#.......#...#...#...#...#.#.#.......#...#.#.........#...#...#...#.# -#####.#####.###.#.#####.#########.#############.###.#####.#.###.#.#.#.#####################.#.#####.#.#######.#.#.#.#.#########.#.#####.###.# -#.....#...#.###...###...#...#...#.............#.#...#E#...#.#...#...#...#...#...###.........#.###...#.........#.#...#...........#.....#...#.# -#.#####.#.#.#########.###.#.#.#.#############.#.#.###.#.###.#.#########.#.#.#.#.###.#########.###.#############.#####################.###.#.# -#.#.....#...#...#...#.#...#...#.............#...#.....#.....#.#.....#...#.#...#...#.........#.#...#.............#...#...#...#...#...#...#...# -#.#.#########.#.#.#.#.#.###################.#################.#.###.#.###.#######.#########.#.#.###.#############.#.#.#.#.#.#.#.#.#.###.##### -#...#.......#.#...#...#...#...#...#...#...#.#.................#.###.#.....#.....#.#.........#...#...#.......#.....#...#...#...#...#...#.....# -#####.#####.#.###########.#.#.#.#.#.#.#.#.#.#.#################.###.#######.###.#.#.#############.###.#####.#.#######################.#####.# -###...#...#...#...........#.#...#...#...#...#.#...#.......#...#...#...#...#...#.#.#...#...#.......###.#...#.#...............#...#...#.......# -###.###.#.#####.###########.#################.#.#.#.#####.#.#.###.###.#.#.###.#.#.###.#.#.#.#########.#.#.#.###############.#.#.#.#.######### -#...#...#.......#...#...#...#.............#...#.#.#...###...#...#.###...#.#...#...###...#...#...#...#.#.#.#...#.....#...#...#.#...#.........# -#.###.###########.#.#.#.#.###.###########.#.###.#.###.#########.#.#######.#.#################.#.#.#.#.#.#.###.#.###.#.#.#.###.#############.# -#.....#...........#.#.#.#...#.#...........#.....#.#...#...#.....#.......#.#.....#...#.........#...#.#...#...#.#...#...#.#.#...#.............# -#######.###########.#.#.###.#.#.#################.#.###.#.#.###########.#.#####.#.#.#.#############.#######.#.###.#####.#.#.###.############# -#...#...#...#.....#...#.....#.#...........###...#...###.#...#...#...#...#...#...#.#.#.#...........#.........#...#.....#...#...#...#.....#...# -#.#.#.###.#.#.###.###########.###########.###.#.#######.#####.#.#.#.#.#####.#.###.#.#.#.#########.#############.#####.#######.###.#.###.#.#.# -#.#...#...#.#...#.....#.....#.#.........#.....#...#...#...#...#...#.#.....#...###.#.#...#.........#...........#.#...#...#...#.#...#.#...#.#.# -#.#####.###.###.#####.#.###.#.#.#######.#########.#.#.###.#.#######.#####.#######.#.#####.#########.#########.#.#.#.###.#.#.#.#.###.#.###.#.# -#.#.....###.....#.....#...#.#.#.....###.........#.#.#...#.#...#.....#...#...#.....#.#.....#.....#...###.......#...#.....#.#.#.#.....#.....#.# -#.#.#############.#######.#.#.#####.###########.#.#.###.#.###.#.#####.#.###.#.#####.#.#####.###.#.#####.#################.#.#.#############.# -#.#.....#.........#...#...#...#.....#.....#...#.#...#...#...#.#.....#.#.....#.....#.#.#...#.###.#.....#...#...#...#...###.#...#...#.........# -#.#####.#.#########.#.#.#######.#####.###.#.#.#.#####.#####.#.#####.#.###########.#.#.#.#.#.###.#####.###.#.#.#.#.#.#.###.#####.#.#.######### -#.#.....#...#...#...#...#.......#...#.#...#.#.#.....#...#...#...###.#.###.....#...#...#.#...#...#...#.#...#.#.#.#.#.#.....#...#.#...#...#...# -#.#.#######.#.#.#.#######.#######.#.#.#.###.#.#####.###.#.#####.###.#.###.###.#.#######.#####.###.#.#.#.###.#.#.#.#.#######.#.#.#####.#.#.#.# -#.#...#.....#.#.#.#.......#...#...#...#.....#.....#.....#.....#.#...#...#.#...#...#.....###...#...#...#.....#.#.#...#.......#.#.#...#.#.#.#.# -#.###.#.#####.#.#.#.#######.#.#.#################.###########.#.#.#####.#.#.#####.#.#######.###.#############.#.#####.#######.#.#.#.#.#.#.#.# -#.#...#.#.....#...#.........#...#...........#...#.........#...#.#.......#.#.#...#.#.#.......#...#...........#...#...#.....###...#.#...#.#.#.# -#.#.###.#.#######################.#########.#.#.#########.#.###.#########.#.#.#.#.#.#.#######.###.#########.#####.#.#####.#######.#####.#.#.# -#.#...#...#...#...#...#...#.....#.......###...#...........#.....#.....#...#.#.#.#...#.....#...#...#.......#.#.....#.....#.........#...#...#.# -#.###.#####.#.#.#.#.#.#.#.#.###.#######.#########################.###.#.###.#.#.#########.#.###.###.#####.#.#.#########.###########.#.#####.# -#.#...#.....#.#.#.#.#.#.#.#...#.......#.........#...#...#.....#...#...#.#...#.#...........#.###.....#...#.#.#.......###.........#...#.......# -#.#.###.#####.#.#.#.#.#.#.###.#######.#########.#.#.#.#.#.###.#.###.###.#.###.#############.#########.#.#.#.#######.###########.#.########### -#...###.....#...#...#...#...#.......#.........#...#...#.#...#.#...#.###.#...#.......#...#...#.....#...#...#.........#...#.....#.#.###...#...# -###########.###############.#######.#########.#########.###.#.###.#.###.###.#######.#.#.#.###.###.#.#################.#.#.###.#.#.###.#.#.#.# -#.....#...#...........#...#.......#.#.......#...#...#...#...#.#...#...#.#...###...#...#...###...#.#...................#.#.#...#...#...#...#.# -#.###.#.#.###########.#.#.#######.#.#.#####.###.#.#.#.###.###.#.#####.#.#.#####.#.#############.#.#####################.#.#.#######.#######.# -#...#.#.#.#...#...###...#.......#.#...#.....#...#.#...###...#.#...#...#.#...#...#...#...#...#...#...............#.....#...#.........#...#...# -###.#.#.#.#.#.#.#.#############.#.#####.#####.###.#########.#.###.#.###.###.#.#####.#.#.#.#.#.#################.#.###.###############.#.#.### -#...#...#...#...#.......#.......#.......#...#.....#.......#.#.#...#.....#...#...#...#.#.#.#.#.#...............#.#...#.....#.....#.....#.#...# -#.#####################.#.###############.#.#######.#####.#.#.#.#########.#####.#.###.#.#.#.#.#.#############.#.###.#####.#.###.#.#####.###.# -#.#.....#...#.......#...#.......#.........#...#...#...#...#.#.#...#.......#...#.#.#...#.#.#.#.#.#.............#...#.....#...###.#...###.....# -#.#.###.#.#.#.#####.#.#########.#.###########.#.#.###.#.###.#.###.#.#######.#.#.#.#.###.#.#.#.#.#.###############.#####.#######.###.######### -#.#.#...#.#...#...#.#.#.......#...#...........#.#.....#.#...#.....#.#...#...#...#.#...#.#.#.#...#...............#.......#.....#...#.........# -#.#.#.###.#####.#.#.#.#.#####.#####.###########.#######.#.#########.#.#.#.#######.###.#.#.#.###################.#########.###.###.#########.# -#...#.....#.....#...#.#...#...#...#.........#...#...#...#.........#.#.#.#.#...#...#...#...#.....#...#...#.....#...........#...###...#.......# -###########.#########.###.#.###.#.#########.#.###.#.#.###########.#.#.#.#.#.#.#.###.###########.#.#.#.#.#.###.#############.#######.#.####### -#...###...#.........#.#...#.....#...........#.#...#...###.......#.#...#.#...#.#...#...#.........#.#...#...###...........#...#...###...#...### -#.#.###.#.#########.#.#.#####################.#.#########.#####.#.#####.#####.###.###.#.#########.#####################.#.###.#.#######.#.### -#.#.....#.....#...#.#.#.....#.......#.......#.#.###.....#...#...#.....#...#...#...###.#.#.......#...#.................#...#...#.#.......#...# -#.###########.#.#.#.#.#####.#.#####.#.#####.#.#.###.###.###.#.#######.###.#.###.#####.#.#.#####.###.#.###############.#####.###.#.#########.# -#...#...#...#...#...#...###...###...#.#.....#.#...#...#.....#.#...###.#...#...#.#.....#.#.#.....###...###.............#...#.#...#...#.......# -###.#.#.#.#.###########.#########.###.#.#####.###.###.#######.#.#.###.#.#####.#.#.#####.#.#.#############.#############.#.#.#.#####.#.####### -#...#.#...#.....#.....#...###...#.....#...###...#...#.......#.#.#...#.#.#...#.#.#.....#...#.#...#...#...#...#...........#.#.#.#.....#.......# -#.###.#########.#.###.###.###.#.#########.#####.###.#######.#.#.###.#.#.#.#.#.#.#####.#####.#.#.#.#.#.#.###.#.###########.#.#.#.###########.# -#...#.#.....#...#.###...#.....#.........#.#...#.#...###...#.#.#...#.#.#.#.#.#.#...#...#.....#.#.#.#.#.#.....#.#.......#...#.#...#.....#...#.# -###.#.#.###.#.###.#####.###############.#.#.#.#.#.#####.#.#.#.###.#.#.#.#.#.#.###.#.###.#####.#.#.#.#.#######.#.#####.#.###.#####.###.#.#.#.# -#...#.#...#...#...#...#...#...#.......#...#.#.#.#.....#.#.#.#.....#...#.#.#.#.#...#...#.....#.#...#.#.........#.....#...###.#.....###...#...# -#.###.###.#####.###.#.###.#.#.#.#####.#####.#.#.#####.#.#.#.###########.#.#.#.#.#####.#####.#.#####.###############.#######.#.############### -#.#...#...#...#.#...#.....#.#.#.#.....#...#.#.#.#.....#.#.#.........#...#.#.#.#.#...#...#...#...#...#...#.......#...###.....#...............# -#.#.###.###.#.#.#.#########.#.#.#.#####.#.#.#.#.#.#####.#.#########.#.###.#.#.#.#.#.###.#.#####.#.###.#.#.#####.#.#####.###################.# -#.#.#...#...#...#.....#...#.#.#.#.#...#.#.#.#.#.#.#...#.#.#...#...#.#...#.#.#.#.#.#...#.#...#...#...#.#.#.....#...#.....#.....#.............# -#.#.#.###.###########.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.###.#.#.#.#.#.###.#.###.#.#####.#.#.#####.#####.#####.###.#.############# -#...#.....###.........#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#...#.#.#.#...#.#.#...#...#...#.#...#.....#...#...#...###...#...#...#.#.#...#...#...# -#############.#########.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#####.#.#.###.#.#.#########.###.#.#######.#######.#.#####.###.#.###.#.#.#.#.#.#.#.#.# -#.............#...#...#.#.#.#...#.#.#.#.#.#.#...#...#.#.....#.#.#.#...#.#.........#.#...#.#...#...###.....#.......#...#.....#.#...#...#...#.# -#.#############.#.#.#.#.#.#.#####.#.#.#.#.#.#########.#####.#.#.#.#.###.#########.#.#.###.#.#.#.#####.#############.#########.#############.# -#...#...#.....#.#...#.#.#...#.....#.#...#.#.........#...#...#.#.#.#.###...#...#...#.#.#...#.#...#...#.....#.......#.........#.#...#.......#.# -###.#.#.#.###.#.#####.#.#####.#####.#####.#########.###.#.###.#.#.#.#####.#.#.#.###.#.#.###.#####.#.#####.#.#####.#########.#.#.#.#.#####.#.# -#...#.#...#...#.#.....#.....#.....#...#...#...#.....#...#.#...#.#.#.....#.#.#.#...#.#.#...#.......#.#.....#.....#.#...#.....#...#.#...#...#.# -#.###.#####.###.#.#########.#####.###.#.###.#.#.#####.###.#.###.#.#####.#.#.#.###.#.#.###.#########.#.#########.#.#.#.#.#########.###.#.###.# -#...#.#...#...#.#.....#...#...###.#...#.....#.#.....#...#.#...#.#.....#.#...#...#.#.#.###...#...#...#.#...#.....#.#.#.#.........#.#...#...#.# -###.#.#.#.###.#.#####.#.#.###.###.#.#########.#####.###.#.###.#.#####.#.#######.#.#.#.#####.#.#.#.###.#.#.#.#####.#.#.#########.#.#.#####.#.# -#...#.#.#.....#.###...#.#...#.#...#.#.....#...#...#.###.#.#...#.....#.#.#...###.#.#.#.#.....#.#.#...#.#.#.#.#...#...#.#...#.....#.#...#...#.# -#.###.#.#######.###.###.###.#.#.###.#.###.#.###.#.#.###.#.#.#######.#.#.#.#.###.#.#.#.#.#####.#.###.#.#.#.#.#.#.#####.#.#.#.#####.###.#.###.# -#.#...#...#...#...#...#...#...#.....#...#...#...#.#.#...#.#.#...#...#.#.#.#.....#.#.#.#.#.....#.#...#.#.#.#...#.#.....#.#.#.....#.#...#.#...# -#.#.#####.#.#.###.###.###.#############.#####.###.#.#.###.#.#.#.#.###.#.#.#######.#.#.#.#.#####.#.###.#.#.#####.#.#####.#.#####.#.#.###.#.### -#...#...#...#...#...#.....#...###...###.#...#.###...#...#.#.#.#.#...#.#.#...#...#.#.#.#.#...#...#.###...#.#.....#.....#.#...#...#.#...#.#.### -#####.#.#######.###.#######.#.###.#.###.#.#.#.#########.#.#.#.#.###.#.#.###.#.#.#.#.#.#.###.#.###.#######.#.#########.#.###.#.###.###.#.#.### -#.....#.........#...###.....#.....#.....#.#.#...#.......#.#.#.#.#...#.#.#...#.#...#.#.#.....#.#...#.......#.........#.#.#...#...#...#.#.#...# -#.###############.#####.#################.#.###.#.#######.#.#.#.#.###.#.#.###.#####.#.#######.#.###.###############.#.#.#.#####.###.#.#.###.# -#.............#...#.....#...#...#...#...#.#...#.#...#...#.#...#.#...#.#.#...#.#.....#.....#...#...#.#.....#.....#...#.#.#.#...#...#...#.....# -#############.#.###.#####.#.#.#.#.#.#.#.#.###.#.###.#.#.#.#####.###.#.#.###.#.#.#########.#.#####.#.#.###.#.###.#.###.#.#.#.#.###.########### -#.............#.###.#...#.#.#.#.#.#.#.#.#...#.#...#...#.#...#...#...#.#.###...#...#...#...#.#...#.#...#...#...#.#...#...#.#.#...#...###...### -#.#############.###.#.#.#.#.#.#.#.#.#.#.###.#.###.#####.###.#.###.###.#.#########.#.#.#.###.#.#.#.#####.#####.#.###.#####.#.###.###.###.#.### -#.......#.....#.#...#.#...#.#.#.#.#.#.#.#...#.#...###...#...#...#...#.#.#.........#.#.#...#...#...#.....#...#.#...#...###.#.###...#.....#...# -#######.#.###.#.#.###.#####.#.#.#.#.#.#.#.###.#.#####.###.#####.###.#.#.#.#########.#.###.#########.#####.#.#.###.###.###.#.#####.#########.# -#.....#...#...#.#...#...###.#.#...#.#.#.#.#...#.....#...#...###.#...#...#...#.......#...#...#.......#...#.#...###.....#...#.....#.#...#...#.# -#.###.#####.###.###.###.###.#.#####.#.#.#.#.#######.###.###.###.#.#########.#.#########.###.#.#######.#.#.#############.#######.#.#.#.#.#.#.# -#...#.#...#...#.#...#...#...#...#...#.#.#.#.#...#...#...#...#...#.........#.#.#.........#...#.....#...#...#...#...#.....#...#...#.#.#.#.#.#.# -###.#.#.#.###.#.#.###.###.#####.#.###.#.#.#.#.#.#.###.###.###.###########.#.#.#.#########.#######.#.#######.#.#.#.#.#####.#.#.###.#.#.#.#.#.# -#...#...#.....#.#.....###...#...#.#...#.#.#.#.#...###...#...#.#...#...#...#...#...#.....#...#.....#.........#...#.#...#...#.#.###.#.#.#.#.#.# -#.#############.###########.#.###.#.###.#.#.#.#########.###.#.#.#.#.#.#.#########.#.###.###.#.###################.###.#.###.#.###.#.#.#.#.#.# -#.#...#.....#...#...........#.#...#...#.#.#.#.#.........#...#.#.#.#.#.#.........#.#.#...#...#.#.....#...#...#...#.#...#...#.#...#.#.#.#.#.#.# -#.#.#.#.###.#.###.###########.#.#####.#.#.#.#.#.#########.###.#.#.#.#.#########.#.#.#.###.###.#.###.#.#.#.#.#.#.#.#.#####.#.###.#.#.#.#.#.#.# -#...#...###...###.............#.......#...#...#...........###...#...#...........#...#.....###...###...#...#...#...#.......#.....#...#...#...# -############################################################################################################################################# +140A +143A +349A +582A +964A diff --git a/src/main.rs b/src/main.rs index 177700a..31419cb 100644 --- a/src/main.rs +++ b/src/main.rs @@ -34,54 +34,144 @@ )] extern crate test; pub mod util; +use atools::CollectArray; +use iter::once; pub use util::prelude::*; const SIZE: usize = 141; -pub fn run(x: &str) -> impl Display { - let i = x.as_bytes(); - let g = unsafe { i.as_chunks_unchecked::<{ SIZE + 1 }>() }; - let start = memchr::memchr(b'S', i).ψ(); - let (y, x) = (start / (SIZE + 1), start % (SIZE + 1)); - let mut cost = [[0; SIZE]; SIZE]; - let base = pathfinding::directed::bfs::bfs( - &(x, y), - |&p| { - [Dir::N + p, Dir::E + p, Dir::S + p, Dir::W + p] +#[rustfmt::skip] +fn numpad(x: u8) -> (usize, usize) { + match x { + b'7' => (0, 0), b'8' => (1, 0), b'9' => (2, 0), + b'4' => (0, 1), b'5' => (1, 1), b'6' => (2, 1), + b'1' => (0, 2), b'2' => (1, 2), b'3' => (2, 2), + b'0' => (1, 3), b'A' => (2, 3), + _ => unreachable!(), + } +} +#[rustfmt::skip] +fn dpad(x: u8) -> (usize, usize) { + match x { + b'^' => (1, 0), b'A' => (2, 0), + b'<' => (0, 1), b'v' => (1, 1), b'>' => (2, 1), + _ => unreachable!(), + } +} + +fn pathfind<const N: usize, const M: usize>( + input: impl IntoIterator<Item = (u8, (usize, usize))>, + grid: [[u8; N]; M], +) -> Vec<Vec<u8>> { + let mut ways = HashSet::<Vec<u8>>::default(); + for ((code, start), first) in input + .into_iter() + .zip(std::iter::once(true).chain(std::iter::repeat(false))) + { + let current = pathfinding::directed::astar::astar_bag( + &(start, code, b'.'), + |&(p, at, _)| { + [ + (Dir::N + p, b'^'), + (Dir::E + p, b'>'), + (Dir::S + p, b'v'), + (Dir::W + p, b'<'), + ] .into_iter() - .filter(|&(x, y)| g[y][x] != b'#') - }, - |&(x, y)| g[y][x] == b'E', - ) - .unwrap(); - let n = base.len() as u32; - for (&(x, y), i) in base.iter().ι::<u32>() { - cost[y][x] = i; + .filter(|&((x, y), _)| matches!(grid.get(y).map(|y| y.get(x)), Some(Some(_)))) + .map(move |(p, dir)| ((p, at, dir), 1)) + }, + |_| 0, + |&((x, y), at, _)| grid.get(y).map(|y| y.get(x)) == Some(Some(&at)), + ) + .ψ() + .0 + .into_iter() + .map(|x| { + x.into_iter() + .skip(1) + .map(|x| x.2) + .chain(once(b'A')) + .collect_vec() + }) + .collect_vec(); + + if first { + ways.extend(current); + } else { + ways = ways + .into_iter() + .flat_map(|x| { + current.iter().map(move |way| { + let mut x = x.clone(); + x.extend(way); + x + }) + }) + .collect(); + } } - let dst = n - 1; - // use rayon::prelude::*; - base.into_iter() - .filter(|&(x, y)| g[y][x] != b'#') - // .par_bridge() - .filter_map(|(x, y)| { - for (y_offset, x_offset) in include!("../offsets") { - let (x2, y2) = ( - (x as i32 + x_offset) as usize, - (y as i32 + y_offset) as usize, - ); - if x2 < SIZE - && y2 < SIZE - && ((cost[y][x] + n - cost[y2][x2] - 1 - + x_offset.abs() as u32 - + y_offset.abs() as u32) - + 100) - <= dst - { - return Some(()); + + ways.into_iter().collect_vec() +} + +fn num(code: [u8; 4]) -> Vec<Vec<u8>> { + #[rustfmt::skip] + let grid = [ + [b'7',b'8',b'9'], + [b'4',b'5',b'6'], + [b'1',b'2',b'3'], + [0 , b'0',b'A'], + ]; + let starts = once(numpad(b'A')).chain(code.iter().copied().map(numpad)); + pathfind(code.iter().copied().zip(starts), grid) +} + +fn pad(code: Vec<u8>) -> Vec<Vec<u8>> { + #[rustfmt::skip] + let grid = [ + [0, b'^',b'A'], + [b'<',b'v',b'>'], + ]; + let starts = once(dpad(b'A')).chain(code.iter().copied().map(dpad)); + pathfind(code.iter().copied().zip(starts), grid) +} + +fn my_pad(code: Vec<u8>) -> Vec<Vec<u8>> { + #[rustfmt::skip] + let grid = [ + [0, b'^',b'A'], + [b'<',b'v',b'>'], + ]; + let starts = once(dpad(b'A')).chain(code.iter().copied().map(dpad)); + pathfind(code.iter().copied().zip(starts), grid) +} + +pub fn run(x: &str) -> impl Display { + let i = x.as_bytes(); + let codes: [&[u8]; 5] = i.行().carr(); + use rayon::prelude::*; + codes + .par_iter() + .map(|&code_| { + let mut complex = usize::MAX; + let numpad_codes = num(code_.try_into().unwrap()); + let numeric: u64 = reading::all(&code_[..3]); + for code in numpad_codes { + for pad in pad(code) { + for pad in my_pad(pad) { + let complexity = pad.len() * numeric as usize; + if complexity < complex { + dbg!(pad.len()); + dbg!(numeric); + } + complex = complex.min(complexity); + } } } - None + dbg!(complex); + complex }) - .count() + .sum::<usize>() } fn main() { |