|
<!doctype html> |
|
<html> |
|
<head> |
|
<title>The Fox Puzzle</title> |
|
<script type="text/javascript" charset="utf-8" src="http://d3js.org/d3.v3.min.js"></script> |
|
<style> |
|
.fox-hole.selected { |
|
fill: white; |
|
stroke: black; |
|
} |
|
#fox { |
|
overflow: auto; |
|
min-height: 300px; |
|
width: 600px; |
|
} |
|
</style> |
|
</head> |
|
<body> |
|
<div id="fox"> |
|
</div> |
|
<script type="text/javascript"> |
|
(function(){ |
|
var |
|
foxHoleR = 45, |
|
xOffset = foxHoleR*2 + 15, |
|
yOffset = foxHoleR/4 + 40, |
|
container = d3.select('#fox'), |
|
svg, |
|
currentDay, |
|
button, |
|
selector, |
|
|
|
/* |
|
* State machine functions |
|
* |
|
* In this example, a state is the set of possible holes that the fox could |
|
* be in on a given day after accounting for the farmer's strategy up to that |
|
* point. |
|
* |
|
* For example on the first day, after the farmer inspects a hole, it is |
|
* possible that the fox is in any of the other holes, so the state for the |
|
* first day would have four entries. |
|
* |
|
* We could represent our state space as a 5-bit bit vector, where a bit is |
|
* on if the fox could be in that hole, and off if the fox couldn't be in |
|
* that hole. I think this representation (an array of possible values) is a |
|
* bit easier to follow and less accessible bit manipulation. |
|
*/ |
|
|
|
ADJACENCY_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] |
|
], |
|
state, |
|
stateHistory; |
|
|
|
|
|
function nextState(pastState, guess) { |
|
/* |
|
* Calculates our next state based on the past state and the next hole to be inspected. |
|
*/ |
|
var next = [], 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 yesterday |
|
possiblePastHole = pastState[i]; |
|
|
|
// look up holes next to the possiblePastHole in our ADJACENCY_LIST |
|
possibleNextHoles = 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 holes |
|
if (possibleNextHole !== guess && next.indexOf(possibleNextHole) === -1) { |
|
next.push(possibleNextHole); |
|
} |
|
} |
|
} |
|
return next; |
|
} |
|
|
|
function getPossibleSequence() { |
|
// only depends on our stateHistory |
|
var i, finalState, stateToDetermine, possibleHoles, possibleHole, seq = []; |
|
if (stateHistory.length === 0) { |
|
return seq; |
|
} |
|
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 sequence |
|
while (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 list |
|
possibleHoles = 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; |
|
} |
|
} |
|
} |
|
return seq; |
|
} |
|
|
|
/* |
|
* End of State Machine Functions |
|
*/ |
|
|
|
function selectHole(selection) { |
|
// update state information |
|
state = 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); |
|
} |
|
} |
|
|
|
function foxCaught(selection) { |
|
alert("You got him!"); |
|
// remove the selector |
|
selector.remove(); |
|
|
|
// our last state was where we caught the fox, so remove the empty state |
|
// and push on a state containing the selection that caught the fox. |
|
stateHistory.pop(); |
|
stateHistory.push([selection]); |
|
|
|
// draw the current selection |
|
drawHoles(currentDay, currentDay, selection); |
|
|
|
// draw all foxes in |
|
drawFoxes(); |
|
|
|
// reset the button |
|
button |
|
.text('Try Again') |
|
.on('click', init); |
|
} |
|
|
|
function advanceOneDay(selection) { |
|
|
|
// increase size of container div and/or svg canvas |
|
updateCanvasSizes(); |
|
|
|
// move the selector down |
|
moveSelector(); |
|
|
|
// draw in row with our selection |
|
drawHoles(currentDay, currentDay, selection); |
|
|
|
// fill in 'missed' label |
|
labelMissed(currentDay, selection); |
|
|
|
// increase our day counter |
|
currentDay += 1; |
|
|
|
} |
|
|
|
init(); |
|
|
|
function init() { |
|
state = [0, 1, 2, 3, 4]; |
|
stateHistory = []; |
|
container.html(''); |
|
svg = container.append('svg') |
|
.attr('width', 600) |
|
.attr('height', 2*yOffset); |
|
currentDay = 0; |
|
button = container.append('button') |
|
.text('I give up. Show me the fox!') |
|
.on('click', giveUp); |
|
selector = drawHoles('selector', 0); |
|
selector.selectAll('.fox-hole') |
|
.on('mouseover', function() { |
|
d3.select(this).classed('selected', true); |
|
}) |
|
.on('mouseout', function() { |
|
d3.select(this).classed('selected', false); |
|
}) |
|
.on('click', function() { |
|
// pull the hole number from the id. XXX pretty hacky |
|
var selection = parseInt(d3.select(this).attr('id').split('-').pop()); |
|
selectHole(selection); |
|
}); |
|
}; |
|
|
|
|
|
function giveUp() { |
|
selector.remove(); |
|
// case where the user didn't make any guesses, put the fox in the first hole |
|
if (stateHistory.length === 0) { |
|
drawHoles(currentDay, currentDay); |
|
drawFox(currentDay, 0); |
|
} |
|
else { |
|
drawFoxes(); |
|
} |
|
button |
|
.text('Try Again') |
|
.on('click', init); |
|
} |
|
|
|
/* |
|
* D3 Drawing functions |
|
*/ |
|
|
|
function drawHoles(idSuffix, row, selected) { |
|
var i, hole, holes = svg.append('g') |
|
.attr('id', 'fox-holes-' + idSuffix) |
|
.attr('transform', 'translate(0,' + ((row+1) * yOffset) + ')'); |
|
holes.append('text') |
|
.text('Day ' + (row + 1)) |
|
.attr('y', yOffset / 4); |
|
for (i = 0; i < 5; i++) { |
|
hole = holes.append('ellipse') |
|
.attr('id', 'fox-hole-' + idSuffix + '-' + i) |
|
.attr('rx', foxHoleR) |
|
.attr('ry', foxHoleR / 4) |
|
.attr('cx', i * xOffset + xOffset) |
|
.attr('cy', foxHoleR / 4 ) |
|
.classed('fox-hole', true); |
|
if (i === selected) { |
|
hole.classed('selected', true) |
|
} |
|
} |
|
return holes; |
|
} |
|
|
|
function drawFoxes() { |
|
var seq = getPossibleSequence(), i; |
|
for (i=0; i < seq.length; i++) { |
|
drawFox(i, seq[i]); |
|
} |
|
} |
|
|
|
function drawFox(row, hole) { |
|
d3.select("#fox-holes-" + row) |
|
.append('image') |
|
.attr('xlink:href', 'fox_white.svg') |
|
.attr('width', foxHoleR) |
|
.attr('height', foxHoleR) |
|
.attr('x', (hole+1) * xOffset - foxHoleR / 2 ) |
|
.attr('y', -1 * foxHoleR / 2 ); |
|
} |
|
|
|
function updateCanvasSizes() { |
|
// increase size of svg canvas if need be |
|
if (svg.attr('height') < (currentDay + 3) * yOffset) { |
|
svg.attr('height', (currentDay + 3) * yOffset); |
|
} |
|
// add to container's height if it's too small |
|
// to facilitate scrolling |
|
var containerHeight = parseInt(container.style('min-height')); |
|
if (containerHeight < (currentDay + 3) * yOffset) { |
|
container.style('min-height', (containerHeight + yOffset*5) + 'px'); |
|
} |
|
} |
|
|
|
function moveSelector() { |
|
selector |
|
.transition() |
|
.attr('transform', 'translate(0,' + (currentDay+2) * yOffset + ')'); |
|
selector.select('text') |
|
.text('Day ' + (currentDay+2)); |
|
// mouseout doesn't fire when using transform to move the selector until the mouse |
|
// is moved again, so manually de-select the hole |
|
selector.select('.fox-hole.selected') |
|
.classed('selected', false); |
|
} |
|
|
|
function labelMissed(row, selection) { |
|
d3.select("#fox-holes-" + row) |
|
.append('text') |
|
.text('Missed!') |
|
.attr('x', (selection+1) * xOffset - foxHoleR / 2 ) |
|
.attr('y', foxHoleR / 3); |
|
} |
|
|
|
})(); |
|
</script> |
|
</body> |
|
</html> |