🏡 2021/day14.nim

Day 14: Extended Polymerization

Today is a chemistry day!

Part 1

Parsing is straightforward

type Rules = Table[string, char]
func parse(text: string): Rules =
  result = initTable[string, char]()
  for line in text.splitLines:
    result[line[0 .. 1]] = line.strip[^1]

let
  testTemplate = "NNCB"
  puzzleTemplate = "VNVVKSNNFPBBBVSCVBBC"
  testRules = parse """
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"""
  puzzleRules = parse readFile("2021/input14.txt")
dump testRules["BB"]
dump testRules.len
dump puzzleRules["BB"]
dump puzzleRules.len
testRules["BB"] = N
testRules.len = 16
puzzleRules["BB"] = H
puzzleRules.len = 100

Let's write the evolution function:

func tick(rules: Rules, polymer: string): string =
  result.add polymer[0]
  for i in 0 ..< polymer.high: # until 1 less than highest index
    let pair = polymer[i .. (i+1)]
    if pair in rules:
      result.add rules[pair]
    result.add polymer[i+1]

func tickN(rules: Rules, polymer: string, n=10): string =
  result = polymer
  for i in 1 .. n:
    result = rules.tick result
    debugEcho i, ": ", result.len
  
dump testRules.tick testTemplate
dump testRules.tickN(testTemplate, n=2)
dump testRules.tickN(testTemplate, n=3)
dump testRules.tickN(testTemplate, n=4)
testRules.tick testTemplate = NCNBCHB
1: 7
2: 13
testRules.tickN(testTemplate, n = 2) = NBCCNBBBCBHCB
1: 7
2: 13
3: 25
testRules.tickN(testTemplate, n = 3) = NBBBCNCCNBBNBNBBCHBHHBCHB
1: 7
2: 13
3: 25
4: 49
testRules.tickN(testTemplate, n = 4) = NBBNBNBBCCNBCNCCNBBNBBNBBBNBBNBBCBHCBHHNHCBBCBHCB

and let's solve part 1

func part1(rules: Rules, polymer: string, n=10): int =
  let polymer = rules.tickN(polymer, n)
  var elementCountTable = polymer.toCountTable
  elementCountTable.sort() # default order is descending
  let
    keys = toSeq(elementCountTable.keys)
    counts = toSeq(elementCountTable.values)
  debugEcho "max: ", keys[0], " -> ", counts[0]
  debugEcho "min: ", keys[^1], " -> ", counts[^1]
  counts[0] - counts[^1]

dump part1(testRules, testTemplate)
dump part1(puzzleRules, puzzleTemplate)
1: 7
2: 13
3: 25
4: 49
5: 97
6: 193
7: 385
8: 769
9: 1537
10: 3073
max: B -> 1749
min: H -> 161
part1(testRules, testTemplate) = 1588
1: 39
2: 77
3: 153
4: 305
5: 609
6: 1217
7: 2433
8: 4865
9: 9729
10: 19457
max: H -> 3618
min: C -> 997
part1(puzzleRules, puzzleTemplate) = 2621

That's the right answer! You are one gold star closer to saving your vacation.

all good except I did not read well and first implemented a function to count pairs and not use the builtin for counting single elements (hence the debugEchos)

Part 2

ok, here clearly the brute force approach we used is not supposed to work and I am pretty sure I am going to need the countPairs I just deleted...

# had to try anyway, but after a few seconds I stopped
#dump part1(testRules, testTemplate, n=40)
#dump part1(puzzleRules, puzzleTemplate, n=40)
discard # cannot have a code block with only comments!
type CountPairs = CountTable[string]

func getCountPairs(polymer: string): CountPairs =
  result = initCountTable[string]()
  for i in 0 ..< polymer.high:
    let pair = polymer[i .. (i+1)]
    result.inc pair

