day 3

2 files changed, 1048 insertions, 0 deletions

diff --git a/3.in b/3.in
new file mode 100644
index 0000000..d89bdcc
--- /dev/null
+++ b/3.in
@@ -0,0 +1,1000 @@
+110000000001
+010011111011
+111000011110
+110101011110
+100000010100
+000101101111
+110100101000
+011100010001
+101001011011
+011000001100
+111101001011
+010001100100
+100101011010
+111101110101
+101001111100
+010010010101
+011100011000
+010110011101
+110001110101
+001111000010
+111011001011
+111111111110
+010000000100
+001011111101
+100111110101
+011011110100
+110101000100
+111010001110
+110101001011
+011100100110
+011100001001
+101001111101
+111111000010
+010010001100
+110010011001
+010100010010
+011010010000
+101111000100
+001010100101
+100010010100
+001000000110
+000011110100
+101101100001
+111100000111
+011010001110
+010110001000
+111101111010
+001001010111
+011001010011
+000111000010
+000010110001
+101000010111
+111010000100
+111001110111
+000000110001
+011111000110
+010110010111
+110100001001
+101100110110
+100111111000
+110000110000
+110110111101
+110011011100
+010001010010
+011011000101
+000001100010
+011001101001
+000111111011
+111000001101
+110100000101
+011000011011
+100101100110
+001001000001
+111011011010
+010101110110
+100011100000
+100000001011
+110101111001
+000101001000
+110111111010
+011001111111
+101000000101
+101000011111
+010010000111
+101101111100
+101110100001
+100111100101
+101111001100
+110101001111
+011100001111
+010000011110
+000010111111
+011110100101
+100010010110
+011101110011
+000000010111
+110111000110
+100110010100
+011110101111
+101101000111
+111111011100
+110000100010
+010110001010
+011001000100
+111001100011
+111101110100
+000011011100
+110011010001
+110011100110
+100000011110
+100100000010
+001000100001
+011000011111
+001001101001
+000100011100
+100001010000
+100000110010
+111001101000
+100011101101
+000111000101
+000011000101
+111110001011
+001111011101
+110110010100
+011010011011
+111111111010
+001010111111
+101111101001
+010000111100
+111010110111
+100100011000
+111010010110
+010100111100
+101001010000
+011100011011
+100101001110
+011100010110
+111010011100
+100110011001
+100110000110
+111010110010
+011000010111
+111101000110
+000001000011
+001011111011
+011100000111
+111011100100
+101111110000
+011111010010
+001100111000
+011001000010
+100110100111
+101000101110
+110100101100
+011101001100
+111100100011
+110101001101
+101111000110
+111010100100
+100101010101
+111011100000
+011100101010
+111111001111
+010010100001
+111001111111
+101000110101
+010001101010
+000110110011
+001010110011
+110001101001
+110110000011
+100111110011
+000100101100
+111010101100
+101011101100
+010110000100
+101001010101
+000001010011
+011110000000
+101111110011
+001010001000
+110000010001
+101010101100
+011010111010
+010100101000
+101100011011
+010010101011
+110101110001
+010101001101
+011110011001
+100000110011
+010110110000
+101100100010
+010000110100
+001000100101
+100011100011
+111000010110
+000110011000
+000011011000
+010101001000
+101000010100
+111011111011
+010110010001
+100111100011
+011011111100
+001010011110
+011110110101
+111100101110
+001001011110
+010100010111
+100011010001
+110110000111
+001000001101
+001011110001
+111001000011
+101101011101
+111000111010
+111111110001
+001100000000
+110011011010
+011010101001
+011010101011
+011010011100
+100100111110
+111001011110
+001010001101
+101101010100
+100100110100
+011000111111
+101011010100
+111010100110
+001111010010
+011001100000
+011010010100
+001100001010
+101001001111
+111011110110
+100101100001
+000100110010
+101111001001
+111001011000
+100010001101
+101101001010
+011001110001
+010110010110
+000100010100
+011011011100
+000101101011
+110010011110
+010010011010
+111110110010
+000010001111
+000010010011
+000000111010
+110001100011
+000010000100
+101011111000
+110111001001
+101111100000
+110101111000
+100010000011
+000001111111
+000110001110
+000010000000
+110110011110
+000101101000
+001101111011
+011101101100
+101100011101
+110001010100
+011010111000
+011101101010
+110010110101
+100101100000
+101001011100
+100101001010
+011110111011
+111101111100
+101000111001
+111001110001
+101100001111
+100001100111
+011001101000
+111000100101
+000000001011
+110011100011
+111010001011
+111100001011
+111101101001
+111001101110
+000110100101
+000111100001
+101101101101
+100000000011
+001100011111
+101101111110
+101010111000
+010100000001
+000110011011
+000100011000
+000001110110
+100111101001
+001111011110
+000010011110
+101001000010
+101001011111
+110011010010
+101100010110
+101110001111
+000111110011
+011011101010
+101010011010
+101100111001
+111111000000
+101100110101
+110100101101
+010000100111
+110011000001
+010001001000
+000111110000
+100101010110
+001010001001
+100100111010
+001010010110
+010111010010
+010010100000
+010110001011
+011001101011
+110001000111
+111001001000
+001101001101
+101000111100
+100011101001
+100011111010
+100000010101
+110010100110
+001000110101
+111100011011
+011001101010
+101011010000
+011111001110
+010011010111
+101100111000
+011111011010
+110110001010
+100010111110
+100001001001
+000001011101
+110001100101
+011001100111
+111001101010
+001000011001
+000011101000
+100100001001
+110001111000
+010111000101
+000111001101
+001110100010
+010110101011
+100111110001
+110000001001
+011100111001
+100111010000
+101111010000
+001110110100
+010111001010
+000100101111
+100000010010
+110110111000
+111010010001
+001101011001
+001011011100
+001001111000
+011101001011
+001101110111
+111111001000
+011001001001
+011100100111
+011011011011
+101010100111
+010101011100
+100000010110
+101101110010
+110111010001
+010000100110
+010011100011
+101111000011
+011110101011
+111101110010
+001100101111
+111101011101
+001010010001
+001110111110
+010101000010
+111010101101
+100001111000
+111100001111
+011010100000
+110001011110
+010000100001
+110001001001
+100101101011
+000010111010
+000110101101
+100110011000
+100100110111
+100010000001
+001110010000
+010001101110
+111001000000
+100010001011
+111010111010
+000100001101
+010101101000
+001101111010
+111100110100
+010010111100
+011010010110
+000001100000
+111111111001
+101001101111
+100011000110
+001100010110
+000110111110
+000001010001
+101010000011
+000110001011
+000110101011
+000011100111
+101011110110
+110100000100
+111000101101
+000100100010
+011011111001
+000010110000
+111010101010
+011000001101
+101111110001
+110101000001
+000000110011
+000100111111
+111001100100
+000011100010
+001100110001
+111000010000
+001011000000
+111000011011
+100001101001
+111100001000
+001011100000
+111101101000
+100100101111
+110110001111
+011110011110
+010011011100
+110110010001
+011001000111
+101111110101
+011101011111
+010100100010
+101101010110
+010001111111
+111110111000
+001010110101
+111000111000
+110101011010
+011001110110
+011101011001
+010100110111
+101101111111
+111111101011
+111010101111
+010000111011
+111010000111
+000100111010
+010011000100
+101010001011
+010111110110
+100001100011
+111001110100
+011000100101
+000011111111
+100101010111
+011000000110
+001011001000
+011100000000
+011110011100
+100101001001
+000001110000
+010110011110
+001111000101
+100101110001
+110111100111
+001010010000
+110011101011
+011111001011
+011010110000
+011011010110
+000111100011
+110000001010
+000010111101
+100100101001
+010100000100
+001101111100
+111000100010
+010110000001
+111010111101
+000001010100
+100100100110
+110011000000
+000111101000
+000110101110
+011101011010
+001100110011
+101011111001
+001101001011
+100110011100
+110001111001
+101101001100
+110000110011
+110000111110
+000010101010
+010001111010
+001100001001
+111000011100
+101011000001
+101000011110
+111001010101
+010001100001
+011001111001
+100010100001
+111101011110
+111110100001
+001011000011
+100010110111
+010100101110
+110001110011
+111001011111
+001101000010
+000001111110
+010011101100
+111010110000
+110001100001
+101001111001
+000101100001
+111110110110
+010010001110
+001010001111
+001010001100
+111000000010
+000101000011
+010110000101
+011111110111
+000000000111
+011101100000
+000011110010
+010110100100
+111011000101
+010111011001
+111111100011
+010111001011
+101110111110
+100001110110
+111110111100
+110011000110
+101100110111
+001000011111
+000000111111
+010100010000
+100000001111
+100010101000
+110110001101
+010101100101
+111110101111
+010010110011
+000101011000
+110001110100
+001111111010
+110100111110
+111010111111
+110100110101
+100000111111
+011011101110
+000001101000
+110011100010
+111011110101
+111100000010
+101000001110
+100101101001
+101110010111
+000001100001
+000101001111
+000101101010
+101011001010
+001100001100
+111010110110
+101100000100
+010011010011
+001000100111
+001110100001
+010101011101
+101011111101
+111110110011
+001101100000
+101111000010
+001110010101
+000111111100
+000110000100
+000101111001
+000011111000
+000010000110
+001010011000
+111111101001
+011000001111
+111010100001
+111110001111
+101110010110
+010011000011
+110001000010
+110111100110
+010100000111
+000011000010
+000000010010
+100111111011
+001011111000
+110010001100
+000111011101
+000101001010
+001100110101
+110110110000
+110111100101
+000000111000
+100011100111
+100100111101
+011011001011
+000100101000
+111101010101
+010011111101
+110100110100
+110011111011
+100111011011
+101000100100
+011000001110
+101000001000
+110101011001
+100110111100
+110010000001
+000111000011
+010001001100
+101001000100
+100000101101
+011011111010
+101000100010
+011001011111
+011001000001
+001100011010
+100011011111
+110011010111
+111000101000
+001001110110
+101010101011
+001110110110
+011111010011
+100111111010
+001111101110
+110010101000
+000001111000
+100110111101
+110110001001
+111000011111
+011111000111
+111100011000
+101001000110
+110010000010
+000100111000
+001000101000
+011100100001
+101101101010
+110110111011
+001011101100
+110111110111
+011000111101
+110000111000
+101010000101
+111010011011
+111011101010
+101100101100
+000110101000
+110011111001
+010111011000
+100101111101
+101110110000
+100001111010
+110101100001
+100010011110
+011000100100
+101110101111
+111011011110
+000110110100
+010100001100
+101001101000
+001001000010
+100110001001
+001011111100
+100011111100
+011100001011
+001100000100
+100111001011
+011101000101
+011110000100
+011011011101
+001001011010
+110110011101
+000000001100
+010111100101
+111011011101
+000100101110
+001100011001
+110001001110
+101010100001
+011101100011
+100000111000
+111111100111
+001000100011
+110000000011
+101001010010
+111101010100
+111101111110
+001110100100
+111100100010
+010000100101
+010100001101
+011010011110
+001110000110
+101000000001
+010111111000
+111111011011
+110110101010
+000000110110
+111001111010
+001110110010
+111011010110
+001100100010
+011111000100
+000111010000
+100101110111
+001011110011
+111110011011
+111001010011
+000110011100
+010111000111
+101000001100
+010101111011
+100001011011
+010100110101
+010000000000
+110010011100
+110101001110
+111010111110
+101101110101
+011010101111
+101010011110
+010111110100
+010100110011
+110110001100
+001011110100
+010001000000
+100011010110
+100111000000
+010111100000
+100010100110
+001100101101
+010111100110
+101101000100
+101110011001
+011011100101
+101101101111
+110010100000
+100100100010
+001100110000
+110110011100
+000010000001
+101001101001
+001001100110
+000101100011
+111101000111
+000110000011
+011011110000
+110010000011
+010111000001
+101101011001
+101100001001
+101100010101
+011010011111
+010100011100
+100111100111
+101110100110
+101011010101
+110110101111
+010001010101
+000010001100
+001110000001
+110011111100
+000001111001
+001000111101
+010011110001
+110100010010
+100000100101
+100100000011
+111110010000
+110010001001
+011111100001
+010011011001
+111110110001
+000011010010
+011101101011
+110011100001
+000110101111
+001111101101
+110101110000
+001000011101
+111111001100
+110101101111
+000110111000
+101100010100
+011101100100
+111000101010
+110001001011
+100010001111
+001101000111
+011000010000
+110010110001
+111100100001
+110111110110
+000010000011
+100001111110
+111001001001
+001011011101
+000100011101
+001100100111
+000011010001
+111111001110
+001111111101
+110001110001
+101010011101
+110010010101
+001011010101
+111110010011
+011001101110
+101000011100
+110100011111
+000001001111
+100001111001
+001101110110
+010111111100
+111101011111
+001111110001
+101001101110
+100100100111
+100010011100
+010110011111
+100010111011
+111011110010
+111010010011
+111001111100
+011100010011
+001010100100
+111001100101
+111100011001
+101110001011
+100000011111
+010010011000
+100001000011
+001001111101
+010111001100
+100101011101
+110011101010
+010010101110
+100011001101
+101100101001
+011110010000
+101000011010
+110100010101
+010110111110
+011110010111
+100000001000
+101000011000
+000111100111
+011001100110
+001010011001
+011011101011
+101000000110
+000100010010
+100100101011
+000101011111
+010000110101
+000000011010
+111101111001
+111011011111
+010000001001
+100101100011
+000111011001
+111011011011
+000011011001
+111101011001
+001000001100
+000110001000
+110111010010
+101100101011
+111101110001
+110101101101
+100111001110
+110010111110
+000010001010
+101101000001
+000011101111
+110000100100
+010001101001
+000000001110
+001110011101
+000100101011
+110100111100
+011000100111
+001110101101
+010101100100
+101110100000
+100110001010
+101110010000
+000111111010
+011011110101
+001111110100
+000111110110
+101011111110
+100010110000
+100100100101
+101000001101
+010011111111
+001110111001
+101010110110
+110010011011
+110001001000
+101110100011
+101001011000
+100111101110
+100111000111
+001000111100
+010101111010
+100010100101
+110011010011
+100100000111
+111010101001
+110001001101
+011000101001
+000110100001
+100011111110
+001100011000
+110100010000
+001010110100
+000100000110
+001011101010
+001100100110
+011111101011
+000101111101
+001110110101
+110000001111
+001010000011
+110101001000
+001000010001
+111011101011
+001001011101
+000001000000
+000110010101
+100110101010
+101010000111
+110101101110
+100000010011
+001110001011
+011110000010
+100000100010
+111111101100
+011010000011
+001101001110
+011100001000
+000001001110
+000111001000
+100100011010
+010000010100
+111110001100
+111100101111
+101000100101
+011100101110
+000011101101
+000100100100
+011111111001
+000100110011
+001011001011
+110101100000
+101111111011
+001101111101
+100110100011
diff --git a/3.py b/3.py
new file mode 100644
index 0000000..32596ef
--- /dev/null
+++ b/3.py
@@ -0,0 +1,48 @@
+from typing import Generator
+from collections.abc import Iterable
+from collections import Counter
+
+Bits = tuple[bool, ...]
+Input = list[Bits]
+
+def column(rows: Iterable[Bits], n: int) -> Generator[bool, None, None]:
+    for row in rows:
+        yield row[n]
+
+def most_common(bits: Iterable[bool]) -> bool:
+    freqs: list[tuple[bool, int]] = Counter(bits).most_common()
+    if freqs[0][1] == freqs[1][1]:
+        return True
+    return freqs[0][0]
+
+def bits_to_int(bits: Bits) -> int:
+    ret: int = 0
+    for i, b in enumerate(reversed(bits)):
+        if b:
+            ret += 2 ** i
+    return ret
+
+def part1(nums: Input) -> int:
+    nbits: int = len(nums[0])
+    gamma: Bits = tuple(most_common(column(inp, i)) for i in range(nbits))
+    epsilon: Bits = tuple(not bit for bit in gamma)
+    return bits_to_int(gamma) * bits_to_int(epsilon)
+
+def part2_impl(nums: Input, complement: bool, bit: int = 0) -> Bits:
+    if len(nums) == 1:
+        return nums[0]
+    target: bool = most_common(column(nums, bit))
+    if complement:
+        target = not target
+    nums = list(filter(lambda n: n[bit] == target, nums))
+    return part2_impl(nums, complement, bit + 1)
+
+def part2(nums: Input) -> int:
+    oxygen: Bits = part2_impl(nums, False)
+    co2: Bits = part2_impl(nums, True)
+    return bits_to_int(oxygen) * bits_to_int(co2)
+
+inp: Input = [tuple(bool(int(c)) for c in l.strip()) for l in open('3.in')]
+
+print(part1(inp))
+print(part2(inp))