Shift Clock
Click here to view.I'm really happy with how this experiment turned out. It's a clock that spells out the time with squares, and then shifts those squares into their new positions whenever the time changes. It draws the time text into a hidden tiny canvas
element at each minute, then uses getImageData
to extract the individual pixels. Any pixel that has been drawn with an alpha > 0.5 is set as a destination for the next squares animation. The animations themselves are performed using d3.js.
The picture above is of the blackonwhite version. There is also a greyonblack version, if you prefer that color scheme.
In order to make the transitions look the best and happen the fastest, I wanted to pair source squares and destinations in the way that minimized the maximum distance any one square would travel. I first tried using a greedy algorithm that simply took the farthestaway source point and paired it with the closest destination, then removed that destination. (Essentially, for each source point, I sorted all destinations by distance. I then sorted all source points by minimum distance to any destination, and took the one that was farthest from its closest destination.) This algorithm, however, tended to choose destinations that forced the leftover sources to travel even longer distances, making it pretty ineffective.
As it turns out, the problem I wanted to solve has a name, and has been researched by others. It is called the Linear Bottleneck Assignment Problem and is part of a family of related problems known as assignment problems. Wikipedia describes it as follows:
There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agenttask assignment. It is required to perform all tasks by assigning exactly one agent to each task in such a way that the maximum cost among the individual assignments is minimized.
In this case, the "agents" are the source points, the "tasks" are the destinations, and the cost of an "agenttask assignment" is the taxicab distance between that source and destination.
There are a few different solutions to this problem. One of the simplest, which I chose to implement, is a thresholding binarysearch solution:
 Set the lower bound
lbound
to the smallest edge length and the upper boundubound
to the largest edge length.  While there are any edge lengths between
ubound
andlbound
(not including lenghts equal to them): Set
med
to the median of all edge lengths betweenubound
andlbound
.  Find the maximum matching using only edges not longer than
med
(med
is the threshold)  If the maximum matching is perfect (if it successfully connects all sources to all destinations), set
ubound
tomed
(because we know every threshold>= med
must result in a perfect match)  Otherwise, set
lbound
tomed
(because we know every threshold<=med
does not result in a perfect match)
 Set
 At this point, usually
ubound
is the best threshold. If we have not testedlbound
already (which can only happen iflbound
is still the smallest edge length), however, we need to test it: Find the maximum matching using only edges not longer than
lbound
(lbound
is the threshold)  If the maximum matching is perfect, set
ubound
tolbound
.
 Find the maximum matching using only edges not longer than

ubound
is the final threshold. Return the maximum matching using using only edges not longer thanubound
.
This solution essentially repeatedly divides the set of possible thresholds in half, ignoring the half that is guaranteed not to contain the optimal solution, until it narrows the set to only two possible edge lengths.
In order to implement this, however, we have to have a method for finding the maximum matching with a given threshold. To do this, I used the Hopcroft–Karp algorithm. The Wikipedia explanation is somewhat hard to understand, so I will explain it slightly differently (but with the equivalent result).
First, I will describe an augmenting path. From Wikipedia:
An alternating path is a path in which the edges belong alternatively to the matching and not to the matching.
and
An augmenting path is an alternating path that starts from and ends on free (unmatched) vertices.
Here's an example: Let A, B, and C be sources, and D, E, and F be destinations, such that:
 A can connect to D and E
 B can connect to D and F
 C can connect to E only
 A and E are already matched
 B and D are matched
We want a perfect matching, but C and F are not matched, and in this case we can't match them directly. We can, however, generate an augmenting path. If we write the connections out like this:
EA DB
we can then insert C and F like this:
C EA DB F
This is our augmenting path, and it is important because we can swap the connections to form a better matching:
CE AD BF
The identification, construction, and swapping of augmenting paths is at the core of the HopcroftKarp algorithm.
 Create a connections matrix, such that
conn[i][j]
istrue
if and only if sourcei
and destinationj
have cost<= threshold
. (This is not technically part of the HopcroftKarp algorithm, but is necessary to use it with thresholding.) Then, until a maximum matching has been found:  Collect all nonmatched sources into
sourcequeue
, and label them all1
. Setnlevel
to2
.  For each source in
sourcequeue
, find all destinations reachable from it using theconn
matrix. Label those destinations with the value ofnlevel
, and add them intodestqueue
. Pop the sources off ofsourcequeue
after they are processed.  If there are no destinations in
destqueue
, STOP. This is the maximum matching.  If any of the destinations in
destqueue
are not matched, skip to step 10.  Increment
nlevel
.  For each dest in
destqueue
, add its currentlymatched source tosourcequeue
, and label itnlevel
. Pop the dests off ofdestqueue
after they are processed.  Increment
nlevel
.  Repeat from step 3.
 At this point, we have identified some number of unmatched destinations that can be paired with some of the unmatched sources by using an alternating path. (We start on an unmatched source, alternately find alreadymatched destinations and their alreadymatched sources, and end on an unmatched destination.) We will now try to swap in as many as possible.
 For each unmatched dest in
destqueue
: Find some source connected to this dest with label equal to its label minus one. (If there are none, STOP.)
 If this source is unmatched, we have an augmenting path! Swap the connections, delete all the labels along this path, and continue with the next dest in
destqueue
.  Otherwise, find it's matched destination. Recursively run these three steps again on that destination. If they succeed, continue. If they fail, find the next source connected to this dest, repeat from 1 on that source.
 Once all possible sources have been tried without a solution, STOP.
 If there are any more unmatched sources, repeat from step 2.
The HopcroftKarp algorithm and the threshold algorithm, used together, allow me to find the pairing of sources and destinations that can be reached in the least amount of time. It runs quite fast given that it is running in the browser. Most of the time, you can barely tell that it is processing. (Some of the larger animations take about a second, though. I might be able to optimize it more, but the delay doesn't bother me much.)
One thing I had to watch out for is the way that Google Chrome's V8 engine optimizes code. At one point, my threshold algorithm got stuck in an infinite loop because of a problem with how I calculated the median. Of course, Google Chrome did not know this was not intended behavior, and thus aggressively optimized the code for the loop. This meant that when I tried to add breakpoints and inspect variable values, it behaved erratically and did not allow me to debug effectively. My guess is that it had compiled that loop into machine code, and then couldn't translate the machine code's execution state back into an interactive debugger view and readevalprint loop. Interestingly, adding calls to console.log()
seemed to prevent this aggressive compilation.
In case the LBAP is relevant to anyone else's Javascript work, I've put the code for my implementation on GitHub, licensed under the MIT license.
Details on how to implement the thresholding solution taken from page 174 of Assignment Problems, by Rainer Burkard, Mauro Dell'Amico, and Silvano Martello.
Details on the Hopcroft–Karp algorithm taken from Wikipedia.