I packaged this up a couple of months ago but here is the official blog post
for backbone-filtermodule.
Documentation is in the README and examples in the examples directory.
I’ve been working on packaging up some components from my work with Engineers
Without Borders. One really great Knowledge Management Tool we use is buildling
timelines with TimelineJS. Our custom KM site is
written in Django and wanted an easy way to integrate timelines with the site,
so I created dj-timelinejs.
The package is pip-installable with pip install dj-timelinejs and provides
admin-interface access to created timelines and a bunch of class-based views
for viewing and importing existing timelines that you may have hosted in Google
Spreadsheets. Documentation is in the
README.
I’ve really enjoyed thinking about the puzzles at
http://gurmeet.net/puzzles/, especially
looking for ways to solve them or get hints as to how to solve them using
visualization without knowing the answers.
Last Time
I explored puzzle 11, Treasure Island, and this time I’ll look at puzzle 5, Fox
in a Hole.
Consider five holes in a line. One of them is occupied by a fox. Each night,
the fox moves to a neighboring hole, either to the left or to the right. Each
morning, you get to inspect a hole of your choice. What strategy would ensure
that the fox is eventually caught?
The Challenge
The question I asked was, can we, without knowledge of a working strategy,
create a fox that plays optimally against us so we can be sure we’ve come up
with a strategy that will work? We could simulate a fox that chooses to move
left or right randomly, but we would never be sure that our strategy is fool
proof. Can we make sure our fox plays hard to get if we don’t even know how
to catch it? Turns out we can. Try out the demo of my solution and see if you
can both figure out how to catch the fox and understand why a strategy works.
Implementation details are below the demo. Code is at
https://gist.github.com/azundo/5941503.
Instructions
Click on a hole to select it for inspection. You win if the fox has nowhere
left to hide. If you give up, click the button and one possible path the fox
could have taken to avoid your inspections will be shown.
A Quantum Fox
Instead of modeling our fox as being in one concrete location, we’ll keep track
of all possible holes the fox could be in at any given time without getting
caught, depending on which holes we have inspected in the past. We’ll use a
finite-state machine to
keep track of which holes the fox could be in. If we ever get to the state
where the fox couldn’t be in any holes without being caught, we know our
strategy is a good one. We don’t require any knowledge of the best path for
the fox to choose, or a winning strategy.
Our State Space
Each state in our state space will consist of all of the possible holes the fox
could be in at any one time. There are 5 holes and each hole has two states: it
is either possible for the fox to be in that hole, or not possible. This gives
us a state space of size 2^5 = 32. We could model this as a bit vector with 5
bits, but for clarity I will use a simple array. If it is possible for the fox
to be in hole i, then our state array will contain i. We’ll number our
holes 0, 1, 2, 3, 4.
For example, before we check any holes, our state would be [0, 1, 2, 3, 4].
The fox could be in any hole. If we check hole 2, then our state would move
to [0, 1, 3, 4]. In the case where there is no possible hole for our fox to
be in without catching him at some point, our state is an empty array [].
State Transitions
The key implementation detail when using a state machine is our state
transitions. How do we decide which state we move to next? In our case our next
state is dependent on two things, our previous state (the set of possible holes
the fox could have been in yesterday) and our selection of which hole to check.
To start let’s forget about the action of checking a hole. How can we determine
what holes the fox can be in based on what holes it could have been in
yesterday? If it was possible for the fox to be in hole i yesterday, then it
is possible for the fox to be in any hole beside i today. If we iterate over
all of the holes that the fox could have been in yesterday then we’ll get the
set of holes it could be in today.
We’ll use a very simple adjacency list to make our lives easy. If we access
element i of the adjacency list we will get back an array containing all of
the holes next to i.
12345678910
varADJACENCY_LIST=[// hole 0 is next to hole 1[1],// hole 1 is next to hole 0 and hole 2[0,2],// etc.[1,3],[2,4],[3]];
This adjacency list defines a
very simple graph where
each hole is a node connected by edges to each of its adjacent holes. The first
and last holes only have one adjacent hole (and thus one edge) while the others
have two.
Accessing element 0 of our ADJACENCY_LIST tells us which holes are next
to hole 0. If we want to know the set of possible future holes, we take the
set of possible past holes and add all of the adjacent holes. Simple enough.
Lastly we don’t include the hole that we chose to inspect since the fox would
get caught if he ended up there. Hence, our transition function looks like this:
functionnextState(pastState,guess){/* * Calculates our next state based on the past state and * the next hole to be inspected. */varnext=[],i,j,possiblePastHole,possibleNextHoles,possibleNextHole;for(i=0;i<pastState.length;i++){// any value in our pastState represents a hole that// the fox was possibly in yesterdaypossiblePastHole=pastState[i];// look up holes next to the possiblePastHole in our ADJACENCY_LISTpossibleNextHoles=ADJACENCY_LIST[possiblePastHole];for(j=0;j<possibleNextHoles.length;j++){// any holes that are ajacent to a possible hole// from the pastState are valid holes for the fox in// the next state, provided that hole wasn't// inspected. Note that the fox cannot stay in the// same hole, it has to move to an adjacent hole.possibleNextHole=possibleNextHoles[j]// don't add holes that are already in the next// state array since our state is the set of// possible holesif(possibleNextHole!==guess&&next.indexOf(possibleNextHole)===-1){next.push(possibleNextHole);}}}returnnext;}
If we ever end up with an empty state, the fox has nowhere to go. We must have
caught it at some point, no matter where it started and how it decided to move.
Every time we select a hole to inspect, we’ll update our state and push a copy
of it onto an array to keep track of what states we’ve been through in the
past. We’ll use that later.
1234567891011
functionselectHole(selection){// update state informationstate=nextState(state,selection);stateHistory.push(state.slice());// if there are no possible holes for the fox to be in, we caught him!if(state.length===0){foxCaught(selection);}else{advanceOneDay(selection);}}
Reconstructing the Fox’s Moves
If we save each state we reach, we can reconstruct a possible path the fox
could have taken to get to the current state. Let’s choose any arbitrary hole
from the current state, and work backwards by looking for adjacent holes in the
previous state. We are guaranteed to find a backwards path since every hole in
our current state must be possible. Here is the code:
functiongetPossibleSequence(){// only depends on stateHistory, an array of our past statesvari,finalState,stateToDetermine,possibleHoles,possibleHole,seq=[];if(stateHistory.length===0){returnseq;}finalState=stateHistory.pop();// pick whatever hole happens to be listed first in the// final state to end our sequence.seq.unshift(finalState[0]);// work backwards through the state history, picking a// valid state from each entry and unshifting it onto// the front of the sequencewhile(stateHistory.length>0){stateToDetermine=stateHistory.pop();// find a hole beside the hole at the front of our// sequence since our 'graph' is not directed, we can// safely use the same adjacency values to move// backwards through the state listpossibleHoles=ADJACENCY_LIST[seq[0]];for(i=0;i<possibleHoles.length;i++){possibleHole=possibleHoles[i];// if the possible hole is in our stateToDetermine, use it.if(stateToDetermine.indexOf(possibleHole)!==-1){seq.unshift(possibleHole);break;}}}returnseq;}
You could also make solving the puzzle a bit easier if you showed all possible
holes the fox could be in as you go along, instead of only showing one possible
path at the end. Feel free to fork and implement this as a good exercise in d3
basics.
SPOILER ALERT. This post contains an answer to puzzle 11 Treasure Island from
http://gurmeet.net/puzzles which appeared on Hacker News recently. If you
want to solve it yourself first, check it out over there before reading on, or
just don’t read too far down the page.
The Puzzle
Here is the wording of the puzzle:
An old parchment has directions to a treasure chest buried in an island:
There is an unmarked grave and two tall oak trees. Walk from the grave to the
left tree, counting the number of steps. Upon reaching the left tree, turn left
by 90 degrees and walk the same number of steps. Mark the point with a flag.
Return to the grave. Now, walk towards the right tree, counting the number of
steps. Upon reaching the right tree, turn right by 90 degrees and walk the same
number of steps. Mark this point with another flag. The treasure lies at the
midpoint of the two flags.
A party of sailors reached the island. They find a pair of tall oak trees
merrily swaying in the wind. However, the unmarked grave is nowhere to be
found. They are planning to dig up the entire island. It'll take a month. Can
they do any better?
My high school geometry is a little fuzzy so I thought I’d do a little
empirical playing around with d3.js to get a sense of the answer before trying
to work out the math. Almost a sort of graphical brute force method. If you’re new
to d3.js this should hopefully act as a good introduction as well.
We’ll start with a little bit of d3 boilerplate to set things up. There are a
few g elements to get our layers working properly but hopefully the comments
in the code make things clear.
12345678910
varwidth=960,height=600,// our svg containersvg=d3.select('body').append('svg').attr('width',width).attr('height',height),// a group within our container that will hold our map featuresfeatures=svg.append('g'),// a group within our features group that will show some of the underlying geometrygeometries=features.append('g');
Next lets set up some parameters for our treasure island.
12345678910111213141516171819
varislandRadius=300,// size of the features we are plotting on the mapfeatureLength=30,// a magic number for placing our trees. Feel free to play around with this number.treeOffset=210,// an array of tree objects with x and y properties// our trees will have the same y coordinate and x coordinates centered// around the middle of the island.trees=[{x:treeOffset,y:treeOffset},{x:islandRadius*2-treeOffset,y:treeOffset}],// an arbitrary initial point for our grave, we'll easily change it later through the graphic.grave={x:islandRadius,y:islandRadius};
Plotting the Static Features
Now we’re ready to plot the static component of our map - the island and the trees.
123456789101112131415161718192021222324
// create the island on top of everything. If we draw our features "over top"// of the island then they will interfere with our event handling. Appending to// the end of the svg container will put the island last in the svg hierarchy// so it will always be on top. We'll give it a transparent fill so we can see// through it.svg.append('circle').attr('r',islandRadius).attr('cx',islandRadius).attr('cy',islandRadius).classed('island',true);// create the trees - these are static so only draw them oncefeatures.selectAll('.tree').data(trees).enter().append('image').attr('xlink:href','images/tree.svg').attr('width',featureLength).attr('height',featureLength)// getX and getY are simple helper functions to return properly offset x// and y coords for our square features.attr('x',getX).attr('y',getY).classed('tree',true);
If we fire this code up you’ll see the following:
Looking good. A couple of trees. Time to get plotting our flags and ultimately the
treasure chest location.
Adding Flags
The tricky part here is getting the geometry right when calculating the
location of the flags for a given location of the grave. By filling in a couple
of extra triangles it becomes clear how we can do it. Here’s a quick diagram
for the left tree:
Remembering that the y-coordinate values increase downwards on our svg canvas, we can see a
couple of equivalent triangles marked by the red, blue and black lines. The
black lines are the path our pirate would mark out,
the red is the y-difference between the grave and the tree,
and and the blue is the x-difference between the grave and the tree.
The coordinates of the left
flag are then given by:
If we swap the grave and the flag in the above diagram, we can work out the
case for the right tree, turning to the right instead of the left:
So we end up with the following function for calculating our flag placements:
12345678910111213141516171819202122232425
// calculate the positions of the flagsfunctiongetFlagPositions(treePositions,gravePosition){varleftTree,rightTree,rise,run,leftFlag,rightFlag;leftTree=treePositions[0];rightTree=treePositions[1];// get left flag positionrise=gravePosition.y-leftTree.y;run=gravePosition.x-leftTree.x;// turn 90 to the leftleftFlag={x:leftTree.x-rise,y:leftTree.y+run};// get right flag positionrise=gravePosition.y-rightTree.y;run=gravePosition.x-rightTree.x;// turn 90 to the rightrightFlag={x:rightTree.x+rise,y:rightTree.y-run};return[leftFlag,rightFlag];}
We’ll need to dynamically update the positions of these flags so lets create a
draw function and call it. At the same time we’ll draw our grave in as well as
the triangles that show the walking directions for illustrative purposes. Check
out the final version of the code to
see the full getPathPoints function.
functiondraw(){// calculate positionsvarflags=getFlagPositions(trees,grave),paths=getPathPoints(trees,flags,grave);// draw the gravefeatures.selectAll('.grave').data([grave]).attr('x',getX).attr('y',getY).enter().append('image').attr('xlink:href','img/grave.svg').classed('grave',true).attr('height',featureLength).attr('width',featureLength).attr('x',getX).attr('y',getY);// draw the flagsfeatures.selectAll('.flag').data(flags).attr('x',getX).attr('y',getY).enter().append('image').attr('xlink:href','img/flag.svg').classed('flag',true).attr('height',featureLength).attr('width',featureLength).attr('x',getX).attr('y',getY);// draw triangles showing the flag calculations// these are in the geometries group so they appear underneath the other featuresgeometries.selectAll('.flag-path').data(paths).attr('d',line).enter().append('path').classed('flag-path',true).attr('d',line);}draw();
We’re getting somewhere. Now lets connect our mouse position to the
grave position and watch our flags dance around.
Making the Flags Move
123456789
// move grave location to wherever the mouse issvg.select('.island').on('mousemove',function(){// 8 is a magic number to make things look nice, on my screen at least.varmousePosition=d3.mouse(this);grave.x=mousePosition[0]-8;grave.y=mousePosition[1]-8;draw();});
Can you guess the answer to the riddle yet? Let’s add a calculation of the
flags’ midpoint and plot our treasure chest on the map.
The Chest
1234567891011121314151617181920212223242526
// modified draw functionfunctiondraw(){...vartreasure=getTreasurePosition(flags);// draw the treasure locationfeatures.selectAll('.treasure').data([treasure]).attr('x',getX).attr('y',getY).enter().append('image').attr('xlink:href','img/treasure_chest.svg').classed('treasure',true).attr('height',featureLength).attr('width',featureLength).attr('x',getX).attr('y',getY);...}functiongetTreasurePosition(flagPositions){// averages the x and y values of the two flag positionsreturn{x:(flagPositions[0].x+flagPositions[1].x)/2,y:(flagPositions[0].y+flagPositions[1].y)/2}}
Success! We’ve now got a clear answer - there’s only a single location where
the chest could be. If you play around with the grave position it becomes
obvious that the chest’s x-coordinate is the midpoint of the two trees’
x-coordinates and the y coordinate is simply that same midpoint distance added
to the y-coordinate of the trees. Here we’re assuming the trees are at the same
y-coordinate and remember that y increases in the downward direction on our
screen. (The y-coordinate assumption is ok because we could always redraw our
coordinate system so that the two trees are level in the y direction.)
The Math
Now that we’ve played around with getting the example to work and
seen that it is a single point solution (not a line or other area function) we
can take a more informed approach to the math.
The X-coordinate
We’ll use the trick that our x and y coordinates are independent. Lets work in
the x-direction first. We know our final x-coordinate is the average of our two
flags’ x-coordinates. Lets start with the left tree’s flag. Here we use
as the left tree’s x-coordinate, as the left flag’s
x-coordinate, as the grave’s x-coordinate and (since X
marks the spot) as the chest’s x-coordinate. Going back to our earlier
formulas:
Averaging these two we can see that our $g_{y}$ term cancels out.
In our case where we get as the average of
and , not dependent on the graveyard location, as we saw
in our brute force method.
The Y-coordinate
Now we can do the same for the y-coordinate.
In the case where
then
, the result we saw earlier in
the brute force method.
One More Thing
We actually don’t have it quite right yet, there is an omission. In the cases
where the grave lies above the trees (from our vantage point looking down at
the map of the island) the left and right trees are actually reversed. Here’s
the final implementation accounting for this possibility. Check out the
gist at
https://gist.github.com/azundo/5928203
for the full final version.
Conclusion
So that’s it. A quick prototype in D3 to brute force our solution so we’ve got
some intution on how to go about solving the geometry. Great practice in
getting simple things done using d3.js and jogging the old geometry proofs
portion of the brain.
Attributions
Thanks to the folks over at The Noun Project for
their svg icon sets. Here are the attributions:
After my past attempt at writing a
concurrent Qsort algorithm I had a few more thoughts about how to change the
architecture.
Instead of creating new channels to pass to every recursively-called goroutine
and then blocking on them until they return, I wanted to create only a single
channel for communication and find a way to return from goroutines immediately.
The solution I came up with is to send back the integer value of the number of
elements in their sorted position when a goroutine returns. In the naive case,
this is when the list is 0 or 1 elements long, leaving this fairly simple code.
12345678910111213141516171819202122232425262728
funcCqsort2(s[]int){// this channel will collect the number of sorted elementsreturnChannel:=make(chanint)gocqsort2(s,returnChannel)// sum up the number of sorted elements until they equal// the length of our original sliceforsortedElements:=0;sortedElements<len(s);{sortedElements+=<-returnChannel}return}funccqsort2(s[]int,donechanint){iflen(s)<=1{// report the number of sorted elements to the// communication channeldone<-len(s)return}pivotIdx:=partition(s)gocqsort2(s[:pivotIdx+1],done)gocqsort2(s[pivotIdx+1:],done)// this goroutine should now return immediately and// doesn't have to block on the child callsreturn}
This still creates too many goroutines and uses too much memory. So taking a
page from most quicksort implementations, lets use a selection sort for the last
few elements. Empirically I found a value of about 75 to be ok. Our overall
architecture doesn’t have to change, just add the selection sort call in the
termination condition of our qsort2 function.
123456789101112131415161718
funccqsort2(s[]int,donechanint){iflen(s)<=75{// run a selection sort when s is smallselectionSort(s)// report the number of sorted elements to the// communication channeldone<-len(s)return}pivotIdx:=partition(s)gocqsort2(s[:pivotIdx+1],done)gocqsort2(s[pivotIdx+1:],done)// this goroutine should now return immediately and// doesn't have to block on the child callsreturn}
Finally when using GOMAXPROCS=2 I got a better running time for the concurrent
version over the non-concurrent Qsort from my last post. This isn’t quite a fair
comparison though because I wasn’t using the selectionSort trick in Qsort.
Adding it in to Qsort and our previous Cqsort brings all three implementations
to about 7s to sort 1 milllion elements. So still no improvements over a
sequential implementation despite using both of my cores at 100% in the
concurrent cases. Memory and communication overhead still provide too much of a
slow down. I’m hoping to get my hands on a computer with 4 cores to see if the
concurrent version will see a speedup when doubling the core count again, or if
communication overhead is still too high.
I’ve been playing around with Go to get some experience in a systems programming
language before applying for applying jobs. I’ve never done concurrent/parallel
programming so I thought I’d try to learn about some of Go’s concurrency tools
by implementing quicksort concurrently.
I started by writing a simple in-place quicksort implementation. The majority of
the algorithm happens in a partition function which picks a random pivot and
then does in-place swapping to partition around the pivot. With this in place
the sequential algorithm falls into place easily.
Since the divide and conquer nature of quicksort means the recursive calls to
Qsort don’t touch the same memory, this should be a decent candidate for
concurrency.
1234567891011121314151617181920212223242526272829
funcCqsort(s[]int){d:=make(chanint)gocqsort(s,d)<-dreturn}funccqsort(s[]int,donechanint){// termination conditioniflen(s)<=1{done<-1return}// where the work happenspivotIdx:=partition(s)// communication channelchildChan:=make(chanint)gocqsort(s[:pivotIdx+1],childChan)gocqsort(s[pivotIdx+1:],childChan)// block until both concurrent children finishfori:=0;i<2;i++{<-childChan}// tell our caller we are donedone<-1return}
This works but is incredibly slow. Goroutines are cheap but not free. For large
s this program spends most of its time in garbage collection as too many
goroutines are created.
funcCqsort(s[]int){iflen(s)<=1{return}workers:=make(chanint,MAXGOROUTINES-1)fori:=0;i<(MAXGOROUTINES-1);i++{workers<-1}cqsort(s,nil,workers)}funccqsort(s[]int,donechanint,workerschanint){// report to caller that we're finishedifdone!=nil{deferfunc(){done<-1}()}iflen(s)<=1{return}// since we may use the doneChannel synchronously// we need to buffer it so the synchronous code will// continue executing and not block waiting for a readdoneChannel:=make(chanint,1)pivotIdx:=partition(s)select{case<-workers:// if we have spare workers, use a goroutine// for parallelizationgocqsort(s[:pivotIdx+1],doneChannel,workers)default:// if no spare workers, sort synchronouslycqsort(s[:pivotIdx+1],nil,workers)// calling this here as opposed to using the deferdoneChannel<-1}// use the existing goroutine to sort above the pivotcqsort(s[pivotIdx+1:],nil,workers)// if we used a goroutine we'll need to wait for// the async signal on this channel, if not there// will already be a value in the channel and it shouldn't block<-doneChannelreturn}
Setting MAXGOROUTINES limits the number of goroutines that ever get created by
switching to a synchronous model once the workers channel is exhausted.
This performs much better than before. Benchmarking puts it at about the same
speed as the built-in sort.Ints, but still slower than our basic Qsort
implementation for a shuffled slice of 1 million elements created by
math/rand.Perm. Playing around with MAXGOROUTINES I seemed to get slight
variations when using numbers anywhere from 2 to 10000 (make sure you have the
GOMAXPROCS environment variable set to the number of cores you want to use
so that goroutines are executed in parallel). Above 10000 and performance starts
to degrade.
This use of Go’s concurrency features purely for the purpose of parallelizing
code goes against Rob Pike’s “Concurrency is not Parallelism” talk, so I’m not
surprised that I don’t see a significant speedup when trying to parallelize this
concurrent code against the sequential version. I am surprised that I don’t get
similar speeds to the sequential version when setting MAXGOROUTINES to 1 as the
code is essentially executing sequentially in this case. Perhaps the few extra
statements and branches are enough to slow things down considerably. In any case
it was a good experiment in writing concurrent Go that also forced me to dive
into profiling with pprof and using Go’s support for writing benchmarks in test
code.
Code is all up on github at (https://github.com/azundo/cqsort).
A new day and a new blog. As I transition from my past role as a Market
Development Specialist with Engineers Without Borders Canada toward a more
technically focused time, I thought it might be useful to start a more
technical blog. At one point I had intended to write about technical things
over at http://theborrowedbicycle.ca but I’ll keep that for thoughts on
personal and human development instead of design and engineering.
The intention of this blog is to keep track of what I’m learning and thinking
about as I get my coding chops back to re-enter the technical world. Right now
my goal is to simply use this blog to record my progress and learnings for
myself and to continue to work on my writing skills and technical
communication. I’ve got a few projects that I hope to blog about as I work on
them over the summer, aiming to land a job as a software engineer starting in
September.