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(inp, 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))