# 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.

# The Dragon Box Algebra Teaching Game

Tags

Over the past couple of weeks, Leo and I have worked through the entire Dragon Box Algebra 12+ app. Dragon Box builds a series of gamified math apps. I can’t speak to any of the others, but Algebra 12+ (hereafter, DBA12+) is about as fun as I could imagine making Algebra, unless, like me, you think that Algebra is just inherently fun on its own! Unfortunately, DBA12+ has, to my mind, some significant flaws.

Note that Leo is only 8 (closer to 9), and I’m not sure what the “12+” means — probably target age — so I hadn’t expected the thing to be self-usable by an 8/9 year old. So Leo and I worked every problem together, although I tried to do my best hands-off scaffolding by only intervening when he was absolutely stuck — although sometimes I was absolutely stuck as well! Another thing that I did was to provide running commentary, giving names, and sometimes explanations, to back up the algebraic concepts being demonstrated, or those he was employing in play. In  my parent-child interaction research we called this “active language”, and we hypothesized that this matters…a lot! I’ll back to this below.

First some of the great things about the game. The central conceit and motivation is well designed and fun: You are feeding a creature in a box to make it grow from an egg into a big scary (in a fun-scary sense) creature. (The box is your algebraic unknown — generally “X”, as will be eventually revealed.) The artwork is great, and the goal is motivating (at least to an 8/9 year old). The moldularization and “leveling up” of the algebra content is well done too. There are around 10 major levels, each with 20 problems. New capabilities, like factoring, are introduced usually at the major level breaks, and new equation-level structural complexities are introduced within levels. This works extremely well, and the problems are extremely well designed to very rapidly bring together and reinforce previously learned capabilities into more and more complex problems without being either boringly redundant, nor taking too large steps. Leo (sometimes with my help around the edges) was able to “solve” pretty much every problem, although the latter problems sometimes took a lot of exploration — sometimes blind trial-and-error.

One thing that DBA12+ does that is, one the one hand very clever, but on the other hand somewhat annoying, is to begin with entirely non-mathematical symbols, specifically, pictures of funny creatures, and then as you level up, it introduces more and more mathematical notation. Sometimes this works, and sometimes it doesn’t. I think that the creatures are supposed to represent symbols that you might see in an algebraic expression, like A, B, M, N, and Y, and the box is always definitely X. But soon enough numbers are introduced (as dice-sides, initially, as with dots, and eventually as numbers), but there are operations that work on numbers that don’t work on symbols, like factoring, so you sort of have to figure this out by trial and error, because the animals could just as easily have been representing numbers!

There are some unfortunate quirks imposed by a combination of the gamification and the requirements of the leveling-up educational sequencing. For example, until very late in the game you are only allowed to add/subtract/multiply/divide through by “reified” terms that it offers you at the bottom of the screen. This blocks some paths that would make sense (to me at least), and which would potentially provide simpler solutions. In the next-to-last level of the whole game you are given an operator that will make (almost) any term in the current equation into a “reified” term, and at that point you can do what I we were reaching for throughout the game to that point!

Another pretty painful aspect of DBA12+ is that although there is a “help” button, it only gives you the complete solution, not hints nor steps that you might consider. So if you’re in the middle of a solution, it’s not smart enough to give you a hint from where you are; You just have to follow it back to its one-and-only-one “correct” solution. (Their solutions are actually often more complex than necessary. In about a quarter of the cases we were able to find solutions that are shorter than theirs!)

One significant problem is that what DBA12+ counts as a “correct” solution is sometimes a bit hard to fathom. A target number of steps is given for solving the problem, and if you go over those, you don’t get “full credit” (three stars). This has the positive effect of tending against “random” solutions where you just keep moving things around until you get something, but it also tends against a very useful strategy, which is to simply move things around until you get a solution, then you’ll know what the solution is, and can start over and work on a more efficient path. Like many games, once you “try”, where you are correct or not, the solution vanishes into the next problem, so you don’t really get a chance to think about your solution. There’s actually no way to think about your solution, because there’s no way to review it. This would be a nice addition: A way to look at the steps you took to get to wherever you find yourself, whether right, wrong, or in the middle of the solution.

