Source: The Sum of Its Parts
Part 1: A custom tree data structure is defined as:
- child count
- metadata count
child countadditional subtrees (recursive)metadata countmetadata 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. 😄