Advent of Code 2021: Day 14 - Extended Polymerization (Golang)

Sebastián — Tue, 14 Dec 2021 19:29:26 +0000

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:

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):

(...)

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)

(...)

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!

DEV Community: Sebastián

Advent of Code 2021: Day 14 - Extended Polymerization (Golang)