# Algebra is Magic (part 1 of many)

Tags

I’ve been doing Algebra with Leo for some time, and every once in a while I actually amaze myself at just how cool Algebra is. Leo and I have in mind writing a book called “Algebra is Magic” which would just be a bunch of short solutions to what look like difficult problems, but which just “magically” drop out through Algebra.

Whenever we do any math, I’ve been trying to engrain that the first question is always “What’s the model?”, that is, what is the formal ‘equational’/’mathematical’/’algebraic’ form of whatever problem we’re doing?

Now, usually I know where we’re going, because I can do most of the things that a K-12 student would ever encounter more-or-less in my head, or at least I can tell right away what the algebraic form is going to be. So, together we write down the model (which I already know … or am able to work out without thinking too hard, so I lead him through this), and then we push through the algebra, and “voila!” the answer. (We always, of course, check the answer, at least for making sense, and usually for being correct by pushing it back through the original equation.)

Now, usually, the “voila!” moment is unsurprising to me, because I knew it was going to work, because I could see that we did it right, and where it was going. But, as I said at the outset, sometimes the problem is hard enough that even I’m not sure whether we’re right, and even I am surprised when it works!

There have been many of these, and our plan is to write these up, first in this blog, and eventually in a book.

Here’s just the latest one, as an example:

We’re starting on Calculus, and the book that I’m using (Stewart’s Calculus [8th ed.] from Engage Learning) has a  diagnostic test in the preface. For the most part these are pretty simple high school Algebra problems, and even Leo can do most of them … maybe with a little guidance from me … and I can, of course, do all of them. But there are a couple that are even tricky for me.

One such is this:

Prove:

$\tan(\theta)\sin(\theta)+\cos(\theta)=\sec(\theta)$

So, first off, we know “SOHCAHTOA”, and have used it a lot, but I had to recall what secant was. (I know its either inverse sine or cosine, but the way I remember which one is that I remember that it’s as confusing as possible, so to be as confusing as possible secant is inverse cosine, and cosecant is inverse sine!)

Okay, fine, but on the face of it I had no sense that this was going to be anything but a mess to prove. But we decided to use the “Algebra is Magic” mantra:

“Get a model and just push it through!”

Okay, so even I don’t know where this was going, but went with it, but here goes:

(I’m using ‘p’ here instead of ‘o’ to mean ‘opposite’, to avoid confusion with zero)

$\sin = p/h, \cos=a/h, \tan=p/a$

Blindly substitute into:

$\tan(\theta)\sin(\theta)+\cos(\theta)=\sec(\theta)$

to get:

$(p/a) * (p/h) + a/h =h/a$

Next, blindly push through the algebra, not really knowing where this is going:

Multiply:

$(p^2/ah) + a/h =h/a$

Multiply through by a:

$p^2/h + a^2/h =h$

Multiply through by h:

$p^2 + a^2 =h^2$

And then … Whoa! What The…. That’s The Pythagorean Theorem!

We weren’t headed there at all; we didn’t actually know where we were headed; Algebra brought us to The Pythagorean Theorem … by Magic!

And if we take The Pythagorean Theorem as axiomatic (which, of course we do!), then we just proved the target expression!

QEfingD … MAGIC … BANG!

(This, of course, led into into long discussions of the difference between theorems and axioms, including studying a bunch of proofs of The Pythagorean Theorem itself. But none of that was as magical as running headlong into it without knowing where we were headed!)

# Learn Math, not Mandarin

Tags

An old joke goes:

Q: What do you call someone who knows three languages?
A: Trilingual
Q: What do you call someone who knows two languages?
A: Bilingual
Q: What do you call someone who knows just one language?
A: An American

Probably mostly true, the joke implies that it’s a bad thing to know only one language. More specifically, it’s poking fun at the fact that most Americans only speak English. But is it such a bad thing to only know English? According to this Wikipedia list of most commonly spoken languages, the most spoken “primary” language (“mother tongue” or “L1 Rank”) is, predictably, Mandarin, followed by Spanish, and then English. So, you’re at least in the top 3 just out of the gate!

But just looking at the number of speakers of their Mother Tongue (L1) is misleading, because when someone does learn a second language, it is almost always English! So instead of looking at the most common “first languages” (L1), you look at the most common languages including second languages , that is, the languages by total number of speakers (L1+L2+…), you get a very different, and somewhat surprising, list (the rightmost column in the WP table, and the main sorting rank of the table). By this measure, English is the most commonly spoken language, with 1.12 Billion speakers (at this writing), followed closely by Mandarin (1.11B), and then by Hindi, Spanish, Arabic, and French. The reason that most people learn English as a second language, if it isn’t their Mother Tongue, is that English is the de facto language of Business, Engineering, Science, and, most influentially, The Internet. Indeed, by the time you get to French, there are fewer speakers of French word-wide than the population of the US! So, really, there are only five global languages: English, Mandarin, Hindi, Spanish, and Arabic. So if you were going to learn a second natural language, you’d do best to learn one of those.

But I’m going to make a play for taking a different path; Instead of bothering to learn a second (natural) language at all, speakers who’s Mother Tongue is one of the four global languages that isn’t English, should definitely learn English as a second language, in order to participate fully in Business, Engineering, Science, and, The Internet. BUT — and here is where I’m going out on a limb of my own!  — native speakers of English (or those who already know it well, if not natively), shouldn’t waste their time learning a second (natural) language at all, but instead, those English-speakers should spend their time learning the only true permanent global language: Math.

Now, I realize that this is an extraordinary suggestion, and that extraordinary suggestions require extraordinary support. I’ve already demonstrated that one doesn’t really need to learn any language other than English in order to participate in the modern technical world. One may want to learn a second natural language for some personal or local reason. For example, I live in California, where knowing Spanish is of great practical value, and I’m personally fascinated by Chinese (esp. it’s ideographic writing system). But some educators have argued (and some scientists have experimental results to support the hypothesis) that learning a second language is good for your brain. My read of this data is that it’s pretty weak. However, I have no interest in trying to tear down that result, but instead to make a different point, which is that, as far as I know, there are no studies that suggest that learning math as a “native speaker” does not have at least the same, and perhaps even more benefit … and it certainly couldn’t hurt!

Now, one might well ask, at what age one should start being exposed, under my theory, to math. My answer is very specific: Immediately — from day one! My hypothesis is that mathematical understandings, as well as mathematical ways of “seeing” the world, can be taught basically bilingually, so that just as someone is bilingual in two natural languages, one can become essentially bi-lingual in English and mathematics.

