Solve 2021 day 7

farbfetzen · farbfetzen · commit eca88a77dd5e · 2021-12-07T19:15:36.000+01:00
diff --git a/README.md b/README.md
@@ -3,7 +3,7 @@
 
 | Year | Stars |
 |------|------:|
-| 2021 |  12 ⭐ |
+| 2021 |  14 ⭐ |
 | 2020 |  50 ⭐ |
 | 2019 |  44 ⭐ |
 | 2018 |   8 ⭐ |
diff --git a/input/2021-07-sample.txt b/input/2021-07-sample.txt
@@ -0,0 +1 @@
+16,1,2,0,4,2,7,1,2,14
diff --git a/python/2021/day07.py b/python/2021/day07.py
@@ -0,0 +1,46 @@
+# https://adventofcode.com/2021/day/7
+
+
+from math import inf
+from statistics import median
+
+
+SAMPLE_PATH = "../../input/2021-07-sample.txt"
+INPUT_PATH = "../../input/2021-07-input.txt"
+
+
+def get_data(filename):
+    with open(filename) as file:
+        return [int(x) for x in file.read().split(",")]
+
+
+def part_1(positions):
+    best_position = int(median(positions))
+    return sum(abs(pos - best_position) for pos in positions)
+
+
+def calc_fuel(steps):
+    return steps * (steps + 1) // 2
+
+
+def part_2(positions):
+    """Just a simple search from min to max position. I could improve it but this one
+    is fast enough. There should be only one minimum so no need to search the other
+    positions after it is found.
+    """
+    min_fuel = inf
+    for best_pos in range(min(positions), max(positions) + 1):
+        fuel = sum(calc_fuel(abs(pos - best_pos)) for pos in positions)
+        if fuel >= min_fuel:
+            return min_fuel
+        min_fuel = fuel
+
+
+if __name__ == "__main__":
+    sample_data = get_data(SAMPLE_PATH)
+    assert part_1(sample_data) == 37
+    assert part_2(sample_data) == 168
+
+    challenge_data = get_data(INPUT_PATH)
+    print(part_1(challenge_data))  # 352331
+    print(part_2(challenge_data))  # 99266250
diff --git a/python/2021/test2021.py b/python/2021/test2021.py
@@ -6,6 +6,7 @@
 import day04
 import day05
 import day06
+import day07
 
 
 class Test2021(unittest.TestCase):
@@ -58,6 +59,15 @@ def test_06(self):
         self.assertEqual(challenge_part_1, 372300)
         self.assertEqual(challenge_part_2, 1675781200288)
 
+    def test_07(self):
+        sample_data = day07.get_data(day07.SAMPLE_PATH)
+        self.assertEqual(day07.part_1(sample_data), 37)
+        self.assertEqual(day07.part_2(sample_data), 168)
+
+        challenge_data = day07.get_data(day07.INPUT_PATH)
+        self.assertEqual(day07.part_1(challenge_data), 352331)
+        self.assertEqual(day07.part_2(challenge_data), 99266250)
+
 
 if __name__ == "__main__":
     unittest.main()