func tick(rules: Rules, countPairs: CountPairs): CountPairs =
  result = initCountTable[string]()
  for pair in countPairs.keys:
    if pair in rules:
      let
        count = countPairs[pair]
        newPairLeft = pair[0] & rules[pair]
        newPairRight = rules[pair] & pair[1]
      result.inc(newPairLeft, count)
      result.inc(newPairRight, count)

func tickN(rules: Rules, countPairs: CountPairs, n=40): CountPairs =
  result = countPairs
  for i in 1 .. n:
    result = rules.tick result
    debugEcho i, ": ", result.len # how many pairs

func part2(rules: Rules, polymer: string, n=40): int =
  var countPairs = polymer.getCountPairs
  countPairs = rules.tickN(countPairs, n)
  var elementCountTable = initCountTable[char]()
  for pair, count in countPairs:
    elementCountTable.inc(pair[1], val=count)
  elementCountTable.inc(polymer[0]) # need to count again first element
  elementCountTable.sort() # default order is descending
  let
    keys = toSeq(elementCountTable.keys)
    counts = toSeq(elementCountTable.values)
  debugEcho "max: ", keys[0], " -> ", counts[0]
  debugEcho "min: ", keys[^1], " -> ", counts[^1]
  counts[0] - counts[^1]

dump part2(testRules, testTemplate, n=10)
dump part2(puzzleRules, puzzleTemplate, n=10)
1: 6
2: 8
3: 11
4: 13
5: 14
6: 15
7: 15
8: 15
9: 15
10: 15
max: B -> 1749
min: H -> 161
part2(testRules, testTemplate, n = 10) = 1588
1: 30
2: 47
3: 62
4: 73
5: 77
6: 78
7: 78
8: 78
9: 78
10: 78
max: H -> 3618
min: C -> 997
part2(puzzleRules, puzzleTemplate, n = 10) = 2621

ok, checks out with part 1

dump part2(testRules, testTemplate, n=40)
dump part2(puzzleRules, puzzleTemplate, n=40)
1: 6
2: 8
3: 11
4: 13
5: 14
6: 15
7: 15
8: 15
9: 15
10: 15
11: 15
12: 15
13: 15
14: 15
15: 15
16: 15
17: 15
18: 15
19: 15
20: 15
21: 15
22: 15
23: 15
24: 15
25: 15
26: 15
27: 15
28: 15
29: 15
30: 15
31: 15
32: 15
33: 15
34: 15
35: 15
36: 15
37: 15
38: 15
39: 15
40: 15
max: B -> 2192039569602
min: H -> 3849876073
part2(testRules, testTemplate, n = 40) = 2188189693529
1: 30
2: 47
3: 62
4: 73
5: 77
6: 78
7: 78
8: 78
9: 78
10: 78
11: 78
12: 78
13: 78
14: 78
15: 78
16: 78
17: 78
18: 78
19: 78
20: 78
21: 78
22: 78
23: 78
24: 78
25: 78
26: 78
27: 78
28: 78
29: 78
30: 78
31: 78
32: 78
33: 78
34: 78
35: 78
36: 78
37: 78
38: 78
39: 78
40: 78
max: H -> 3918098460190
min: C -> 1074264218824
part2(puzzleRules, puzzleTemplate, n = 40) = 2843834241366

That's the right answer! You are one gold star closer to saving your vacation.

surprised I got the second part at first try (had to think a bit to get it correct)!

import animu, nimib

nbInit(theme=useAdventOfNim)
nbText: """## Day 14: [Extended Polymerization](https://adventofcode.com/2021/day/14)

Today is a chemistry day!

### Part 1

Parsing is straightforward
"""

nbCode:
  type Rules = Table[string, char]
  func parse(text: string): Rules =
    result = initTable[string, char]()
    for line in text.splitLines:
      result[line[0 .. 1]] = line.strip[^1]

  let
    testTemplate = "NNCB"
    puzzleTemplate = "VNVVKSNNFPBBBVSCVBBC"
    testRules = parse """
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"""
    puzzleRules = parse readFile("2021/input14.txt")
  dump testRules["BB"]
  dump testRules.len
  dump puzzleRules["BB"]
  dump puzzleRules.len
