Advent of Code day 2 was nice and simple and came with a small reminder lesson about Golang’s slice internals. Let’s dive in!

---

The below is a guest post by the amazing Shraddha Agrawal.

---

Part 1

The first problem was extremely simple, let’s quickly over it.

Problem

Day 2, Part 1 problem was pretty straight forward. Given multiple rows of numbers, supposedly “reports”, each row is a valid entry only if:

1. Numbers in a row are either all increasing or all decreasing but not both. This means:
   1. 1 2 3 4 5 is a valid row.
   2. 10 9 8 7 6 is a valid row.
   3. 1 10 2 3 4 is not a valid row.
2. The difference between any two consecutive numbers in a row must be between [1,3]. This means:
   1. 1 5 7 8 9 is an invalid row even though it satisfies rule 1, as the difference between the first two numbers is 4 which is not in the set [1,3].

The result should be a count of the total number of valid rows.

Solution

The main part of the problem is to figure out if a row is safe or not. I did this by iterating over the contents of a row, calculating the difference between the current and last index numbers and exiting early if any of these conditions were met:

1. First encounter of a peak, ie when the numbers change from increasing to decreasing or the other way round. I did this with the use of two flags, one for increasing and other for decreasing. Initially both are set to false. When the difference is positive, the increasing flag is set, and when the difference is negative, the decreasing flag is set. If both flags are set, it means both increasing and decreasing numbers are encountered, time to exit.
2. Absolute value of difference does not fall within [1,3].

My function looked like this:

func isReportSafe(reportNum []int) bool {
	flagIncrease, flagDecrease := false, false

	for i := 1; i < len(reportNum); i++ {
		diff := reportNum[i] - reportNum[i-1]

		if diff > 0 {
			flagIncrease = true
		} else if diff < 0 {
			flagDecrease = true
		} else {
			// difference is zero
			return false
		}

		if flagDecrease && flagIncrease {
			return false
		}

		if diff > 3 || diff < -3 {
			return false
		}
	}

	return true
}

Iterating over all reports in the input, checking if its safe or not gave the final answer. Simple and straight forward without any gotchas. You can find my complete code here.

Part 2

A slight modification in introduced in part 2.

Problem

Now, we can tolerate upto 1 bad number for each row, ie, if by deleting at most one number from the row makes it valid, we can count that row towards the final sum. There are a few things to keep in mind here:

1. The number to be removed can be at any index in the row. The first, the last or somewhere in between. Highlighting it here as I often mistakenly miss checking the boundary numbers.
2. After removing a single number from the row, the rest of the row, preserving the order, should follow the rules highlighted in part 1 to be considered as valid. eg - taking the previous example of 1 10 2 3 4 , if we remove 10, we are left with 1 2 3 4 which follow both rules and is thus a valid row.

Part 2: Solution

I went with the brute force solution. For each row, I iteratively removed each number and tried if the resultant row was valid. Since we already have a function to check for validity, we need:

1. checkReportSafetyWithDeletion - A function to iterate over the row to attempt deleting indexes to find a valid row with deletion.
2. isReportSafeWithDeletion - A function to create a slice with the input index deleted and check for row validity.

The first one is easy enough to do, we just need to iterate over the row and call function 2.

func checkReportSafetyWithDeletion(reportNum []int) bool {

	for i := 0; i < len(reportNum); i++ {
		if isReportSafeWithDeletion(reportNum, i) {
			return true
		}
	}

	return false
}

The second one is where things get interesting. Let’s implement isReportSafeWithDeletion.

func isReportSafeWithDeletion(report []int, deleteIndex int) bool {

	var newSlice []int 
	
	if deleteIndex == len(report)-1 {
		newSlice = report[:deleteIndex]
	} else {
		newSlice = append(report[:deleteIndex], report[deleteIndex+1:]...)
	}
	return isReportSafe(newSlice)
}

The function gets two arguments: the row slice and the index of the item to delete from the row slice. We use append to delete the character and assign the resultant slice back to the input row slice. Now that we have the resultant row, we call isReportSafe to check for validity.

Its subtle, but the above implementation is wrong. Can you spot the error?

Let’s do a brief overview of slice internals. From the official Go blog:

A slice is a descriptor of an array segment. It consists of a pointer to the array, the length of the segment, and its capacity (the maximum length of the segment).

Slicing does not copy the slice’s data. It creates a new slice value that points to the original array. This makes slice operations as efficient as manipulating array indices. Therefore, modifying the elements (not the slice itself) of a re-slice modifies the elements of the original slice.

The problem with the above code is: append operations are modifying the underlying array segment of the input slice. And although slices are passed by value, since the underlying input slice itself is changed, the slice is also modified for the parent function, checkReportSafetyWithDeletion. We definitely don’t want that.

So, how can we fix this? Instead of doing operations on the input slice, we should make a copy and do the delete operation on it. This can be achieved using the copy() method. Our modified function would look like this:

func isReportSafeWithDeletion(report []int, deleteIndex int) bool {
	
	copyReport := make([]int, len(report))
	copy(copyReport, report)

	if deleteIndex == len(copyReport)-1 {
		copyReport = copyReport[:deleteIndex]
	} else {
		copyReport = append(copyReport[:deleteIndex], copyReport[deleteIndex+1:]...)
	}
	
	return isReportSafe(copyReport)
}

We’re using extra memory here. Alternatively, the above problem can be side stepped entirely by modifying the isReportSafe function to just ignore the deleted index. I didn’t wanna go that route so I can reuse the same function in both parts.

Now, that the function is done, we can iterate over the whole input and count all valid rows with tolerance level 1. My final code is available here.

And thats it! A small, easy problem to nail home Golang’s slice internals. I’ve made this exact mistake a countless number of times. Hopefully writing this blog has landed this fact home and I won’t fall in this pit again.

As always, if you’re also solving advent of code, I would love to compare notes and checkout your solution. Reach out to me on Twitter, Bluesky or on e-mail at contact[at]shraddhaag[dot]dev.