Advent Of Code - Day 3

Here we go for day 3!

This day was a tiny bit more complex. A lot of more things to read for sure! But all the more exciting!

Let’s get to it!

Day 3 - Part 1

We are dealing with binary numbers. At fist glance it can be daunting, but it’s actually not that complicated. We have to find two numbers. gamma rate and epsilon rate. To do that, we have to parse some binary numbers and then convert them to decimal. The two numbers can be found by looking for the most common bit at a given position in all of the numbers and the least common one at a given position in all of the given numbers. Better put, as we read on, find the bit that occurs most of the time and the one that occurs least of the time in all numbers and put them together. That’s your new number.

As always, let’s write out our constraints first!

we have a list of binary numbers
we have to go through all of them and check a certain position for all of them
find the most occurring number ( either 0, or 1 ) that occurs at position n
append this number to a new number that is being constructed result

Okay, so… loop through the numbers, as we loop, check all of the numbers at position 0, 1, 2, 3… and check which digit occurs most and least. Add the most one to the gamma rate and the least one to the epsilon rate.

This needs a bit of a brain wrap. We will loop through all the numbers, but we will also loop through all the numbers again but check a certain position. Meanwhile, we track the number of zeros and ones we count.

This will result in two loops. The first loop goes as long as the numbers are. And the second goes as many times as many numbers there are.

    // Loop as much as long the numbers are...
	for i := 0; i < len(nums[0]); i++ {
		zeros := 0
		ones := 0

        // loop through all the numbers and check digit location.
		for j := 0; j < len(nums); j++ {
            // count ones and zeros
			if nums[j][i] == '0' {
				zeros++
			} else {
				ones++
			}
		}

        // if zeros are larger gamma is 0 epsilon is 1.
		if zeros > ones {
			gamma += "0"
			epsilon += "1"
		} else {
            // if ones are larger, gamma is 1 epsilon is 0.
			gamma += "1"
			epsilon += "0"
		}
	}

This will result in the right gamma and epsilon numbers, but we aren’t done yet there. We have to convert this to decimal. Lucky for us, Go provides tools for this. We simple call strconv.ParseInt like this:

	g, _ := strconv.ParseInt(gamma, 2, 64)
	e, _ := strconv.ParseInt(epsilon, 2, 64)
	fmt.Println("result: ", g * e)

And that’s it. We have our power consumption. On to Part 2!

Day 3 - Part 2

Now that’s a doozy! That is a LOT of text… Let’s try breaking it down. AOC now will teach you how to read. This is actually an important skill to acquire. A lot of times you will have to parse a lot of text and try to figure out what the actual task is.

Again, we are looking for two numbers. oxygen generator rating and CO2 scrubber rating. Now, it’s important again, to identify certain aspects here. Like last time I talked about that there are things which you can take for granted. Things and rules which will make it easier to find something or will define an exit criteria for a search or a filter. Reading here, we find such an exit criteria:

process that involves filtering out values until only one remains.

We have to filter the numbers until only one remains. This is important. You can be sure that the result will always be a single number out of the list of numbers. That’s your exit criteria. You can stop once your list is filtered to a single number.

The next sentence I actually find confusing.

Before searching for either rating value, start with the full list of binary numbers from your diagnostic report and consider just the first bit of those numbers.

For me this implies that I would have to do something with the numbers before I start search. This is not true. It’s actually just outlining what you filter criteria will be… which is:

start with the first bit
selected numbers based on a predicate (described later as bit criteria)
if you have one number left, stop
continue with the next bit

So what are the bit criteria?

Each number has its own definition of criteria that it needs.

oxygen generator rating:

the most common value in a bit position
if equal keep the 1s

CO2 scrubber rating:

the least common value in a bit position
if equal keep the 0s

Then we have a nice and detailed example for both of the values. Basically, we’ll have two loops and we duplicate our list of numbers. Both loops will delete numbers based on the predicate until only a single number remains. All the while going through the bit positions until it’s done.

The basic algorithm looks like this:

func filter(list []string, pred func(zeros, ones int) bool) string {
    // Start at position zero.
	bitPosition := 0
    // until there is only a single left...
	for len(list) != 1 {
		zeros := 0
		ones := 0

        // same as before, we count the ones and zeros
		for _, o := range list {
			if o[bitPosition] == '0' {
				zeros++
			} else {
				ones++
			}
		}

        // we decide which number / position to keep
		var bit byte
        // based on the predicate, ones and zeros, decide which number will be kept.
		if pred(zeros, ones) {
			bit = '1'
		} else {
			bit = '0'
		}
        // remove the numbers which are not needed
		for i := 0; i < len(list); i++ {
			if list[i][bitPosition] == bit {
				list = append(list[:i], list[i+1:]...)
				i--
			}
		}
        // check the next bit position
		bitPosition++
	}
    // return
	return list[0]
}

And our predicates look like this:

	oxygen := filter(oxygens, func(zeros, ones int) bool {
		return zeros > ones
	})
	co2 := filter(co2s, func(zeros, ones int) bool {
		return zeros < ones || zeros == ones
	})

For oxygens, we are looking for most common values, otherwise it’s not needed. And for co2s we are looking for the least common values and if they equal, we want the zeros.

And that’s pretty much it. Parsing and finding and understanding the problem was a bit harder this time around, but it will get a lot more convoluted after this.

Conclusion

We got a taste of what longer and more convoluted descriptions will look like. We got prepared for reading. We learned a bit about strconv.ParseInt. Maybe it will be handy later.

BTW this is something that is called trivially parallel. We could easily call these in a Go routine. But it wouldn’t matter since our sample size is rather small. Just keep in mind to keep an eye out for these.

The repository for all my solutions for AOC 2021 can be found here.

Thank you for reading!

Happy coding!

Gergely.

Advent Of Code - Day 3#

Day 3 - Part 1#

Day 3 - Part 2#

Conclusion#

Advent Of Code - Day 3

Day 3 - Part 1

Day 3 - Part 2

Conclusion