“But wait!” I hear you saying to me (via your computer screen), “Math isn’t a natural language — it’s a faux language — a notation made up by mathematicians to describe and manipulate things mathematical!” This, of course, depends upon your definition of “natural” (and it’s opposite: “faux”). Whereas math doesn’t have apparent surface structure of natural languages, I assert that it does have the basic elements thereof: There are abstract and concrete nouns (e.g., numbers, triangles) and verbs (operations such as addition and subtraction, or, if you prefer: “more” and “less”), and there is a grammar and a semantics, whereby grammatical sentences have clear and specific semantic referents, and ungrammatical sentences do not.

Moreover, just as natural languages derive directly from our needs to do things with, and communicate about, things in, and state of in the real world, such as running away from lions, attracting mates, and (more recently) engaging in commerce, mathematics derives directly from our needs to do the exact same sorts of things: count chickens (or the number of lions you are running away from), mark time, distance, and rate (as you run from them) and their relationships, and so on. Indeed, the typical elementary mathematical practice of word problem solving relies explicitly upon the fact that natural expression and mathematical ones are closely related.

To wit:

“John has three bags with four faux diamonds in each. He trades half of the bags with Mary for six dollars total. Five minutes later Mary discovers that the diamonds are glass, and releases a hungry lion to eat John. A lion can run ten times as fast as a person walks, and five times faster than John can run. John, having had a five minute walking head start, starts running from 500 yards away when Mary releases the lion. How much longer does John have to figure out how much per faux diamond he had just traded his life away for?”

See, perfectly fine, either as a natural or mathematical language!

Moreover, there is constant hand-wringing about which second language one should learn. For the rest of the world, the decision has clearly been made: English. As a result, I believe that people whose Mother Tongue is English are missing a phenomenal opportunity to get an enormous leg up on the rest of the world in business, science, and engineering, by bothering to learn a second natural language, but instead, they ought to be taught math bilingually – a native language – from birth.

What does it mean to learn math bilingually, as a native language? First, of course, there is counting, which can be learned from the very earliest months of life. As poor John above demonstrates, mathematical operators, like multiplication and division have natural language phrases, for example, “of” or “at” are forms associated with multiplication, and the same is true for most mathematical operations and most basic mathematical objects are directly groundable on natural objects and experiences (at least until you get to very abstract concepts).

Math is the only truly universal language, even more so than English. Learn Math, not … well, anyway, not French! [I’m mostly kidding here; Half my family is French, so I have no loss of love for French, and would have a good personal reason to teach it to my kids, if there weren’t several way more practical options, like math, Spanish, and Chinese!]

ps. I’m reminded of something I heard a physicist say on a radio interview once. The interviewer ask him what his greatest fear was (scientifically speaking). He had a fun answer, that was something like (paraphrasing): “I’m afraid that we’re going to finally communicate with intelligence aliens who are way more sophisticated than us, and they’re going to explain all the scientific mysteries of the universe to us, beginning with: ‘Math? Yeah, we tried that for a while; it didn’t work out so well…'” 🙂

# A Minecraft Virtual Diorama

Tags

Leo’s 4th grade class had a Project Based Learning (PBL) exercise that latest several weeks. I only barely know any of the details about this assignment (because what self-respecting 4th grader would tell their dad anything?!) But as I vaguely understand it, the focus of the PBL was on animal habitats. They started out with a field trip to the Oakland zoo a few weeks before. Then each group of about 4 students was assigned two animals that usually live in a given ecosystem, and they had to design an “ethical enclosure”, and explain various aspects of it in a powerpoint presentation. There was also a tiny bit of electronics, and scratch programming involved in the project, although most groups just used the electronics to let the visitors to their booth click the powerpoint forward.

Leo’s group was assigned the Australian Spinifex hopping mouse, and some kind of mole that presumably lives in the same deserts as the hopping mouse.  Now, when I was a kid, we would make dioramas in shoeboxes. But since Leo is so into Minecraft, I suggested that they use it to create a virtual diorama. Which they did! I bought the team a “Realm”, which is basically a specialized Minecraft server, and they went at it for about five hours, and it seemed to me to have come out pretty well, although it’s a bit hard to see in the below pic.

The animals were represented by two different MC “mobs” (their name for an NPC — a monster or, as in the case, animal). They “built” (as in MC building) a clear glass enclosure that had both internal and external relevant desert features, including above and below ground. Then the visitor could freely navigate around inside or outside the inclosure (including below ground, of course) and visit the (quasi)animals in their (approximately computationally simulated) natural habitat.

# Trap, Pillar, and Teleport Chess

Tags

Leo likes making up new kinds of chess. Usually his mods are pretty unplayable, but a couple of them have been sort of fun.

Trap Chess

For some time we’ve had these elementary math table things that have pretty solid spring mechanisms so that you can pop in or out the problems to reveal the answer. These are kinda fun; One fun thing to do is to make a marble maze and then trying to run a marble through it. Over the weekend, we invented what actually appears to be a an interesting — and even playable! — kind of chess that we call “Trap Chess”. It works like this: Whenever you take another piece, you are “trapped”, that is, the square that you take on is depressed, and you have to use a move to pop it back up. And if you take into a trapped piece, the attacker is now trapped.

Here’s are a couple of examples:

(Note that because a times-table is 9×9, we had to depress one edge all around.)

In the righthand game the black rook is trapped (from having taken something in some previous move). If it was white’s turn, the rook could be attacked by the white bishop moving to 5×3, because the rook would have to spend a move to pop out of the trap, and would thence be prey to the 5×3 bishop.

In the lefthand game, the black knight at 6×4 is NOT checking the white king, because the knight is trapped. But if it were black’s move, and the knight were to pop out of the trap, THEN the white king would be in check! (And note that the bishop is pinned by the rook!) Also, that if the black rook was to take the white bishop, it would become trapped, and the white king could take it (as usual), but then the king would become trapped. Having a trapped king is a recipe for a checkmate because in order to move out of check, the king would first have to pop out of the trap!

We tried several modifications on this, but the basic rule, as above, seemed to be pretty good. One mod that seemed sensible was that you were also trapped if you promote a pawn, giving the defender an extra move.

Pillar Chess

The nice thing about Trap Chess is that it doesn’t introduce randomness, just a new twist to the standard chess game. Two other kinds of chess that Leo invented had random components, and were less playable. In one, which I’ll call “Pillar Chess”, there is a 2×2 object (we used a pill bottle — and called it a “pillar” :-)) in the middle of the board, and on every move (or maybe it was ever two moves — one white and one black) you would throw a 1d6 die, which would dictate how the pillar would move. 1 = no move, 2 = toward black, 3 = right from black, etc. And I think that 6 was “throw again” … doesn’t matter how the assignments work, obviously, the idea is just that this thing in the middle of the board both blocks long moves, and randomly moves around the board! If a piece is bumped by the pillar moving, it pushes in the obvious direction, and this “dominoes” along in the obvious way. Any piece bumped off the board, either directly or indirectly, is out of the game.

