Oh dear, from first glance this is going to be all about binary. Last year I discovered a python package, bitstring that can make it easier to work with bit strings, but it's annoying that Python doesn't handle bitstrings by default.
Right, so we're doing two things at once, firstly we're looking for the most common bit in a stream. Secondly, we're looking at bits in columns rather than each individual word
I'm super tempted at this point to transpose the lines around. Transposition is a way of taking [1,2,3] and [4,5,6] and turning it into [1,4],[2,5],[3,6]. If we did that, we'd be able to then read along a single list and count frequencies.
The other way to do this is to go down the bitstreams, one at a time and keep a count of 1's and 0's in each line. Since we want to know how many we have, we could treat 1's as +1 and 0's as -1, and then at the end, if the total is positive, it's a 1, and if it's negative it's a 0.
Let's try that slightly simpler way instead of fancy transposition
## Import ipytest and get it setup for use in Python Notebook
import pytest
import ipytest
ipytest.autoconfig()
test_data = [line.strip() for line in """00100
11110
10110
10111
10101
01111
00111
11100
10000
11001
00010
01010""".split("\n")]
def most_common_bits(lines):
# First we setup the sums as being 0 for each bit in the first line
sums = []
for bit in lines[0]:
sums.append(0)
for line in lines:
for i,bit in enumerate(line):
match bit:
case "0": sums[i] -= 1
case "1": sums[i] += 1
return [1 if sum >= 0 else 0 for sum in sums]
test_result = most_common_bits(test_data)
assert [1,0,1,1,0] == test_result
Ok, so we can get the most common bits this way. There's two interesting bits in here for new python programmers.
Firstly, I've used the new python 3.10 match case functionality. Discovering pattern matching in Scala a decade or more ago was brilliant, and I've missed it in python. Looking at other peoples solutions yesterday I remembered that Python 3.10 has gained pattern matching.
Pattern matching means you can do match variable and then a set of case statements, if the case matches, then the block is executed. It would have been brilliant for the up, down, forward parsing in day 2!
Secondly, I've used the 1 if sum > 0 else 0 inline if structure. What's unusual here is that I've used it within a list comprehension. It's no different than normal, but it looks a bit funky.
Anyway, our next step is to find the gamma rate, which is just the epsilon rate in reverse. Now we could rerun out algorithm with a different sum at the end. But we also know that if it's the opposite, then the number will just be the bitwise negation of the result.
Time to break out the bitstring module, which allows us to use the ~ for bitwise negation
import bitstring
test_bs = bitstring.BitArray(test_result)
assert 22 == test_bs.uint
assert 9 == (~test_bs).uint
Great, that works, let's try it on real data
data = [line.strip() for line in open("day3.txt").readlines()]
result = most_common_bits(data)
bs = bitstring.BitArray(result)
assert 218 == bs.uint
assert 3877 == (~bs).uint
print(bs.uint * (~bs).uint)
845186
Now I'm glad that I wrote my loop the way I did, as we're going to want to use similar logic for this searching loop.
We're going to want to filter the list of numbers based on the most common and least common bits. We're going to have to calculate the most_common_bits each time however, as the list gets smaller.
So the way it's going to work is we're going to need to search the list for the most common bits. We're then going to look at the nth bit (starting at 0), and filter the list down to only those with the same bit set there Then once we've filtered, we'll increase n, and do it again, until we're left with just one result.
Let's try explaining that in code
def find_oxygen_rating(data):
n = 0;
while (len(data) > 1):
most_common = most_common_bits(data)
data = [item for item in data if int(item[n]) == most_common[n]]
n += 1
return data[0]
assert '10111' == find_oxygen_rating(test_data)
def find_co2_rating(data):
n = 0;
while (len(data) > 1):
most_common = most_common_bits(data)
data = [item for item in data if int(item[n]) != most_common[n]]
n += 1
return data[0]
assert '01010' == find_co2_rating(test_data)
Note: At this point I discovered an error in my most_common_bits. Originally we had return [1 if sum > 0 else 0 for sum in sums], and because there was never a situation in which there was an equal number of 1s and 0s, it didn't matter than I had a greater_than rather than greater_or_equal. But my result was coming out wrong for the bits that were equal, so I modified this to be the >= instead.
So that's not too bad. We could probably neaten that up a bit, but it'll do, let's calculate numbers on the final production data
data = [line.strip() for line in open("day3.txt").readlines()]
oxygen = bitstring.BitArray(bin=find_oxygen_rating(data))
co2 = bitstring.BitArray(bin=find_co2_rating(data))
assert 1459 == oxygen.uint
assert 3178 == co2.uint
print(oxygen.uint * co2.uint)
4636702