Algorithm for Day 14 of Advent of Code 2021

aoc-2021-14.go

package main

import (
	"fmt"
)

type Output struct {
	Pair1, Pair2 string
	NewElement   string
}

type Step struct {
	Pairs map[string]int
	Count map[string]int
}

func main() {
	// 0. load your input
	data := []string{
		"NNCB",
		"",
		"CH -> B",
		"HH -> N",
		"CB -> H",
		"NH -> C",
		"HB -> C",
		"HC -> B",
		"HN -> C",
		"NN -> C",
		"BH -> H",
		"NC -> B",
		"NB -> B",
		"BN -> B",
		"BB -> N",
		"BC -> B",
		"CC -> N",
		"CN -> C",
	}

	// 1. create rules

	// e.g. for the rule "NN -> C", this maps NN -> { (NC, CN), C }
	rules := map[string]Output{}

	// rule data starts from the line index 2
	for _, rule := range data[2:] {
		var in, out string
		fmt.Sscanf(rule, "%s -> %s", &in, &out)

		rules[in] = Output{
			Pair1:      string(in[0]) + out,
			Pair2:      out + string(in[1]),
			NewElement: out,
		}
	}

	// 2. convert input polymer to internal format
	s := NewStep(data[0])

	// 3. execute 40 steps
	for i := 0; i < 40; i++ {
		s = next(s, rules)
	}

	// 4. find the min and max counts
	min := math.MaxInt
	max := 0
	for _, v := range s.Count {
		if v < min {
			min = v
		}
		if v > max {
			max = v
		}
	}

	// 5. print out your answer
	fmt.Println(max - min)
}

func next(in *Step, rules map[string]Output) *Step {
	// 0. init a new struct to hold the next step
	out := &Step{
		Pairs: map[string]int{},
		Count: map[string]int{},
	}

	// 1. copy all existing counts over
	for k, v := range in.Count {
		out.Count[k] = v
	}

	// 2. pairs don't get copied over -> they are expanded into different pairs
	// for each pair, increment the count of the new pairs that it becomes,
	// and also increment the count for the new element that gets inserted
	for p, count := range in.Pairs {
		t := rules[p]
		out.Pairs[t.Pair1] += count
		out.Pairs[t.Pair2] += count
		out.Count[t.NewElement] += count
	}

	return out
}

func NewStep(in string) *Step {
	s := &Step{
		Pairs: map[string]int{}, // pairs in the polymer and how many of each
		Count: map[string]int{}, // elements in the polymer and how many of each
	}

	// 1. take every pair in the polymer and add it to Pairs
	for i := 0; i < len(in)-1; i++ {
		pair := in[i : i+2]
		s.Pairs[pair]++
	}

	// 2. count every element in the polymer and add it to Counts
	// (you could do this with the previous loop)
	for i := 0; i < len(in); i++ {
		s.Count[string(in[i])]++
	}

	return s
}

The idea is that instead of keeping track of the entire polymer as a string (or array, or whatever), we only keep track of:

1. the number of each possible pairing of elements
2. the count of each element

For example, consider the input polymer "NN" using the rules from the example input in the problem description:

Rules:

NN -> NC, CN (+C)
NC -> NB, BC (+B)
CN -> CC, CN  (+C)
NB -> NB BB (+B)
BC -> BB BC (+B)
CC -> CN NC (+N)
BB -> BN NB (+N)

Steps:

0: 1 NN (2N)
1: 1 NC, 1 CN (2N 1C)
2: 1 NB, 1 BC, 1 CC, 1 CN (2N 1B 2C)
3: NB, 2BB, BC, 2CN, NC, CC (+3B 3N 3C)
4: 4NB 2BB 2BN 2BC 2CC 3CN NC (+6B 6N 5C)

On further thought, you don't actually need to keep track of the counts. Each element, except for the first and last elements, exist twice in the pairs - another way to say this is that each one is part of two pairs, except for the first and the last, which are only part of 1 pair each.

In other words, instead of keeping track of the counts separate, you can just keep track of the pairs. To get a count, simply count the number of occurrences of each element in the pairs, add 1 to the count of each of the first and last elements, then divide the count by 2.