Kendall Stories

Lala and Sing acting out an argument.

Here are some web animations I made for my daughter.  One day she asked me to cut a hole out of a cardboard box so she could use it as a TV.  She then made three "shows", and for each one she drew scenes on several sheets of paper.  To present the shows, she would hold the paper up to the hole in the box while the rest of us sat on the other side and watched.

I thought it would be cute to turn her drawings into SVG images and animate them, and to record her voice and sync it up with the animation.  She really got into it, giving me very strict directorial instructions.  Part of the challenge for me was to try not to "improve" on her work with my own ideas.  I tried to stay as true to her vision for the shows as possible, and I included all of her mistakes (that she didn't catch in post-production and demand that I fix).

Not gonna what?

I used GreenSock GSAP's TweenMax library for the animations, and howler.js for audio.  Both are overpowered for this kind of project, but they saved time that I would have spent dealing with little headaches.  For instance you can't trigger HTML5 audio directly on mobile browsers.  I should have found a library for preloading and sizing images, because I ended up with some frustrating work making sure image sizes were loaded properly for IE.

Kendall Stories

Word Search Generator

Here's a quickly-slapped-together little project that generates word search puzzles.

I've been kicking around an idea for a kind of "evil" word search, in which there are tons of letter combinations that almost spell words, but don't.  The trick would be to see how distracting the almost-words are, and whether that makes the correctly-spelled words harder to find.  That's not what this one is, though.  This one is just a regular, non-evil word search generator.

The core generator code is at this githib repo, or on npm as @sbj42/word-search-generator.

Word Search Generator

Mr. Floppypants

Here's Mr. Floppypants.  A simple ragdoll-physics game.  Maybe it's about a very lazy person who needs to be forced to go explore and have fun.

It's based loosely on a "Chrome experiment" called Boingy, which the kids really got a kick out of.  I think they mostly liked dropping stuff on the poor protagonist, or forcing it to fall down stairs, or getting it twisted up into painful-looking poses.  After I played a bunch of MANYGOLF and through that learned about the p2.js javascript physics engine, I thought I'd make a more complicated version of my own.

It seems to work in Chome, Firefox, and Edge.  It does not work in IE.

Basically you click and drag to toss the guy around.  For more advanced play, if you click on his hand and drag it to something then he'll "grab" the thing.  You can use this to carry an item with you to some other part of the world, and to operate the car.

This game isn't nearly finished yet.  I was hoping to make the world a lot larger, and to add other characters to meet and also toss around.  If you get any ideas for things I could add to the game, let me know in the comments below.

Mr. Floppypants

Song: Coming Up for Air

I was trying to make some background music for It's EELectric!, but I failed.  I had various ideas, mostly working around an undersea theme.  I originally wanted something like the "Evan's Room" song from Legend of Zelda: Majora's Mask.  (digression: I always associated that song with being underwater because that's the context in which you hear it in the game, but I just learned from Zeldapedia that it's also the "Game Over" music from the original Legend of Zelda.)

Anyway after various ideas didn't seem to work, I settled on a sequence of 9th chords.  I expanded that into a more complete piece with a solemn, contemplative verse and a hopeful chorus.  Then I realized that it didn't at all fit the whimsical theme of the game for which I was writing it, and completely gave up on using it in that context.


Now I don't have anything to attach it to, so here it is by itself:

Coming Up for Air

Maze generators

I'm working on another game for the kids, called "Mr. Floppypants", of which I'll say no more in this article, except that I'm using node.js, and that for it I required some code to generate a maze.  For once not wanting to write my own code for that particular subfeature, I searched around npm for "maze generator" packages.  There were a few.

Watch out for bull-men!

I set about looking into each one in turn to see if it would suffice, but I discovered for each one a reason not to use it.  One of them simply didn't run, another used Ecmascript 6 (and so wouldn't work in some browsers without being transpiled), one only worked for square mazes, and some (and I admit I was a bit picky) just weren't written to my taste.  Maze generation is a fun little project, and it's natural that many people have made their own generators, in varying degrees of quality.  Yes, I gave up and wrote my own.

Here's what I learned about mazes... wait, no.  Instead let me point you at some much better sources of information:

Jamis Buck writes a mostly-programming blog, and wrote a great series on maze generators in 2010 and 2011.  This in-browser presentation sums up the whole maze generation concept very nicely, and this recap of the blog series is a great place to get more details.  He describes how to implement a handful of algorithms, and provides in-browser demos so you can watch the algorithm run.

Walter Pullen has such a variety of interests that I refuse to summarize his site, in one part of it you can find a very thorough maze generator program he wrote, and he has written extensively about maze generation.  Also I just can't keep myself from mentioning his extensive files about the movie Labyrinth.

Now you know everything about mazes.  But just in case you didn't spend hours reading through all that stuff, here are some highlights:

A maze is basically equivalent to a spanning tree of a graph based on a rectangular grid.  Consequently, algorithms that compute spanning trees can be adapted to make mazes.  Kruskal's algorithm is like this, and builds mazes in an seemingly magical way:  It connects random adjacent cells, taking care not to create a loop, until a maze basically appears out of the noise.

