An Elementary Problem
Sunday, May 3, 2015 · 5 min read
This is The Awesome Elements Problem. I wrote it for my AP Computer Science class, but I decided to put it up here because I think it’s pretty, uh, elementary.
Perhaps more than the actual problem, I love the bonus problems at the bottom. They show how all these “boring” Scheme exercises can be used to do all sorts of neat things. They’re written to introduce a new idea with lots of questions—the solver is expected to explore them both on their own, with external resources, and, of course, with other friends.
Finally, it’s worth noting that (as the first bonus problem should make amply clear) this problem is an absolute pain to do in an imperative language. I think it lets beginners see a rare outside-the-textbook example of functional programming rocking out in the wild, rather than silly contrived scenarios involving bank accounts or store inventories or parking meters.
Teachers are welcome to steal this for their classes.
Some names are inherently different from others. For instance, the name Casey can be written as a list of element symbols, as Ca-Se-Y (Calcium-Selenium-Yttrium). However, Josh cannot be written this way. In this project, you get to write a Scheme program to break up a word into its—ahem—constituent elements.
We begin by defining a list of all the elements. An element’s symbol is
described by a list of Scheme symbols, so Helium is
'(h e). As a sanity
check, you can run
(length elements) and get 118.
(define elements '((a c) (a g) (a l) (a m) (a r) (a s) (a t) (a u) (b) (b a) (b e) (b h) (b i) (b k) (b r) (c) (c a) (c d) (c e) (c f) (c l) (c m) (c o) (c r) (c s) (c u) (d b) (d s) (d y) (e r) (e s) (e u) (f) (f e) (f m) (f r) (g a) (g d) (g e) (h) (h e) (h f) (h g) (h o) (h s) (i) (i n) (i r) (k) (k r) (l a) (l i) (l r) (l u) (m d) (m g) (m n) (m o) (m t) (n) (n a) (n b) (n d) (n e) (n i) (n o) (n p) (o) (o s) (p) (p a) (p b) (p d) (p m) (p o) (p r) (p t) (p u) (r a) (r b) (r e) (r f) (r g) (r h) (r n) (r u) (s) (s b) (s c) (s e) (s g) (s i) (s m) (s n) (s r) (t a) (t b) (t c) (t e) (t h) (t i) (t l) (t m) (u) (u u b) (u u h) (u u o) (u u p) (u u q) (u u s) (u u t) (v) (w) (x e) (y) (y b) (z n) (z r)))
Whew. For extra credit, come up with a way to make that list automatically from some table you find on the Internet. Here’s a nice one.
Let’s warm up with some easy helper functions. Write
(get-rest-of-string str len). It should return the list
str after the first
len elements have been removed.
If you’ve written
compose before, think of a super-elegant way to do this.
(begins-with-element str el), where
el are lists of symbols. The function should return true if
exactly the beginning of
str, and false otherwise. Think about what should
happen if either string is empty.
(begins-with-element '(d o c t o r w h o) '(d o c)) --> #t (begins-with-element '(a m e l i a p o n d) '(a m y)) --> #f
It turns out that these are all the helpers we need to write
elementize is our main function. It breaks up the word
str into elements
in the list
els, and returns all possible results. Fill in the blanks to
Or, if you can think of a better way to write it that doesn’t fit in the blanks, do that instead.
(define (elementize str els) (cond ((null? els) ___) ((null? str) ___) ; Hint: this is not the same as above. ((begins-with-element ___ (___ ___)) (append (elementize ___ (___ ___)) ; Remember, `append` concatenates ; two lists into one bigger list. (map (lambda (list-of-subsolutions) (cons (___ ___) ___)) (___ (___ ___ (length (___ ___))) ___)))) (else (elementize ___ (___ ___)))))
You can use these tests to try out
elementize. I’ve provided the solutions
at the bottom of this page.
(write (elementize '(j a v a) elements)) (newline) (write (elementize '(i s) elements)) (newline) (write (elementize '(u n n e c e s s a r y) elements)) (newline)
Great job! Now for the fun part. Try solving each of the bonus problems below. They’re in no particular order of difficulty. Each one is meant to introduce you to a new, exciting CS topic.
Bonus problem 0! Rewrite your solution in C or Java. Time yourself. Then realize how much you love Scheme.
Bonus problem 1! UNIX computers come with a built-in dictionary of English
words in the file
/usr/share/dict/words. Each word is on its own line. Spend
some time hacking Scheme to see if you can find the single English word that
can be elementized the most ways. How about the longest elementizable word? Are
there any “unnecessary” elements which can be removed from the list without
making any words un-elementizable?
Bonus problem 2! You’ve just discovered a new element! With all your modesty, you decide not to name it after yourself. Instead, you decide to name it so that the addition of the new element will maximize the number of new elementizable words in English (based on the list above). What do you name it? (This one is hard because the program needs to be fast! See if memoization can be useful.)
Bonus problem 3! On a small planet in the vicinty of Betelguese, only two elements can exist in a stable state: Zaphodium and Zemzine. Their symbols were carelessly named Z and Zz by the Chief Chemist (who was later thrown into a vat of zaphodous zemzide (ZZz) by his angry confused chem students).
How many different ways are there to elementize the word
with Z and Zz? How is this related to the question “how many ways are there to
cover a two-by-ten grid with dominoes”? (Hint: this is purely a math problem.
You can use a computer to help find the answer, but try to use math to prove
Bonus problem 4! Read about lazy lists. Figure out how to implement them in Scheme, and then use them to solve this problem. Is your solution faster? More space-efficient? Does it look prettier?
Once you’ve done that, read about
call-with-current-continuation. Figure out
how to use it cleverly to solve this problem (if you’re confused, read about
backtracking, or consult the Python program linked at the bottom of this
page). Is your solution faster? More space-efficient? Does it look prettier?
Think about how the above two implementations are the same, and how they are
different. Can you use
call-with-current-continuation to implement lazy
Bonus problem 5! Read about regular expressions. Which regex do names like “Casey” match? Which regex do names like “Josh” match? Which of the previous two questions is easier, and why?
You can use a program called
grep to test your solutions.
(Non-aqueous) Solutions to the tests above:
java (0) () --- Java is *clearly* not an awesome name. Try Lisp instead. is (1) (((i) (s))) unnecessary (2) (((u) (n) (n e) (c e) (s) (s) (a r) (y)) ((u) (n) (n e) (c) (e s) (s) (a r) (y)))
(This problem was written in November 2014. It is based on a bad Python program I wrote in December 2013. The only modification is that it was originally distributed as a Scheme source file where all the text was commented out, and method stubs were left for students to fill in. I have also added a couple of bonus problems—only 1-3 were in the original source. Please contact me directly if you’d like the original file, along with its solution file.)