Another aspect of DBA12+’s obscurity with regard to “correct” solutions is there there are certain forms that it is expecting as “the correct answer”, and others that are formally correct (because, of course, you’re only allowed to correctly apply algebraic rules), but which are somehow, to DBA12+’s mind, not simplified enough … or something. Because there are no words in the thing, except for the work “Yuk”, when it doesn’t like your solution, it can’t explain to you why it doesn’t like certain solutions. So you are sometimes — quite often, in fact — left guessing as to what it didn’t like about your solution, and just trying different things randomly to try to get to a solution it likes. In a similar vein, when there just a singleton box left on either side of the equation, it considered you to have completed the problem, and tries to “eat” everything on the other side, like it or not! I would have preferred, for all of the above, a button called “Try” (or somesuch name or appropriate icon) which, when pressed, the dragon comes out of the box and tries your solution, and if it doesn’t like it, you get to continue working, or back out, etc. And it would be great if, when it didn’t like something you left it, it told you why.

This leads me to my main criticism of DBA12+, which is that there are no explanations at all at any time, no explanations of why it doesn’t like you solution, and no naming of operations. To my mind, this significantly diminishes the educational utility of the product. If I was designing this app, as new operations were introduced, I would provide “active language”, giving names to the operations, as I was over Leo’s shoulder, like factoring, dividing or multiplying through, and so forth. And I would explain the constraints on when you can and can’t do these in terms that made sense to him in the context, using the vocabulary we had built up. Unless you have someone who knows Algebra pretty well sitting over your shoulder, there’s just no way you can make sense of some of the constraints that are either inherent in algebra itself (like that you can’t add fractions that don’t have a common denominator), or those imposed by DBA12+, like you can only do integer arithmetic, and can only factor certain things and not others, or those leading it to disliking certain solutions that it simply thinks are “Yuk”y. If, when new capabilities are introduced it would give them names, like factoring or distribution, and then these were maybe flashed on the screen whenever you used them, it would enable so much more depth of understanding of what’s going on. For example, you might be able to tell that factoring a common term out of a parenthesized expression is closely related to factoring a number, or that the “through” operations (dividing through, etc.) are related in terms of their application across all the terms. It could also use these terms in hints (e.g., “Maybe consider factoring?”), and in explanations for Yukky (Yuky?) results (e.g., “This isn’t in its simplest form!”)

After we went through the whole game, I had the opportunity to test Leo’s understanding of algebra in a natural experiment that happened to arise when we were talking about the earth’s polar regions. He asked why “they chose” -40 to be the same in Fahrenheit and Centigrade” (His hypothesis was that the folks who invented temperature, or perhaps just centigrade, lived in a polar region! 🙂 ) Aha! A perfect opportunity for some algebra! (The benighted reader can easily work this out for him or herself by taking the equation: C=5/9(F-32), or whatever version of that you like, asserting the fixed point: C=5/9(C-32), and then solving for C!) I used the DBA12+ conceit by making the C into a box, and asking him to solve the equation, just like in DBA12+. There are, of course, many paths to get to C=-40, but the DBA12+ way, where you can only do integer arithmetic, and can’t distribute composite terms (like 5/9) is to start from C=(5(C-32))/9, multiply through by 9, yielding 9C=5(C-32), distribute the 5 to get 9C=5C-(5*32), isolate: 9C-5C=-(5*32), do the math (on both sides): 4C=-(160), simplify out the minus sign (could be done earlier, or by distribution, or just drop the parens): 4C=-160, and then divide through by 4 to get just C=-40.

