Advent of Code 2021 Day 18: Snailfish
Andreas Røssland
https://adventofcode.com/2021/day/18 https://github.com/roessland/advent-of-code
This one was pretty tricky. I had to write a ton of tests to figure out the bugs in my program. (The trickiest one was related to forgetting to update the parent pointer.)
Tree data structure
Parsing the input: It really looks like a tree structure will work here, so I use the builtin JSON decoder to create an untyped tree (interface{}), and then convert that tree to a proper type.
I came up with the following type:
type Number struct {
parent *Number
value int
left *Number
right *Number
}Go lacks sum/union types, so this was the best I could do. Instead the type contains both left/right pointers and a value, but the value is only valid if both left and right are nil.
graph TD;
*["[[1,2],[[3,4],5]]"]--->|L|12
*-->|R|345
12-->|L|1
12["[1,2]"]-->|R|2
345["[3,4],5]"]-->|L|34
34["[3,4]"]-->|L|3
34-->|R|4
345--->|R|5I decided to parse the input as JSON, and then convert the JSON tree to a properly typed tree. Note that recursion works fine for anonymous functions; you just have to declare the type first.
func FromString(str string) *Number {
var v []interface{}
decoder := json.NewDecoder(strings.NewReader(str))
decoder.UseNumber()
err := decoder.Decode(&v)
if err != nil {
log.Fatal(err)
}
var f func(interface{}, *Number) *Number
f = func(listOrInt interface{}, parent *Number) *Number {
switch v := listOrInt.(type) {
case json.Number:
n, err := strconv.Atoi(string(v))
if err != nil {
panic(err)
}
return &Number{value: n, parent: parent}
case []interface{}:
n := &Number{parent: parent}
n.left = f(v[0], n)
n.right = f(v[1], n)
return n
default:
log.Fatalf("unknown type %T", v)
}
return nil
}
return f(v, nil)
}Another data structure that might be worth exploring for this problem is a zipper.
Addition
Addition of snailfish numbers is defined as concatenating two numbers into a new list, and then reducing the result.
func (n *Number) Add(m *Number) *Number {
sum := &Number{left: n.Copy(), right: m.Copy()}
sum.left.parent = sum
sum.right.parent = sum
sum.Reduce()
return sum
}Copies are used to avoid mutating the input. I added that when I saw Part 2 and realized that numbers must be used multiple times, so it’s a bad idea to modify them in-place.
Reduction
Just try exploding or splitting until there is nothing left to explode or split. If something was exploded, try exploding again.
func (n *Number) Reduce() {
for {
explodable := n.findExplodable(0)
if explodable != nil {
explodable.Explode()
continue
}
splittable := n.findSplittable()
if splittable != nil {
splittable.Split()
continue
}
break
}
}Splitting
Walk through the leaf nodes in left to right order, and return the first number that is too high (“splittable”), then replace that number with a new pair.
func (n *Number) findSplittable() *Number {
if n == nil {
return nil
}
if leftSplittable := n.left.findSplittable(); leftSplittable != nil {
return leftSplittable
}
if n.value >= 10 {
return n
}
if rightSplittable := n.right.findSplittable(); rightSplittable != nil {
return rightSplittable
}
return nil
}
func (n *Number) Split() {
down := n.value / 2
up := n.value / 2
if n.value%2 == 1 {
up++
}
n.left = &Number{value: down, parent: n}
n.right = &Number{value: up, parent: n}
n.value = 0
}Exploding
Exploding a pair wasn’t too bad to implement after left/right traversal was working.
func (n *Number) findExplodable(level int) *Number {
if n == nil || n.HasValue() {
return nil
}
if level == 4 {
return n
}
if leftExplodable := n.left.findExplodable(level + 1); leftExplodable != nil {
return leftExplodable
}
if rightExplodable := n.right.findExplodable(level + 1); rightExplodable != nil {
return rightExplodable
}
return nil
}
func (n *Number) Explode() {
if n.left == nil || n.right == nil {
panic("cannot explode number without left and right")
}
leftInorder := n.findLeft()
rightInorder := n.findRight()
if leftInorder != nil {
leftInorder.value += n.left.value
}
if rightInorder != nil {
rightInorder.value += n.right.value
}
n.left = nil
n.right = nil
n.value = 0
}Left/right leaf node traversal
I came up with an algorithm where you start on the exploding number, then traverse up until there is a left branch, follow that left branch, then follow only right branches until a literal number is found. Make two such functions, one for left and one for right.
func (n *Number) findLeft() *Number {
// Move up until some node has a left branch
for {
if n.parent == nil {
return nil
}
if n.parent.left != n && n.parent.left != nil {
n = n.parent.left
break
}
n = n.parent
}
// Move down all right branches until a value is found
for !n.HasValue() {
n = n.right
}
return n
}
func (n *Number) findRight() *Number {
// ...
}The rest of the code
This runs in about 30 ms in total for part 1 and part 2.
package main
import (
"bufio"
"encoding/json"
"fmt"
"github.com/roessland/gopkg/mathutil"
"log"
"os"
"strconv"
"strings"
"time"
)
func (n *Number) Copy() *Number {
if n == nil {
return nil
}
c := &Number{}
if n.HasValue() {
c.value = n.value
} else {
c.left = n.left.Copy()
c.left.parent = c
c.right = n.right.Copy()
c.right.parent = c
}
return c
}
func (n *Number) HasValue() bool {
return n.left == nil && n.right == nil
}
func (n *Number) String() string {
if n.HasValue() {
return fmt.Sprintf("%d", n.value)
} else {
return fmt.Sprintf("[%s,%s]", n.left.String(), n.right.String())
}
}
func (n *Number) Magnitude() int {
if n.HasValue() {
return n.value
}
return 3*n.left.Magnitude() + 2*n.right.Magnitude()
}
func main() {
t0 := time.Now()
part1()
part2()
fmt.Println(time.Since(t0))
}
func part1() {
nums := ReadInput()
for i := 1; i < len(nums); i++ {
nums[0] = nums[0].Add(nums[i])
}
fmt.Println("Part 1:", nums[0].Magnitude())
}
func part2() {
nums := ReadInput()
maxMagnitude := 0
for i := 0; i < len(nums); i++ {
for j := 0; j < len(nums); j++ {
magnitude := nums[i].Add(nums[j]).Magnitude()
maxMagnitude = mathutil.MaxInt(maxMagnitude, magnitude)
}
}
fmt.Println("Part 2:", maxMagnitude)
}
func ReadInput() []*Number {
f, err := os.Open("input.txt")
if err != nil {
panic(err)
}
scanner := bufio.NewScanner(f)
var nums []*Number
for scanner.Scan() {
num := FromString(scanner.Text())
nums = append(nums, num)
}
return nums
}Appendix: Tests
package main
import (
"github.com/stretchr/testify/require"
"testing"
)
func TestParse12(t *testing.T) {
num := FromString("[1,2]")
require.NotNil(t, num)
require.Equal(t, 0, num.value)
require.NotNil(t, num.left)
require.Equal(t, 1, num.left.value)
require.Nil(t, num.left.left)
require.Nil(t, num.left.right)
require.NotNil(t, num.right)
require.Equal(t, 2, num.right.value)
require.Nil(t, num.right.left)
require.Nil(t, num.right.right)
require.Equal(t, num, num.right.parent)
require.Equal(t, num, num.left.parent)
}
func TestParseBigDude(t *testing.T) {
num := FromString("[[[[1,3],[5,3]],[[1,3],[8,7]]],[[[4,9],[6,9]],[[8,2],[7,3]]]]")
require.Equal(t, 6, num.right.left.right.left.value)
require.Equal(t, num, num.right.left.right.left.parent.parent.parent.parent)
}
func TestReduce(t *testing.T) {
num := FromString("[[[[[9,8],1],2],3],4]")
num.Reduce()
require.Equal(t, 9, num.left.left.left.right.value)
num = FromString("[7,[6,[5,[4,[3,2]]]]]")
expectExplodable := FromString("[3,2]")
explodable := num.findExplodable(0)
require.NotNil(t, explodable, "didnt find explodable")
require.Equal(t, expectExplodable.String(), explodable.String())
num.Reduce() // [7,[6,[5,[7,0]]]]
require.Equal(t, 7, num.right.right.right.left.value, num.String())
num = FromString("[[6,[5,[4,[3,2]]]],1]")
num.Reduce() // [[6,[5,[7,0]]],3]
require.Equal(t, "[7,0]", num.left.right.right.String())
require.Equal(t, 3, num.right.value, num.String())
num = FromString("[[3,[2,[1,[7,3]]]],[6,[5,[4,[3,2]]]]]")
num.Reduce() // [[3,[2,[8,0]]],[9,[5,[4,[3,2]]]]]
require.Equal(t, "[8,0]", num.left.right.right.String())
require.Equal(t, 9, num.right.left.value, num.String())
num1 := FromString("[[[[4,3],4],4],[7,[[8,4],9]]]")
num2 := FromString("[1,1]")
num = num1.Add(num2)
expect := FromString("[[[[0,7],4],[[7,8],[6,0]]],[8,1]]")
require.Equal(t, expect.String(), num.String())
}
func TestExplode(t *testing.T) {
num := FromString("[[[[[9,8],1],2],3],4]")
explodable := num.findExplodable(0)
require.Equal(t, num.left.left.left.left, explodable)
expect := FromString("[[[[0,9],2],3],4]")
explodable.Explode()
require.Equal(t, expect.left.left.left.left.value, num.left.left.left.left.value)
require.Equal(t, expect.left.left.left.right.value, num.left.left.left.right.value)
require.Equal(t, expect.left.left.right.value, num.left.left.right.value)
num = FromString("[[[[0,9],2],3],4]")
explodable = num.findExplodable(0)
require.Nil(t, explodable)
num = FromString("[[[[0,7],4],[[7,8],[0,[6,7]]]],[1,1]]")
explodable = num.findExplodable(0)
require.Equal(t, "[6,7]", explodable.String())
explodable.Explode()
require.EqualValues(t, "[[[[0,7],4],[[7,8],[6,0]]],[8,1]]", num.String())
}
func TestFindLeft(t *testing.T) {
num := FromString("[[[[[9,8],1],2],3],4]")
explodable := num.findExplodable(0)
require.Nil(t, explodable.findLeft())
four := num.right
require.Equal(t, 3, four.findLeft().value)
three := num.left.right
require.Equal(t, 2, three.findLeft().value)
}
func TestFindRight(t *testing.T) {
num := FromString("[[[[[9,8],1],2],3],4]")
explodable := num.findExplodable(0)
require.Equal(t, 1, explodable.findRight().value)
four := num.right
require.Nil(t, four.findRight())
three := num.left.right
require.Equal(t, 4, three.findRight().value)
num = FromString("[[[[0,7],4],[[7,8],[0,[6,7]]]],[1,1]]")
sixSeven := num.left.right.right.right
require.Equal(t, "[6,7]", sixSeven.String())
one := sixSeven.findRight()
require.NotNil(t, one)
require.Equal(t,1, one.value)
require.Equal(t, 1, one.parent.right.value)
}
func TestBlackMagic(t *testing.T) {
num := FromString("[[[[[4,3],4],4],[7,[[8,4],9]]],[1,1]]")
num.findExplodable(0).Explode()
require.Equal(t, "[[[[0,7],4],[7,[[8,4],9]]],[1,1]]", num.String())
require.Equal(t, num, num.left.parent)
num.findExplodable(0).Explode()
require.Equal(t, "[[[[0,7],4],[15,[0,13]]],[1,1]]", num.String())
require.Equal(t, num, num.left.parent)
num.findSplittable().Split()
require.Equal(t, "[[[[0,7],4],[[7,8],[0,13]]],[1,1]]", num.String())
require.Equal(t, num, num.left.parent)
num.findSplittable().Split()
require.Equal(t, "[[[[0,7],4],[[7,8],[0,[6,7]]]],[1,1]]", num.String())
require.Equal(t, num, num.left.parent)
num.findExplodable(0).Explode()
require.Equal(t, "[[[[0,7],4],[[7,8],[6,0]]],[8,1]]", num.String())
require.Equal(t, num, num.left.parent)
}