Hi everyone, I got late into the advent of code problems and currently I'm solving day 3 and 4.

I've been writing my solutions in `rust`

and `go`

(see my aoc repo), and today, while solving **day 03** I came across with an interesting comparison between rust and go code that I'd like to share in this post.

## The problem: Binary Diagnostic

The solution to the problem can be found with array/slice methods: **filter, map and reduce** and **bitwise operators**. For the first part of the problem I knew that I would need to calculate the **complement** of a number applying the **NOT** operator to the `gamma rate`

value so I could get the `epsilon rate`

.

Let's compare both solutions:

**ALERT: spoiler ahead**

```
fn part_one() -> i32 {
let data: Vec<Vec<i32>> = BufReader::new(File::open("data/day_03.in").unwrap())
.lines()
.map(|l| {
l.unwrap()
.chars()
.map(|c| (c as u8 - b'0') as i32)
.collect()
})
.collect();
let cols = data[0].len();
let half = data.len() as i32 / 2;
let gama_rate = data
.iter()
.fold(vec![0; cols], |mut v, line| {
for i in 0..cols as usize {
v[i] += line[i]
}
v
})
.iter()
.map(|d| if *d > half { 1 } else { 0 })
.fold(0, |acc, d| (acc << 1) + d);
gama_rate * (!gama_rate << (32 - cols) >> (32 - cols))
}
```

```
func day03_partOne() uint32 {
file, _ := os.Open("data/day_03.test")
defer file.Close()
scanner := bufio.NewScanner(file)
lineCount := uint(0)
var columnSums []uint
for scanner.Scan() {
line := scanner.Text()
if columnSums == nil {
columnSums = make([]uint, len(line))
}
for i, c := range line {
columnSums[i] += uint(c - '0')
}
lineCount += 1
}
gamaRate := uint32(0)
for _, s := range columnSums {
gamaRate = gamaRate << 1
if s > lineCount/2 {
gamaRate += 1
}
}
colShift := 32 - len(columnSums)
return gamaRate * (^gamaRate << colShift >> colShift)
}
```

Worth to mention: I coded the `rust`

solution **first**.

At first glance, both solutions seem to have the same amount of code, but one solution performs **less operations** than the other. In the `rust`

solution I used array/vector methods to **reduce** and **map** the bits into decimal numbers having the total sum of each column. Whereas in `go`

, and since `go`

is **is not a functional language** I had to use the good old for loops. This "constraint" made me rethink the solution I already had working with `rust`

and thus reduced the **auxiliary space**. For the **time complexity** we can see that in rust we do a few more iterations than in `go`

over the data due to the usage of `map`

and `fold`

functions.

## Analisys

In the `rust`

code, we can identify these steps:

- Read the file content.
- Transform the input into a 2D vector of integers, transforming line by line.
- Reduce the matrix to a a vector where each item is the
**sum of each column** - Transform the vector to a vector of 1 and 0's. For each item, set
**1**if the sum is greater than half of the number of row (this is basically checking if 1 is the most common bit in each column). Else, set it to**0**. At this point we are left with a**binary number.** - Transform the binary number into a decimal number
- Calculate the
`epsilon rate`

by getting the**complement**of the`gamma rate`

.

**Note:** Rust uses the two’s complement to find the bitwise negation for signed types. Rust’s signed integer types are called **the signed two’s complement integer types**.

For the `go`

code our steps are:

- Iterate each line of text
- For each line start adding up the sum of each column by converting string to int.
- Iterate over the columns and start converting the binary number to decimal. Note: we actually calculate each bit of the binary number in each loop and store it into an
**uint32**variable. More on that later. - Calculate the
`epsilon rate`

by getting the**complement**of the`gamma rate`

.

At this point I was more satisfied with my `go`

solution.

## Bitwise operations

Let's analyze what exactly is going on in the last line of each solution.

Let's first consider our data types. When using bitwise operators we can only use **unsigned integers**. As noted before, `rust`

handles this for us when working with **i32**. For `go`

I explicitly used `uint32`

.

So now we want to calculate the **complement**, this is done with the `NOT`

operator. `rust`

uses `!`

whereas `go`

doesn't have the unary operator but it can be replaced with the `XOR`

operator `^`

(nicely explained here). Let's assume our `game rate`

is 11, which is `1011`

. But since our data container has **32 bits** this will actually be `00000000 0000000 00000000 00001011`

. See the problem? If we get the compliment of this number, we will get the complement for the for **all the bits** and this will not be the complement of 11. Our number looks like this:

```
11111111 11111111 11111111 11111100
```

In order to solve this problem, we need to **bit shift** the bits in the number **32 - cols** times to the left, losing the **most significant** bits. At this point our number looks like this:

```
01000000 0000000 00000000 00000000
```

If we now shift **32 - cols** bits to the right, the least significant bits are lost and **zeros** are inserted. Now our number looks like:

```
00000000 0000000 00000000 00000100
```

So now our decimal value is **4**, our `epsilon rate`

.

What are your thoughts on this solutions?

## Top comments (0)