This wasn’t actually all that much fun. Since it’s really hard to plan moves around where the pillar might end up, you just end up planning around it, and it’s possible path, so as to avoid potential problems, making this much less interesting than it sounds. Pretty much where the pillar is, is just a big hole in the board, and one there aren’t as many pieces on the board, the pillar didn’t move fast enough to matter much.

Teleport Chess

The other version we played was teleport chess, where on every move, 2d8 die (that is, 2-eight sided dice) are thrown twice. The first throw identifies where the “black hole” opens up, and the second roll identifies where it exits. Any piece on the hole’s entrance gets sucked in and deposited at the exit. This turned out to be slightly interesting, until there weren’t enough pieces on the board for it to pretty much ever hit on of them, so the rolls had no effect. You could imagine versions of this that would fix that problem, but still, as above, it’s pretty hard to plan against randomness, which breaks the main beauty of chess!

# Simulating Synesthesia (with Lego)

Tags

One of my students wanted to study synesthesia, but he isn’t synesthetic (nor am I), and it’s sort of a hard thing to simulate (at least legally). Coincidentally, I was recently trying to decided whether Leo was too young to read Dune, Frank Herbert’s SciFi masterpiece. He probably is, but there is a scene in it where the hero is tested by having to hold his hand in a pain-inducing box. (The pain is induced in the nerves; No damage is actually done to the person’s hand.) One of the examples that I give in class is “blindfolded cooking”, the idea being to give someone the sense of what it might be to be blind while doing a task in which we normally depend heavily upon sight. Actual blindfold cooking is pretty dangerous, so we don’t actually do it in class, but putting these ideas together gave me what I thought was a great idea for my student: How about having someone do a fairly complex task in a “blinded” glovebox. Usually you can see into a glovebox, but here we would preclude that by simply making the glovebox without a window!

What about the task? Recall that the idea is to give the sense of synesthesia. The task that we finally hit upon was to copy a somewhat complex lego construct. We would create a small random lego construct with, say, 10 different pieces, then stick it in a cardboard box with a bunch of other random lego pieces, including at least one of each piece needed to copy the target construct. Finally, we cut two wrist-sides “glove” holes through the side of the box.

Here’s the box wit the top open, and Leo holding up the target construct:

The idea, of course, is to copy the construct with the box top closed, like this:

(The book is just to keep the box top closed.)

This turns out to be a really interesting puzzle, and I do think that if you close your eyes and try to visualize the target, and what’s going on when you copy it, it does gives you a little bit of a sense of crossed senses, a bit like what it might be like to be synesthetic.

# A Simple, Fun, and Interesting Card Game

Tags

I was skimming best-of list for games of 2018 and came across The Mind on several lists. It looks like a relatively simple, but interesting game, and after watching a couple of videos showing its gameplay, I decided that I could create more-or-less the equivalent thing just using a standard 52-card deck.

At first The Mind seems too simplistic; Players just cooperate to put out their cards in numerical order (I think it’s 1-100 in The Mind). What makes this hard is that you can’t talk to one another! So somehow you and the other player(s) have to “communicate” who should go next by … who knows … ESP or something? Under these circumstances, The Mind seems nearly impossible; how could you possibly know who’s got the next highest card without signaling in some way or other. I haven’t play The (original) Mind, but given that it gets such glowing reviews, I’m going to assume that what happens is that the players sort of learn one another’s non-verbal cues.

Regardless of how The (original) Mind works, I created what seems to be a very doable and fun version that uses a standard 52-card deck (plus jokers). Here’s how it goes:

Setup: Separate the (2) jokers, and the (13) hearts from the deck. Place the 2 jokers face up. These are your lives. Order the hearts from Ace-through-king face up, and place them in a stack, so you’ll be looking at an Ace. This is your level counter. (This is an “Ace Low” game: Ace = 1, J=11, Q=12, and K=13.) Shuffle the remaining 39 cards (the remaining 3 suits).

Overall Goal: The play is cooperative; when I say “you”, I mean, “you all the players cooperating”.  The hearts indicate your level, so you start at level 1 (ace), and win if you get to level 13 without dying either 2 or 4 times. (I recommend 4 times for the beginners). The jokers indicate your lives; Each time you fail, you either discard a joker if you’re playing 2-lives, or turn over, and then on the next fail discard a joker, thus affording you 4 lives. (Of course you can do life and level counting any way you like! This setup just makes things convenient.)

Level Play: For each level (1-13 == ace->king) play goes as follows:

1. Shuffle the 39 cards.
2. Deal as many cards to each player as your level. So on the first play each player gets one card, second level 2, etc. and if you should make it to the 13th (King) level, each player would get 13 cards. (There can only be 3 players, obviously, or else you’ll have to either play with multiple decks, or somehow otherwise modify the rules so that you don’t have to deal more cards than there are in the stack.)
3. Play as many rounds as you can get to without failing. If you fail, you decrement a life (jokers). If you get through all the dealt cards, then you win that level.
4. In either case, flip over one of the hearts to go on to the next level.
5. GoTo 1 🙂

Rounds within a level are really simple, but here is also where things get interesting:

Each round is independent — don’t worry about whether the cards between rounds are higher or lower than one another, HOWEVER, leave all the cards face up (you’ll see why this is in a moment).

Even though the players are cooperating, they cannot look at one another’s cards, nor talk to one another, except to decide which player should go first, then next, etc.

On each round, each player must place exactly one of their cards in an order that the players can discuss, but without telling one another what card they are playing. If the cards are placed in lowest-to-highest order, then that’s a win. If they are not, then the level is failed. (Ties count as wins; only out-of-order sequencing fails.)

For example, in level one, since each player has just one card, there will only be one round. If one of the players was dealt an Ace, they should argue strenuously to go first since regardless of what any other player could place, it will either tie or be larger than an Ace.

If you succeed at level 1, go on to level 2, where each player has 2 cards, and so on up to 13. If you haven’t failed 2 (or 4) times by the end of level 13, the game is won!

If you think this sounds either too easy or too hard to be interesting, try it and see for yourself; It’s actually quite difficult and interesting. Consider these factors:

1. As you get to higher levels, since there are only 3 of any card in the deck, you are more and more likely to be able to guess what cards the other players must have, especially combined with what has been already played. (Recall that I said it’s useful to leave all the played cards face-up and exposed. This helps in the card counting that can be a useful strategy.)
2. Since the rounds within a level are independent, you don’t have to play your lowest card on each play. It may be useful, for example, to play your very high cards early in order to get rid of some of them. Recall that you can’t talk about anything except who is going to place the next card, so you can’t agree no an algorithm. However, you can figure out, perhaps, what your team-mates’ algorithm might be, and play cooperatively with them based on this analysis.