Speaking of Kruskal's, the hardest part is quickly deciding whether two adjacent cells are already connected.  It can be done with a disjoint-set forest, and the tricks they use to make that fast (union by rank and path compression) are neat.

One of the simplest algorithms, recursive-backtracking, is my pick for making the best-looking mazes.  While generators like Kruskal's tend to make lots of clustered dead-ends, recursive-backtracking prefers meandering passages.  It works as basically a randomized depth-first-search of the grid.

Eller's algorithm can generate the maze one entire row at a time.  It works by keeping track of which cells connected to the previous row have already been connected (possibly by an earlier, now forgotten row).  On the very last row, it patches up any not-yet-connected regions of the maze.  In doing so, it may end up with a long straight passage along the bottom.

The Aldous-Broder algorithm generates all possible mazes with equal probibility, but you probably don't want to use it because it's very slow.  It's interesting to think about though: Start in a random cell and perform the well-named  "drunkard's walk", digging a passage when (and only when) you walk into a cell you've never visited before.  Assuming you have enough patience, you'll eventually visit every cell and oh hey, there's a maze!

It's not a generator, but "dead end filler" is an amusing way to solve some mazes without ever visiting cells in the solution path.  Find all the dead ends in the maze and fill them in.  Then find any new dead ends you created, and fill those in too.  Repeat until there are no more dead ends.  The remaining unfilled spaces are the solution.

Back to my project:  I implemented three algorithms (recursive-backtracking, modified Prim's, and Kruskal's).  I also used this as an opportunity to learn about node and npm, so the algorithm packages also have unit tests, benchmarks, and demos, and I spent some time trying to optimize them for speed and also make them easy to plug in to another project without needing to bring a lot of dependencies along.

Demos of my maze generator algorithms

@sbj42/maze-generator npm package

Update (10/15): I added a maze "puzzle" to Probably Puzzles.
Update (6/17): Added a link to Mr. Floppypants

Generating Shikaku-like puzzles

A very small
Shikaku
in progress.

In my last post, I talked about adding Nonograms to Probably Puzzles.  Now let's talk Shikaku.

In Shikaku your task is to divide a grid into rectangular regions, such that every cell is assigned to a region, every region has exactly one number in it, and that number is the area of the region.

This one turned out to be harder to generate than Hidato, though maybe I haven't found the right algorithm.  The first step was to generate a random division of the grid into rectangles (i.e. to generate the solution).  I didn't find a good algorithm for that, so I made up a mediocre one:

1. Choose a random cell that isn't yet in a rectangle
2. Randomly decide on a major axis (horizontal or vertical)
3. See how far we can stretch from that cell along the major axis (e.g. for horizontal we see how many empty cells there are to the left and right)
4. Choose a random range from that span, with length no greater than 8
5. See how far a rectangle of that width can go along the minor axis
6. Choose a random range from that span, no longer than 8, where the rectangle's area is no bigger than 16
7. If we were able to pick a rectangle bigger than 1x1, then go back to 1 and repeat until all cells are consumed.
8. If not, then pick a random rectangle adjacent to the cell and remove it, then go back to 1.

That last step was the key to speed.  At first I had it just give up and start over if it hit an isolated cell, but it had to do a lot of resetting before it randomly ended up perfectly dividing the grid.  The last step allows it to make a small adjustment and try from there, rather than losing all the work it put into the earlier rectangles.

A grid, divided.

 This gives us a divided grid.  A solution in search of a problem.  So now we choose a random cell from each rectangle to use as the hint.  Here things get a little tricky.  To make sure there is only one unique solution for a given puzzle, we need to go ahead and solve it.

I wrote a brute force solver, but it was taking far too much time for puzzles of moderately-large size.  One trick I used to speed it up was to do a first pass on each hint, seeing how many possible rectangles could go there at the beginning of the puzzle.  Then we sort the hints from fewest to most possible rectangles, ensuring that we try all the "forced" ones first.

I suspect I can make the solver even faster if I resort at each decision in the solver tree, because placing one rectangle frequently reduces the number of options for another, and I find that for most of the Shikaku I'm generating, every rectangle is forced at some point or another, leaving the best kind of brute-force tree ever: a straight line to the solution.

There was another problem.  Too often the generator would put two 2x1 rectangles next to each other, and too often the hint-picker would select kitty-corner hints from those rectangles, giving the puzzle multiple solutions.

An ambiguous Shikaku.

When this happens, the solver takes longer to run, and in the end we have to throw all that work away because we won't accept a puzzle with multiple solutions.  So I threw in a pass to detect when this was happening and auto-correct it (by moving one of the hints).

That left me with a fast-enough generator and a not-so-fast-but-maybe-ok solver to verify the puzzles.

A generated Shikoku-like puzzle.

For the other puzzle types, I have a feature that allows you to adjust the "difficulty" of the puzzle, but so far I don't have that for Shikaku.  I could go by the number of choices made in the solver (which is what I did for Numbrix and Hidato), or I might even be able to use "number of initially-forced regions".  However I would need to speed up the solver before I attempted that.  At the highest grid-size setting, 15x15, it currently takes a while just to generate one puzzle, and if it started getting picky about difficulty it might take way too long.

Solving in progress.