Notice how nice it is to express this solution path in a combination of words and symbols, and how if we were going to have a conversation about it, we’d be diminished to grunting and pointing if we didn’t have names for things! Active Language provides these names and ways of speaking about activity, and through this process forms the foundation for reasoning.Human language is possibly our only unique feature, and it is probably the most ennobling and enabling!  Unfortunately, by trying to force absolutely everything into gestures, DBA12+, and similar “educational” games, diminishes their topic, algebra in this case, to mere grunting and pointing.

# Portal Physics

Tags

Elsewhere I’ve briefly written about Leo’s obsession with Portal, a clever, (mostly) non-violent, Steam game. As always, I try to turn his obsessions into lessons (I should trademark that!) and so it is with Portal. In another post I talked about the game’s clever “AIs” (scare-quoted because, of course, they are merely scripted, not real AIs!) Here I talk about a cool little physics lesson that we recently did using Portal.

One of the really fun and clever things that you can do with portals is to put an In-Portal in a floor, and an Out-Portal in a wall, and then drop something into the In-Portal and it’ll come out of the wall. If you drop it from a distance into the In, it’ll blow out the Out with what we shall hypothesize is the same horizontal velocity at which is hit the In in the floor.(Watch this happen quite dramatically at about 4:40 in this video.)

This can be quickly turned into an interesting physics question: How high do I have to jump from such that I go a specified distance across the room? Here’s the setup (I’ve redrawn all this because we initially did it on a white board, and between erasures and scribbling, the white board is entirely incomprehensible!)

A box is dropped (or a person jumps!) from the tube at the top left at a height of Hf, and accelerates (presumably at 9.8m/s^2), hitting the In portal (the circle at the bottom left) with Vf. It instantaneously blows out of the Out portal (the circle on the wall in the middle left of the picture, at a height of Hp) with the same velocity, Vf and immediately begins to fall, eventually hitting the floor and stopping at distance D. (We neglect a lots of the usual things like rolling along the floor, air resistance, and that the box isn’t a point mass.)

The question is: How high to I need to put the Out portal (Hp), if the drop point (Hf) is, say, 20 meters high, and I want the box to land (D) at, say, 20meters from the left wall?

Notice that there are three equations involved here [all equations from this wikipedia page, or any of the other zillion pages that have the same info]: For the drop we can compute Vf from Hf (20m) (given g=9.8m/s^2). But in order to figure out how far it’s going to go to the right after coming out of the wall need to compute for how LONG (i.e., t in secs) we want it to travel in order to hit the ground in D (20m), and then back-compute the high (Hp) given how long we want it to be in the air before hitting the ground.

Okay so $V_f=V_0+{\sqrt{2gH_f}}$ [Since the drop is static, $V_0=0$.] We’ll round 9.8 to 10m/s^2, so $V_f={\sqrt{20*10*20}}={\sqrt{20^2}}$, which, coincidentally, is really easy to calculate: Vf=20m/s.

Okay, now at 20m/s going 20m upon exit from the Out portal, leads to the sort of trivial use of $t=D/V_f=20/20$, which is exactly 1 sec. (I actually didn’t make these numbers up to come out so nicely!)

Finally, we need to figure out how far something will fall in 1 second, which is just $1/2*g*t^2$, where t=1, and g=10, as above, so $H_p=1/2*10*1 = 5$ meters. So, we have to put the (center of the) portal 5 meters up the left wall.

By a little algebra we can reduce these three equations:

$V_f={\sqrt{2gH_f}}$
$t=D/V_f$
$H_p=1/2*g*t^2$

into one:

$H_p={gD}/({2\sqrt{2gH_f}})$

I’ll update this post with a screen cap from Leo’s actually implementing this so check it out (spoiler alter: it worked out pretty well!)

[By the way, there are many quite clever videos where people work out aspects of the physics of Portal, as well as many funny thought experiments about what could happen if portals were real!]

# 8-year-old Kid v. 45-year-old Pseudo AI

Tags

