Sunday, January 14, 2018

Egressors - those who escape

Charlene and I have really gotten into escape rooms lately.  I mean, really gotten into them.  We did our first room in September of 2016, and since then we've been playing as many as we can.  So far we've done about 26 rooms in 5 states and 3 countries.  If you haven't tried them yet, I just can't recommend them enough.

We started a spreadsheet to track which rooms we've visited, and it wasn't long before I thought there ought to be a website for that.  I've seen at least one (, but it's mostly in Dutch and doesn't cover our area.  After a while I decided this was something I could do.  So after a few months of on-and-off coding while the kids were asleep, I'm finally ready to launch:

Egressors Logo

Egressors is a directory of escape rooms in the New England area, and a place where you can sign in and track your own escapes.  We're starting simple and planning to build up features over time.  For instance, right now you can track your escapes but you can't see anyone else's.

Fancy graphics.
One of the first updates I plan for the site will be to see how many users have logged plays at each room, and see the escape rates.  I'm holding back on reviews and comments and other judgement-y features at first, because I don't want the site to impact any of the venues in a negative way.

Another early update I hope to include will be a tailored news system - so that users can sign up to hear about new rooms and events, but specifically ones in their area or for rooms they are "watching".  Some rooms have their own mailing lists, but you have to sign up to those one at a time.  There are mailing lists out there for general escape room info, but they don't have any way to filter to local information.

The other escape-room-related project we're working on is a "passport" for rooms in the North Shore area.  There's a great concentration of rooms along I-95 north of Boston, and if other "egressors" are like me, then once you're hooked you want to escape them all.  This passport provides a physical way to track where you've gone, and a goal greater than just one room.

Not valid for travel to foreign countries.
Plus, and of course, there's a puzzle on it.  To solve the puzzle you need to visit enough of the rooms (not necessarily all of them).  Each room will write something different that will get you one step closer to the solution.  Nine venues in the North Shore area have signed up to distribute the passport, all fine places to get out of:
At some point I might add a feature to where you can enter the solution to the passport and thus get some internet points.  If the passport goes well I could see expanding it to other areas.

So if you're in New England and like escape rooms, check out the site and consider signing up for an account.  And if you're near the North Shore then keep an eye out for the passport.

Friday, December 15, 2017

QblePon is the best game

The best game.
I want to fix a problem with the internet.  First of all, I think we can all agree that QblePon is the best game.

