Self-reducing bags

links = {}      # source -> target mapping
frontier = [(0, 0)]
digit_counts = lambda num: (num.bit_length() - num.bit_count(), num.bit_count())
while len(frontier) > 0:
    new_zeros, new_ones = old_zeros, old_ones = frontier.pop()
    while True:
        while True:
            (z1, o1), (z2, o2) = digit_counts(new_zeros), digit_counts(new_ones)
            used_zeros, used_ones = z1+z2+(new_zeros>0), o1+o2+(new_ones>0)
            unused_digits = new_zeros + new_ones - used_zeros - old_zeros - used_ones - old_ones
            if unused_digits > 0:
                break
            if (old_zeros+used_zeros, old_ones+used_ones) == (new_zeros, new_ones) and used_zeros+used_ones > 0:
                links[(new_zeros, new_ones)] = (old_zeros, old_ones)
                frontier.append((new_zeros, new_ones))
            new_ones += 1
        if new_ones == old_ones:
            break
        new_zeros, new_ones = new_zeros+1, old_ones
print(f"Found {len(links)} self-reducing bags")