So, there you go. Fun game for a rainy afternoon!

# Target Trig Tiff

Tags

A few nights ago, Leo and I were playing with a glowing nerf bow-and-arrow-like rocket launching toy. I’m not much for toy weapons, but the “arrows” on this one are more like little rockets, they make a whizzing noise, and glow bright red, so it’s pretty fun at night in our cul-de-sac street.

Anyway, at one point Leo decided that he needed a bright white target, because it was getting quite dark, so he went inside and brought out a large sheet of art paper that he wanted me to hold up so he could shoot at it. Not really wanting to be the backstop for either his good or (more likely) poor aim, I suggested instead that it would be just as easy to lay the target on the ground.

This led to a bit of a tiff between us (the petty argument kind, not the tagged image file format kind!) Leo thought that laying it down on the street made it nearly impossible to target, whereas I thought it was more-or-less irrelevant. Later he depicted his argument with the following graphic:

That’s a bit hard to follow without the attached angry 9-year-old angrily explaining it at you, but the idea is that when the target is mounted on the wall (i.e., I’m holding it up, or it’s stuck to a tree, or something), as depicted in the center top and middle images, it is apparently larger than when it is laying on the ground. He made a rough guess about the ratio as the laying down apparent area being the old area divided by 2pi, or about 6x smaller.

On the left are depictions of how it’s harder to hit, in addition, because you have to shoot parabolically rather than directly at the target. I think that the the parabolic problem isn’t true — you’re always, shooting parabolically — although it may feel like you need to do that more-so because the thing is laying flat. So, I won’t pursue that part of the tiff. However, his point about the target’s apparent size is absolutely correct. Moreover, as he correctly, and angrily, pointed out, it’s worse for someone shorter!

I grasped the opportunity to redirect his ire into some trig, in order to figure out exactly how much small the target apparently is when laying down, as opposed to being mounted at eye level.

This is depicted here, and explained a little below. (I’ve slightly annotated the original page that Leo and I did the math on.)

