Added solution for day 25

askrepps · askrepps · commit fefa4d66ab5c · 2021-12-01T02:47:50.000-05:00
diff --git a/advent2020/day25.py b/advent2020/day25.py
@@ -0,0 +1,63 @@
+# MIT License
+#
+# Copyright (c) 2021 Andrew Krepps
+#
+# Permission is hereby granted, free of charge, to any person obtaining a copy
+# of this software and associated documentation files (the "Software"), to deal
+# in the Software without restriction, including without limitation the rights
+# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the Software is
+# furnished to do so, subject to the following conditions:
+#
+# The above copyright notice and this permission notice shall be included in all
+# copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+
+
+import math
+
+from . import util
+
+
+def parse_input(lines):
+    assert len(lines) == 2
+    return int(lines[0]), int(lines[1])
+
+
+def find_loop_size(subject, modulus, output):
+    # uses baby-step giant-step algorithm
+    m = math.ceil(math.sqrt(modulus))
+    subject_to_j_table = {pow(subject, j, modulus): j for j in range(m)}
+    gamma = output
+    subject_to_neg_m = pow(subject, -m, modulus)  # requires python 3.8+
+    for i in range(m):
+        if gamma in subject_to_j_table.keys():
+            return i * m + subject_to_j_table[gamma]
+        gamma = (gamma * subject_to_neg_m) % modulus
+    return None
+
+
+def get_part1_answer(lines):
+    subject = 7
+    modulus = 20201227
+    card_public_key, door_public_key = parse_input(lines)
+    card_loop_size = find_loop_size(subject, modulus, card_public_key)
+    if card_loop_size is not None:
+        return pow(door_public_key, card_loop_size, modulus)
+    door_loop_size = find_loop_size(subject, modulus, door_public_key)
+    if door_loop_size is not None:
+        return pow(card_public_key, door_loop_size, modulus)
+    return None
+
+
+def run():
+    lines = util.get_input_file_lines("day25.txt")
+    print(f"The answer to part 1 is {get_part1_answer(lines)}")
+    print(f"There is no part 2. Go back to enjoying the holidays!")
diff --git a/main.py b/main.py
@@ -47,6 +47,7 @@
 from advent2020 import day22
 from advent2020 import day23
 from advent2020 import day24
+from advent2020 import day25
 
 
 day_runners = [
@@ -73,7 +74,8 @@
     lambda: day21.run(),
     lambda: day22.run(),
     lambda: day23.run(),
-    lambda: day24.run()
+    lambda: day24.run(),
+    lambda: day25.run()
 ]
 
 
diff --git a/test/test_day25.py b/test/test_day25.py
@@ -0,0 +1,39 @@
+# MIT License
+#
+# Copyright (c) 2021 Andrew Krepps
+#
+# Permission is hereby granted, free of charge, to any person obtaining a copy
+# of this software and associated documentation files (the "Software"), to deal
+# in the Software without restriction, including without limitation the rights
+# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+# copies of the Software, and to permit persons to whom the Software is
+# furnished to do so, subject to the following conditions:
+#
+# The above copyright notice and this permission notice shall be included in all
+# copies or substantial portions of the Software.
+#
+# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+# SOFTWARE.
+
+
+import unittest
+
+from advent2020.day25 import get_part1_answer
+from advent2020.util import get_input_data_lines
+
+
+data = """
+5764801
+17807724
+"""
+
+
+class Day25Test(unittest.TestCase):
+    def test_day25(self):
+        lines = get_input_data_lines(data)
+        self.assertEqual(get_part1_answer(lines), 14897079)