The UI is pretty straightforward.  You click and drag to make rectangles.  It colors a rectangle red if it's invalid (i.e. if it contains no number, or more than one number, or doesn't have the right area for the number it contains).

Probably Puzzles

Generating Nonograms

In my last post, I discussed a generator for Numbrix-like puzzles.  Since then I've extended Probably Puzzles with three more puzzle types.

Hidato is very similar to Numbrix.  The only difference is that the path can move diagonally.  To get that I had to drop the Hamiltonian path generator I scrounged up, and replace it with one that generalizes to accept the diagonal connections.  The new path generator is based on this stackoverflow answer.  Hidato is interesting, the path can cross itself and that seems to lead to some surprises while I'm solving it.

Another puzzle type I added is Nonogram (a.k.a. "Paint by Numbers", "Griddler", and lots of other names).  This one is the most popular of the ones I've done so far (but will certainly drop to second place if I add Sudoku).  In this puzzle you color in the cells of a grid to draw a "picture".  There are numbers along the left and top of the grid which constrain which cells you can fill in.  They tell you how many sequences there are on each row and column, and the lengths of those sequences, but not exactly where those sequences go.

A randomly-generated 9x9 nonogram.

On the one hand, generating these is easier than Numbrix/Hidato.  We don't need to pick a subset of the hints that leaves the puzzle uniquely solvable, we just need to generate a picture.  The hints are determined directly from that.  On the other hand, how do we generate "a picture"?  I considered pulling from a library of images, or scattering various geometric shapes around, but I though it would be better for this particular site if the puzzles were completely random.  In the end, I decided to use simplex noise, which generates basically a bunch of random blobs.  At low difficulty, you get very big blobs, and a high likelihood that some rows or columns are completely determined by the hints.  At the highest difficulty, each cell is independently random, and it ensures that no rows or columns are completely determined.

Nonogram in progress.

For the play interface, I took some advice from my wife, who is an avid nonogram puzzler.  You left click to fill the cells, and right-click to place little dots in the cells which you can use as a reminder to yourself that you've decided that particular cell must be empty.

The third puzzle type I added was Shikaku, which I'll describe in the next post.

Probably Puzzles

Generating Numbrix-like Puzzles

Very tiny
Numbrix-like
 example.

We got the kids interested in a simple kind of logic puzzle called Numbrix.  I showed my son a multiplication table and he became obsessed for a time with filling out more and more tables with bigger and bigger numbers.  Since he seemed to like writing numbers into boxes, we looked around for a puzzle we could print off the web that he could do, and found some kids' Numbrix at this "Math in English" site.

Numbrix is apparently a puzzle published in Parade magazine, developed by Marilyn vos Savant, who had the Guinness Book of World Records "Highest IQ" in the late eighties and also a serendipitous surname.  The goal is to complete a Hamiltonian path on a grid with consecutive numbers.  If you've heard of Hidato, it's like that but you can't move diagonally.  The ones at Math in English seem to be randomly generated, but the ones made by vos Savant are cleverly constructed by hand.

Either way, there are a limited number of Numbrices at both places.  I haven't found anything that generates them "while u wait", so I set about writing some code to do that.

A randomly generated Numbrix-like puzzle.

The first step is to generate a random-ish Hamiltonian path.  With a little googling I came across this "HamPath" library, which does the trick well enough.  Next we need to take away random numbers until we have a puzzle we like.  The puzzle has to have a unique solution, so each time we take away a number we have to check to see if there's another solution, so we need a solver.  The solver just runs all the possibilities and stops early if it finds a second solution.

I wanted it to have a difficulty knob, so we need some kind of measurement of difficulty and then we need to make sure when we take a number away we haven't made it too difficult.  I use two measures of difficulty: "choice count" and "stretch".

Choice count is a measure of how many branches were encountered in the solver.  This vaguely represents the number of ways you can go wrong if you just jot down numbers without thinking or looking ahead.  It's not perfect, because sometimes the path forward is obvious to a human but not to the solver.  It measures a choice at each number, but it would be better if it considered sequences of numbers that link two given cells.  For instance, starting with 1 in the above picture, you need to reach the 6.  There are a few ways to get to the 6, and the solver counts those, but it also counts ridiculous choices that never reach the 6, and I don't think humans would count those as making the puzzle more difficult.

The other measure is stretch.  Stretch is just the maximum distance between two given numbers.  A smaller stretch generally means you need to look ahead a smaller distance to find the next number, and it tends to mean fewer paths between one number and the next.  This one also has the benefit that it speeds up the solver; a very large gap in the numbers causes the solver to consider a large number of possible paths and while that might make an interesting puzzle, we need the solver to finish in a reasonable amount of time.

So we take away numbers, making sure the solution is unique and keeping the difficulty in check, and then stop after a certain number of tries, and now we have a puzzle.  The rest is user interface.

Puzzle in progress.

I tried to keep the interface simple.  The Parade site requires you to type the numbers, which I found annoying.  Instead I wanted to just click to place the next number.  There are some edge cases to consider, however.  The user should be able to start at any number, and go in both directions.  Also, the user needs to be able to remove numbers they've entered.  And when you hit a sequence you've already placed, it should skip over that to set you up to put the next number after the sequence.

As you'll guess from the intro menu, I'm thinking of adding more puzzle types later.

