bendns' repos / aoc
heh
Diffstat
-rw-r--r--Cargo.toml2
-rw-r--r--src/inp.txt1521
-rw-r--r--src/main.rs199
-rw-r--r--src/util.rs11
4 files changed, 253 insertions, 1480 deletions
diff --git a/Cargo.toml b/Cargo.toml
index c94db9a..c8d7374 100644
--- a/Cargo.toml
+++ b/Cargo.toml
@@ -7,9 +7,11 @@ edition = "2021"
[dependencies]
atools = "0.1.5"
+bitvec = "1.0.1"
# hinted = "0.0.1"
itertools = "0.12.0"
memchr = "2.6.4"
+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 1568517..1436e70 100644
--- a/src/inp.txt
+++ b/src/inp.txt
@@ -1,1391 +1,130 @@
-39|57
-31|97
-31|75
-29|45
-29|73
-29|84
-66|91
-66|39
-66|57
-66|54
-97|16
-97|38
-97|59
-97|11
-97|62
-87|38
-87|59
-87|18
-87|93
-87|13
-87|33
-25|55
-25|22
-25|31
-25|64
-25|33
-25|85
-25|93
-68|11
-68|57
-68|36
-68|78
-68|66
-68|73
-68|39
-68|27
-32|29
-32|73
-32|45
-32|14
-32|48
-32|39
-32|54
-32|74
-32|17
-17|76
-17|45
-17|25
-17|14
-17|91
-17|11
-17|27
-17|38
-17|16
-17|22
-34|66
-34|91
-34|64
-34|29
-34|74
-34|65
-34|68
-34|26
-34|36
-34|13
-34|93
-48|76
-48|34
-48|55
-48|22
-48|42
-48|89
-48|14
-48|85
-48|87
-48|23
-48|38
-48|79
-73|62
-73|13
-73|42
-73|25
-73|55
-73|26
-73|65
-73|59
-73|18
-73|21
-73|64
-73|34
-73|79
-52|21
-52|18
-52|13
-52|22
-52|32
-52|55
-52|85
-52|42
-52|93
-52|39
-52|26
-52|66
-52|34
-52|68
-74|27
-74|57
-74|48
-74|73
-74|91
-74|16
-74|87
-74|38
-74|54
-74|75
-74|29
-74|62
-74|69
-74|84
-74|23
-38|37
-38|21
-38|13
-38|42
-38|64
-38|55
-38|66
-38|23
-38|85
-38|32
-38|79
-38|34
-38|89
-38|33
-38|52
-38|22
-69|65
-69|62
-69|38
-69|55
-69|34
-69|37
-69|33
-69|79
-69|21
-69|18
-69|87
-69|23
-69|85
-69|22
-69|16
-69|93
-69|89
-11|18
-11|85
-11|89
-11|59
-11|52
-11|22
-11|26
-11|87
-11|25
-11|76
-11|37
-11|23
-11|42
-11|21
-11|62
-11|38
-11|13
-11|69
-33|97
-33|27
-33|68
-33|29
-33|44
-33|31
-33|93
-33|66
-33|32
-33|84
-33|11
-33|45
-33|17
-33|54
-33|78
-33|75
-33|39
-33|36
-33|91
-91|79
-91|55
-91|22
-91|87
-91|23
-91|36
-91|25
-91|16
-91|76
-91|45
-91|59
-91|11
-91|75
-91|29
-91|62
-91|27
-91|69
-91|54
-91|48
-91|52
-75|34
-75|21
-75|42
-75|25
-75|76
-75|79
-75|23
-75|89
-75|18
-75|22
-75|26
-75|62
-75|69
-75|73
-75|11
-75|85
-75|37
-75|14
-75|52
-75|59
-75|38
-59|55
-59|13
-59|79
-59|32
-59|65
-59|93
-59|42
-59|52
-59|18
-59|44
-59|37
-59|85
-59|22
-59|25
-59|68
-59|33
-59|38
-59|31
-59|21
-59|23
-59|89
-59|26
-26|29
-26|39
-26|44
-26|31
-26|91
-26|17
-26|32
-26|93
-26|74
-26|66
-26|48
-26|57
-26|36
-26|97
-26|13
-26|45
-26|64
-26|65
-26|27
-26|33
-26|84
-26|78
-26|68
-79|42
-79|26
-79|57
-79|31
-79|89
-79|93
-79|18
-79|17
-79|33
-79|68
-79|74
-79|39
-79|85
-79|37
-79|78
-79|21
-79|44
-79|66
-79|65
-79|34
-79|64
-79|32
-79|97
-79|13
-42|37
-42|18
-42|13
-42|97
-42|29
-42|39
-42|78
-42|64
-42|65
-42|66
-42|89
-42|26
-42|44
-42|57
-42|85
-42|34
-42|32
-42|93
-42|31
-42|74
-42|91
-42|17
-42|33
-42|68
-18|17
-18|97
-18|44
-18|36
-18|29
-18|33
-18|91
-18|27
-18|64
-18|74
-18|57
-18|65
-18|13
-18|68
-18|84
-18|26
-18|78
-18|39
-18|66
-18|54
-18|93
-18|31
-18|32
-18|37
-22|26
-22|93
-22|13
-22|78
-22|66
-22|37
-22|31
-22|97
-22|34
-22|32
-22|85
-22|21
-22|39
-22|42
-22|65
-22|64
-22|44
-22|33
-22|89
-22|74
-22|79
-22|68
-22|55
-22|18
-62|44
-62|25
-62|85
-62|22
-62|64
-62|33
-62|13
-62|87
-62|26
-62|89
-62|16
-62|23
-62|79
-62|38
-62|59
-62|93
-62|55
-62|37
-62|18
-62|21
-62|42
-62|34
-62|65
-62|52
-21|34
-21|66
-21|93
-21|17
-21|44
-21|37
-21|68
-21|26
-21|74
-21|57
-21|18
-21|91
-21|65
-21|13
-21|31
-21|89
-21|32
-21|85
-21|39
-21|97
-21|78
-21|42
-21|64
-21|33
-93|84
-93|11
-93|57
-93|45
-93|36
-93|29
-93|76
-93|39
-93|31
-93|14
-93|91
-93|32
-93|66
-93|75
-93|48
-93|97
-93|78
-93|73
-93|74
-93|54
-93|17
-93|27
-93|44
-93|68
-23|32
-23|26
-23|68
-23|79
-23|39
-23|64
-23|25
-23|65
-23|22
-23|85
-23|31
-23|93
-23|55
-23|21
-23|13
-23|89
-23|37
-23|66
-23|52
-23|18
-23|33
-23|44
-23|42
-23|34
-84|52
-84|73
-84|11
-84|55
-84|14
-84|87
-84|76
-84|89
-84|16
-84|62
-84|48
-84|42
-84|54
-84|21
-84|69
-84|38
-84|22
-84|45
-84|79
-84|34
-84|23
-84|75
-84|59
-84|25
-16|22
-16|18
-16|85
-16|65
-16|37
-16|44
-16|13
-16|21
-16|38
-16|59
-16|25
-16|23
-16|87
-16|55
-16|68
-16|52
-16|89
-16|33
-16|34
-16|64
-16|42
-16|79
-16|26
-16|93
-85|44
-85|65
-85|39
-85|37
-85|84
-85|57
-85|64
-85|26
-85|32
-85|91
-85|74
-85|33
-85|18
-85|27
-85|78
-85|93
-85|17
-85|97
-85|66
-85|31
-85|36
-85|29
-85|13
-85|68
-55|26
-55|89
-55|64
-55|37
-55|78
-55|44
-55|93
-55|68
-55|39
-55|97
-55|79
-55|17
-55|21
-55|31
-55|85
-55|66
-55|13
-55|65
-55|42
-55|18
-55|34
-55|33
-55|32
-55|74
-65|75
-65|66
-65|11
-65|78
-65|39
-65|68
-65|44
-65|97
-65|36
-65|31
-65|45
-65|91
-65|14
-65|48
-65|33
-65|57
-65|84
-65|17
-65|93
-65|54
-65|27
-65|29
-65|74
-65|32
-76|37
-76|25
-76|42
-76|69
-76|23
-76|18
-76|16
-76|89
-76|62
-76|52
-76|34
-76|55
-76|21
-76|13
-76|79
-76|38
-76|65
-76|85
-76|26
-76|59
-76|87
-76|73
-76|64
-76|22
-27|21
-27|55
-27|38
-27|79
-27|59
-27|73
-27|75
-27|11
-27|16
-27|62
-27|42
-27|23
-27|76
-27|22
-27|45
-27|34
-27|52
-27|84
-27|87
-27|25
-27|48
-27|69
-27|54
-27|14
-14|52
-14|73
-14|22
-14|69
-14|25
-14|34
-14|16
-14|23
-14|21
-14|37
-14|38
-14|64
-14|87
-14|85
-14|59
-14|26
-14|13
-14|18
-14|76
-14|42
-14|62
-14|79
-14|55
-14|89
-36|48
-36|75
-36|23
-36|21
-36|73
-36|84
-36|54
-36|87
-36|25
-36|62
-36|42
-36|16
-36|79
-36|76
-36|27
-36|38
-36|11
-36|22
-36|69
-36|52
-36|45
-36|14
-36|55
-36|59
-13|17
-13|44
-13|27
-13|93
-13|32
-13|33
-13|66
-13|48
-13|91
-13|31
-13|54
-13|78
-13|57
-13|29
-13|64
-13|84
-13|74
-13|68
-13|39
-13|45
-13|97
-13|36
-13|75
-13|65
-57|29
-57|14
-57|54
-57|25
-57|76
-57|45
-57|59
-57|69
-57|91
-57|75
-57|87
-57|27
-57|16
-57|11
-57|22
-57|84
-57|55
-57|73
-57|38
-57|36
-57|48
-57|62
-57|52
-57|23
-89|29
-89|18
-89|66
-89|37
-89|33
-89|68
-89|39
-89|85
-89|13
-89|44
-89|97
-89|27
-89|91
-89|32
-89|93
-89|31
-89|64
-89|36
-89|74
-89|57
-89|17
-89|65
-89|26
-89|78
-78|75
-78|23
-78|45
-78|48
-78|69
-78|25
-78|17
-78|84
-78|73
-78|29
-78|36
-78|14
-78|91
-78|57
-78|76
-78|87
-78|62
-78|27
-78|38
-78|16
-78|11
-78|54
-78|59
-78|52
-64|33
-64|27
-64|44
-64|57
-64|78
-64|11
-64|65
-64|48
-64|31
-64|93
-64|39
-64|45
-64|17
-64|84
-64|91
-64|74
-64|29
-64|75
-64|68
-64|97
-64|32
-64|36
-64|54
-64|66
-54|34
-54|16
-54|79
-54|85
-54|23
-54|87
-54|69
-54|73
-54|52
-54|21
-54|14
-54|75
-54|22
-54|11
-54|48
-54|59
-54|25
-54|38
-54|45
-54|55
-54|89
-54|76
-54|62
-54|42
-37|91
-37|65
-37|44
-37|13
-37|31
-37|64
-37|17
-37|66
-37|33
-37|36
-37|78
-37|93
-37|68
-37|74
-37|32
-37|29
-37|26
-37|48
-37|39
-37|54
-37|97
-37|84
-37|57
-37|27
-44|54
-44|75
-44|68
-44|69
-44|14
-44|45
-44|97
-44|17
-44|84
-44|29
-44|74
-44|78
-44|27
-44|66
-44|31
-44|39
-44|32
-44|91
-44|57
-44|76
-44|11
-44|48
-44|73
-44|36
-45|76
-45|34
-45|73
-45|21
-45|85
-45|38
-45|59
-45|25
-45|79
-45|87
-45|11
-45|62
-45|52
-45|75
-45|16
-45|37
-45|18
-45|23
-45|22
-45|89
-45|69
-45|55
-45|42
-45|14
-39|29
-39|73
-39|48
-39|59
-39|38
-39|36
-39|87
-39|14
-39|54
-39|91
-39|17
-39|74
-39|76
-39|11
-39|62
-39|78
-39|16
-39|45
-39|69
-39|27
-39|75
-39|97
-39|84
-31|57
-31|48
-31|39
-31|11
-31|27
-31|74
-31|54
-31|66
-31|36
-31|91
-31|16
-31|78
-31|87
-31|45
-31|17
-31|76
-31|84
-31|69
-31|14
-31|29
-31|62
-31|73
-29|11
-29|87
-29|79
-29|25
-29|16
-29|36
-29|22
-29|48
-29|21
-29|62
-29|14
-29|69
-29|75
-29|55
-29|59
-29|76
-29|23
-29|52
-29|38
-29|27
-29|54
-66|14
-66|59
-66|69
-66|27
-66|75
-66|62
-66|84
-66|45
-66|17
-66|78
-66|76
-66|97
-66|87
-66|11
-66|16
-66|36
-66|73
-66|29
-66|48
-66|74
-97|27
-97|91
-97|29
-97|57
-97|78
-97|45
-97|54
-97|14
-97|48
-97|23
-97|69
-97|17
-97|36
-97|73
-97|74
-97|76
-97|84
-97|87
-97|75
-87|44
-87|85
-87|79
-87|55
-87|21
-87|23
-87|22
-87|65
-87|64
-87|42
-87|26
-87|68
-87|32
-87|52
-87|34
-87|89
-87|25
-87|37
-25|34
-25|21
-25|65
-25|42
-25|26
-25|13
-25|44
-25|79
-25|18
-25|68
-25|97
-25|89
-25|32
-25|37
-25|39
-25|74
-25|66
-68|32
-68|62
-68|45
-68|91
-68|29
-68|74
-68|54
-68|14
-68|69
-68|75
-68|84
-68|76
-68|17
-68|48
-68|97
-68|31
-32|69
-32|31
-32|11
-32|27
-32|66
-32|36
-32|97
-32|75
-32|76
-32|84
-32|91
-32|16
-32|57
-32|78
-32|62
-17|57
-17|23
-17|36
-17|69
-17|29
-17|73
-17|75
-17|62
-17|59
-17|48
-17|87
-17|84
-17|54
-17|52
-34|31
-34|57
-34|32
-34|85
-34|39
-34|37
-34|78
-34|17
-34|97
-34|44
-34|18
-34|89
-34|33
-48|52
-48|75
-48|21
-48|59
-48|18
-48|69
-48|73
-48|16
-48|62
-48|11
-48|45
-48|25
-73|52
-73|33
-73|16
-73|85
-73|89
-73|23
-73|87
-73|22
-73|38
-73|69
-73|37
-52|64
-52|31
-52|44
-52|33
-52|25
-52|97
-52|65
-52|89
-52|79
-52|37
-74|36
-74|76
-74|17
-74|11
-74|78
-74|14
-74|52
-74|45
-74|59
-38|26
-38|65
-38|31
-38|68
-38|93
-38|44
-38|25
-38|18
-69|13
-69|26
-69|25
-69|52
-69|42
-69|59
-69|64
-11|16
-11|73
-11|34
-11|55
-11|14
-11|79
-33|74
-33|14
-33|48
-33|76
-33|57
-91|14
-91|38
-91|73
-91|84
-75|55
-75|87
-75|16
-59|34
-59|64
-26|54
-
-78,45,48,38,52,62,29
-87,59,38,52,25,55,79,42,34,85,37,26,13,64,65,33,68
-57,29,84,48,45,75,11,14,76,73,69,16,38,23,22
-74,57,91,36,27,84,54,45,75,11,14,76,73,69,87,59,38
-69,62,16,87,59,38,23,52,25,22,55,79,21,42,34,89,85,18,37,26,13,64,33
-33,44,68,32,31,66,39,97,74,78,17,57,91,29,36,27,54,48,75,11,14
-32,66,39,97,74,78,17,57,91,29,36,27,84,54,48,45,11,14,73,69,62
-74,66,65,34,93,32,21,26,89,31,78,44,18,13,37,85,33,68,79,64,55
-38,52,25,55,21,34,85,18,26,13,64,33,93,44,68,32,31
-68,36,64,33,48,32,93,31,13,26,74
-48,45,75,11,76,73,69,62,87,59,38,23,22,55,79,21,42,34,85
-33,16,44,34,85,79,65,22,42,25,64,87,18,55,52,89,13
-73,69,62,16,87,59,38,23,52,25,22,55,79,21,42,89,85,18,37,26,13,64,65
-14,78,45,23,16,36,57,74,76,87,75,59,62,73,54,27,17,91,48,29,84,69,38
-33,93,44,32,31,66,97,74,78,17,57,91,29,36,84,54,48,45,75,11,14
-38,23,79,42,34,37,33,32,31
-65,93,44,68,32,31,66,39,97,74,78,17,57,91,36,27,84,54,48,75,11
-11,84,59,45,54,38,36,14,29,52,16,27,62,76,87,78,75
-54,48,45,75,11,14,76,73,69,62,16,87,59,38,23,52,25,22,55,79,21,34,89
-34,18,26,74,29,31,85,17,64
-16,87,38,52,21,34,18,37,13,64,33
-91,31,78,66,27,84,74,36,32,39,68,73,44
-69,62,36,74,45,66,54,91,14,11,27,32,75,39,84,48,73,76,31,29,17,78,97
-44,68,32,31,66,74,78,57,36,27,84,54,14,76,73
-59,73,22,21,76,62,14,23,16,79,27,36,55,75,38,54,48,11,52,45,25,84,69
-29,36,27,54,45,75,11,14,73,69,62,16,87,59,38,23,52,25,22,55,79
-64,68,39,44,93,13,31,26,74,33,22,66,79,42,55,34,18,65,89,85,37
-79,18,37,13,32,66,17
-87,38,78,57,36,62,45,17,91,59,23,84,76,75,54,14,29,27,48,16,11
-87,59,23,55,79,42,85,18,37,64,65,33,93,44,68
-68,17,57,31,11,48,54,73,14,76,91,75,69,74,78,32,84,45,97,66,29,36,39
-38,55,65,52,13,87,18,44,22,16,64,26,23,34,37,42,59,85,21
-89,85,26,13,64,65,33,68,31,66,74,17,57,91,36
-75,11,14,76,73,62,16,87,59,38,23,52,25,22,55,79,21,42,34,89,85,18,37
-59,93,33,79,62,16,55
-66,39,17,36,84,54,48,75,11
-89,21,37,79,93,25,22,52,34,42,64,55,23,68,44,65,32,66,31,26,85,18,13
-13,64,32,31,17,84,54
-16,65,25,33,55,79,21,34,87,18,64,93,52,38,37,23,59,42,62
-91,29,36,84,54,45,75,11,73,69,62,16,87,59,38,23,52,22,55
-31,66,39,17,57,27,11,62,16
-26,33,32,66,29,36,48
-18,37,26,65,33,44,32,66,39,97,57,29,36,27,84
-93,44,68,31,39,97,74,78,17,57,91,29,36,27,54,48,45,75,11,14,76
-32,31,66,39,97,78,17,57,91,29,36,27,54,48,45,75,14,76,73,69,62
-26,13,65,31,66,39,74,57,91,36,84,54,48
-68,13,32,93,85,18,25,97,39,42,34
-27,84,11,14,76,69,16,38,25
-93,66,57,27,54,75,76
-16,37,89,73,87,13,14,52,23
-85,37,26,13,65,33,93,44,32,66,39,97,17,91,29,36,27
-66,78,57,75,11,76,69
-75,11,76,73,69,62,16,87,59,38,23,52,25,22,55,79,21,42,34,89,85,18,37
-78,27,73,14,38,45,84,69,23,48,11,87,54,16,62,57,29,74,36,17,59,91,75
-33,68,17,21,39
-26,13,65,33,44,68,32,39,97,74,78,17,91,36,84,54,48
-93,13,68,34,32,37,55
-11,76,73,69,62,16,87,59,38,23,52,22,55,79,21,42,34,89,85,37,26
-14,38,23,25,79,42,89
-57,38,84,75,14,59,23
-25,34,89,18,26,13,64,65,33,93,44,31,66,39,97
-48,91,65,33,97,68,31,57,39,44,27,29,78,64,17,75,93,36,74,66,54,45,32
-87,79,13,65,33
-55,79,33,44,68,74,78
-25,52,26,65,18,13,23,22,37,59,32,42,33,85,44
-57,29,75,59,73,17,36
-16,13,89,33,21,42,65,38,55,37,59,34,44,25,85,23,22,64,87
-32,97,42,39,78,21,33,26,13,85,55
-31,84,74,91,32,78,76,36,62
-69,16,52,22,55,37,33
-13,65,33,68,32,66,39,97,74,78,17,36,27,84,54,48,45
-85,23,13,55,42,89,22,68,93,21,26,79,52,59,65,18,87,25,37,34,38
-34,75,84,23,62,54,48
-76,55,59,62,29,36,38,73,84,16,75,48,87,22,14,79,11
-93,26,21,89,64,31,78,79,17,66,13,65,33,32,44,37,68,74,34
-11,14,76,73,69,62,16,59,38,23,25,22,55,79,21,42,89,37,26
-34,85,93,32,39
-44,68,66,39,78,57,54,14,73
-42,37,21,44,85,16,64
-64,44,32,31,39,97,74,91,36,84,54,45,75
-31,66,39,74,78,17,57,91,36,27,45,75,11,14,76,73,69
-93,97,57,11,14
-65,31,57,13,78,64,45,66,17,48,68,93,54,27,29,36,32,97,44,84,39
-73,45,55,11,23,59,76,75,25,87,34,52,22
-21,34,89,85,18,37,26,13,64,65,33,93,44,68,32,31,66,39,97,74,78,17,57
-42,34,89,85,18,37,13,64,65,33,93,44,68,32,66,39,97,74,78,17,57
-18,37,79,26,11
-16,59,48,11,14,55,36,87,73,21,76,23,69,27,52,75,54,45,62,84,22
-66,78,17,57,91,36,27,84,54
-31,44,65,37,78,33,68,36,32,66,17,18,91,93,64,74,26,89,85
-89,65,79,85,22,18,64,42,55,31,34,33,97,26,13,25,68
-55,21,89,18,26,13,64,93,68,32,31,39,78
-22,18,26,44,32,31,66,39,97
-38,79,21,42,18,37,64,65,31
-34,89,85,18,26,13,64,33,93,68,66,74,78,17,57,91,29
-17,39,16,59,54,36,78,69,57,48,76,27,84,97,91,75,45,73,62,11,14
-65,33,93,44,68,32,31,74,78,17,57,91,29,36,27,84,54,48,45,75,11
-84,48,75,73,16,59,23,52,55,79,21
-93,21,32,66,55,89,42,74,85,68,22,44,13,64,26
-14,76,73,69,62,16,87,59,38,23,52,25,22,55,21,42,34,89,85,18,37,26,13
-32,74,78,27,84,45,11
-65,26,44,74,36,78,89,31,66,32,29,13,57
-89,85,26,93,68,32,31,17,57,91,29
-59,38,23,52,25,22,55,79,21,42,34,89,85,18,26,13,64,65,33,93,44,68,32
-31,66,39,74,17,91,29,36,27,84,54,48,45,75,11,76,73,62,16
-59,91,75,11,84
-91,29,36,11,69,62,16,87,25,22,55
-91,97,39,29,57,32,73,78,48,11,84,75,45,76,27,36,69,31,68,66,74,14,17
-33,93,44,85,22,26,64,31,32,65,52,66,34,55,68,39,37,42,18
-23,37,26,42,34,65,18,21,68,79,33,31,66,89,52,22,25,93,32
-55,79,89,13,32,31,78
-84,48,45,14,69,87,38
-91,29,36,27,84,54,45,75,76,73,62,87,59,38,23,52,25,22,55
-37,33,18,66,34,64,32,89,26,79,85,25,68,39,52,44,21
-76,73,87,22,79,21,26,13,64
-75,11,14,76,73,62,16,87,22,21,42,34,89,85,37
-52,25,22,55,79,21,42,34,85,18,37,26,13,65,33,93,44,68,31,66,39
-65,22,33,79,13,68,32,42,37,44,26,25,64,85,18,93,66,89,39
-73,23,34,85,37,26,65
-45,75,11,14,76,73,69,62,16,87,59,38,23,52,25,22,55,79,21,42,34,89,85
-14,59,69,87,26,13,34
-42,34,89,26,64,65,44,31,66,39,78,17,91
-18,37,26,13,93,32,31,66,97,78,57,29,36
-42,34,23,11,79,45,75,52,55,73,38,54,22,25,87
-85,34,68,65,33,21,37,26,93,89,22,79,38,52,55,44,87,42,23,13,18
-75,48,22,73,27,45,57
-14,76,73,69,16,59,38,52,22,55,79,21,34,89,18,37,13
-26,32,48,36,91,33,65,93,66
-36,39,84,13,17,57,26,32,65,54,93,37,97,78,31
-42,87,34,73,13,14,85
-66,13,37,17,91,31,57,65,27,78,84,97,68,54,39
-42,39,97,68,25,26,79,18,21,85,44,34,65,89,93,37,55,31,22
-18,34,55,37,64,44,21
-23,52,84,87,57,38,76,27,69,22,48,62,16
-26,93,29,44,54,33,31,13,66,65,84,78,64,27,74,39,37
-37,18,57,13,17,29,31,32,36,93,26
-27,87,76,29,78,48,17
-32,31,66,39,78,57,91,29,48,75,76,73,62
-59,38,55,79,21,89,85,65,33,44,32
-27,54,17,64,45,39,97,84,36,65,44,32,74
-87,38,23,52,22,21,42,34,89,37,13,65,33,93,68
-66,31,22,32,55,13,42,37,18,68,21,79,89,23,85,44,33,34,25
-93,74,39,78,17,18,64,57,13,31,33,29,36,37,84,26,32,65,27,66,97,91,44
-97,18,33,31,13,93,84,44,26
-62,73,48,27,45,54,36,97,16,84,57,76,11,69,78,91,87,59,39,29,17,74,14
-29,31,14,39,45,11,84,16,57,27,73
-66,39,29,69,87
-69,74,59,84,48,73,16,87,62,97,75,76,54,38,45,29,17,36,14,91,27
-18,64,65,33,93,44,68,32,31,66,39,97,74,78,17,57,91,29,36,27,84
-48,45,73,79,42,34,85
-75,11,76,69,62,16,87,59,23,22,55,79,21,34,85
-93,22,26,64,33,23,52,65,87,18,25,44,55,38,37,21,42,68,85,13,79,89,59
-76,69,87,59,23,52,25,79,42,34,37,13,64
-22,37,13,38,69,18,55,21,52,14,62,34,25,23,16,73,59,85,89
-79,55,62,73,85,87,26,13,69,42,76,37,64,38,16,21,23,52,25,18,59,34,22
-22,21,85,18,26,93,32,66,39,97,74
-14,57,11,17,74,29,87
-64,65,33,31,74,78,27,84,54,48,75
-85,66,68,23,21,32,93
-85,89,93,74,65,26,64,78,79,33,66,39,55
-57,29,27,54,45,11,76,16,87,59,52,25,22
-32,31,97,17,57,29,36,27,84,48,45,75,62
-69,91,76,75,14,36,97,54,11,74,62,17,29,45,27
-48,45,73,62,16,59,38,23,55,89,85
-37,26,13,65,33,93,44,68,32,31,74,78,17,91,29,27,84
-33,65,89,37,69,38,18,79,87,52,16,23,34,59,21,62,26,42,55
-74,17,91,27,84,54,48,45,75,11,14,76,73,69,62,16,87
-66,39,74,78,91,36,27,84,54,48,45,75,11,14,69,16,87
-85,25,13,55,21,64,93,38,62,79,65,23,37
-44,36,33,68,29,32,13,65,97,39,27
-16,22,38,14,62,11,52
-45,36,93,68,14,33,44,32,48
-93,57,45,97,75,78,27,76,14
-62,23,65,33,22,34,13,21,69,79,87
-22,69,14,16,52,79,73,11,37
-66,68,26,13,39,34,52,85,32,64,33
-64,33,44,68,39,74,78,17,57
-37,21,73,25,38,55,62,59,34,87,79,89,64
-84,59,73,74,75,17,91,78,23
-78,45,74,17,84,27,91,29,14
-54,45,44,27,17,39,75,31,57,64,48
-25,84,23,45,57,69,91,76,87,17,27,73,62,29,54,52,11
-97,91,29,84,45,75,11,14,76,59,38
-17,57,91,36,27,84,48,45,11,76,73,69,62,16,59,38,23,52,25
-21,42,89,85,18,37,26,13,64,65,33,44,68,32,66,39,97,74,78,17,57
-34,21,93,23,65,52,37,32,26,25,22
-21,89,87,59,16,62,26,76,55,23,11,14,25,69,42,85,79,34,38,22,37
-27,54,11,14,62,87,59,38,52,25,22,55,79
-42,34,89,85,18,37,26,13,64,65,33,93,44,68,32,31,66,39,97,74,78,17,91
-23,25,22,55,34,89,65,93,32
-68,13,38,32,18,26,93,89,52,85,22,42,44,65,25,34,21,59,33
-57,91,29,36,27,84,54,48,45,75,14,76,73,69,62,16,87,59,38,23,52,25,22
-91,29,27,14,16,52,25,22,55
-97,26,13,79,66,37,64,42,31,55,65,85,39,44,22,18,68,34,93,33,32
-87,11,17,27,36,14,29,76,75,69,78,74,59,91,38,48,62,73,16,57,23
-42,89,85,18,64,65,33,93,66,97,74,78,91
-75,11,14,76,73,69,62,16,87,59,38,23,52,25,22,55,79,21,42,34,89,18,37
-26,64,65,33,93,44,68,32,31,66,39,78,17,57,91,29,36,27,84,54,48
-38,23,22,55,42,34,89,37,26,33,93
-29,18,34,13,89,17,39,37,26
-76,73,69,62,16,87,59,38,23,52,25,22,55,79,42,34,89,85,18,37,26,13,64
-68,89,32,17,85,42,74,33,65,18,34,37,31,79,44
-23,21,73,18,42,22,34,14,79,59,69,45,25,52,87,55,75
-75,11,14,73,69,62,16,87,59,38,23,52,25,22,55,21,42,34,85,18,37
-31,26,17,39,97,36,13,65,89,29,64
-39,97,74,17,91,29,36,27,84,54,45,11,14,76,73,69,62,87,59
-65,44,32,66,97,78,57,91,36,27,54,48,45,75,11
-31,74,78,57,29,84,45,75,62
-52,25,22,55,79,21,42,34,89,85,18,37,13,65,33,44,68,32,31,66,39
-21,62,18,25,69,55,26,65,85,79,33,34,89,42,13,59,22,87,38
-91,29,27,69,38,25,55
-27,84,48,75,11,76,73,69,62,16,87,59,38,23,52,25,55,21,42
-34,32,37,55,44,52,22,42,23,26,66,85,25
-65,33,93,44,68,32,66,39,97,74,78,17,57,29,36,84,54,48,45,75,11
+..................#................................................................#........#.....................................
+...#...........#...................................................#........................................#.................#...
+...................................#................#.#...............#.................................................#.........
+.....#......#................#.....................................................................#..........#........#......#...
+............................................................................................#.....................#...............
+.....................#..##...#........................#.................#.......................#..#.........#.......#...#......#.
+............##....................................##..................#...............................#....#......................
+.............#............#.#..#.......#...........#..............#...............#.....#.........................................
+....................#..........##.........#.........#................#............................................................
+....#.......#................................................................#...#.#..........................................#.#.
+..#..............#.....................................#..........#.#....#..............#..................#.#............#.......
+.#.......#.........................#........................#..#.....#............................................................
+........#...#......................#...........#......................................#....................#......................
+.............................#..............#........##....#....................#......#....................#............#......#.
+..............#..............#............#.......................##....#..........................................#.........#....
+.............#............#..........#..........#...#.....................................................#.......................
+..#........#.....#..........................................#................................................#...#.#...#..........
+........#.....................#...#..#......#.........................................................#.....##.........#..........
+..............................................................................................#...#...............................
+..#.......................#..........................#......#...................................................................#.
+.......#.........................#..............#.........#.............#.......................................#...#.............
+..................#.................#.......................#....................#....................................#...........
+...#...#.......#......##.#...............#....#..............#..........................................#....#..#.................
+#................................#.......#.....#.......#.............#..................#........#................................
+...........#..................................#.......................................................................#.#..#......
+.......#........#.........................................#..........................#...........................#.....#..........
+................#..#.....................#..#...........................#...........................................#.............
+#...#.......................#................................................#................#................................#..
+..........#...........................#.......#............................................................................#.....#
+..................................#............................................................#..................................
+......................#........#.............#....#.....#.......#..........................#..........................#...........
+...........................##.................#.............#........................#...#..................#.....................
+.............................................................................................................#....#..........#....
+................#...................................#...........#..........#....................#............................#....
+........#....#................................................#................##..#..................................#...........
+...........#....................................................#...#.#......#....................................................
+.......................#.........................................................^....................................#...........
+..........................#.............##..#........#.#....#.......#....................#...........#.........#.....#............
+........#...........................#..#..........................................................#...............................
+....#....................................#....#.........................................#.........#...............................
+...............#...................................#.....#.................................#....................................#.
+......#...............................................................#.............................#........................#....
+.........................#.....#.........................#.#...............#.........#.....#..................#..#.........#......
+.........................................................#......#........##.......................#...#......#................#...
+.......................................#.....#.................................#..................................................
+..................#..................................#..........................................................................#.
+...................#....#.........#.......#................#....................#.........................#......#.....#..#.......
+................................#..............................................................................#....#.............
+.....................#.#.............#.................#..........#.......#.........................................#.............
+......#....................#....................................................................#...#.............................
+........#........#...........#.##.............#........................#............#..............#.........#....#........#......
+........................#.................................................................#.......................................
+............................................................#.....#....................#............#.....#....#............#.....
+...........#............#....#........................................................##............#..............#..............
+...........#...........#.....#..............#..............##....#........#......#................................................
+..#................................................................................#......................#......#................
+....................#.........#......................#.............................#.......#.......................#.............#
+..#...#....#......................................................................................................#...............
+...........#................................................................................#...............................#.....
+....................................#............#..........#.........................#..................................#.......#
+...................#......#...................#............#......#........#................#.............#...........#.........#.
+........................#..................................#........#..................#..........................................
+............#..#...........#..................##....................#...........................................#.................
+.......................................................................................#.....#............#.......................
+...............................................#....#................................#..#..........................#..#...........
+..............#..#.....#.........#....................#.......#..#..............#...............................#.....#...........
+..........#............................#..........................................................................................
+........................................#........#........................................................#.#.....................
+#................#......................#..................................................................................#......
+...............................................................................#................................#.................
+...................................................................................................................#.#........#...
+#........................................................................#......................................#.#...............
+...#......#............#...................#.............#........#..........................................#......#.............
+..............##....#...................................................#......................#..................................
+...............#........................................................................#...........#...#.#.......................
+..........#.#.....#................................#...........#........#.......#.................................................
+#....................#......................................................................................#.....................
+..............#...##...........................................#.............#.......#..................#..............#..........
+.#.............................................#..............................................................................#...
+...#................................#............................................#............................#...................
+..............................#......................................................#..........................................#.
+...................#.....................................#..................................#......#..............................
+....#.#..........##.............#.......#........................##..........#.................#..................................
+#..#................#........##....................................................................................#..............
+........#...#.........................................................................#...........................................
+......................................................#....#...................#..#.................................#.............
+........#...............#........#..............................................#............................#....................
+...#..............................#.........................................##.......................................#....#.......
+...#................#..............#.......#......................................................................................
+........#..................#.............................................................#...........................#....#.......
+......................#.#..........#.......#..................................#..#...#............#...............#...............
+.....#..................#....#..#......#.......................#.....................................................#............
+.....#................................#.........................#..................#.#..........#...#............#.....#..........
+....#...................#....#.#.........#........#..................................................................#....#..#....
+........#...............#......................................#........#..............................#..........................
+....#...#.#.....#..............#..................#..........#...#..#......................#...#..........#......................#
+...........#...................................................................................................#................#.
+.................................##..............#.............................#...............................#..................
+...........#.................#.............##...................................#.......................#.................##......
+.....#..................#......#........#.................................................#..#........................#..#........
+......#.......#......................................................................#.#.........#....#...........................
+..................#.#........................#......#................................................................#......#.....
+.....................#............#...................#.....#....................................#.......#..........#.......#.....
+#.............................#...............................#...#...............................................................
+..##.........#........#......................................#.....................#...#.............#............#..#............
+..........#.....................#..#....................#...#....................#....................#.....................#.....
+...........#..........#...............#..#..........#..............................................#.#............................
+............#...#...#.............#.........#.............................#...............#.......................................
+.........#...........#...............................................................#............................................
+.#..#.................................................................#............#.#.......................##...................
+........##............#...................#................................#......................................................
+............................................#..........................#..........................................................
+#...................#...........#..............#...#............#.#........#.................#......#.............................
+........#....................................#....................................................................................
+...........#.........#..#...............#...........#.....##.#......#....##............#....#....#.#.........##.........#.........
+..#......................#..........#.................#.................#......#.............................#........#...........
+....................#.................#....#..............................#....#.............#....#....#.....................#....
+............#.................#.................................#...............................#..#...........................#..
+...................................................#.....#..............#.......#....................#.#..........................
+..#.........##..#........#...................................................................................#............#.......
+.....#..............................#......................................................................#........#.............
+................................#........##.......#...............#..............#.......#...#.#........#.........................
+..............................#.....................#.........................................#..................................#
+...........#...................##.................#.................................#...............................#........#....
+..............................#...##......#..................#...#................................#......#.......#...............#
+.....................##......#......#.#.......#..............#......#.................#.........#...................#.............
+..........................#................................#...........#..........................................................
+...#.....#....................#.....................#...#.....#.............................#.#....#.....#.#.................#....
+............................#...#........#......................................................................#.....#...........
+............#..........##..................#.............................................................#.....#..#...............
diff --git a/src/main.rs b/src/main.rs
index 7698364..9eeed6e 100644
--- a/src/main.rs
+++ b/src/main.rs
@@ -29,112 +29,133 @@
extern crate test;
pub mod util;
pub use util::prelude::*;
-struct Setz {
- bits: [u128; 100],
-}
-impl Setz {
+
+const SIZE: usize = 130;
+
+#[derive(Clone, Copy)]
+struct bitset16960([u64; 265]);
+impl bitset16960 {
fn new() -> Self {
- Self { bits: [0; 100] }
+ Self([0; 265])
}
- fn insert(&mut self, a: u8, b: u8) {
- unsafe { *self.bits.get_unchecked_mut(a as usize) |= 1 << b };
+ #[inline(always)]
+ fn set(&mut self, index: usize) {
+ unsafe { *self.0.get_unchecked_mut(index >> 6) |= 1u64.wrapping_shl(index as u32) };
}
- fn test(&self, a: u8, b: u8) -> bool {
- unsafe { (*self.bits.get_unchecked(a as usize) & 1 << b) != 0 }
+ #[inline(always)]
+ fn get(&self, index: usize) -> bool {
+ unsafe { *self.0.get_unchecked(index >> 6) & 1u64.wrapping_shl(index as u32) != 0 }
+ }
+ #[inline(always)]
+ fn popcnt(self) -> u32 {
+ self.0.into_iter().map(u64::count_ones).sum::<u32>()
}
}
-#[no_mangle]
-pub fn run(i: &str) -> impl Display {
- let i = i.as_bytes();
- let c = unsafe { C! { &i[..1176 * 6]}.as_chunks_unchecked::<6>() };
- let mut bitsets = Setz::new();
- for i in 0..1176 {
- let [a, b, _, c, d, _] = C! { c[i] };
- bitsets.insert((a - b'0') * 10 + (b - b'0'), (c - b'0') * 10 + (d - b'0'));
- }
- let mut sum = 0;
- let mut v = Vec::with_capacity(25);
- 'out: for mut pages in C!(&i[1176 * 6 + 1..]).行() {
- v.clear();
- let [a, b, rest @ ..] = pages else {
- unsafe { std::hint::unreachable_unchecked() }
- };
- pages = rest;
- v.push((a - b'0') * 10 + (b - b'0'));
- let mut i = 0;
- loop {
- mat!(pages {
- [b',', a, b, rest @ ..] => {
- v.push((a - b'0') * 10 + (b - b'0'));
- if let &[a, b] = &v[i..] {
- // valid ones always have a rule
- if !bitsets.test(a, b) {
- continue 'out;
- }
- i += 1;
- }
- pages = rest;
- },
- [] => break,
- })
+// type bits = bitvec::BitArr!(for 16960, in u64);
+// #[derive(Clone, Copy)]
+// struct bitset16960(bits);
+// impl bitset16960 {
+// fn new() -> Self {
+// Self(bits::default())
+// }
+// #[inline(always)]
+// #[no_mangle]
+// fn set(&mut self, index: usize) {
+// unsafe { self.0.set_unchecked(index, true) };
+// }
+// #[inline(always)]
+// #[no_mangle]
+// fn get(&self, index: usize) -> bool {
+// unsafe { *self.0.get_unchecked(index) }
+// }
+// #[inline(always)]
+// fn popcnt(self) -> u32 {
+// self.0.count_ones() as _
+// }
+// }
+
+fn follow(i: &[u8]) -> bitset16960 {
+ let mut marked = bitset16960::new();
+ let grid = unsafe { i.as_chunks_unchecked::<{ SIZE + 1 }>() };
+ let guard = memchr::memchr(b'^', i).ψ();
+ let mut y = (guard / SIZE) as i64;
+ let mut x = (guard % (SIZE + 1)) as i64;
+ let mut pointing = 0u8;
+ loop {
+ marked.set(y as usize * SIZE + x as usize);
+ let (check_x, check_y) = mat!(pointing {
+ 0 => (x, y - 1),
+ 1 => (x + 1, y),
+ 2 => (x, y + 1),
+ 3 => (x - 1, y),
+ });
+ if (check_y >= SIZE as i64) || (check_y < 0) || (check_x >= SIZE as i64) || (check_x < 0) {
+ return marked;
+ }
+ if C! { grid[check_y as usize] [check_x as usize] } != b'#' {
+ (x, y) = (check_x, check_y);
+ } else {
+ pointing += 1;
+ pointing %= 4;
}
- sum += C! { v[(v.len() - 1) / 2] } as u32;
}
- leek!(v);
- sum
+}
+
+#[no_mangle]
+pub fn run(i: &str) -> impl Display {
+ follow(i.as_bytes()).popcnt()
}
#[no_mangle]
pub fn p2(i: &str) -> impl Display {
let i = i.as_bytes();
- let c = unsafe { C! { &i[..1176 * 6]}.as_chunks_unchecked::<6>() };
- let mut bitsets = Setz::new();
- for i in 0..1176 {
- let [a, b, _, c, d, _] = C! { c[i]};
- bitsets.insert((a - b'0') * 10 + (b - b'0'), (c - b'0') * 10 + (d - b'0'));
- }
- let mut sum = 0;
- let mut v = Vec::with_capacity(25);
- for mut pages in C!(&i[1176 * 6 + 1..]).行() {
- v.clear();
- let [a, b, rest @ ..] = pages else {
- unsafe { std::hint::unreachable_unchecked() }
- };
- pages = rest;
- v.push((a - b'0') * 10 + (b - b'0'));
- let mut i = 0;
- let mut faults = 0;
+ fn run(i: &[u8], obstacle: (i64, i64)) -> bool {
+ let mut marked = [bitset16960::new(); 4];
+ let grid = unsafe { i.as_chunks_unchecked::<{ SIZE + 1 }>() };
+ let guard = memchr::memchr(b'^', i).ψ();
+ let mut y = (guard / SIZE) as i64;
+ let mut x = (guard % (SIZE + 1)) as i64;
+ let mut pointing = 0u8;
loop {
- mat!(pages {
- [b',', a, b, rest @ ..] => {
- v.push((a - b'0') * 10 + (b - b'0'));
- if let &[a, b] = &v[i..] {
- if !bitsets.test(a, b) {
- faults += 1;
- }
- i += 1;
- }
- pages = rest;
- },
- [] => break,
- })
- }
- if faults == 0 {
- continue;
- }
- let mid = (v.len() - 1) / 2;
- let (_, &mut mid, _) = v.select_nth_unstable_by(mid, |&a, &b| {
- if bitsets.test(a, b) {
- std::cmp::Ordering::Greater
+ let i = y as usize * SIZE + x as usize;
+ if C! { &marked[pointing as usize] }.get(i) {
+ return true;
} else {
- std::cmp::Ordering::Less
+ C! { &mut marked[pointing as usize] }.set(i);
}
- });
- sum += mid as u32;
+ let (check_x, check_y) = mat!(pointing {
+ 0 => (x, y - 1),
+ 1 => (x + 1, y),
+ 2 => (x, y + 1),
+ 3 => (x - 1, y),
+ });
+ if (check_y >= SIZE as i64)
+ || (check_y < 0)
+ || (check_x >= SIZE as i64)
+ || (check_x < 0)
+ {
+ return false;
+ }
+ if C! { grid[check_y as usize] [check_x as usize] } != b'#'
+ && (check_x, check_y) != obstacle
+ {
+ (x, y) = (check_x, check_y);
+ } else {
+ pointing += 1;
+ pointing %= 4;
+ }
+ }
}
- leek!(v);
- sum
+ let marked = follow(&i);
+ use rayon::prelude::*;
+ (0..SIZE)
+ .flat_map(|x| (0..SIZE).map(move |y| (x, y)))
+ .filter(|&(x, y)| marked.get(y * SIZE + x))
+ .filter(|&(x, y)| i[y * (SIZE + 1) + x] == b'.')
+ .par_bridge()
+ .filter(|&(x, y)| run(&i, (x as i64, y as i64)))
+ .count()
}
fn main() {
diff --git a/src/util.rs b/src/util.rs
index 3b8a80b..f845230 100644
--- a/src/util.rs
+++ b/src/util.rs
@@ -427,6 +427,17 @@ impl std::ops::Add<(u8, u8)> for Dir {
}
}
+impl Dir {
+ pub fn turn_90(&mut self) {
+ match self {
+ Dir::N => *self = Dir::E,
+ Dir::E => *self = Dir::S,
+ Dir::S => *self = Dir::W,
+ Dir::W => *self = Dir::N,
+ }
+ }
+}
+
pub fn pa<T: std::fmt::Debug>(a: &[T]) {
for e in a {
print!("{e:?}");