But the thing is, I searched for a list of QblePon characters on the internet and as far as I can tell there isn't one.  This is ridiculous, people.  There's a list of animals with fraudulent diplomas, for Pete's sake.  Where is someone to go when they can't remember which QblePon character has the floppy disk in its head?  (It's Stanchmode)

So I'm here to help.  Please enjoy below a list of all the known QblePon characters.  There are probably more, but these are the ones that Hector mentioned when he described the epic game that he and This Kid played, which come to think of it may be the only game of QblePon ever played.

Before we begin, a little bit about the game itself.  It's a card game.  We know that two players can play it, and they sort of mostly take turns.  The characters seem to have a single stat: Something the range of one to five.  Also, in this episode of the TV show, it is revealed that Twirbirdler can do an attack called "Gashing Slice".  It is not known how the attack works in the game.

Well that's enough details, let's see some characters.  You know you want to look at them.  Here they are in alphabetical order:

Stat: 5
"My main man and yours."
Hard to stop thinking about.

Stat: 3
"All day long."
Combo: Good with Feedems (Jersey) and Feedems (Raw).

Feedems (Jersey)
Stat: 3
See also: Feedems.

Feedems (Raw)
Stat: 3
See also: Feedems.

Stat: 3
"Not actually a QblePon character."
Actually, a QblePon character.

Stat: 5
Combo: Can be played with Skweezout.

Stat: 1

Stat: 1
"Some fourth level beeswax."
Not the best card to start with.

Seemingly Sam
Stat: 2

Stat: 2
Combo: Can be played with Pantso.

Stat: 5

Stat: 4

Stat: 3
Attack: "Gashing Slice"

Stat: 1
May not have been played in Hector's game.

Zock Click
Stat: 3

There, problem solved.

Sunday, December 10, 2017

Mancala AI

My kids were into mancala for a little while this year, and so I made a version of it that you (mainly my kids) can play in a web browser.  A secondary reason to do it was to explore more about the game and its strategies.
Looks like south has a pretty good lead here...

There are around 650 billion board positions (depending on which rule set you use, here I'm focusing on "Kalah").  In the year 2000, someone at Caltech found the winning strategy for it - that is, they solved it so we can now know what the best move is in each position.  The player that goes first has a slight advantage in random play.  

For a simple human-player strategy, we could learn from the "Advanced Heuristic Minimax", which uses the following principles, weighing the earlier ones more strongly than the later ones:
  • Maximize the amount of counters in your own store.
  • Keep the opponents score to a minimum.
  • Prefer to move the counters from your right-most pit.
  • Have as many moves as possible from which to choose.
  • Hoard as many counters as possible in the left-most pit.
  • Keep as many counters on your own side as possible.
Below is a link to the online version I made, which has four computer opponent choices: Random Rachel just picks each move randomly.  Greedy Greg moves to take as many pieces as he can, choosing randomly when he can't capture.  Minnie Max uses a minimax strategy, looking ahead about 8 moves.  And then there's Foolish Frank, who also uses minimax, but makes the worst move he can find.

Wednesday, October 11, 2017

An unfinished Pikmin-like game prototype

Here's a project that I haven't managed to finish.  It's a 2D imitation of Pikmin, which I think is a fascinating take on the real-time strategy genre.  I was working furiously on it in March, and then I ran out of steam and moved on to something else.  I was a little too ambitious here for a short-term project, but it was some good exercise for certain tools.  I used the Phaser framework for the rendering and tile/map management, and Tiled to make the maps.

To try it out, just click anywhere to get past the menu and then:

  • W A S D to move your character
  • left-click to throw a minion
  • right-click (and hold) to call minions in a certain area
  • space to disband (and sort) your army
Throw minion onto a pellet to pick it up and carry it back to their home.  They'll carry it to whichever color makes up the majority of the carrying crew.  That will then spawn more minions.

Thursday, September 14, 2017

SporkFeed: command-line rss/atom feed reader

I get really frustrated trying to read websites on my phone.  I used to use Google Reader, but that died so I switched to Feedly.  But I became frustrated with the ads, including some particularly invasive ones.  So I just started cycling through sites, one bookmark at a time.

Even ignoring the extra work it takes to move from site to site, it's still not much better.  Websites are full of ads too, and increasingly they seem to be videos or animated images.  I just want to see a list of the article names, and maybe an excerpt of the article, so I can decide whether to skip it, read it, or save it for later.  I don't need to download all those bytes.

So I thought about making my own (yet another) feed reader.  What's different about this one?  It runs on the command-line.

SporkFeed is a command-line rss/atom feed reader.  It loads articles from multiple websites and lets you read them in plain text.  Here are some of the features:

  • No central website or server - the feed data is under your control
  • You choose where to put the reader state (e.g. put it in DropBox so you can read from multiple devices)
  • Simple keyboard command interface
  • Launch articles in a web browser (where possible)
  • Open Source (github)
  • Cross-platform

The core of the reader is in a separate module, sporkfeed-core, so in theory multiple user interfaces ca n be written against the same reader state.  That would mean that the feed data could be shared between the command-line interface and a mobile interface.  I'm thinking of making either a web interface or a mobile app, which would finally solve my phone reader problem.

This command-line version requires node.js.  Once you have that, just run this to install it:
npm install -g sporkfeed

Thursday, July 13, 2017

Tower of Hanoi Variations

A long, long time ago (1993) I spent a few weeks at a summer residential governor’s school, hosted by the college of William and Mary.  I remember only fragments of that time:  Playing capture-the-flag across the campus.  Some kind of fancy asteroids game.  Recording professors' answering machine messages and editing them to make them say funny things.

During one programming class, I remember the professor describing a linear congruential generator for pseudorandom numbers.  I thought to myself, "That can't be the best way, I came up with that on my own at home."  Then, being young, I said that out loud.  I think the professor said something to the effect of "Yes, you're very smart, now shut up."

I also remember helping to solve a variation of the Tower of Hanoi, and getting my name in a published paper.

You should already know what the Tower of Hanoi puzzle is.  If not, you know how to use Google: I'm not going to describe it to you here.

You probably didn't need a diagram for how to swap something.
This variation was pretty simple: As in the classic puzzle you can move the smallest disk to any other peg.  But the other disks can only be moved by swapping them with the next-smallest disk (and only when the two swapped disks are at the tops of their stacks).  This variation was introduced in 1944, and as far as Professor Stockmeyer could determine no algorithmic solution had been published (and he has looked around pretty thoroughly).  You can try it out at this demo site I made, by choosing the variation called "Swapping".

I hadn't thought about this for years, and then I go and watch two 3blue1brown videos about the Tower (part 1 and part 2) and the whole thing comes trickling back.

We were given a challenge: if we could produce a correct algorithm to solve this variation, then the professor would put our names on the paper he was going to publish.  It wasn't easy, but after some days we managed to find the solution.  The rest, as they say, is in the International Journal of Computer Mathematics.

Classic Tower of Hanoi solution
The classic Tower has a simple recursive solution:  Consider the biggest disk.  You want to get it from peg A to peg C, so first move everything else off of it and onto peg B.  Now you can move the big one to C, then move everything else from B to C.  The "move everything else" steps are where the recursion comes in, because doing that is just solving the puzzle again but with a slightly smaller tower.

Here's a notation that will help:  We'll list the positions of the disks from biggest to smallest, in a single string.  So we start out at "AAAA..." and we want to end up at "CCCC...".  The classic solution is to first go from AAAA... to ABBB... (by recursion), then to CBBB..., then to CCCC....

There's another variation, mentioned in the 3blue1brown videos, where you can only move disks to the right, except that you can also move a disk from the last peg to the first.  This might be called the Cyclic Tower of Hanoi, and it has a solution that's different from, but similar to, the classic Tower.  The difference is that here you can't just move the big disk from A to C.  It has to go to B first.  So you move everything else to C, move the big disk to B, move everything else to A, move the big disk to C, then move everything else to C.  This involves "move everything else" three times, so overall it takes more moves.  Using our notation, this means we go from AAAA... to ACCC... to BCCC... to BAAA... to CAAA... to CCCC....

Our variation involved swapping, and was a little more complicated.  Suppose we're going to implement a function "solve", which moves a tower from A to C.  To move the big disk to C you can't just get "everything else" out of the way.  You need the second-biggest disk to be on C, for the swap to work.  That is, we need to get from AAAA... to ACBB....  Let's ignore how to do that for a moment, and just say we have a function that does that, called "unfold".  Basically the function "unfold" takes a stack "AAAA..." and moves to "CBBB...", where the biggest disk of that stack is on one peg, and the rest of that stack is on another.  Suppose we also have the reverse function, "fold".

So the overall solution function, "solve", can work by first calling "unfold" to set up the big-disk swap (ACBB...), then doing that swap (CABB...), then calling "fold" to tidy everything up (CCCC...).  This is a good start, but unlike with the classic and cyclic variations, our "unfold" function isn't just a smaller version of the overall solution.  We still need to define it.

To implement "unfold", how do we get from AAAA... to CBBB...?  As before we've got to move the big disk from A to C.  So we start by going from AAAA... to ACBB..., then swap to CABB..., then somehow get from CABB... to CBBB....  The first part is easy, we call "unfold" on the sub-tower.  This last part is new, though.  Now we need some algorithm that can insert a disk underneath a stack.  That is, it needs to get from something like ABBB... to BBBB.... This requires another function, let's call that "insert".  We'll also need "extract", the inverse of this function (so we can implement "fold").

To implement "insert", how do we get from ABBB... to BBBB...?  The big disk needs to get from A to B, so we need to set things up for that swap.  This means we need to go from ABBB... to ABCC..., swap to BACC..., and then go from BACC... to BBBB....  Finally we have all the tools we need:  The first step there is just moving a whole tower (BB... to CC...), which is the "solve" function we're ultimately building.  The last step is "fold" (ACC... to BBB...).

How the five functions call each other.
So our solution involves five functions: "solve", "unfold", "fold", "insert", and "extract".  The paper rigorously describes why this solution is optimal, but I prefer to simply note that there aren't really any other options.  For the implementation of each function, the biggest disk really does need to move to the right place, and it can only get there if every other disk is set up just right.  It seems to me that it's optimal because it only makes necessary moves.

I made a site that demonstrates this and a few other variations of the Tower of Hanoi, at the link below.

Wednesday, June 21, 2017

Musical Notes and the Hilbert Curve

3blue1brown logo
seriously go watch the videos
Grant Sanderson makes a great series of YouTube videos, called 3blue1brown, that explore math concepts with animations.  This video talks about Hilbert curves, which are continuous fractal curves that completely fill a two-dimensional area.  The video uses them for a hypothetical system of encoding a two-dimensional image (as a grid of pixels) into a one-dimensional sound (as a range of frequencies).  I'm not sure such a system would work very well as described (to me, this system called "vOICe" seems a bit more practical) but that's not really the point of the video.  It's just a setting for talking about the curves, and how a concept like "approaching infinity" can have practical applications.

Fourth order Hilbert curve
would not make a good maze
Here, the Hilbert curve is used as a mapping from a 1D space into a 2D space.  A useful property of these curves is that when you increase the resolution (or the number of iterations) the mapped 2D location of a given 1D value is not drastically changed.  So someone can get used to 0.083 being at the top-center of the image, and it doesn't much matter what resolution is chosen for the curve - it's still basically at the top-center.

After watching the video, I wondered about the reverse procedure.  That is, what kind of images would it take to produce a given sound.  In particular, where would the standard musical pitches lie on the curve, and what would chords look like?

So I made a little web experiment to find out.  I call it Hilbert Chords.  Here's how it works:  I mapped the 1D space onto a single octave, the range of frequencies between middle-C and high-C.  It's a logarithmic scale, so the 12 pitches in the chromatic scale (plus one for the repeated C) are spaced evenly apart.  You can move your mouse over either the 2D or 1D regions to hear the corresponding pitch and also see where each point maps to in the other space.  Also you can click a handful of buttons that play preselected chords and see what the chord would look like.

locations of pitches on the chromatic scale
in color.. because, you know..
I was surprised, at first, to see that the notes all lie on corners of the four quadrants.  After thinking about it a bit, it makes sense.  Each quadrant connects to the next one at one of its corners.  The pair of corners connecting two quadrants are basically the same pitch.  So that leaves three distinctly-pitched corners per quadrant, for a total of twelve (and again there's the final corner for the repeated C).

When we increase the number of iterations, the curve gets denser, but the points representing the pitches move less and less.  As the number of iterations approach infinity, the pitch-points approach specific points on the square.  I don't have a complete understanding of the math, but it seems to me that four of them (E, G#, and the two Cs) approach the corners, six of them (C#, F, G, A, and B) approach the centers of the sides, and three of them (D, F#, and A#) approach the center.  At sufficiently high resolution, you wouldn't be able to see the difference between some very different chords, and the D augmented chord would look like a single point in the middle.

Ok, not a good visualization of the chromatic scale.  A plain circle is much better.  Or even just a keyboard.