Advent of Code 2021 Journey with Golang

2023-02-22 . 4 min read

Intro

Each day I got to learn something new while solving the advent of code. It's not like learning a new concept for each problem you solve but understanding the language you're using a little bit more, and being fluent with it; it's about the approach toward the problem, the way we choose to see, understand, and solve it. Here, I write about my experience solving each problem on AOC 2021 with Golang.

Don't forget CRLF while parsing the input file

Day 1

I was still learning about GO Interfaces and came across this package bufio which helps in implementing buffered i/o. Both parts of the problem are pretty straightforward; Iterate over slice elements and do the required checks but since I was learning a new language, solving the problem while learning the new language's idioms and implementations can be a very fun experience. Here is the main snippet of the program.

for scanner.Scan() {
    val, err := strconv.Atoi(scanner.Text())
    check_err(err)
    if (val > prevVal) { count++ }
    prevVal = val
}

func slidingWindowIncrementNumber(numbers []int) int {
    prev := numbers[0] + numbers[1] + numbers[2]
    var res int
    for i := 1; i <= len(numbers) - 3; i++ {
	curr := numbers[i] + numbers[i+1] + numbers[i+2]
	if curr > prev {
	    res++
	}
	prev = curr
    }
    return res
}

Day 2

Day 2 problem is also not so tough. It's just a simple iteration over each line in the input text and do whatever it commands.

Day 3

It gets complicated each day and day 3 made me think for a while about how to solve the problem efficiently. For part 1, I wanted to finish the counts of the bits in one whole iteration over the input. I noticed that each number in the input file had the same length. So I decided to make a Count struct for storing the count of the biitsst(1s and 0s) at each index for the whole input. Here's what it looks like:

type Count struct {
	one int
	zero int
}

func getCountsOfBitsAtEachPosition(input []string) []Count {
	numb := input[0]
	
	counts := make([]Count, len(numb))

	for i := 0; i < len(input); i++ {
		numb := input[i]
		for i, chr := range numb {
			if chr == '1' {
				counts[i].one += 1
			}
			if chr == '0' {
				counts[i].zero += 1
			}
		}
	}

	return counts
}

As I already had the count of bits at each position, I tried to reuse it and solve part 2 in a similar fashion but it was a dumb move. You have to filter the numbers each time, which means that the count of bits is not the same for the new set of numbers as it was for the whole set.

Day 4

I was taking it too easy and then day 4 just slapped me. I had to cheat this time; Well, I didn't actually cheat but just took some ideas out of the awesome online community we have. For me, parsing the input to store it in the right data structure was the tricker part than actually solving the problem of bingo. Once I had that, it was pretty straightforward. Here's something I've been realizing repeatedly: an algorithm to solve a problem, most of the time, mimics the steps we, a human, take while solving a problem. Maybe I still need to solve a lot of problems to correct myself or that is what it is. Anyway, it was so much fun taking an OOP (sortof) style (in a part) in this problem. Here's a snippet.

type Board struct {
	cells  [][]string
	called [][]bool
}

func (b *Board) getScore(mutiplier int64) int64 {
	var score int64
	for i, row := range b.cells {
		for j, cell := range row {
			if b.called[i][j] != true {
				num, err := strconv.Atoi(cell)
				utils.HandleError(err)
				score += int64(num)
			}
		}
	}
	return score * mutiplier
}
func (b *Board) checkBingo(row, col int) bool {
	rows := len(b.called)
	columns := len(b.called[0])
	rowBingo := true
	columnBingo := true
	for i := 0; i < rows; i++ {
		if b.called[i][col] == false {
			columnBingo = false
			break
		}
	}
	for i := 0; i < columns; i++ {
		if b.called[row][i] == false {
			rowBingo = false
			break
		}
	}

	return rowBingo || columnBingo
}

func (b *Board) checkNumAndBingo(num string) bool {
	// check if the board contains the number and if it does
        // check for bingo
}


func createBoard(rawData string) Board {
	lines := strings.Split(rawData, "\r\n")
	if len(lines[len(lines) - 1]) == 0 {
		lines = lines[:len(lines) - 1]
	}
	card := make([][]string, len(lines), len(lines))
	cardCalled := make([][]bool, len(lines), len(lines))
	for i, line := range lines {
		nums := strings.Fields(line)
		card[i] = nums
		cardCalled[i] = make([]bool, len(nums), len(nums))
	} 
	return Board{ card, cardCalled }
}

For part 2, just keep playing the game until all boards have bingoed.

Day 5

You have a moment when you don't know how to do something and you think "I don't think I am made for this!" until you find out the solution and think "Am I smart to understand this or dumb for not figuring it out on the first place?". This is exactly what happened to me. I had to surf the internet to get the idea but once I understood it, I again realized what I said on day 4; the steps in an algorithm are simply the same steps our brain takes when solving a problem for most cases. Just use the correct data structure for the problem and you are set.

