Monday, April 25, 2016

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.

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:


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×47 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).

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.

Monday, April 18, 2016

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.

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
Top Five First Names, Actresses
Top Five Last Names
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

Sunday, April 10, 2016


There are many logo quizzes on the internet.  Many.  Yeah, just tons.  Here's another one.

An uninformative screenshot.
It's called logoplex.  This one focuses on big vector graphics, animations, and clean design.  I limited myself to the logos I could get in SVG form, and which if I removed the identifying text from them I was left with a (mostly) recognizable shape.  I collected 100 logos in total, but logoplex only chooses 10 of them at a time to throw at you.

Gathering the logos was quite a grind.  Logopedia was useful, they have just about everything there - plus for any given logo you can see how it has changed over the years.  Wikipedia was also great (as usual) for things like lists of companies and fast food chains and whatnot, and if there's an SVG version of a logo out there Wikimedia Commons probably has it.

However, some of them seem to have been badly converted from Illustrator, with lots of unnecessary elements.  I wanted to make sure each logo stayed less than 10 kB.  In some cases I had to allow more than that, but in others I simply had to let the logo go.  For example, I dropped the Discovery Channel logo because the globe image makes that one pretty big.  Some of them I just edited down to size.

The program lets you get a little sloppy with your answers.  In addition to allowing variations in some answers, it also allows minor misspellings using Levenshtein distance.

Give it a try, and let me know what you think:

Saturday, April 2, 2016

Dimensional Insight Logo Animation

Here's a little web animation I made.  It's based on the logo of the company I work for, Dimensional Insight:

Truly, this shape evokes "business intelligence".
Don't tell anyone but sometimes we refer to it as "the Q*Bert logo".  The main elements of it are tileable and I took that to its natural conclusion, imagining an infinite wall of isometric madness.  I thought it would be neat if the little diamond-shapes unfolded to create the pattern.

It's like this, but more animated.
The hardest part (and the least apparent in the final product) was getting the 3D transforms right for the folding of each little parallelogram.  There were also difficulties in getting CSS transitions to start exactly when I wanted.  Other than that, there are the usual cross-browser issues: Firefox and Chrome disagree about things like 'letter-spacing', and Internet Explorer simply doesn't seem to support the 3D transforms at all (specifically, 3D CSS transforms on G elements within the SVG).

So, if you're using Internet Explorer, sorry (not sorry) it won't work for you.  But for everyone else: