# AoC 2018 Day 8: Checksum Treeification

### Source: The Sum of Its Parts

Part 1: A custom tree data structure is defined as:

• child count
• child count additional subtrees (recursive)
• metadata count metadata nodes

Calculate the sum of all metadata nodes.

Yay! Something Racket is great at! text=&ldquo;Trees&rdquo; page=&ldquo;Tree (data structure)&rdquo;!

First, let’s read in the structure. Reading recursive data is wonderfully simple in Racket:

(struct tree (children metadata) #:transparent)

(tree (for/list ([i (in-range child-count)])


And calculating the sum recursively across a tree is just about as short:

; Sum all metadata values for a simple checksum
(define (simple-checksum tr)
(+ (for/sum ([child (in-list (tree-children tr))])
(simple-checksum child))


Fun!

Part 2: Now, calculate the sum as follows:

• If a node has no children, sum the metadata nodes
• Otherwise, sum the metadata nodes as follows:
• If a metadata value is small enough to be a 1-based index of children, use that child’s checksum
• Otherwise, use 0
• Calculate the new checksum.

Honestly, it’s just as long to describe the algorithm as to make it into code. There’s a bit of weird since the data structure is using 1-based indexing (what are we, Lua? Matlab?), but not too bad:

; Checksum with no children is sum of metadata
; Checksum with children uses the metadata as index, sums those children
(define (complex-checksum tr)
(cond
[(null? (tree-children tr))
[else
(cond
[(<= 1 index (length (tree-children tr)))
(complex-checksum (list-ref (tree-children tr) (sub1 index)))]
[else
0]))]))


Print them and we go:

\$ cat input.txt | racket checksum-treeificator.rkt

[part 1] 37262
[part 2] 20839


I like trees. 😄