Probably Puzzles

It's EELectric! (Junior)

My kids really wanted to play It's EELectric!, but it's way too hard for them.  So I made a new version with simpler rules and easier levels.  You know, for kids.  Or adults who couldn't stand the punishment of the previous version.

It's EElectric! (Junior)

Music Theory, Sound Science and Digital Audio

This isn't the demo.
This is just a screenshot.

I've been working on some JavaScript music code for a possible future project.  So far I've learned a few interesting things about music theory, sound, and digital audio, and I've reached a milestone so here's Keyboard Demo, a little electronic keyboard demo.

Here are some things I needed to learn to get this far:

Generating audio with FFmpeg

I wanted to be able to play a range of pitches; the standard 88-key piano keyboard runs from C0 to C8, so at least those.  I also wanted to support IE.  There don't seem to be a lot of good baked-in options for that sort of thing, so I knew the lowest common denominator would be to have a bunch of tiny audio files, one for each pitch.

I considered generating all the pitches with MIDI in Anvil Studio, recording with Audacity, and then cutting that audio up into individual files, but that would have taken forever.  After poking around, I discovered that you can generate audio in batch using FFmpeg.

FFmpeg is a very useful tool for audio and video manipulation.  It can transcode audio and video files, change sample- and frame- rates, apply filters, crossfade, and probably hundreds of other tricks I don't even know about.  I didn't know it could generate audio (or video) until I ran into this superuser.com question.  The idea is to use ffmpeg's filtergraph feature as an input, with a command line like this:

ffmpeg -f lavfi -i "<filtergraph string>" <output>

FFmpeg's filtergraph strings are pretty complicated, but making a sine wave is pretty easy:

sine=frequency=440:duration=1

Yup.  That's a sine wave.

A quick python script to generate 88 calls to FFmpeg and now I've got all the pitches I need as individual m4a files (IE won't play ogg, sadly).  There's some interesting music theory in just the choice of frequencies, of which I'll give a taste here:

I generated pitches using equal temperatment, meaning that each pair of adjacent pitches has the same frequency ratio.  As temperaments go, this is the one that all the cool kids are using.  It beats out well and meantone temperament, and generally makes sense if you want to play in multiple keys using the same set of pitches.  Apparently it produces some slightly impure intervals, though I haven't yet compared it to just intionation with my own ear.

Then I based the frequencies around the notion that A4 (the A above middle C) is 440 hertz.  That's called concert pitch, or at least that's what we call it lately, and it's not the only pitch reference out there.  It's nice that it's a round number like that - makes it easier to remember. I've heard it said that music played in different keys can "feel" different, as though simply transposing a piece upward a semitone can turn it from melancholy to hopeful, or something.  But the fact that the exact frequency of a pitch has changes through the ages, and that different ensembles might choose something other than the standard, makes me a little skeptical.  Some people have perfect pitch, of course, but I don't know how that works with respect to different pitch references.  I guess both the feeling-of-the-key and perfect-pitch concepts are relative to contemporary practice.  Anyway, 440.

My ears

The range of frequencies that humans can hear is (very roughly) 20 Hz to 20 kHz, which are nice round numbers that should make you suspicious about the error bars around them.  I don't know what the standard deviation is, but I was surprised when I went to listen to those audio files I made.  I couldn't hear most of the low octave (C1-A1, ~32-55Hz)!  I was sure that I had made a mistake in my script.  I've played an 88-key piano before and while my memory, like my pitch, isn't perfect, I seem to recall being able to hear those low notes.

I ran a highly scientific test using this YouTube video, and sure enough, my ears don't kick in until around 55 Hz.  I didn't get to check on the high end of my range because the dogs started barking and I can't blame them because those are some annoying frequencies up there.

So what's going on?  Well, as you know, a piano doesn't sound like a sine wave.  It produces a crazy mess of noise that goes well beyond the fundamental frequency.  Some of the biggest frequencies in the spectrum are multiples of the fundamental frequency (called "harmonics"), but also the whole audible range is spattered with low-amplitude impurities, and all that stuff together makes the timbre of the note.  That's why those frequency spectrum visualizers are never very satisfying to me - it's all a mess, all the time.  I guess it turns out that when I play C1 I'm not usually hearing the fundamental frequency at all (although more volume can help), but my brain is putting the harmonics and other noice together and I end up with a good approximation.

Adding harmonics

So I went back to those sound files and added some harmonics.  This stackoverflow answer has some numbers in it for relative frequencies of harmonics for a piano, supposedly.  I don't know where they got those numbers from, but I figured it was better than just guessing.  I plugged those into my script and generated some more complicated FFmpeg filtergraphs.  For example, heres A4 with just the first three harmonics:

sine=frequency=440.00000:duration=1[s1];
[s1]volume=volume=3[i1];
sine=frequency=880.00000:duration=1[s2];
[s2]volume=volume=1.197[i2];
sine=frequency=1320.00000:duration=1[s3];
[s3]volume=volume=0.897[i3];
[i1][i2][i3]amix=inputs=3

The actual filtergraph I used was a little more complex: more harmonics, plus I added a delay to each harmonic so that I didn't end up with a sawtooth-like shape.

