### Source: The Sum of Its Parts

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

- child count
- metadata count
`child count`

additional subtrees (recursive)`metadata count`

metadata nodes

Calculate the sum of all metadata nodes.

Yay! Something Racket is great at! text=“Trees” page=“Tree (data structure)”!

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

```
(struct tree (children metadata) #:transparent)
; A tree is count-children, count-metadata, children..., metadata...
(define (read-tree)
(define child-count (read))
(define metadata-count (read))
(tree (for/list ([i (in-range child-count)])
(read-tree))
(for/list ([i (in-range metadata-count)])
(read))))
```

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))
(apply + (tree-metadata tr))))
```

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))
(apply + (tree-metadata tr))]
[else
(for/sum ([index (in-list (tree-metadata tr))])
(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. 😄