In this lab we'll review the things you've learned over the quarter.
Part 1 As we all know, Santa has a massive organization of elves that do his work for him. For our purposes, the only interesting things about an elf are its name (a string) and its age (a number). Write a data definition for elves. Then write the template for elf-processing functions.
Part 2 Santa has lots of elves and needs help needs help keeping track of them. Using the built-in function quicksort, develop the functions elves-by-age : (listof elf) -> (listof elf) and elves-by-name : (listof elf) -> (listof elf). elves-by-age returns the input list of elves sorted by ages (oldest first); elves-by-name returns the input list of elves sorted alphabetically by name.
Part 3 With each passing year Santa's list of elves needs to be updated. Every elf needs to have its age incremented by one, and elves that are older than 100 need to be taken off the roster (the Elves' Union doesn't permit elderly elves to work in Santa's toyshop). Write the function update-elf-list : (listof elf) -> (listof elf) that takes an un-updated list and returns the updated version. Do this without writing any recursive functions; instead use built-in helpers.
Part 4 As with any large organization, when Santa has an urgent piece of news it can be a difficult logistical challenge for Santa to get the word out to his elves (for instance, when there's a snow day). To do that, he arranges his elves in a phone tree where each elf has a list of other elves to call whenever he or she gets a message. Santa calls one elf himself, that elf calls some number of other elves, those elves call more elves, and so on until every elf has been called.
Write a data definition and template for phone trees.
Part 5 Santa needs your help! Still! Write a function reachable-elves : phone-tree -> (listof elf) that produces a list of all elves that will eventually get called by the given phone tree.
Part 6 Write a function well-formed-tree? : phone-tree -> boolean verifies that any elf only appears once in the given phone tree. Write it two ways: once using natural recursion without an accumulator, and once using an accumulator.
Part 7 During the long summer months, Santa keeps himself occupied with the "number palindrome" problem described here. Write a program that finds number palindromes for given seeds (in other words, a function that takes the red numbers on that page and produces the green numbers).
Hint: you'll need to write a function reverse-number that produces the digit-reverse of a given number (so 123 becomes 321 and 100 becomes 001 = 1). To do that, write a helper function number->reversed-digit-list : number -> (listof digit) and recall the to10 function from class. You'll also need a function is-palindrome? : number -> bool; recall that a number is a palindrome if and only if it's equal to its reverse.Jacob Matthews
jacobm at cs.uchicago.edu
Hinds 026