Now I can hear the low notes.  Plus, the notes are a little less annoying.  It's interesting that adding frequencies other than the one I want to play - impure, dirty, frequencies - ones that don't belong - actually make the sound more real.

Aliasing

Hey wait a minute.  I can hear the low octave now, just fine, but the high octave sounds just terrible.  The notes I hear don't even seem related to the ones I'm asking for.  Luckily, I remembered something from college about the Nyquist frequency (so I guess it wasn't a total waste).  I had picked a sample rate of 16 kHz, because I wanted to save bandwidth and it made the audio files nice and small.  Sure enough, if your sample rate is less than twice some frequency you'd like to hear then sorry, that's just not gonna happen.  Instead you're going to hear a bizzaro mirror-world frequency, and you probably won't like it.

To me, the best analogy is to that old experiment where you look at a fan in a strobe light: at a certain strobe frequency the fan appears to stop spinning, and then if you strobe faster the fan seems to rotate backwards.  It's not a perfect analogy, but basically this is the kind of crazy stuff that happens when analog meets digital.  I probably could have fixed it by filtering out the high frequencies or increasing my sample rate, but these audio files are just for IE users.  I can just drop those pitches from the range.  The IE users probably won't miss them.  What are the non-IE users going to get?

The Web Audio API

Modern browsers have the Web Audio API built-in, and with that I don't need any silly audio files laying about.  I can generate my noises in real time!  It's as simple as this:

    var context = new AudioContext();

    var oscillator = context.createOscillator();

    oscillator.frequency.value = 440;

    oscillator.connect(context.destination);

    oscillator.start();

That's produces a pure A4 sine wave.  Add more oscillators for the harmonics, watch out for aliasing, put a "gain" node in there because the default oscillator is super loud, and we're in business.  There are some cool tricks like amplitude envelopes that I could use to make better or crazier sounds (see this web synthesizer site for instance).  Really, the engineering of synthesizers is an enormously deep rabbit-hole, and I'm tempted to jump in, but this will do for now.

Volume

Another thing about sounds:  Loudness.  I used to think it was mostly about how far up and down the waveform moved.  Nope.  It's also not about the rate-of-change of the waveform at any given point.  If you're thinking about amplitude of sine waves, that's closer, but still not right.

Uh-uh.

Nope.

From what I now understand, it's a combination of the amount of energy in the wave over a certain span of time, and the sensitivity of the human ear to the frequencies involved.  A big spike in the wave means the speaker (for example) has to push a bunch of air molecules really hard, but it has to keep working on that air for a while before it will affect how loud we think the sound is.  Plus, even a very energetic sound may be very quiet if it's near the edges of the range of our hearing, like those low-octave pure-sine-wave notes I couldn't hear.  Loudness is a messy concept, and, when it comes to commercial music, thank goodness for ReplayGain.

In my demo you'll notice that some of the notes are louder than others, due partly to the fact that I didn't vary the oscillator amplitudes as the pitch went up, but also due to a phenomenon represented well by the Fletcher-Munson curves, which show that some frequencies just sound louder than others even when the "sound pressure level" is the same.

The interface

The interface for this demo is pretty simple:  Click and hold a key to play it.  If you want to get fancy, you can hold down shift and click different notes to make chords.  I took a tape ruler to the little electric keyboard I have for some measurements and then used a little dynamic SVG to generate the keys.  There's a little dot on middle C just to get you oriented.  That's about it.  I have some bigger plans for this code, so stay... tuned.  See what I did there?  Tuned?  It's.. oh, ok.  Here's the link again:

Keyboard Demo

It's EELectric!

Do you like eel-based puzzle games?  Ready for some mind-bending diagonal-moving action?  No?  Nevertheless, let me introduce you to It's EELectric!, an original puzzle game I've been working on.

In this game you star as an apex predator, the deadly Electrophorus electricus, better known as the electric eel. This is not a realistic eel simulation. In fact, I looked it up: electric eels don't look like this thing at all.

Plus, I don't think there starfish in the same... you know what, just swim with it.  Your job is to eat all the fish on the level, but before you chow down on the unsuspecting prey you have to kill it with your electric shock attack.  And you're hungry and getting hungrier, so you'll have to be careful not to waste any moves.  Otherwise you'll perish and have to press R to go back in time to try again.  I already mentioned it's not realistic.  SHOCKING.

Enjoy 37 fiendfishly difficult pools of funderwater puzzling!  Sound sea-ffects?  It's um, reel.. something.  Hmm.

Anyway here it is:

It's EELectric!

Callooh Callay, World!

I wrote some puzzles for the 2014 MIT Mystery Hunt.  For one of them, Callooh Callay, World!, I invented a new esoteric programming language called Wonderlang.

It's frabjous.

I imagine this is how one would program computers in Wonderland, if there were any.  It's not meant to be particularly difficult to use, but it has a different perspective.  It requires a few characters not found in the ASCII character set: I suspect keyboards in Wonderland would have a great deal more keys than ours.

Wonderlang hasn't made it onto esolangs.org (yet).  To be fair, I haven't written a proper specification for it, which seems likely to be a requirement.  But then that's probably another natural characteristic of programming in Wonderland - why should they need to write this stuff down, or if they did, despite needing to, why should they go and actually do it?  After all, they're all mad there.

Callooh Callay, World!
[solution]

Hexfold

Here is HEXFOLD, a web-based puzzle game inspired by the puzzle toy Cool Circuits.  For some background, see my post analyzing Cool Circuits, and the one describing how to extend Cool Circuits to a hexagonal board.

Level 7: "Lucid Sitar"

TL;DR: The object of the game is to place the pieces on the board to create a loop, using every piece and obeying certain constraints that are different for each level.  I made 36 levels (the 37th and final one is randomly generated) which more or less increase in difficulty from hand-holding tutorial to absurdly hard.

I should warn you, this isn't an easy, kid game like Robot Quest or a simple, casual game like Logoplex.  Oh, sure, it starts out easy enough.  But that doesn't last.

If you give it a try, please provide feedback in the comments below.

Before you ask: the level names are just arbitrary adjective-noun combinations.  I generated a bunch using The Sillifier, and picked out the ones that amused me.

HEXFOLD (Web)

It's also available as a Chome App:

HEXFOLD (Chrome Store)

Cool Circuits: Hexagons

If you haven't read my previous post about Cool Circuits, better go read that first.

What if Cool Circuits was made with a hexagonal grid instead of a square one?  More precisely, what if the turns in each piece were 60 degrees instead of 90?

We'll use the same pattern for generating the pieces: Each piece is a path composed of five turns either clockwise or counterclockwise, and each piece is uniquely described by a sequence of four bits, where each bit indicates whether the next turn is in a different direction than the previous turn.  Here's what the pieces would look like:

"JUVENILSQ"

Compared to the 90-degree pieces, these new ones are a little more stretched out.  If you've been paying attention you'll notice there's a new one.  The last piece in that image corresponds to the bit sequence 0001, which wasn't possible in the original Cool Circuits because it would have intersected itself.  I'm going to call it "Q".

Can we make a circuits with all of these pieces?  Nope.  In 90-degree-land, each piece contributed a single 90-degree turn (either way) to the overall path, and since there were an even number of pieces that meant we could end up with the complete 360-degree turn necessary for a circuit.  But with these new pieces, 6 of them contribute a 60-degree turn, and 3 of them contribute a 180-degree turn.  That means if we use all the pieces we'll always end up 180 degrees off. Here's a tabular summary:

Letter	Description	Flipped	Contribution
J	0011	1100	180
U	1001	(same)	±60
V	1011	1101	±60
E	0110	(same)	180
N	0101	1010	±60
I	1111	(same)	±60
L	0111	1110	±60
S	0010	0100	±60
Q	0001	1000	180

So we'll have to drop at least one piece.  For now, just to be true to the original puzzle, we're going to have to let Q go.  Sorry Q.  Maybe we'll find a job for you later.

Behold!  Hexagons!

Because the turns are 60 degrees, the pegs on the board will be arranged in a hexagonal grid.  Clearly, the overall shape of the board should also be a hexagon, but what size?  Five seems like a nice diameter - it would have almost the same number of points as the original puzzle.  I modified my solver from the original puzzle for these new parameters, kicked it off, and sat back to watch the solutions roll in.  Sadly, there are none.

Cool Circuits has a neat property that every solution leaves behind 6 untouched pegs.  In "Cool Circuits, Jr" they add 6 rings that you can use to wrap those pegs.  Once you've done that, there is no position left untouched.  This hexagonal version doesn't have that feature.  For each turn you make, you make it impossible for the path to later hit the point you didn't turn towards.  Near the edges, that can cascade and make other points untouchable as well.  I suspect this is a clue to why there aren't any solutions in the 5-board.

Before we give up on this board though, what if we had even fewer pieces?  I tried dropping J and E (leaving us with only pieces that contribute 60 degree turns), and I found that there are solutions to that variant.  Exactly four of them (ignoring solutions that are equivalent via rotation and reflection).  Here they are:

Four unique solutions for the 5-board, using the UVNILS pieces.

Note how the V and N pieces can be swapped (and flipped and rotated) to convert one solution into another.  That's also true in some of the solutions to Cool Circuits, though in both cases it depends on how tightly-packed the circuit is.

To me, this doesn't seem like enough solutions for an interesting puzzle game.  Sure, with rotation and reflection we could make more circuits, but they would all end up feeling the same.

Time to raise the diameter to 7.  You can probably guess going into this one that there will be too much space on the board.  Going back to 8 pieces, I let the solver run overnight, and it says there are 1503 circuits.

Alternative boards.

So with lots of space (A) we have lots of solutions.  I also considered removing the six outer-most pegs (B: 474 solutions) and removing four pegs from each of three edges, forming a somewhat triangular board (C: 130 solutions), but the bigger hexagonal board seems more thematic to me.  The large number of solutions does mean that we'll need to have plenty of constraints in each puzzle to make it uniquely solvable.

Overall, while not as elegant, I think this configuration works pretty well as a variant of Cool Circuits.  I'm working on a web-based playable version called HEXFOLD, which I'll post here once I've finished the levels and had some people play-test it.

HEXFOLD Solver

Cool Circuits

I came across a particular kind of puzzle, the design of which is really fascinating to me.

I wanted to get my son some electronics toys for his last birthday.  I had one of those 100-in-1 electronics kits when I was a kid but he's still a bit young for the complex wiring, or at least that's what I thought.  I ended up picking Snap Circuits, which he loves.  I had to pick one more thing because you never know with kids, it's safer to get a couple of smaller things than one big one, so I tossed in Cool Circuits, because it had a similar name, and I think Amazon suggested it or something.  He also loved that one.  It's not really about electronics, it's just a puzzle game, but I've come to realize it's a very cleverly-made one.

A cool circuit in progress.

Here's how it works: the board has 25 pegs, arranged in a kind of diagonal grid.  There are 8 serpentine pieces which can fit in between the pegs, and each has a unique shape.  For each puzzle you are given some constraints (e.g. part of the circuit must travel along this path) and you must put the pieces on the board in a way that meets the constraints.  The one universal constraint is that the pieces must form a single loop.  In the toy, that triggers some mechanism which lights up the board and plays some music, but I've found that feature to be pretty finicky.

It's pretty tough to make a circuit from scratch, so the constraints tend to help more than hurt, and the more of them there are the easier the puzzle.

At first I thought the shapes of the pieces were arbitrary, but there's a mathematical beauty and completeness to them that took some pondering to discover.

As a font, it would not be easy to read.

Each piece is made of a sequence of five quarter-circles.  The manual describes them as "J", "U", "V", "E", "N", "I", "L", and "S".  So if you're looking at a given piece, starting from one end, you might describe it by listing the chirality of each segment.  For instance the "V" piece would be: turn right, left, left, right, left.  Or maybe clockwise, counter-clockwise, etc..  But that's a terrible description because the same piece would be described differently if you started from the other end, or flipped it over.

Math!

We can normalize the description for flipping by listing not the turns themselves, but the changes.  So if it starts out in one direction, we just say whether the next turn is the same as the previous one or different.  The "V" piece would then be different-same-different-different.  Now imagine same as 0 and different as 1 (e.g. 1011).  Each piece is described by four bits.  But some pieces have a different description if we start from the other end.  To correct for that, for each piece we'll pick the description that has the smallest number when treated as binary.

Here are the eight pieces:

Letter	Description	Flipped
J	0011	1100
U	1001	(same)
V	1011	1101
E	0110	(same)
N	0101	1010
I	1111	(same)
L	0111	1110
S	0010	0100

In this scheme, you can't have three zeros in a row, because that would make the piece intersect itself.  So 0000, 0000, and 1000 are out.  That means every workable bit sequence is represented.  These aren't arbitrary shapes at all, it's all possible unique shapes of length 5!  At length 4, there are 6 possible pieces.  At length 6, there would be 15.

All possible locations for the first piece.
Testing just the blue ones is enough.

So how many circuits are there? Let's start with an upper bound. For now let's say the first piece we put down can go in any point, in any direction, flipped or not. There are 224 possible first points (red and blue arrows in the diagram to the right).  However, some of those are equivalent to one another, because we could just rotate or "flip" the board itself.  So we'll cut that down to 28 (blue arrows only).

Suppose each piece can fit two ways at one of the blue arrows.  Actually, some pieces fit fewer ways than that, and sometimes they won't fit at all, but let's not work out those details yet.  After that first piece, we choose a next piece and fit it on in one of four ways.  This overestimated upper bound says there are fewer than 28×8!×2×4⁷ paths (36,993,761,280). That's pretty high.  Luckily, many of the paths terminate quickly, either running off the board or crossing and earlier section of the path, so we're not going to need to search them all just to find the complete circuits.

I wrote a program to brute force all the paths.  It found 17,473 paths, starting from those blue-arrow positions, that used all 8 pieces without self-intersection or running off the board.  Of those, 1,520 ended up where they started, forming (possibly cool) circuits.

We're overcounting with that number though, because for any given unique solution, we're seeing it 16 different ways (counting reflection and cycling through the 8 pieces as starting pieces).  Now I very well may have made a mistake (or several) here, but I think the final answer, the number of unique solutions to this puzzle, the number of Cool Circuits, is 95 (no, see UPDATE below).

Cool Circuits at ScienceWiz

Solver Source Code

UPDATE 4/27: I found a mistake.  I didn't account for some solutions that fit so tightly that they leave four empty pegs all along one side of the board.  Those solutions are double counted in my initial number because they can be translated into another solution.  I was accounting for rotation and reflection, but not translation.  There are apparently 11 solutions like that, so my final answer (today) is 84.

Name Chains

Some people's last names sound like first names, such as Larry David.  Some have first names that sound like last names, like Taylor Swift.  And some have both, like Campbell Scott and Wallace Shawn.

FWIW

I downloaded a list of names of actresses and actors from IMDB and did some messing around with the data.  At first, I wanted to create chains of names, where the first name of each person matched the last name of the one that came before.  I think I'd get even better results if I could just extend my list to celebrities in general (not just IMDB actors and actresses), but so far I haven't found any better lists.

On second thought, I'll take the check.

There are a 3.6 million people in these lists, and most of them are quite obscure.  I'm not great with knowing celebrity names, but I think even the most die-hard movie memorizer would have trouble recognizing the names of all the "Documentary Couple" people in When Harry Met Sally, one of whom was apparently Peter Pan, and all of whom are in this database.  Plus - and I feel bad about this - the likelihood that I'll recognize an actor or actress by name decreases the longer it has been since that person graced the screen.  I figure recognizability is important in the kind of name chains I want to make, because that's what makes the chain interesting when compared, say, to a randomly generated list of names.

But how can I consider only the recognizable thespians?  I don't know a good way to do it, so I picked a bad way.  I created a "credit score" for each person, which does not at all reflect their quality as a performer, and honestly it's a pretty bad measure of fame, too.  But it was something.  It goes like this: for each credit they have in a TV episode or movie released in or after 1970, they get a number of points (1 point for a TV episode, 5 points for a direct-to-video movie, 10 points for a made-for-TV movie, and 20 points for a... standard(?)... movie).  Anyone with 30 or fewer points was discarded.  Maybe I could have linked their performances with ratings, orcounted how far down the cast list they were, or discounted multiple appearances on the same TV show, but I didn't. I did drop everyone for whom I couldn't parse out a first and last name, and people with the 'Jr.' suffix, because they won't fit well in a chain.

"I'm gonna play it safe. I'll wager $0."

Most of the top credit scores are porn stars, simply because they make a lot of movies.  I'll let you guess who tops that list.  Yes, that's right.  Skipping those, the top score goes to Shakti Kapoor (12423), a prolific Bollywood actor.  Skipping Bollywood as well, we get to Frank Welker (10544), a prolific voice actor.  Skipping voice actors too... Alex Trebek (8144), whose score was bumped by thousands of episodes of "Jeopardy!".  It goes on like this for a while.  Like I said, it's not a great algorithm.

Now, with only around 428,000 names, and a slightly better (but still terrible) chance of each name being known by an average reader, let's look at some numbers.  Here are the basic high-fives:

Top Five First Names, Actors

Michael

4,420

David

4,223

John

4,030

Robert

2,480

Paul

2,217

Top Five First Names, Actresses

Anna

1,110

Sarah

1,105

Jennifer

1,075

Maria

981

Laura

916

Top Five Last Names

Smith

1,357

Lee

1,249

Jones

1,016

Johnson

1,000

Williams

979

For chaining, those would be great names to see switched.  Somebody named Smith Michael would be very handy.  Let's call his name "inverted".  Sadly, there's nobody with that name, but there are plenty of other inverted names.  I gave everyone an "inversion score": (F_L * L_F) / (F_F * L_L), where for instance F_L is the number of people whose last name matches your first name.  Low inversion scores include Jennifer Lopez (0.000004) and Chris Williams (0.000005).  Top score goes to King Jeff (4,884), but others include Rooney Mara (455) and Pruitt Vince (235), whose names definitely sound backward to me.

In this data set, there are around 285,000 "dead ends" - people whose last name matches nobody's first name.  Reedus, Gurira, or Cudlitz, for instance.  That means if I picked matching names randomly, there's a 2 in 3 chance at each link that the chain will end there.  If I picked each name optimizing for how many choices I'll have after that, it's going to be a very boring chain, full of Michael John, John Michael, Michael Paul, Paul John, John Paul, Paul Michael, and so on.  All real people, apparently.  It turns out this is a hint about how many branches there are in this system, and why my next idea won't work.

I opted to avoid a centipede metaphor.

I tried to automate chain-generation.  I wrote a program (hereafter abbreviated as IWAP) that searches for the top-scoring chains/cycles of a given length.  2-cycles are interesting because that's basically two people whose names are switched.  My favorite among those is Keith David/David Keith.  The problem is that the program takes too long for lengths greater than 2.  There are a ton of possibilities, and even if I just pick a few random ones, that's not really what I'm looking for - I want good ones.

Perhaps there are still some things at which humans can beat computers.  I'll just try doing it by hand.

Ok, maybe not entirely by hand.  IWAP that takes a name and lists everyone with that as their first name.  IWAP for last names, too.  In each case, it sorts the list by yet another score, this one the product of the person's score and the number of choices I would have for the next link.  With these programs I can just explore the tree of possibilities manually.  Here are some chains I've produced so far:

Michael Shannon Elizabeth Ashley Judd Nelson Franklin

Mia Sara Gilbert Gottfried John Oliver Platt

James Taylor Elizabeth Jordan Elizabeth Taylor James

Clark Gregg Henry Thomas (Ian) Nicholas Brendon

One more idea before I wrap this up.  A simple 2-person chain can be used as part of a puzzle.  If I give you the first name of one person, and the last name of another, it could clue the name I didn't give you, which they share.  For instance, Meg Reynolds would clue Ryan (at least, given the particular set of people I narrowed it down to).  In theory, another pair of names could clue another "middle" name, and the middles could be put together, and so on.  In practice I think it would be very difficult to construct such a tree of names and have it be solvable by hand.  For the simplest 2-person case, IWAP that takes a name and finds unique clue pairs, but once again lots of human intervention is necessary to prune the possibilities.  Here are some examples for you to try:

Kurt Crowe

Clive Teale

Aaron Sorvino

Samuel Rathbone

Brion Woods

Gene Osbourne

Currie Norton

Clint Hesseman

Diane Stapleton

Peter Mewes