I’ve variously been on again off again regarding computer/video games. Early on I had this fantasy concept that Leo would only be allowed to play computer games that he programmed himself, and that held for a little while, during which time we created some interesting, although laughably poor, games on the HopScotch platform. Since then we’ve engaged in several rounds of brief run-ins with puzzle games such as Where’s My Water and Monument Valley, and a couple others. We finally came to a mutual landing on Minecraft, which is at least slightly creative, and has a lot of programming and math_ed potential. Still, his media (including games) time is quite limited.

Another game that Leo has become enamored with (within the tight content and time controls that we put on him) is Portal, which is an extremely clever puzzle game with amazing graphics. (It has a tiny bit of robot violence, but is generally just a clever puzzle.) One of the best parts of Portal is that your adventure through the “lab” is narrated by an AI companion, named Glados (in Portal 2 it’s Wheatley). There some kind of complex back story, where Glados was a person uploaded into a computer, but Wheatley is a fully self-conscious AI. Of course, what these “AI”s say is completely canned, but it’s also (sometimes) clever and (often) funny.

Somewhat to my surprise, Leo’s interest in the games, combined with the (sometimes/often) clever/funny commentaries from the companion (pseudo) “AI”s has gotten Leo interested in AI more generally. Yesterday, Leo was monkeying with the Chegg flashcard app on my phone (for no reason other than wasting time on a long car ride), and, unbidden, he created some AI flashcards:

I have a bit of personal history with this sort of AI, having been the author (many many year ago — like, 1973!) of a BASIC version of Eliza that ran in very early PCs, and so became extremely popular. Indeed, I’ll bet that my Eliza is about the most knocked-off (as in copied/modified) program on the planet!

I happen to have a copy of Peter Schorn’s iAltair on my iPhone that coincidentally comes with a close knock-off of my actual old BASIC Eliza! So, since Leo is interested, having done the AI flash cards, I put him on my Eliza, now, um, 2018-1973=45 years later!

Here’s their conversation:

A while back we did a little toe-in-the-water experiment, using Lisp to write (bad) poetry. So, next week we’re going to start writing our own AI!

# Car Physics Revisted

Tags

Long long time ago (actually, only back in 2015) we tracked a short road trip and manually computed and plotted the Time/Distance/Velocity/Acceleration. I’ve been wanting to revisit that fun little experiment, and this past weekend we had the opportunity on a 60-mile trip. Leo recorded our distance from start every five miles. This time, instead of manually plotting (which he does a lot of in school), I started him on Excel, which is certainly how he’ll be doing this once he gets beyond 3rd…or maybe 5th grade!

Here’re the results (you can see the master by clicking the pic):

The valley in the middle of the trip is where we stopped for lunch and turned around. And, yes, we really did travel exactly 60 miles, although that wasn’t planned!

# Calculus Craft

Tags

Okay, so I’m a little slow! I’ve been working my way toward calculus with Leo for a long time. We’ve explored a great deal among the preliminaries, such as algebra, geometry, and trig, done a little “real life calculus” using cars and rockets, and I’ve even left various fun “calculus coloring books” around, which he’s picked up and variously paged through. We’ve even done some Minecraft-math before that verges on calculus. But until today I hadn’t really broached any real calculus.

Today it hit me that Minecraft provides a perfect setting to discuss integration via Riemann Sums (which most of you will remember as the method of rectangles). The reason is obvious: In Minecraft you (generally) only have rectangles, so if you want to know the area under something — say the roof of semi-circular building — you don’t have any choice but to build the thing out of blocks. Therefore, the actual area is actually most conveniently measured in terms of piles of blocks, i.e., rectangles, i.e., the basis of the Reimann Sums!

Once I realized this it took only a couple of minutes to come up with some easy examples. To you and me, this just looks like simple intro calculus, but the “patter” — the story I was telling all the way through — is all about Minecraft!

Next I explored the idea that if the blocks were smaller, the approximation would get better and better. Conveniently, the Minecraft blocks are 16-units wide, so you can divide them in half four times and still be working with integers, making it easy to actually work the detailed math.

