Advent of code: Rust, Go, and Binary operators
Tags: rust, go, adventofcode, programming
Published: 2021-12-14 19:32:59

Hi everyone, I got late into the [advent of code](https://adventofcode.com/) problems and currently I'm solving day 3 and 4.
I've been writing my solutions in `rust` and `go` (see my [aoc repo](https://github.com/protiumx/aoc)), 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](https://adventofcode.com/2021/day/3) 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**

```rust
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))
}
```


```go
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](https://www.geeksforgeeks.org/bitwise-not-operator-in-golang/)). 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](https://www.geeksforgeeks.org/left-shift-right-shift-operators-c-cpp/)** 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?


### Resources

- https://github.com/protiumx/aoc
- https://adventofcode.com/2021/day/3
- https://www.geeksforgeeks.org/bitwise-not-operator-in-golang/
- https://www.geeksforgeeks.org/left-shift-right-shift-operators-c-cpp/