from collections.abc import Iterable Bits = tuple[bool, ...] Input = list[Bits] def most_common(nums: Iterable[Bits], n: int) -> bool: count: int = 0 length: int = 0 for num in nums: if num[n]: count += 1 length += 1 return count >= length - count def bits_to_int(bits: Bits) -> int: return sum(b * 2 ** i for i, b in enumerate(reversed(bits))) def part1(nums: Input) -> int: gamma: Bits = tuple(most_common(nums, i) for i in range(len(nums[0]))) 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(nums, bit) ^ complement 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(c == '1' for c in l.strip()) for l in open('3.in')] print(part1(inp)) print(part2(inp))