What’s most interesting about this is that because of Leo’s facility with Minecraft, once he had his Minecraft thinking cap on (which, once on, is extremely hard to get off!), he was able to see right away how the simple version of the rectangle-based integration worked, and was also able to easily think through (approximately) how things would go if the blocks were divided in half, and then half again and again and again!

In the last example (second half of the page) Leo worked the Integral[X^2] by rectangles while I worked it by the usual (X^(N+1))/(N+1) method. (I had to help him a little with his.) And we both got about 42, which is about right! (Actually, it’s 125/3 = 41.666…)

I think that this (somewhat “duh”) realization of the relationship between Minecraft and Calculus has opened up our whole next level of math fun!

# Magic v. The Machines: Septimus Heap, Hyper-Literal AI, and Public Key Encryption

Tags

For a long time, now, Leo and I have been listening to audio books of long Fantasy and Steam Punk series, and at some point I’ll write a post — or probably several — about our responses to these, as there’s a lot to say. But occasionally we are able to make a contained and useful lesson out of some tidbit in these series. For example, the wonderful Leviathan series by Scott Westerfeld offers many opportunities ranging from discussion of evolutionary theory to the inventions of Nikola Tesla.

One of the ongoing issues that Leo and I discuss around these various series is the difference between fantasy and science fiction (or steam punk, which is what we tend toward). This is, of course, not a simple question, and the answer is probably as philosophical as it is problematic, so I’m not going to offer any deep theory of it here. But only of the things that is more-or-less clear is that in fantasy you can just make things up, that have no bearing at all to possible physical reality, whereas in SciFi/steam punk, there is generally some plausible way in which at least most of the things that play a role in the story could have some plausible reality in our real universe. So, in fantasy you find magic, whereas in SciFi you get machines. Whether the machines are really plausible is debatable — sometimes they’re time machines, for example! But at least there’s no explicit magic in SciFi. SciFi sort of has to follow the rules, whereas fantasy came just make up magic. In fact, this is one of the problems with fantasy: If you can make up random magic, why can’t you just make up magic that solves whatever problem you have. Fantasy writers end up creating endless random constraints on their magic in order to keep the story interesting. (“You can only use the magical Time Turner twice on Tuesdays between the hours of 3 and 4 pm when the moon is blue.” … or whatever …)

The opposite direction is less constrained; You often find steam-punky-quasi-machines in fantasy: Doors with special complex locks seem to be a favorite, with special keys scattered all about. The series that we’re listening to at the moment is the extremely long, but wonderfully written Septimus Heap series, by Annie Sage (hereafter SH).

There are many interesting things about this series (and about all of the series that we’ve been reading and/or hearing), but I just want to draw out two small details in SH that struck me as particularly interesting and funny, in a somewhat STEM-educational sense.

Hyper-Literal AI Self-Driving Sled Gone Wrong

The climax of the 5th book in the SH series, Syren, turns on a bunch of under-sea tunnels, called “ice tunnels”. It’s not giving away too much to tell you that in order for our heroes to get through these tunnels fast, they utilize a magical sled, which they can call remotely, and which is some sort of AI that they can tell where to go within the ice tunnels. At one point our heroes call the sled, which shows up (just in time, of course!) and upon climbing aboard, they tell the sled to “Head for the nearest hatch!” The sled takes off at a shot, but in the wrong direction! Too late they realize that what they should have said is: “Head for the nearest hatch in the castle!” The literally nearest hatch is in the opposite direction!

Public Key Encryption Saves (actually nearly loses) the Kingdom to the Dark Domain

The resolution 6th book of the SH series, Darke, turns on the decoding of a spell that will save everyone from some sort of magical evil, called the “Dark Domain”. The spell is protected by a complicated split key book cipher, with a few interesting properties. First, interesting property of the cipher is that each part lives on a circular disc — something akin to a DVD, but where you can read the “bits” off it with a strong magnifying glass. The circularity of the discs introduces an interesting problem, which they make a bit of in the story, which is that you don’t know where to start on a circular cipher! You could use the grammar of the language, or try all 49 (in this case) starting points, but Sage pulls out plausible escape clause that these are many hundred year old spells, and also that if you get it wrong you could do more harm than good. Hilarity ensues, and, of course, good triumphs over evil at the last possible moment.

