Last active
December 14, 2021 06:42
-
-
Save echojc/b175c4e377f2a08af1e2e870569a64e0 to your computer and use it in GitHub Desktop.
Algorithm for Day 14 of Advent of Code 2021
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 | |
} |
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.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
The idea is that instead of keeping track of the entire polymer as a string (or array, or whatever), we only keep track of:
For example, consider the input polymer "NN" using the rules from the example input in the problem description: