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 rateby getting the complement of thegamma 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 rateby getting the complement of thegamma 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?
Oldest comments (0)