(Another slightly funny aspect of this situation — if you’re 8 years old! — is that one of the halves of the split key had been eaten by one of the bad guys. The heroes had to get him to throw it up, and then utilize the disgust-covered disc! I guess it could have been worse! 💩 )

All this is very interesting (or perhaps not), but the point for the present is that Leo and I were able to use this imaginary cipher as a jumping off point for discussion of public key encryption, which is also a split key cipher, the details of which basically followed this excellent Numberphile video. (Numberphile, by the way, is a terrific video series on math … or as the Brits call it, “Maths”.)

# Bayes Rule for 8-year-olds

Tags

Leo has been fascinated for some time by the probabilities of things. He’s telling us all the time about the probability that, for example, the light will turn red before we get to it, or a meteor will destroy the earth tomorrow. Of course, he’s totally making up the numbers, although he does know that a probability lies between 0 and 1 (inclusive), and that when something can’t possibly happen, it’s p=0.0, and when it either is sure to  happen, or has already happened, it’s p=1.0 He also knows the general principle that p of n equally-likely events is 1/n, and he sort of gets the p of complex things generally in the right range. (For example, he puts the probability of the meteor at 0.0000…lots of zeros…and then a 1.)

Given that he’s fascinated by probabilities, my main principle of teaching, “Catch ’em while they’re interested!”, suggests taking this to the next level, so today we started into Bayesian probability updating. In order to do this, I had to devise a particularly simple example. Biomedical tests (a typical example) aren’t really gonna work for him. So I invented a little card game, that goes like this:

Take N ordered cards … I’ll start with 3 for these examples … so, say J Q K of the same suit. Could be 1 2 3, but I don’t want to get all confused with the numbers, so actually, I’m just gonna call them A B C. Shuffle them and lay them face down. Now, the question (hypothesis, in Bayesian terminology) is whether they have been laid out in order: ABC.  p(H) at this point is obviously 1/6 (could be any of ABC ACB BAC BCA CAB CBA) — this is our prior.

Okay, so we turn over the first card. In the easy case, it’s not an A. Intuitively, p(ABC|first<>A) should be zero, and indeed, if we use Bayes’ rule to compute p(first<>A|ABC) = 0, so the whole equation just obviously becomes zero, regardless of the other terms.

What? Oh, you’ve forgotten Bayes’ rule….Here you go:

p(H|D) = (p(H)*p(D|H))/p(D)

So, one more time, p(D|H) = p(ABC|first<>A) = 0, so regardless of the other numbers in the equation, the result is 0. (Assuming p(D) isn’t zero, which it never is in any real problem.)

Okay, now suppose first = A. What’s the “posterior”, that is the new p(ABC|first=A)? Now we have to ask about p(D) and p(D|H). p(D|H) = p(first=A|ABC) = 1 because it had to be an A if the hypothesis was true. Okay, so what’s p(D). Well, that’s just 1/3rd since there are three letters (ABC).

(You might be lured into thinking that P(D) is 1/2, since you’ve used up one of the letters (A), but that would be P(D|first=A), but at this stage we have all three letters. It’s common to confuse the order of explanation with the order of term evaluation in the equation! Just p(D) is unconditional at this stage, and is just the probability of the data given just the structural properties of the situation. At this stage that is all three letters, so 1/3, whereas at the next stage, it’ll be only two letters.)

Recall that p(H) was 1/6th (six possible sequences, as above).

So you end up with:

p(ABC|first=A) = (1/6 * 1)/(1/3) = 3/6 = 1/2

(Remember how to divide fractions? Invert and multiply!)

So there’s now a 1/2 = 0.5 = 50:50 chance that it’s the right sequence, i.e., ABC given that the first card is an A. That is: p(ABC|first=A)=0.5. This accords with intuition since there are now only two possible orders for the B and C cards.

