# Binary Diagnostic

`2021-12-03`

Original Prompt ## Part 1

Though the binary math may look intimidating, we can actually avoid it entirely. At least in part 1, it’s just a red herring. Instead of binary numbers, think of them as strings where each character can only have a single value.

This would be easy enough to with an list of lists, each representing a “column” in the arranged input (the first character of each line). We could iterate through the input and then iterate through each line, adding the value to its matching list. Then we’d need to iterate each list and count the values. It would be a fair amount of code, but it *would* work!

Luckily, we know a couple of Python tricks that will *drastically* simplify this one.

There are two major things to tackle:

- How to “rotate” the input
- How to count the lists

Let’s do them in order.

When I say “rotate”, instead of a 3-length list where each element has length 5:

`[ "00100", "11110", "10110",]`

We want a 5 item list where each element has length 3:

`[ ("0", "1", "1"), ("0", "1", "0"), ("1", "1", "1"), ("0", "1", "1"), ("0", "0", "0"),]`

It might look hard, but we already know the function for this. It’s `zip`

, as mentioned in the bonus part of the day 1 solution. It takes many lists and gives you lists of the 1st element from each, the 2nd element from each, etc. But, all we have now are a single list of strings. We want to call `zip('00100', '11110', '10110')`

, but we can’t type that out ahead of time- it has to be dynamically called using our input.

Enter Python’s “spread operator”, the humble asterisk `*`

. It tells Python that instead of passing this list to a function as a single list, transform it into individual arguments:

```
l = [1,2,3]
def func(a, b, c): print(a, b, c)
func(l)# => func() missing 2 required positional arguments: 'b' and 'c'
func(*l)# => "1 2 3"
```

The spread operator lets us call `zip(*self.input)`

and get the exact structure we need! :tada:

Next is counting. It’s easy to do by hand, but Python’s ever-helpful `collections`

package includes a `Counter`

class. Pass it an iterable (anything that can be iterated over) and it’ll count how many times each element appears:

```
from collections import Counter
Counter(("0", "1", "1"))# => Counter({'1': 2, '0': 1})
```

Even better, it comes with a `most_common`

method, which will sort the output:

`Counter(("0", "1", "1")).most_common()# => [('1', 2), ('0', 1)]`

So `some_counter.most_common()[0][0]`

gives us the string which appears the most time.

Wrap that all up and we’ve got our gamma value:

```
from collections import Counter
gamma = "".join( [ Counter(place_values).most_common()[0][0] for place_values in zip(*self.input) ])# => 10110
```

Because each line can only have 2 possible values, you know that for each most common character, the “opposite” one is the least common. So, we invert that string:

```
epsilon = []for c in gamma: if c == '1': epsilon.append('0') else: epsilon.append('1')epsilon = ''.join(epsilon)
# or, shrunk down:
epsilon = "".join(["0" if c == "1" else "1" for c in gamma])
```

It’s good not to pack *too* much functionality into a single line, but in this case, I find it readable enough.

savvy readers will notice that I broke my guideline from literally yesterday where I cautioned against having an

`else`

at the end of a block to catch defaults. In this case, binary isreally doesonly have the two options, so it’s safe enough.

All that’s left is to convert our answers from a string to a binary number, and multiply them:

`return int(gamma, 2) * int(epsilon, 2)`

The `2`

here tells Python to parse the input as a “base 2”, or “binary” number. Other types of numbers work too, such as `8`

, `16`

, and our default counting system of `10`

.

## Part 2

Part 2 is definitely an exercise in reading comprehension. It’s similar to part 1, but we’re filtering the list as we go, so we can’t *just* `zip`

our whole `self.input`

. Instead, we’ll have to get a count of the bits in a given position for all remaining numbers. Easy enough:

`place_to_check = 0values = self.inputcounts = Counter([i[place_to_check] for i in values])`

That works for our first loop, but we’ll have to make it more dynamic as we shrink that list down. We’ll circle back to that though- let’s finish our algorithm first. We need to build a `result`

that has the bits that our answer should start with. We get that value from `counts`

depending on which of the two is higher:

`...result = ""if counts["1"] > counts["0"]: result += "1"elif counts["0"] > counts["1"]: result += "0"else: result += "1"`

Then, we re-filter our values to keep only those that start with the right sequence:

`values = [n for n in values if n.startswith(result)]``

Python’s `.startswith`

makes this easy, as does being able to include an `if`

statement in a list comprehension.

Our current approach works great for the first loop, but we need to plug wire everything else together. We can wrap the above in a `while`

loop, which keeps going until we’ve got exactly 1 value left. We can also ditch manually tracking `place_to_check`

, since it’ll be the same as `len(result)`

. So, all together:

```
values = self.inputresult = ""
while len(values) > 1: place_to_check = len(result) counts = Counter([i[place_to_check] for i in values]) if counts["1"] > counts["0"]: result += "1" elif counts["0"] > counts["1"]: result += "0" else: result += "1"
values = [n for n in values if n.startswith(result)]
```

When the loop exits, we’ll have a `values`

list with exactly one item, which is the `02`

result. The process for `C02`

is similar, but what goes into `result`

changes - it takes the less popular option and `0`

in case of ties. So, let’s put our algorithm in a function and make it configurable:

```
from typing import Literal, Unionone_or_zero = Union[Literal["0"], Literal["1"]]
class Solution(StrSplitSolution): ...
def filter_list( self, val_if_1_higher: one_or_zero, val_if_0_higher: one_or_zero, val_if_tied: one_or_zero, ) -> str: values = self.input result = ""
while len(values) > 1: place_to_check = len(result) counts = Counter([i[place_to_check] for i in values])
if counts["1"] > counts["0"]: result += val_if_1_higher elif counts["0"] > counts["1"]: result += val_if_0_higher else: result += val_if_tied
values = [n for n in values if n.startswith(result)]
return values[0]
```

Same basic idea, but we can manually specify what happens in each of the 3 cases. This makes our final puzzle solution:

`o2 = self.filter_list("1", "0", "1")co2 = self.filter_list("0", "1", "0")return int(o2, 2) * int(co2, 2)`