Advent of Code 2021: Day 14 - Extended Polymerization (Golang)
Tags: go, adventofcode, algorithms, spoiler
Published: 2021-12-14 19:29:26

I've been learning Go for the past month and a half now and after solving most AoC puzzles using JavaScript I decided to give Go a go.

Actually I've been solving the last 4 puzzles (10-14) in Go, but definitely #14 was the most difficult of all so far.

First, to parse the input I wrote the following:

```go
package main

import (
	"fmt"
	"io/ioutil"
	"math"
	"strings"
)

const filePath = "14.txt"

func loadData(file string) (string, map[string]string) {
	dataBytes, err := ioutil.ReadFile(filePath)
	if err != nil {
		panic(err)
	}

	data := string(dataBytes)

	dataString := strings.Split(data, "\n")

	var initialState string
	transformations := map[string]string{}

	for i, v := range dataString {
		if i == 0 {
			initialState = v
		} else if v != "" {
			transformation := strings.Split(v, " -> ")

			transformations[transformation[0]] = transformation[1]
		}
	}

	return initialState, transformations
}

func main() {
	//
}
```

Part one wasn't really that complicated (or at least the naive approach I took to solve it):

```go
(...)

func partOne(initialState string, transformations map[string]string) {
	// Iterates over the polymerization process 10 items
	for i := 1; i <= 10; i++ {
		newChars := ""

		// Adds the new characters that result from the pair insertion
		// rules to newChars
		for j := 0; j < len(initialState)-1; j++ {
			newChar := transformations[string(initialState[j:j+2])]
			newChars += newChar
		}

		oldInitialState := initialState
		newInitialState := ""

		// Creates the new state by interlocking the current state
		// and the new chars
		for k := 0; k < len(newChars)+len(oldInitialState); k++ {
			if k%2 == 0 {
				newInitialState += string(oldInitialState[k/2])
			} else {
				newInitialState += string(newChars[(k-1)/2])
			}
		}

		initialState = newInitialState
	}

	// Gets the # of repetitions of most common and least common
	// characters
	maxChar := 0
	minChar := math.MaxInt32
	for m := 'A'; m <= 'Z'; m++ {
		repetitions := strings.Count(initialState, string(m))

		if repetitions > maxChar {
			maxChar = repetitions
		}

		if repetitions < minChar && repetitions != 0 {
			minChar = repetitions
		}
	}

	// Prints answer
	fmt.Println(maxChar - minChar)
}

func main() {
	initialState, transformations := loadData(filePath)
	partOne(initialState, transformations)
}
```

But part two was really tough:

(**SPOILER ALERT**, I really recommend you not reading the solution unless you have tried to solve it for a reasonable amount of time. It took me a couple of hours to write the following piece of code, so I would suggest you to take as much time as you need to first solve it by your own means)

```go
(...)

func partTwo(initialState string, transformations map[string]string, steps int) {
	// Creates a matrix that stores a slice of length 26
	// for each of the base cases (each pair after 1 step of polymerization)
	memo := map[int]map[string]map[string][]int{}
	memo[1] = map[string]map[string][]int{}

	for k, v := range transformations {
		tmp := make([]int, 26)
		for i := range tmp {
			tmp[i] = 0
		}
		tmp[rune(v[0])-65]++

		memo[1][k] = map[string][]int{}
		// The distinction between "nonAcc" and "acc" variants
		// is necessary so that the letters don't get repeated
		// in the cases that will be built-up
		memo[1][k]["acc"] = tmp
		memo[1][k]["nonAcc"] = tmp
	}

	// Builds the rest of the cases for each pair and number of steps
	// (This is the magic part)
	for i := 2; i <= steps; i++ {
		memo[i] = map[string]map[string][]int{}
		for k, v := range transformations {
			transformFirstPair := string(k[0]) + v
			transformSecondPair := v + string(k[1])

			prevFirstPairNonAccum := memo[i-1][transformFirstPair]["nonAcc"]
			prevSecondPairNonAccum := memo[i-1][transformSecondPair]["nonAcc"]
			prevPairAccum := memo[i-1][k]["acc"]

			memo[i][k] = map[string][]int{}
			memo[i][k]["acc"] = sumUpSlices(prevFirstPairNonAccum, prevSecondPairNonAccum, prevPairAccum)
			memo[i][k]["nonAcc"] = sumUpSlices(prevFirstPairNonAccum, prevSecondPairNonAccum)
		}
	}

	// Finally adding up the occurrences of each letter for
	// the cases with the required number of steps and "acc"
	// variant since that's the one that has the complete amount
	// of "children" for a given pair
	finalCount := make([]int, 26)

	for i := 0; i < len(finalCount); i++ {
		finalCount[i] = 0
	}

	for j := 0; j < len(initialState)-1; j++ {
		currRes := memo[steps][initialState[j:j+2]]["acc"]

		for k := 0; k < len(finalCount); k++ {
			finalCount[k] += currRes[k]
		}

		// Since the matrix stores the "children" of each of the original
		// pairs, it is necessary to add the original pairs to the sum.
		// Also, since they overlap, the first letter only gets added after
		// adding the first pair to the final count
		if j == 0 {
			finalCount[rune(initialState[0])-65]++
		}

		finalCount[rune(initialState[j+1])-65]++
	}

	// fmt.Println(finalCount)

	getDiff(finalCount)
}

// Auxiliary functions to make code more clear
func sumUpSlices(args ...[]int) []int {
	c := make([]int, 26)
	for _, v := range args {
		for j := 0; j < len(v); j++ {
			c[j] += v[j]
		}
	}

	return c
}

func getDiff(count []int) {
	min := math.MaxInt64
	max := 0

	for _, v := range count {
		if v < min && v != 0 {
			min = v
		}

		if v > max {
			max = v
		}
	}

	fmt.Println(max - min)
}
```

This was the last approach of 3 that I tried.

Of course I first tried the **naive** brute-forcing solution but I soon realized that was not going to work.

After that I tried the **memoized brute-forced** solution, but that didn't do the trick as well.

After that I took the **last approach**, but **without the distinction between "accumulative" and "non-accumulative"** versions, which resulted in repeated characters and a wrong result.

Finally I remembered that I previously read a couple of solutions to dynamic programming problems that involved different versions of a calculation (generally including or excluding something), and after doing some drawings and diagrams and writing it out I finally managed to make it work.

This was fun!