Now, when we turn over the next card, and see that it’s B. At this stage, p(D) = 1/2 (only two possible letters!), and p(D|H) = 1, and the p(H) = 1/2 from the previous stage (that stage’s posterior is this stage’s prior!) = 1/2. (This could also be written p(D|first=A)). So we have p(ABC|first=A & second=B) = (1/2)/(1/2) = 2/2 = 1. Tada!

And, of course, if we’d turned over C here, again p(D|H) would be 0 and the whole thing would come to a crashing zero again, which, again, correctly accords with intuition!

It’s fun to go to very large numbers, which Leo also likes. That’s easy to do using cards by just asking exactly the same question as above, but using all 52 cards, that is, p(ABCDEF…). We know that, given a fair shuffle, this is very very very very small. (Here’s a terrific video about how very very very very small a given ordering from a shuffle really is!) I’ll call this “epsilon” (a number very very very very very close to zero!)

So in this case p(H) = epsilon (~=0), and p(D) = 1/52 the first time through.So although getting an Ace of Spades (assuming that’s what you are counting as the first ordered card) multiplies the probability 52 times, it’s still very very very very small, and will continue to be so for a very very very long time!

So, now I have to start engaging Leo when he generates random probabilities, for example of meteorites hitting the earth tomorrow, to reenforce his Bayesian thinking.

# The Young Lisper Meets Infinite Ravens

Tags

When I was a young lisper, of, say, 16 (which at the time was quite young, although these days would be considered quite old!), I read The Little Lisper (TLL). Of course, very few folks actually read TLL to learn Lisp; It’s mostly a curiosity among those who already know Lisp, or at least among quasi-adults trying to learn Lisp efficiently.

So usually, when one read TLL one usually actually just read through the whole book in one sitting, the whole exercise taking a whopping hour. When approached in this way, TLL seems a bit silly; After a couple pages, one says to oneself: “Oh come on! This is silly! Just give me a damned language manual!” (Indeed, I was one who said exactly these words, so I wrote my own!)

Now, however, I think that I — and pretty much everyone — was approaching TLL the wrong way. Obviously it’s not meant for those who know Lisp already. But I also don’t think that it’s meant for adults (or even quasi-adults) who want to learn Lisp efficiently. I contend that TLL is actually meant for CHILDREN (Soylent green is people!), or those of us who can put our mind in the mode of being a child, which I think is actually extremely difficult.

Brief aside: When you apply for at teaching job, they ask you to describe your “educational (or teaching) philosophy”. As one might expect, this is a difficult question, and I’m not going to try to give my whole teaching philosophy. But one of its pillars is this: You only get people’s (esp. children’s!) attention for a couple of minutes at a time, so be sure to do tiny fun things, and build them up over days, weeks, months, and years to reach where you want to go.

So when I decided that it was time for Leo to learn Lisp — specifically, when he turned 8, and was proficient at those “baby languages”, like scratch and hopscotch — I deployed my afore(partially)described teaching philosophy: I started with atoms, then lists, and so on, building up Lisp concepts and programming, no “lesson” consisting of more than about 10 minutes, and usually containing only one of a couple of concepts.

This worked exceptionally well with Leo (as you’ll see below). But just today, after a couple weeks at this, and now writing some actually vaguely-interesting programs, it just hit me that I was doing The Little Lisper ALMOST EXACTLY! Of course, wasn’t actually using TLL; rather, my teaching method enacted TLL! This is when the aforementioned realization that Soylent Green is… er… that TTL is written for children (or, again, more likely, adults with child-like minds — which probably describes Lispers of a certain age).

Okay, so this long winding dissertation is all by way of introducing Leo’s first substantial Lisp program, which we have called…

RANDOM-RAVEN

First we create two variables WORDS and PATTERNS:

(setf words '(
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
...))