type Point struct {
	x int
	y int
}

type Line struct {
	start Point
	end Point
}
func move(start, end Point, move string, pointOverlapCount map[string]int) {
	curr := start
	// for horizontal movement, we loop until we reached the last x coordinate towards right
	// for vertical movement, we loop until we reached the last y coordinate downwards
	// for diagonal movement, we fix the downward movement and move either right or left; 
	// that means, we loop just like the vertical movement
	var loop_start *int
	var loop_end int

	// we move down for both vertical and diagonal movement
	// else we move completely towards right
	// choose the startin and ending point for loop
	if move == "right" {
		loop_start = &curr.x
		loop_end = end.x
	} else {
		loop_start = &curr.y
		loop_end = end.y
	}
	
	for *loop_start <= loop_end {
		point := strconv.Itoa(curr.x) + "," + strconv.Itoa(curr.y)
		if _, ok := pointOverlapCount[point]; ok {
			pointOverlapCount[point] += 1
		} else {
			pointOverlapCount[point] = 1
		}
		step(&curr, move)
	} 
}

func step(curr *Point, move string) {
	switch move {
	case "down":
		curr.y += 1
	case "right":
		curr.x += 1
	case "diag_right":
		curr.x += 1
		curr.y += 1
	case "diag_left":
		curr.x -= 1
		curr.y += 1
	default:
		panic("Unsupported Move Step Requested")
	}
}

Make sure you parse the input correctly and visualize the coordinate plane.

Day 6

This is where you realize why they teach about Time Complexity, the Big O notation in CS classes. Unless you are really really experienced or intelligent, almost everyone, on their first try at this problem tries the naive approach of iterating and appending to the population slice and yes that is what I did too. And I guess if you're here after trying out the problem and feeling really accomplished on part 1 until you got to part 2, you've already tried the naive approach. And if you haven't, I suggest you first try it out yourself.

There's a more efficient way to solve this problem. Think about it, since the birth of new fishes depend only on the timer on a fish, and the direction and rate at which the timer changes is the same for all fish, all we should care about in this problem is the number of fishes with the same timers.

func initialPopulationTimers(data []int) map[int]int {
	fishWithSameTimer := make(map[int]int)
	for _, timer := range data {
		if _, ok := fishWithSameTimer[timer]; ok {
			fishWithSameTimer[timer] += 1
		} else {
			fishWithSameTimer[timer] = 1
		}
	}
	return fishWithSameTimer
}
func finalPopulationTimers(initialTimers map[int]int, days int) map[int]int {
	currDay := 1
	
        for each day {
                -> check if it's time of birth
                   -> if it is create new fishes with their new timer
                   -> reset the timer of the mother fish
                -> decrease the timer on all other 
        }
}

Day 7

There are 2 things to talk about here. The first is the role of Math in Computer Science. The fact that I learned Statistics in my academic years made me solve the first part of the problem almost instantly. And the fact that the old me, like almost everyone who doesn't realize the importance of math in programming tend to keep scratching your head because you know only one approach to a problem and you know that the approach is really really inefficient.

The second thing is the question: "Am I smart or dumb?". The instant solution to part 1 made me feel smart. Just Move Towards The Median, we've got a frequency distribution, so we would consume the lowest fuel when we move to where most of the population already lies. Think about how efficient the solution is.

Let's talk about the naive approach where you make a list of the fuel cost of moving every crab to each position and after all that calculation you get the minimum fuel cost. I could do a benchmark test but I have yet to learn how to do that with go. Anyways, math helps.

But again, part 2 made me feel so dumb for not realizing the solution to this simple problem. The fuel cost is just the Sum of the First N Natural Numbers where N is the number of steps. Here, unlike part 1, we have to calculate the fuel cost at every position there is but hey, the calculation of that fuel cost is really straight forward.

// since fuel cost increases by 1 unit each step
// so if the number of steps is 5, total fuel cost: 1 + 2 + 3 + 4 + 5 = 15
// which is the sum of first n natural numbers
// in this case n is 5
func part2(uniquePositions []int, frequency map[int]int) int {
	var lowestFuelCost int
	lastPosition := uniquePositions[len(uniquePositions) - 1]

	// for each position calculate the number of steps crabs at each position have to step and find
	// the sum of first ( n = steps ) natural numbers for all the position and crabs at each position
	
	// initial cost 
	for _, num := range uniquePositions[1:] {
		lowestFuelCost += frequency[num] * sumOfNaturalNumbers(int(math.Abs(float64(uniquePositions[0]) - float64(num))))
	}

	-> Now calculate the fuel cost for every position
           -> Check if the fuel cost is lower than the previous one

	return lowestFuelCost

}

Coming Soon...

Hey I assume you finished reading, I would love to know your feedback or if found any error or mistake in this blog post, please do not hesitate to reach out to me.