We assumed a 6ft person (my eye level) looking at a 4ft target mounted at eye-level 20ft away. (For Leo, the observer would be about 1.5ft shorter.) We assumed as well that the target is laying flat with the center exactly at the 20ft point. We drew the two right triangles, for eye-to-far-end and eye-to-near-end of the fallen target (which would be at 22 and 18ft away along the base-line, respectively). Simple trig gave us the angles from vertical to eye-line for these, being 74.75 and 71.57 degrees, respectively.  Now it’s a little geometrically tricky, but arithmetically easy to compute the length of the vertically-projected line at 20ft between the two hypotenuses (hypothenusa? hypotenua? hypotena?), but breaking it into two right triangles that are similar to the larger ones. (This can probably be done by similar triangle ratios, but it was clearer, at least at that moment, to use trig.

The result is 1.211 ft. of apparent size, which isn’t 6x smaller, but it’s about 3x smaller. And although we didn’t compute it for Leo’s height, it would obviously have been even smaller than 1.2ft apparent size. (You can prove this to yourself by observing that if all you do is to turn the paper on edge, at 6ft, where it is mounted at eye-level, it will essentially disappear altogether because you’re looking at it edge on. In general, the more parallax you have, the larger it will appear. So a shorter person with less parallax will see a small apparent target size. So it may well be that it is ~6x smaller for someone 4″9′ tall!)

Now, actually what you want is not quite this, because one’s view goes around an arc, always at 90 degrees from the center. So there’s actually a small correction required to “lean” the page slightly, as depicted by the hypotenuse on to bottom right inset. I don’t show this computation, which I did later myself, but the final size comes to about 1.14ft of apparent size (as I recall), and this is actually still slightly off since I cheated by making a right triangle with one of the sight lines, but since we’ve been wildly rounding the angles all along, a greater level of precision is definitely not called for!

# Visualizing DNA? (Probably not!)

Tags

Last week we did a week-long unit on ecosystem dynamics and evolution, which included the usual activities: looking at pond water microbes under the microscope, DNA extraction, walks in the woods (saw a snake!), predator-prey modeling, and so forth.

(Incidentally, we did our modeling in NetLogo, which is a terrific tool for teaching multi-agent modeling; I should do a separate post about this!)

Most this was run-of-the-mill science, and not too worthy of report, except for one interesting event.

DNA extraction from strawberries — using dish soap, salt, and alcohol — is about the most fun lab activity you can do in your kitchen! Here’s one of many all-the-same protocols you can find online. Unfortunately, all you get at the end is a huge clump of what is supposedly DNA. Since we were doing microscope work earlier in the week, I decided to try to visualize the DNA. My microscope goes up to about 470x (without oil), and since you need an electron microscope to see the helical structure at all, I figured that we wouldn’t see much in my light microscope.

However, when I was working in the lab we used a simple technique, called molecular combing, to stretch out the chromosomes in order to count them and get their sizes. I didn’t think that this would do anything useful in our kitchen, as you generally have to attach fluorescent markers to see the chromosomes in the lab, but I decided to give it a try anyhow.

Amazingly, just using the cover slip of the microscope slide to “comb” the strawberry DNA extract, we were able to visualize … well, I have no idea what this is:

They sure do look like helical structures of some sort. I’m guessing that these aren’t DNA, unless strawberry DNA are humongous! Rather, they are probably some sort of connective tissue from the strawberries. But for our first try at visualizing something DNA-like, it was pretty exciting. (I didn’t let on to Leo that these are almost certainly NOT DNA!)

Incidentally, this “photomicrograph” was taken by just putting my iPhone up to the eyepiece of the microscope. It took a few tries, but I’m slightly amazed that it worked at all!

# Raven Redux

Tags

(I actually had to look up “redux” to make sure that it wasn’t a synonym of “reduce”.)

Anyway…

So, you probably don’t recall — because I hardly did — that about year ago Leo and I wrote a Lisp program to randomly generate “poems” by randomly selecting words from The Raven. Leo has recently been reading my Lisp book (heaven help him!), and got interested in revisiting our old program. Rather than just rehash it, I thought that we could do something a bit more clever this time around, I explained n-gram language models (although not in those terms), and then hash tables, with the goal of writing much more interesting poems.

Leo started out in Snuffy Code, which is a programming language he invented for himself some time ago, and which is actually pretty close to what computer scientists call pseudo-code. Here’s his Snuffy Code version of the algorithm:

You can see bits of our working on the data structures at the top, and to the right is a bit of our work on translating his Snuffy Code into Lisp. Here’s the Lisp:

(defvar *table* (make-hash-table :test #'equal))

(defun learn ()
(clrhash *table*)
(loop for sentence in *sentences*
do
(loop for (cur nxt) on (:start ,@sentence :end)
do (push nxt (gethash cur *table*)))))

(defun compose-line ()
(loop with cur = :start
as options = (gethash cur *table*)
as nxt = (nth (random (length options)) options)
until (eq nxt :end)
do (setq cur nxt)
collect cur))

(defun compose-poem ()
(loop for sentence in *sentences*
as this-length = (length sentence)
if (= this-length 0)
do (print nil)
else do (print (loop for random-line = (compose-line)
until (= this-length (length random-line))
finally (return random-line)))))

(In the previous post what is here called *sentences* was there called patterns, or p.)

All you need to do, then is:

(learn)
(compose-poem)

Et voila! (I’ve replaced the nils at paragraph breaks with double newlines.)

(DARKNESS PEERING LONG I PONDERED WEAK AND OMINOUS BIRD OR DEVIL)
(THEN THE RARE AND SAT ENGAGED IN THERE WONDERING FEARING)
(THIS EBONY BIRD AND THIS GRIM UNGAINLY FOWL TO BORROW)
(BY HORROR HAUNTED TELL THIS KIND NEPENTHE FROM AN UNSEEN CENSER)
(QUAFF OH QUAFF OH QUAFF OH QUAFF THIS MYSTERY EXPLORE)
(BUT THE NIGHTS PLUTONIAN SHORE)

(ON THE FACT IS THERE BALM IN THE NIGHTLY SHORE)
(WRETCH I PONDERED WEAK AND FOLLOWED FASTER TILL I SHRIEKED UPSTARTING)
(THOUGH THY MEMORIES OF A TAPPING AT MY FANCY INTO SMILING)
(FANCY UNTO FANCY THINKING WHAT THY FORM FROM AN UNSEEN CENSER)
(QUAFF OH QUAFF THIS I OPENED WIDE THE BUST AND STORE)
(TILL HIS CHAMBER DOOR)

(SHE SHALL CLASP A FEATHER THEN NO LIVING HUMAN BEING)
(IS SOMETHING AT MY HEART BE SHORN AND NOTHING MORE)
(NOTHING FARTHER THEN THIS AND BUST OF A FLIRT AND AN UNSEEN CENSER)
(OVER MANY A DEMONS THAT ONE WORD HE FLUTTERED)
(RESPITE AND CURIOUS VOLUME OF EVIL PROPHET SAID NEVERMORE)
(FOR THE LAMP-LIGHT GLOATED O ER)

(SIR SAID I NODDED NEARLY NAPPING SUDDENLY THERE SPOKEN)
(TIS THE PLACID BUST ABOVE HIS SONGS ONE GENTLY RAPPING)
(STARTLED AT MY BOOKS SURCEASE OF LORD OR BEAST UPON THE RAVEN NEVERMORE)
(ON THE RAVEN OF THE SAINTLY DAYS OF LORD OR DEVIL)
(PERCHED UPON A SAINTED MAIDEN WHOM THE SCULPTURED BUST OF THE NIGHTS PLUTONIAN SHORE)
(BACK THE NIGHTS PLUTONIAN SHORE)

(AS A MINUTE STOPPED OR BEAST UPON THE RAVEN OF YORE)
(THIS EBONY BIRD OF SORROW FOR THE COUNTENANCE IT WORE)
(TELL ME TELL ME AS OF BIRD BEGUILING MY CHAMBER DOOR)
(NOT A TAPPING TAPPING TAPPING AT MY HOPES HAVE FLOWN BEFORE)
(BUT THE SILENCE WAS UNBROKEN QUIT THE BIRD OF FORGOTTEN LORE)
(THEN METHOUGHT THE TUFTED FLOOR)

(BY THE SHUTTER WHEN WITH THE GRAVE AND THE CHAMBER DOOR)
(SWUNG BY THAT LIES FLOATING ON THE LAMP-LIGHT O ER)
(TIS THE SHUTTER WHEN WITH SORROW LADEN IF HIS CHAMBER DOOR)
(SHE SHALL CLASP A DEMONS THAT IS DREAMING DREAMS NO LONGER)
(SOME ONE GENTLY RAPPING RAPPING AT MY HEART BE LIFTED NEVERMORE)
(THAT IS ITS ONLY WORD LENORE)

(DESOLATE YET ALL THE ONLY THIS AND THIS KIND NEPENTHE AND THE FLOOR)
(FOR THE SILENCE WAS SURE I HEARD YOU CAME A TAPPING TAPPING)
(FANCY THINKING WHAT THIS SOUL WITHIN THE TEMPEST TOSSED THEE HERE I IMPLORE)
(SIR SAID I WHEELED A RARE AND THE STILLNESS GAVE NO CRAVEN)
(TIS SOME VISITOR I PONDERED WEAK AND THIS DESERT LAND ENCHANTED)
(NOT A TOKEN OF FORGOTTEN LORE)

(SHALL PRESS AH DISTINCTLY I HAD SOUGHT TO DREAM BEFORE)
(IN THE CUSHIONS VELVET SINKING I WISHED THE LAMP-LIGHT O ER)
(BUT THE FOWL WHOSE FIERY EYES NOW BURNED INTO THE LAMP-LIGHT GLOATED O ER)
(AH DISTINCTLY I CRIED THY SOUL WITH SUCH NAME LENORE)
(QUOTH THE COUNTENANCE IT IS SITTING STILL IF WITHIN THE NIGHTLY SHORE)
(AND SO APTLY SPOKEN)

(IT UTTERS IS I HEARD A BUST SPOKE ONLY WORD LENORE)
(WRETCH I SAT ENGAGED IN THE MORROW HE)
(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(SOME VISITOR ENTREATING ENTRANCE AT MY SOUL IN FRONT OF LENORE)
(CAUGHT FROM SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(OF A STATELY RAVEN NEVERMORE)

(QUOTH THE SHUTTER WHEN WITH MY HEART BE THAT IS DREAMING)
(BUT THE WHISPERED AND NOTHING FARTHER THEN HE UTTERED NOT A BUST OF YORE)
(SWUNG BY REPLY SO FAINTLY YOU CAME RAPPING AT EASE RECLINING)
(THAT NOW BURNED INTO THAT IS ON THIS AND NOTHING MORE)
(DESOLATE YET ALL THE AIR GREW DENSER PERFUMED FROM THE ANGELS NAME LENORE)
(THAT NOW TO DREAM BEFORE)

(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(AND THE RAVEN STILL A FEATHER THEN THE LAMP-LIGHT GLOATING O ER)
(GET THEE BY THE SEEMING OF THE FLOOR)
(AND BUST AND RADIANT MAIDEN WHOM THE BIRD BEGUILING MY DOOR)
(TIS SOME VISITOR ENTREATING ENTRANCE AT MY HEART AND MORE)
(PRESENTLY MY DOOR)

(TO THE ONLY STOCK AND THIS AND AN UNSEEN CENSER)
(SHALL PRESS AH DISTINCTLY I WHISPERED AND FOLLOWED FASTER TILL THE WHISPERED WORD LENORE)
(FANCY UNTO FANCY THINKING WHAT THEREAT IS AND NOTHING MORE)
(DOUBTLESS SAID I WHEELED A BUST ABOVE HIS CHAMBER DOOR)
(FOLLOWED FASTER TILL I THING OF SOME VISITOR I SHRIEKED UPSTARTING)
(LEAVE MY CHAMBER DOOR)

(THEN UPON A SAINTED MAIDEN WHOM THE ANGELS NAME LENORE)
(BUT WHOSE FOOT-FALLS TINKLED ON THIS EBONY BIRD OF EACH PURPLE CURTAIN)
(AND NEPENTHE FROM THY SOUL FROM MY SOUL WITH THE RAVEN SITTING)
(SIR SAID I SCARCE WAS UNBROKEN QUIT THE NIGHTS PLUTONIAN SHORE)
(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(BE SHORN AND NOTHING MORE)

(THRILLED ME WITH MY HEART BE STILL IF BIRD OF LENORE)
(MEANT IN THAT SHADOW ON THE SAINTLY DAYS OF YORE)
(MEANT IN GILEAD TELL ME AS IF WITHIN THE RAVEN STILL IS AND SO PLAINLY)
(BIRD OR FIEND I FLUNG THE NIGHTS PLUTONIAN SHORE)
(WHILE I STOOD THERE CAME A MINUTE STOPPED OR STAYED HE)
(THIS DESERT LAND ENCHANTED)

(WRETCH I WISHED THE FACT IS ON THE RAVEN NEVER FELT BEFORE)
(EVER YET WAS IN GUESSING BUT THE NIGHTS PLUTONIAN SHORE)
(PERCHED UPON THE TEMPEST AND STERN DECORUM OF LENORE)
(TELL ME I HEARD YOU CAME TAPPING AT MY CHAMBER DOOR)
(MERELY THIS SOUL WITH MY CHAMBER TURNING ALL THE ONLY WORD THERE SPOKEN)
(THIS DESERT LAND ENCHANTED)

(BY HORROR HAUNTED TELL ME TRULY YOUR FORGIVENESS I REMEMBER IT WORE)
(WHAT THY BEAK FROM AN ECHO MURMURED BACK INTO THE NIGHTS PLUTONIAN SHORE)
(BUT THE FACT IS SITTING LONELY ON THE NIGHTS PLUTONIAN SHORE)
(MEANT IN GILEAD TELL THIS GRIM UNGAINLY FOWL TO DREAM BEFORE)
(THIS GRIM UNGAINLY FOWL WHOSE VELVET-VIOLET LINING THAT THE MORROW HE)
(RESPITE AND SO PLAINLY)

(THEN METHOUGHT THE GRAVE AND FORGET THIS I THING OF MY WINDOW LATTICE)
(AS A RARE AND CURIOUS VOLUME OF PARTING BIRD OR DEVIL)
(TIS THE ONLY WORD AS A MIDNIGHT DREARY WHILE I WAS THE RAVEN NEVERMORE)
(RESPITE AND FORGET THIS HOME BY THESE ANGELS HE FLUTTERED)
(AND FOLLOWED FAST AND SO THAT ONE WORD THERE CAME RAPPING AT MY CHAMBER DOOR)
(THEN THE RAVEN NEVERMORE)

(LEAVE ME I SAID I NODDED NEARLY NAPPING SUDDENLY THERE SPOKEN)
(TELL THIS I STOOD THERE CAME A QUAINT AND NOTHING MORE)
(FOLLOWED FAST AND THE PALLID BUST OF HIS SOUL FROM THE DISTANT AIDENN)
(EAGERLY I MUTTERED TAPPING SOMEWHAT LOUDER THAN MUTTERED OTHER FRIENDS HAVE FLOWN BEFORE)
(BUT WITH MIEN OF PALLAS JUST ABOVE US BY THAT GOD HATH SPOKEN)
(ONCE UPON THE FLOOR)



Before going any father I must point out some of the gems from this run, and a few others from other runs of the same code:

(QUAFF OH QUAFF OH QUAFF OH QUAFF THIS MYSTERY EXPLORE)
(FANCY UNTO FANCY THINKING WHAT THY FORM FROM AN UNSEEN CENSER)
(TIS SOME VISITOR ENTREATING ENTRANCE AT MY HEART AND MORE)
(PROPHET STILL IS SOMETHING AT MY LONELINESS UNBROKEN QUIT THE RAVEN OF LENORE)
(RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE RESPITE AND FLUTTER)
(QUOTH THE CUSHIONS VELVET LINING WITH FANTASTIC TERRORS NEVER NEVERMORE)

and my personal favorite:

(THOUGH ITS ANSWER LITTLE MEANING LITTLE MEANING LITTLE MEANING LITTLE MEANING LITTLE RELEVANCY BORE)

That was fun. After Leo went off to other things I decided to do a little refinement of my own, so I did a trivial little hack to improve the flow a little. First I rewrote the data by separating the paragraphs (whereas, in *sentences* there’s no concept of a paragraph, except for the nils between them.) That is, I created this structure:

(defparameter *paragraphs*
'(
(
(Once upon a midnight dreary  while I pondered  weak and weary  )
(Over many a quaint and curious volume of forgotten lore  )
(    While I nodded  nearly napping  suddenly there came a tapping  )
(As of some one gently rapping  rapping at my chamber door  )
( Tis some visitor  I muttered  tapping at my chamber door  )
(            Only this and nothing more  )
)
(
(    Ah  distinctly I remember it was in the bleak December  )
(And each separate dying ember wrought its ghost upon the floor  )
(    Eagerly I wished the morrow  vainly I had sought to borrow )
(    From my books surcease of sorrow sorrow for the lost Lenore  )
(For the rare and radiant maiden whom the angels name Lenore  )
(            Nameless here for evermore  )
)
...and so on...
))

Then, by integrating learning and composition, and then simply localizing the global *sentence*, which both the learning and composition use, first to 3-paragraph windows for learning, and the to each paragraph for composition:

(defun compose-progressive-poem ()
(loop for (p1 p2 p3) on *paragraphs*
do (let ((*sentences* (append p1 (append p2 p3)))) (learn))
(print '==============)
(let ((*sentences* p1))
(compose-poem))))

we get much better conceptual localization:

(EAGERLY I HAD SOUGHT TO STILL THE RARE AND NOTHING MORE)
(AH DISTINCTLY I WISHED THE BEATING OF EACH PURPLE CURTAIN)
(THIS IT IS AND CURIOUS VOLUME OF EACH PURPLE CURTAIN)
(WHILE I REMEMBER IT WAS IN THE BEATING OF FORGOTTEN LORE)
(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(AH DISTINCTLY I STOOD REPEATING)
==============
(TIS SOME LATE VISITOR ENTREATING ENTRANCE AT MY CHAMBER DOOR)
(THIS IT WAS SURE I SCARCE WAS NAPPING AND NOTHING MORE)
(NAMELESS HERE I SCARCE WAS SURE I HAD SOUGHT TO BORROW)
(NAMELESS HERE I IMPLORE)
==============
(PRESENTLY MY HEART I SCARCE WAS UNBROKEN AND NOTHING MORE)
(AND SO FAINTLY YOU CAME TAPPING AT MY CHAMBER DOOR)
(DEEP INTO THAT I WHISPERED AND SO FAINTLY YOU HERE I STOOD REPEATING)
(MERELY THIS IT IS I HEARD YOU CAME RAPPING)
(THIS IT IS I STOOD THERE AND NOTHING MORE)
(AND SO FAINTLY YOU CAME RAPPING)
==============
(PRESENTLY MY SOUL WITHIN ME SEE THEN NO TOKEN)
(TIS THE WIND AND THE SILENCE WAS THE CHAMBER DOOR)
(BACK THE SILENCE WAS SURE I OPENED WIDE THE WHISPERED AND NOTHING MORE)
(BUT THE STILLNESS GAVE NO MORTAL EVER DARED TO DREAM BEFORE)
(DEEP INTO THE FACT IS I SCARCE WAS SURE I SURELY THAT I IMPLORE)
(DOUBTING DREAMING DREAMS NO TOKEN)
==============
(NOT THE STILLNESS GAVE NO MORTAL EVER DARED TO DREAM BEFORE)
(LET MY CHAMBER TURNING ALL MY SOUL WITHIN ME BURNING)
(DEEP INTO THAT DARKNESS PEERING LONG I WHISPERED AND NOTHING MORE)
(TIS THE LEAST OBEISANCE MADE HE NOT THE ONLY WORD LENORE)
(DEEP INTO THE SAINTLY DAYS OF THE WHISPERED AND NOTHING MORE)
(TIS THE WHISPERED WORD LENORE)
==============
(THEN WHAT THY LORDLY NAME IS SOMETHING AT MY CHAMBER DOOR)
(PERCHED AND ANCIENT RAVEN WANDERING FROM THE NIGHTS PLUTONIAN SHORE)
(THOUGH THY CREST BE STILL A TAPPING SOMEWHAT LOUDER THAN BEFORE)
(TELL ME SEE THEN THIS EBONY BIRD BEGUILING MY WINDOW LATTICE)
(SOON AGAIN I SAID I SURELY THAT IS AND NOTHING MORE)
(BY THE LEAST OBEISANCE MADE HE)
==============
(PERCHED UPON A MINUTE STOPPED OR BEAST UPON THE SAINTLY DAYS OF YORE)
(NOT A FLIRT AND ANCIENT RAVEN OF THE SCULPTURED BUST OF YORE)
(IN THERE STEPPED A MINUTE STOPPED OR LADY PERCHED ABOVE MY CHAMBER DOOR)
(TELL ME WHAT THY LORDLY NAME IS ON THE COUNTENANCE IT WORE)
(WITH MIEN OF LORD OR LADY PERCHED ABOVE HIS CHAMBER DOOR)
(PERCHED UPON THE NIGHTS PLUTONIAN SHORE)
==============
(THOUGH THY LORDLY NAME AS MY SAD FANCY INTO SMILING)
(THEN THIS EBONY BIRD SAID ART SURE NO LIVING HUMAN BEING)
(THEN THE RAVEN SITTING LONELY ON THE MORROW HE WILL LEAVE ME AS NEVERMORE)
(FOR WE CANNOT HELP AGREEING THAT ONE WORD AS NEVERMORE)
(THOUGH THY CREST BE SHORN AND STERN DECORUM OF THE RAVEN NEVERMORE)
(BY THE NIGHTLY SHORE)
==============
(FOLLOWED FASTER TILL HIS SOUL IN THAT NO LIVING HUMAN BEING)
(CAUGHT FROM SOME UNHAPPY MASTER WHOM UNMERCIFUL DISASTER)
(FOLLOWED FAST AND FOLLOWED FAST AND FOLLOWED FAST AND STORE)
(TILL I MARVELLED THIS UNGAINLY FOWL TO HEAR DISCOURSE SO PLAINLY)
(TILL I SCARCELY MORE THAN MUTTERED OTHER FRIENDS HAVE FLOWN BEFORE)
(NOTHING FARTHER THEN HE FLUTTERED)
==============
(ON THE MORROW HE UTTERED NOT A FEATHER THEN HE FLUTTERED)
(ON THE MORROW HE UTTERED NOT A CUSHIONED SEAT IN THAT MELANCHOLY BURDEN BORE)
(ON THE RAVEN STILL BEGUILING ALL MY HOPES HAVE FLOWN BEFORE)
(TILL I SCARCELY MORE THAN MUTTERED OTHER FRIENDS HAVE FLOWN BEFORE)
(FOLLOWED FASTER TILL I WHAT IT UTTERS IS ITS ONLY STOCK AND DOOR)
(FANCY UNTO FANCY INTO SMILING)
==============
(STARTLED AT THE STILLNESS BROKEN BY REPLY SO APTLY SPOKEN)
(STRAIGHT I WHEELED A CUSHIONED SEAT IN FRONT OF BIRD OF YORE)
(WHAT THIS AND OMINOUS BIRD OF NEVER NEVERMORE)
(WHAT THIS I SAT DIVINING WITH MY HEAD AT EASE RECLINING)
(ON THE FOWL WHOSE FIERY EYES NOW BURNED INTO SMILING)
(OF NEVER NEVERMORE)
==============
(BUT WHOSE FOOT-FALLS TINKLED ON THE LAMP-LIGHT GLOATED O ER)
(THIS I BETOOK MYSELF TO THE FOWL WHOSE FOOT-FALLS TINKLED ON THE TUFTED FLOOR)
(THIS GRIM UNGAINLY GHASTLY GAUNT AND OMINOUS BIRD OF LENORE)
(WRETCH I BETOOK MYSELF TO THE LAMP-LIGHT GLOATING O ER)
(ON THE CUSHIONS VELVET SINKING I CRIED THY MEMORIES OF YORE)
(BUT NO SYLLABLE EXPRESSING)
==============
(WRETCH I SAT DIVINING WITH THE LAMP-LIGHT GLOATING O ER)
(QUOTH THE FOWL WHOSE FIERY EYES NOW BURNED INTO MY BOSOMS CORE)
(RESPITE AND MORE I SAT ENGAGED IN GUESSING BUT NO SYLLABLE EXPRESSING)
(RESPITE RESPITE RESPITE RESPITE RESPITE AND MORE I THING OF LENORE)
(WRETCH I SAT ENGAGED IN GUESSING BUT NO SYLLABLE EXPRESSING)
(SHE SHALL PRESS AH NEVERMORE)
==============
(WRETCH I CRIED THY MEMORIES OF EVIL PROPHET SAID I IMPLORE)
(CLASP A RARE AND RADIANT MAIDEN WHOM THE RAVEN NEVERMORE)
(PROPHET SAID I CRIED THY MEMORIES OF EVIL PROPHET STILL IF WITHIN THE RAVEN NEVERMORE)
(RESPITE RESPITE AND RADIANT MAIDEN WHOM THE RAVEN NEVERMORE)
(QUAFF OH QUAFF OH QUAFF OH QUAFF THIS DESERT LAND ENCHANTED)
(QUOTH THE RAVEN NEVERMORE)
==============
(IS THERE IS THERE BALM IN GILEAD TELL THIS DESERT LAND ENCHANTED)
(PROPHET SAID I THING OF EVIL PROPHET SAID I IMPLORE)
(CLASP A SAINTED MAIDEN WHOM THE NIGHTS PLUTONIAN SHORE)
(QUOTH THE TEMPEST TOSSED THEE BACK INTO THE ANGELS NAME LENORE)
(TELL ME TELL THIS SOUL WITH SORROW LADEN IF WITHIN THE RAVEN NEVERMORE)
(QUOTH THE DISTANT AIDENN)
==============
(AND MY HEART AND TAKE THY FORM FROM OFF MY CHAMBER DOOR)
(TAKE THY SOUL WITH SORROW LADEN IF BIRD OR FIEND I SHRIEKED UPSTARTING)
(TELL THIS SOUL FROM OFF MY SOUL FROM OFF MY DOOR)
(PROPHET SAID I THING OF EVIL PROPHET SAID I SHRIEKED UPSTARTING)
(SHALL CLASP A DEMONS THAT HEAVEN THAT GOD WE BOTH ADORE)
(AND MY CHAMBER DOOR)
==============
(LEAVE NO BLACK PLUME AS A DEMONS THAT SHADOW ON THE RAVEN NEVERMORE)
(AND HIS SHADOW ON THE RAVEN NEVER FLITTING STILL IS DREAMING)
(AND THE LAMP-LIGHT O ER HIM STREAMING THROWS HIS SHADOW ON THE RAVEN NEVERMORE)
(BE THAT LIE THY BEAK FROM OFF MY CHAMBER DOOR)
(AND THE LAMP-LIGHT O ER HIM STREAMING THROWS HIS SHADOW ON THE NIGHTS PLUTONIAN SHORE)
(AND THE RAVEN NEVERMORE)
==============
(ON THE PALLID BUST OF PALLAS JUST ABOVE MY CHAMBER DOOR)
(AND THE RAVEN NEVER FLITTING STILL IS SITTING STILL IS SITTING)
(AND HIS SHADOW ON THE SEEMING OF PALLAS JUST ABOVE MY CHAMBER DOOR)
(AND HIS EYES HAVE ALL THE SEEMING OF A DEMONS THAT IS DREAMING)
(AND THE PALLID BUST OF A DEMONS THAT LIES FLOATING ON THE FLOOR)
(SHALL BE LIFTED NEVERMORE)`

# NP Complete 3rd Grade Math Problems

Tags

Leo’s third grade class got to try a Noyce Foundation math worksheet [1] the other day. They didn’t fare so well, but I gotta tell you, some of the problems are REALLY hard! In fact, one of them is NP-Hard! Now, I’m sure that there must be a trick to this problem, but I wasn’t able to see it in the couple of minutes that I thought about it. In fact, Leo even recognized that it’s NP-Hard; He told me the day of the quiz that they had given out an NP-Complete problem! (In fact, if you look closely at the page, you’ll see that he wrote “NP Compleite” (Sic 🙂 ) diagonally across the picture:

One of the things I’ve told my students over the years, only half jokingly, is that computer scientists are fundamentally lazy; Why should we work when we can get a computer to work for us?! Since I couldn’t figure out off the top of my head how to solve this problem without trying all possible combinations (and god help you if you allow repeats!), Leo and I set about writing a program to solve it for us.

Without going into great detail, here’s the code:

*Items* is the list of items as pairs, as: (name . price):

The only interesting function here is the combs function, and that’s the only one that I bothered to work through in detail with Leo. We first set out the recurrence on the board (bottom to top, excluding the top line, which is the input):

Leo got the recurrence pattern right away, although I, of course, had to help him put it into Lisp. (Compare with his Snuffycode version, below.)

Of course, first making a huge list of all possible combinations, and then scoring each one, is extremely space-inefficient. A depth first search would be better, but making all the combinations first is conceptually simpler.

Anyway, space-wasting aside, calling it (via seek\$) results in 279 non-redundant solutions.

Here are the first few:

We also found the shortest and longest solutions (shortest was 7 — the reduce…mapcar got cropped out of the screencap):

After all this was done, Leo wanted to write the program in “Snuffycode”, his own private programming language (for which, thank goodness, neither a compiler or interpreter exists):

Note that this code uses a different search method, counting up to 2^20, and using binary expansion to select the item list. Snuffycode, being a bit like APL, has implicit type conversion (L=N), operators that select a subset of an array when the array index is represented in binary (A[L]), and an operator that sums up arrays (/ \). 🙂

By the way, Leo says that some kids actually solved the problem exactly, so there may be a trick that wasn’t obvious to Leo or me, or maybe they just got lucky. It seems to me that there must be a trick, because if you’re only looking for 1 solution in 279 out of 2^20, that’s about a 1 in 3000+ chance of finding it by luck. (The problem might be easier is you allow redundant solutions. Although that makes for many more possible solutions if you were brute-forcing it (technically, an infinite number! … although you could apply a sensible limit), you maybe could do some sort of stacking up to a target that you can then fill in….or some such algorithm.

Like I said at the outset, it’s not worth thinking deeply about such a small problem; That’s why we invented computers!

By the way, the problems in the Noyce set were supposedly in difficulty order, and this was only the second of five problems! I solved the third one using straightforward algebra (although apparently some of Leo’s classmates solved it by brute force — remember, these are THIRD GRADERS!). The fourth required slightly more complex algebra.

The fifth problem was extremely easy, if you know anything about probability.

Go figure…

[1] Unfortunately, I think that the Noyce Foundation has ceased operations.