nbText: "Let's write the evolution function:"
nbCode:
  func tick(rules: Rules, polymer: string): string =
    result.add polymer[0]
    for i in 0 ..< polymer.high: # until 1 less than highest index
      let pair = polymer[i .. (i+1)]
      if pair in rules:
        result.add rules[pair]
      result.add polymer[i+1]

  func tickN(rules: Rules, polymer: string, n=10): string =
    result = polymer
    for i in 1 .. n:
      result = rules.tick result
      debugEcho i, ": ", result.len
    
  dump testRules.tick testTemplate
  dump testRules.tickN(testTemplate, n=2)
  dump testRules.tickN(testTemplate, n=3)
  dump testRules.tickN(testTemplate, n=4)
nbText: "and let's solve part 1"
nbCode:
  func part1(rules: Rules, polymer: string, n=10): int =
    let polymer = rules.tickN(polymer, n)
    var elementCountTable = polymer.toCountTable
    elementCountTable.sort() # default order is descending
    let
      keys = toSeq(elementCountTable.keys)
      counts = toSeq(elementCountTable.values)
    debugEcho "max: ", keys[0], " -> ", counts[0]
    debugEcho "min: ", keys[^1], " -> ", counts[^1]
    counts[0] - counts[^1]

  dump part1(testRules, testTemplate)
  dump part1(puzzleRules, puzzleTemplate)
gotTheStar
nbText: """all good except I did not read well and first implemented a function to count pairs
and not use the builtin for counting single elements (hence the `debugEchos`)

## Part 2

ok, here clearly the brute force approach we used is not supposed to work and I am pretty sure
I am going to need the `countPairs` I just deleted...
"""
nbCode:
  # had to try anyway, but after a few seconds I stopped
  #dump part1(testRules, testTemplate, n=40)
  #dump part1(puzzleRules, puzzleTemplate, n=40)
  discard # cannot have a code block with only comments!

nbCode:
  type CountPairs = CountTable[string]
  
  func getCountPairs(polymer: string): CountPairs =
    result = initCountTable[string]()
    for i in 0 ..< polymer.high:
      let pair = polymer[i .. (i+1)]
      result.inc pair

  func tick(rules: Rules, countPairs: CountPairs): CountPairs =
    result = initCountTable[string]()
    for pair in countPairs.keys:
      if pair in rules:
        let
          count = countPairs[pair]
          newPairLeft = pair[0] & rules[pair]
          newPairRight = rules[pair] & pair[1]
        result.inc(newPairLeft, count)
        result.inc(newPairRight, count)
  
  func tickN(rules: Rules, countPairs: CountPairs, n=40): CountPairs =
    result = countPairs
    for i in 1 .. n:
      result = rules.tick result
      debugEcho i, ": ", result.len # how many pairs

  func part2(rules: Rules, polymer: string, n=40): int =
    var countPairs = polymer.getCountPairs
    countPairs = rules.tickN(countPairs, n)
    var elementCountTable = initCountTable[char]()
    for pair, count in countPairs:
      elementCountTable.inc(pair[1], val=count)
    elementCountTable.inc(polymer[0]) # need to count again first element
    elementCountTable.sort() # default order is descending
    let
      keys = toSeq(elementCountTable.keys)
      counts = toSeq(elementCountTable.values)
    debugEcho "max: ", keys[0], " -> ", counts[0]
    debugEcho "min: ", keys[^1], " -> ", counts[^1]
    counts[0] - counts[^1]

  dump part2(testRules, testTemplate, n=10)
  dump part2(puzzleRules, puzzleTemplate, n=10)
nbText: "ok, checks out with part 1"
nbCode:
  dump part2(testRules, testTemplate, n=40)
  dump part2(puzzleRules, puzzleTemplate, n=40)
gotTheStar
nbText: "surprised I got the second part at first try (had to think a bit to get it correct)!"
nbSave