-
Notifications
You must be signed in to change notification settings - Fork 8
/
Copy pathelementary.html
231 lines (217 loc) · 12.1 KB
/
elementary.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
<!DOCTYPE html>
<html>
<head>
<link rel="canonical" href="https://hardmath123.github.io/elementary.html"/>
<link rel="stylesheet" type="text/css" href="/static/base.css"/>
<title>An Elementary Problem - Comfortably Numbered</title>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"/>
<meta charset="utf-8"/>
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no" />
<link rel="alternate" type="application/rss+xml" title="Comfortably Numbered" href="/feed.xml" />
<!--
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script>
MathJax.Hub.Config({
tex2jax: {inlineMath: [['$','$']]}
});
</script>
-->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.css" integrity="sha384-Um5gpz1odJg5Z4HAmzPtgZKdTBHZdw8S29IecapCSB31ligYPhHQZMIlWLYQGVoc" crossorigin="anonymous">
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/katex.min.js" integrity="sha384-YNHdsYkH6gMx9y3mRkmcJ2mFUjTd0qNQQvY9VYZgQd7DcN7env35GzlmFaZ23JGp" crossorigin="anonymous"></script>
<script defer src="https://cdn.jsdelivr.net/npm/[email protected]/dist/contrib/auto-render.min.js" integrity="sha384-vZTG03m+2yp6N6BNi5iM4rW4oIwk5DfcNdFfxkk9ZWpDriOkXX8voJBFrAO7MpVl" crossorigin="anonymous"></script>
<script>
document.addEventListener("DOMContentLoaded", function() {
renderMathInElement(document.body, {
// customised options
// • auto-render specific keys, e.g.:
delimiters: [
{left: '$$', right: '$$', display: true},
{left: '$', right: '$', display: false},
{left: '\\begin{align}', right: '\\end{align}', display: true},
{left: '\\(', right: '\\)', display: false},
{left: '\\[', right: '\\]', display: true}
],
// • rendering keys, e.g.:
throwOnError : false
});
});
</script>
</head>
<body>
<header id="header">
<script src="static/main.js"></script>
<div>
<a href="/"><span class="left-word">Comfortably</span> <span class="right-word">Numbered</span></a>
</div>
</header>
<article id="postcontent" class="centered">
<section>
<h1>An Elementary Problem</h1>
<center><em><p>Can you find the Solution?</p>
</em></center>
<h4>Sunday, May 3, 2015 · 5 min read</h4>
<p>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,
<em>elementary</em>.</p>
<p>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.</p>
<p>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.</p>
<p>Teachers are welcome to steal this for their classes.</p>
<hr>
<p>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.</p>
<p>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 <code>'(h e)</code>. As a sanity
check, you can run <code>(length elements)</code> and get 118.</p>
<pre><code>(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)))
</code></pre><p>Whew. For extra credit, come up with a way to make that list automatically from
some table you find on the Internet.
<a href="http://akiscode.com/project_files/pt/periodictabledump.csv">Here’s</a> a nice
one.</p>
<p>Let’s warm up with some easy helper functions. Write
<code>(get-rest-of-string str len)</code>. It should return the list <code>str</code> after the first
<code>len</code> elements have been removed.</p>
<p>If you’ve written <code>compose</code> before, think of a super-elegant way to do this.</p>
<p>Now, write <code>(begins-with-element str el)</code>, where <code>str</code>
and <code>el</code> are lists of symbols. The function should return true if <code>el</code> is
exactly the beginning of <code>str</code>, and false otherwise. Think about what should
happen if either string is empty.</p>
<pre><code>(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
</code></pre><p>It turns out that these are all the helpers we need to write <code>elementize</code>.
<code>elementize</code> is our main function. It breaks up the word <code>str</code> into elements
in the list <code>els</code>, and returns <em>all</em> possible results. Fill in the blanks to
complete <code>elementize</code>.</p>
<p>Or, if you can think of a better way to write it that doesn’t fit in the
blanks, do that instead.</p>
<pre><code>(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 ___ (___ ___)))))
</code></pre><p>You can use these tests to try out <code>elementize</code>. I’ve provided the solutions
at the bottom of this page.</p>
<pre><code>(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)
</code></pre><hr>
<p>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.</p>
<p><strong>Bonus problem 0!</strong> Rewrite your solution in C or Java. Time yourself. Then
realize how much you love Scheme.</p>
<p><strong>Bonus problem 1!</strong> UNIX computers come with a built-in dictionary of English
words in the file <code>/usr/share/dict/words</code>. 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?</p>
<p><strong>Bonus problem 2!</strong> 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 <em>memoization</em>
can be useful.)</p>
<p><strong>Bonus problem 3!</strong> 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).</p>
<p>How many different ways are there to elementize the word <code>zzzzzzzzzzzzzzzz</code>
with Z and Zz? How is this related to the question <em>“how many ways are there to
cover a two-by-ten grid with dominoes”</em>? (Hint: this is purely a math problem.
You can use a computer to help find the answer, but try to use math to prove
it.)</p>
<p><strong>Bonus problem 4!</strong> Read about <em>lazy lists</em>. 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?</p>
<p>Once you’ve done that, read about <code>call-with-current-continuation</code>. Figure out
how to use it cleverly to solve this problem (if you’re confused, read about
<em>backtracking</em>, or consult the Python program linked at the bottom of this
page). Is your solution faster? More space-efficient? Does it look prettier?</p>
<p>Think about how the above two implementations are the same, and how they are
different. Can you use <code>call-with-current-continuation</code> to implement lazy
lists?</p>
<p><strong>Bonus problem 5!</strong> Read about <em>regular expressions</em>. Which regex do names
like “Casey” match? Which regex do names like “Josh” match? Which of the
previous two questions is easier, and why?</p>
<p>You can use a program called <code>grep</code> to test your solutions.</p>
<hr>
<p>(Non-aqueous) Solutions to the tests above:</p>
<pre><code>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)))
</code></pre><hr>
<p>(This problem was written in November 2014. It is based on a <a href="https://gist.github.com/Hardmath123/7862258">bad Python
program</a> 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.)</p>
</section>
<div id="comment-breaker">◊ ◊ ◊</div>
</article>
<footer id="footer">
<div>
<ul>
<li><a href="https://github.com/kach">
Github</a></li>
<li><a href="feed.xml">
Subscribe (RSS feed)</a></li>
<li><a href="https://twitter.com/hardmath123">
Twitter</a></li>
<li><a href="https://creativecommons.org/licenses/by-nc/3.0/deed.en_US">
CC BY-NC 3.0</a></li>
</ul>
</div>
<script>
(function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
(i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
})(window,document,'script','//www.google-analytics.com/analytics.js','ga');
ga('create', 'UA-46120535-1', 'hardmath123.github.io');
ga('require', 'displayfeatures');
ga('send', 'pageview');
</script>
</footer>
</body>
</html>