(setf patterns '(
(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 the silken  sad  uncertain rustling of each purple curtain )
(Thrilled me filled me with fantastic terrors never felt before  )
(    So that now  to still the beating of my heart  I stood repeating )
(     Tis some visitor entreating entrance at my chamber door  )
(Some late visitor entreating entrance at my chamber door   )
(            This it is and nothing more  )
()
...))

(Yeah, yeah, we could have computed words from patterns…cut the 8 year old a break! He’s only been doing Lisp for about an hour total, over a couple weeks!)

Okay, so you can see where this is going:

(defun random-raven (w p)
(loop for line in p
do (print (loop for word in line
collect (nth (random (length w)) w)))))

Et voila!

(MANY THIS WORD THING HORROR OF ITS ER ME MAIDEN LENORE)
(MORE NIGHT IS OF RELEVANCY SAD CHAMBER IS TOKEN WORD)
(NEVERMORE AS LENORE BUT I NEVERMORE ANSWER WHEN VOLUME YOUR)
(ENCHANTED TUFTED NOTHING WITH SAID AND DOUBTING SURE MORE SILENCE BURNED)
(JUST BE AT SO EYES NOTHING DECORUM A BEFORE MY)
(WAS THY A NEVERMORE IF)
NIL
(TAKE BEFORE SURELY BACK NEVERMORE US HATH SOUL LORE BUT)
(OF JUST ONE THAT TIS I WITH A FOLLOWED WHEELED THE)
(LENORE PERCHED RAPPING OF CORE THE VELVET FOWL PERCHED MARVELLED WHISPERED)
(THEN THE AND THEREAT NEVERMORE NOTHING RADIANT FLOOR UNCERTAIN DEVIL I)
(SO WAS A RECLINING WAS MY SEE SINKING AND NOW OF)
(LET BUT AND LENORE)
NIL
(YET MYSELF SMILING THOU PALLAS YORE BIRD MY OH ANCIENT)
(MORROW TELL HEART DECEMBER RAVEN O THIS VELVET DIVINING OF)
(FOR STILL I MIDNIGHT STILL HAUNTED SOME THAT TAPPING THE STILL NAME BETOOK)
(CUSHIONED PALLID OBEISANCE EAGERLY I ITS I SYLLABLE DOOR)
(SAT AND THAN BIRD THE WITH FRONT TUFTED UNCERTAIN)
(FLUNG MY ONE EVIL SUDDENLY HUMAN)
...

And so on! If read with the correct Vincent Price horror movie voice and prosodics, this stuff sounds both great and hysterically funny!

Next week… Eliza?! 🙂

# Leo and Jeff’s Zillion Notations

Tags

In other posts I’ve talked about Leo being fascinated by giant numbers, and a while back, based on his interest, I proposed a joke number called 11Z, called “eleventy zillion”. Today we put some specific mathematical meat on this notation, in two different ways, which we agreed to call “Leo Numbers” v. “Jeff Numbers”.

Jeff’s Z Numbers:

Both are based on Jeff’s Numbers, which is the following exponentiation ladder:

nZ = n^n^n^n… n times.

For example:

3Z = 3^3^3

Now, there is immediately a problem, which is which way to evaluate the ladder.

Does 3Z = (3^3)^3 = 27^3 = 19,683, or is it = 3^(3^3) = 3^27 = 7,625,597,484,987

I think that the mathematical default if left-to-right, i.e., up the ladder, but I hate these defaults because they aren’t explicit, so I prefer to have an explicit notion telling you which way to evaluate the ladder.

So to clarify this, we use arrows as:

3Z→ = (3^3)^3 = 27^3 = 19,683– called “3 zillion up”

3Z← = 3^(3^3) = 3^27 = 7,625,597,484,987 — called “three zillion down”

Now, Leo, who like scientific notation and thinks in terms of Googol and Googolplex, thinks of Z notion slightly differently.

Leo’s Z Numbers:

3Z→ = 3e19,683

and

3Z← = 3e7,625,597,484,987

So, just as Z-down notation is way bigger than Z-up notation, Leo numbers are way bigger than Jeff numbers!