Added solutions for day 13

askrepps · askrepps · commit f81f8ee8b212 · 2020-12-13T15:54:48.000-05:00
diff --git a/advent2020/day13.py b/advent2020/day13.py
@@ -0,0 +1,87 @@
+# MIT License
+#
+# Copyright (c) 2020 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 functools
+import operator
+
+from . import util
+
+
+def parse_bus_schedule(lines):
+    return int(lines[0]), [int(token) if token != 'x' else -1 for token in lines[1].split(',')]
+
+
+def find_earliest_bus(arrival_time, buses):
+    t = arrival_time
+    while True:
+        for bus in buses:
+            if bus > 0 and t % bus == 0:
+                return t, bus
+        t += 1
+
+
+def find_time_with_cosmic_bus_alignment(buses):
+    max_bus = max(buses)
+    max_idx = buses.index(max_bus)
+    t = max_bus
+    searching = True
+    while searching:
+        searching = False
+        for idx, bus in enumerate(buses):
+            if bus > 0 and (t + (idx - max_idx)) % bus != 0:
+                searching = True
+                break
+        if searching:
+            t += max_bus
+    return t - max_idx
+
+
+def find_time_with_cosmic_bus_alignment_except_faster_since_apparently_the_buses_are_pairwise_coprime(buses):
+    limit = functools.reduce(operator.mul, filter(lambda x: x > 0, buses), 1)
+    answer = 0
+    skip = 1
+    for idx, bus in enumerate(buses):
+        if bus > 0:
+            current = answer
+            while current < limit and current % bus != (bus - idx) % bus:
+                current += skip
+            if current >= limit:
+                return None
+            answer = current
+            skip *= bus
+    return answer
+
+
+def get_part1_answer(arrival_time, buses):
+    departure_time, bus = find_earliest_bus(arrival_time, buses)
+    return (departure_time - arrival_time)*bus
+
+
+def get_part2_answer(buses):
+    return find_time_with_cosmic_bus_alignment_except_faster_since_apparently_the_buses_are_pairwise_coprime(buses)
+
+
+def run():
+    arrival_time, buses = parse_bus_schedule(util.get_input_file_lines("day13.txt"))
+    print(f"The answer to part 1 is {get_part1_answer(arrival_time, buses)}")
+    print(f"The answer to part 2 is {get_part2_answer(buses)}")
diff --git a/main.py b/main.py
@@ -35,6 +35,7 @@
 from advent2020 import day10
 from advent2020 import day11
 from advent2020 import day12
+from advent2020 import day13
 
 
 day_runners = [
@@ -49,7 +50,8 @@
     lambda: day9.run(),
     lambda: day10.run(),
     lambda: day11.run(),
-    lambda: day12.run()
+    lambda: day12.run(),
+    lambda: day13.run()
 ]
 
 
diff --git a/test/test_day13.py b/test/test_day13.py
@@ -0,0 +1,51 @@
+# MIT License
+#
+# Copyright (c) 2020 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.day13 import get_part1_answer
+from advent2020.day13 import get_part2_answer
+from advent2020.day13 import parse_bus_schedule
+from advent2020.util import get_input_data_lines
+
+
+bus_data1 = """
+939
+7,13,x,x,59,x,31,19
+"""
+
+
+class Day13Test(unittest.TestCase):
+    def test_day13(self):
+        arrival_time, buses = parse_bus_schedule(get_input_data_lines(bus_data1))
+        self.assertEqual(get_part1_answer(arrival_time, buses), 295)
+        self.run_part2_test("7,13,x,x,59,x,31,19", 1068781)
+        self.run_part2_test("17,x,13,19", 3417)
+        self.run_part2_test("67,7,59,61", 754018)
+        self.run_part2_test("67,x,7,59,61", 779210)
+        self.run_part2_test("67,7,x,59,61", 1261476)
+        self.run_part2_test("1789,37,47,1889", 1202161486)
+
+    def run_part2_test(self, bus_line, expected_result):
+        _, buses = parse_bus_schedule(["-1", bus_line])
+        self.assertEqual(get_part2_answer(buses), expected_result)
