davidbau.com

Python pi.py Spigot

Here is pi.py (not to be confused with pypy), a short python implementation of Jeremy Gibbons's 2005 spigot generator for decimal digits of pi:

def pi_decimal_digits():
  q, r, t, j = 1, 180, 60, 2
  while True:
    u, y = 3*(3*j+1)*(3*j+2), (q*(27*j-12)+5*r)//(5*t)
    yield y
    q, r, t, j = 10*q*j*(2*j-1), 10*u*(q*(5*j-2)+r-y*t), t*u, j+1

The code to drive the algorithm is longer than the algorithm:

count, digits = 0, pi_decimal_digits()
while 1:
  print '%6d: %s' % (
    count, ''.join([str(digits.next()) for j in xrange(50)]))
  count += 50

This little script can be quite handy if, for example, you want to look up where in the digits of pi you can find the phone number for the Mass Audubon Society that is down the road from my house:

> ./pi.py | grep --color 2599661
  3050: 56638937787083039069792077346722182562599661501421

Conveniently, their phone number starts at the very visible 3087th digit of pi after the decimal point. My home phone number is a little bit further into the private section the pi phone book, at the 6,301,261th digit. And, if you must, you can reach me at my cell at the 22,000,091th digit, although I should warn you that my reception is not very good out here in the boonies.

Happy pi day.

Collected Hacks

Here is a list of the programming hacks that have appeared in this blog in the last few years.

Most still work.

Minimum Hint Sudoku Hunt

The smallest number of hints that have been discovered in a Sudoku puzzle with a unique solution is 17. Nobody knows if there are any fully-determined Sudoku puzzles with 16 hints. Gordon Royle maintains a comprehensive list of the (currently) 49151 17-hint Sudoku puzzles that have been discovered. This list has grown over time, but nobody knows how incomplete this list might be.

The Sudoku Hint Machine now has two new features to help play with 17-hint puzzles:

1. If you press the "Min Puzzle" button at the bottom, a random 17-hint puzzle (permuted and shuffled) from Gordon Royle's list will be chosen and shown (code here).
2. If, while manually editing a puzzle, you arrive at a fully-constrained puzzle that is 17 hints or less, exclamation points will appear in a button at the bottom, and you can submit your puzzle to Gordon's list to see if it is a newly discovered minimum puzzle or not.

Note that an easy technique to discover other small-hint sudokus is to go into the hint machine with a 17-hint sudoku, solve a few extra squares, and then click on "Make Puzzle". The hint machine will subtract squares until the puzzle is minimal again, and it can often get back down to a different 17 squares.

If you find one that is 16 or fewer, definitely submit it to Gordon Royle's list. It will be the first one ever.

There is Brilliance in this Language

Douglas Crockford, speaking about Javascript, explains why the vilified language is actually full of brilliant features and has "much more expressive power than the classical system." He also gives an entertaining view of the history of web programming, which roughly traces the timeline of my personal experience, from HyperCard to NCSA to Netscape to IE to Google.

Worth a watch. (mp4 wmv other)

I have been thinking that Javascript is really the right first programming language for kids to learn. I might give it a try with a little group of kids this spring. Any advice?

The Next Grand Deception

A few of my colleagues sat around Friday trying to guess which company or industry would be exposed as the next Ponzi scheme or bubble. We have suffered through Worldcom and Enron and Lehman, AIG, B of A, and Citibank.

In each of those cases, we saw the same pattern.

• The whole world thought they were geniuses, and they believed it too.
• Even adversaries in the marketplace and regulators were dazzled.
• In each case there was a conceit: "We play by a new set of rules."
• The "new rules" turned out to be finite, not sustainable; like a Ponzi scheme.
• Problems were obvious in retrospect: we all suffered from willful blindness.

In some cases there was outright fraud; in other cases there was just a lot of self-deception, but despite the particulars and differences, there was actually a lot of commonality behind all of these cases.

Can we find the Next Grand Deception before the bubble pops?

Making a Time Machine

Piper has created a machine that reverses the arrow of time, and you can make one too (video). Her novel setup stubbornly defies the second law of thermodynamics at large scales.

At steady state the material in her device is not in stasis. We are used to seeing matter in familiar static phases: solids, liquids, gases; supercritical fluids, degenerate gases, plasmas, even Bose-Einstein condensates. When viewed at macroscopic scale, all these materials sit still. Liquid will flow into a puddle, gas will expand to fill its box, solids will slump. But in a few moments ordinary matter will find its steady-state configuration, and then it will sit unmoving.

But Piper's contained mixture does something new. It does not fill its box. It does not stay still.

Handheld Glasses-Free 3D

Alan Kay, famously:

People who are really serious about software should make their own hardware.

Yesterday Nintendo announced a clever new version of the DS, rumored to use Sharp 3d Parallax LCD display technology for glasses-free 3D. This type of 3D is only effective if you are looking at the screen from a particular spot. Just perfect for the handheld DS, isn't it.

The neat thing about Sharp's display is that it can flip from 3d mode to 2d mode by electronically removing the parallax screen layer. So users don't have to fight with the fiddly 3d display when they're just reading text on the device: software can switch on 3d mode when it's appropriate. The innovation comes from Sharp's European lab in Oxford, which published the work in this 1999 paper, this 2000 paper, and this 2003 whitepaper.

Sharp tried to sell their own laptop with their 3d display in 2003. It was a commercial flop. For software Sharp bundled the snoozer "Sharp Smart Stereo Photo Editor," and a third-party "TriDef Movie Player."

This suggests an ancillary principle to Kay's law:

People who are really serious about hardware should not make their own software.

Sharp's display will be awesome with Mario. Go Nintendo.

Tutorial: Fifteen Puzzle

I am trying to come up with elementary yet modern javascript examples for teaching middle-schoolers. Here is one idea:

The 68-line html file fifteen-puzzle.html contains 12 lines of javascript to implement the classic puzzle. By looking at and editing the source code I am hoping kids can learn several things all at once:

• The nested structure of HTML tags, and tables.
• CSS and CSS selectors.
• Jquery selectors and jquery event handlers.
• Javascript itself.

Also, hopefully it's enough of a program that it is actually fun to fiddle with. The program isn't really done - you'd want to add a "you win!" feature and other things. Or make a 3x3 version or whatever you like.

Too steep for first exposure to programming? My idea here is "plumbing first." When I learned to program on the Atari 800, I learned all about joystick movement and flashing colors before I learned about nested loops.

Ideas for any simpler examples to start with first?

Tutorial: Ten Followers

OK, based on comments from Cezar and MichaelW and DavidMay and my kids at home, here is another idea for a javascript tutorial for middle-school kids, with a bit more cowbell.

The program ten-followers.html is another 60-line program that does a simple animation on the screen following the mouse. (view-source)

It uses the excellent Raphael library to simplify use of SVG.

$('body').mousemove(function(event) {
  for (var j = 0; j < circles.length; ++j) {
    var c = circles[j];
    var d = distance(c.attr('cx'), c.attr('cy'),
                     event.pageX, event.pageY);
    c.animate({cx: event.pageX, cy: event.pageY}, d * j * 2);
  }
});

Tutorial: Guess My Number

Continuing the Javascript tutorial series. The guess-my-number.html program is truly a straightforward example of 1978 programming style, with an interactive prompt that blocks the program flow to have the user guess a secret number. (view source)

Not very modern, but a classic first program. Javascript certainly permits this style.

Any other ideas? What other "good first programs" are there?

I feel like I'm looking for some intersection between "what is understandable" to a sixth grader and "what is cool" to the same set.