Introduction
This year, several of us at Mojang decided to participate in the Advent of Code. It was the first time for me, and I
chose Go as my programming language. Inevitably, choosing a static language meant spending a bit more time each day
on input parsing. In this posts I will share some insights from day 13.
Problem description
First, lets have a look at the problem description:
Your handheld device must still not be working properly; the packets from the distress signal got decoded out of order.
You'll need to re-order the list of received packets (your puzzle input) to decode the message. Packet data consists of
lists and integers. Each list starts with [, ends with ], and contains zero or more comma-separated values (either
integers or other lists). Each packet is always a list and appears on its own line.
When comparing two values, the first value is called left and the second value is called right. Then:
- If both values are integers, the lower integer should come first. If the left integer is lower than the right integer,
the inputs are in the right order. If the left integer is higher than the right integer, the inputs are not in the right
order. Otherwise, the inputs are the same integer; continue checking the next part of the input.
- If both values are lists, compare the first value of each list, then the second value, and so on. If the left list
runs out of items first, the inputs are in the right order. If the right list runs out of items first, the inputs are
not in the right order. If the lists are the same length and no comparison makes a decision about the order, continue
checking the next part of the
input.
- If exactly one value is an integer, convert the integer to a list which contains that integer as its only value, then
retry the comparison. For example, if comparing [0,0,0] and 2, convert the right value to [2] (a list containing 2); the
result is then found by instead comparing [0,0,0] and [2].
and here is what the example input looked like:
[1,1,3,1,1]
[1,1,5,1,1]
[[1],[2,3,4]]
[[1],4]
[9]
[[8,7,6]]
[[4,4],4,4]
[[4,4],4,4,4]
[7,7,7,7]
[7,7,7]
[]
[3]
[[[]]]
[[]]
[1,[2,[3,[4,[5,6,7]]]],8,9]
[1,[2,[3,[4,[5,6,0]]]],8,9]
Solution
I think the logic for the comparisons is pretty straightforward. The tricky part is how to represent a dynamic
data structure like this in a statically typed language.
For the previous questions I had divided the process into two steps. Step one, I parsed the input. Step two, I tried
to solve the puzzle.
However, this approach wouldn't work very well here. Instead, I decided to merge the input parsing with the
comparisons. By using recursion, I was able to delay the type evaluation of the entire input, choosing to examine
the data type at each index individually. If the elements at each index were numbers, I could then perform the
necessary comparisons.
Here is the code for my solution:
func cmp(a, b any) int {as, aok := a.([]any)
bs, bok := b.([]any)
switch { case !aok && !bok: return int(a.(float64) - b.(float64)) case !aok: as = []any{a} case !bok: bs = []any{b}}
for i := 0; i < len(as) && i < len(bs); i++ { if c := cmp(as[i], bs[i]); c != 0 { return c}
}
return len(as) - len(bs)}
func parseInput(input io.Reader) ([]any, int) {rawInput, _ := ioutil.ReadAll(input)
packages, total := []any{}, 0 for i, s := range strings.Split(strings.TrimSpace(string(rawInput)), "\n\n") { s := strings.Split(s, "\n") var a, b any json.Unmarshal([]byte(s[0]), &a) json.Unmarshal([]byte(s[1]), &b) packages = append(packages, a, b) if cmp(a, b) <= 0 { total += i + 1}
}
return packages, total}
func PartOne(input io.Reader) int {_, total := parseInput(input)
return total}
func PartTwo(input io.Reader) int {packages, _ := parseInput(input)
packages = append(packages, []any{[]any{2.}}, []any{[]any{6.}}) sort.Slice(packages, func(i, j int) bool { return cmp(packages[i], packages[j]) < 0 }) total := 1 for i, p := range packages { if fmt.Sprint(p) == "[[2]]" || fmt.Sprint(p) == "[[6]]" { total *= i + 1}
}
return total}
The end
I usually tweet something when I've finished writing a new post. You can find me on Twitter
by clickingÂ