This morning, [Bill] Tozier posted an interesting problem:

In one of the best puzzle collections I know, Peter Winkler’s ​Mathematical Mind Benders​, is a little quickie that seems like it’d be interesting to un-quicken. The original is something like: “Three spiders and an ant are walking on a framework in the shape of the edges of a cube. The spiders want to eat the ant, and they all walk at last 1/3 as fast as the ant walks. Prove that some spider can catch the ant.”

We were meeting today at the Brighton Agile Roundtable, and we decided to play with the ant problem in codea. It turned out to be fun, and a good way to think about the problem from a programming viewpoint if not from a formal mathematical one.

We began by drawing a projection of a cube:

function draw()
    background(140, 140, 150)
    strokeWidth(5)
    drawCubes()
end

function drawCubes()
    rectMode(CENTER)
    fill(0,0,0,0)
    lineCapMode(SQUARE)
    rect(center.x, center.y, 400, 400)
    rect(center.x, center.y, 800, 800)
    translate(center:unpack())
    line(200,200, 400, 400)
    line(-200,-200, -400, -400)
    line(-200,200, -400, 400)
    line(200,-200, 400, -400)
end

Then we wrote a little table for our ant, so we could draw him at any fraction of the way along a line. We went through a few iterations of this and quickly wound up with a table of corners, a table of edges, and this code:


corners = { 
    vec2(-400, -400), vec2(-400,400 ), vec2(400, 400), vec2(400, -400),
    vec2(-200, -200), vec2(-200,200 ), vec2(200, 200), vec2(200, -200)
}

cube = { {2,4,5}, {1,3,6}, {2,4,7}, {1,3,8}, {1,6,8}, {2,5,7}, {3,6,8}, {4,5,7} }

ant = {}
ant.start = 1
ant.stop = 2
ant.frac = math.random()
ant.speed = speed*3
ant.nextGoal = nextGoal

function draw()
    background(140, 140, 150)
    strokeWidth(5)
    drawCubes()
end

function drawCubes()
    rectMode(CENTER)
    fill(0,0,0,0)
    lineCapMode(SQUARE)
    rect(center.x, center.y, 400, 400)
    rect(center.x, center.y, 800, 800)
    translate(center:unpack())
    line(200,200, 400, 400)
    line(-200,-200, -400, -400)
    line(-200,200, -400, 400)
    line(200,-200, 400, -400)
    progress()
end

function progress()
    moveBug(ant)
    drawBug(ant, color(0,255,0))
end

function moveBug(aBug)
    aBug.frac = aBug.frac + aBug.speed
    if aBug.frac > 1 then
        aBug.start = aBug.stop
        aBug.stop = aBug.nextGoal(aBug.start)
        aBug.frac = 0
    end
    aBug.pos = (1-aBug.frac)*corners[aBug.start] + aBug.frac*corners[aBug.stop]
end

function drawBug(aBug, col)
    pushMatrix()
    pushStyle()
    translate(aBug.pos.x, aBug.pos.y)
    stroke(col)
    fill(col)
    ellipse(0,0,20,20)
    popStyle()
    popMatrix()
end

We had a rudimentary verson of the nextGoal function, which we used for an interim version that just drove the ant around the screen. This code just selects one of the three lines leading away from the corner we just arrived at:

function nextGoal(index)
    local choice = math.random(3)
    local choices = cube[index]
    return choices[choice]
end

The result was that the ant runs around the cube randomly, as desired:

Note: If video stalls, click the YouTube button in the embedded one and then refresh when you get to YouTube. I have no idea why it’s doing that.

It’s worth remarking on our approach to the ant. Instead of making him an object with a class, he’s just a table with some values:

ant = {}
ant.start = 1
ant.stop = 2
ant.frac = math.random()
ant.speed = speed*3
ant.nextGoal = nextGoal

All these are fairly straightforward: we start him on corner 1, heading toward corner 2. At first we started him at zero but when we implemented the spiders, we had everyone starting at zero and that was boring, because everyone arrived at the corners at the same time, so we started them all at a random fraction 0-1 along the line.

But what about that line

ant.nextGoal = nextGoal

Well, that second nextGoal refers to the nextGoal function up above. We see it being called here:

function drawCubes()
    rectMode(CENTER)
    fill(0,0,0,0)
    lineCapMode(SQUARE)
    rect(center.x, center.y, 400, 400)
    rect(center.x, center.y, 800, 800)
    translate(center:unpack())
    line(200,200, 400, 400)
    line(-200,-200, -400, -400)
    line(-200,200, -400, 400)
    line(200,-200, 400, -400)
    progress()
end

function progress()
    moveBug(ant)
    drawBug(ant, color(0,255,0))
end

function moveBug(aBug)
    aBug.frac = aBug.frac + aBug.speed
    if aBug.frac > 1 then
        aBug.start = aBug.stop
        aBug.stop = aBug.nextGoal(aBug.start)
        aBug.frac = 0
    end
    aBug.pos = (1-aBug.frac)*corners[aBug.start] + aBug.frac*corners[aBug.stop]
end

function drawBug(aBug, col)
    pushMatrix()
    pushStyle()
    translate(aBug.pos.x, aBug.pos.y)
    stroke(col)
    fill(col)
    ellipse(0,0,20,20)
    popStyle()
    popMatrix()
end

All this comes down to moving the bug along his line, incrementing the fraction by the speed value, and when the fraction exceeds 1, set his start to his previous stop, pick a new goal, and keep on keeping on.

The drawing is simple, we just translate to where the bug is (somewhere along his line), and draw a circle.

We went through a phase where we created three spiders and made them work the same way, except at slower speed:

s1 = {}
s1.start = 2
s1.stop = 6
s1.frac = math.random()
s1.speed = speed
s1.nextGoal = nextGoal

s2 = {}
s2.start = 7
s2.stop = 3
s2.frac = math.random()
s2.speed = speed
s2.nextGoal = nextGoal

s3 = {}
s3.start = 4
s3.stop = 1
s3.frac = math.random()
s3.speed = speed
s3.nextGoal = nextGoal

We extended the progress function to move and draw all four bugs:

function progress()
    moveBug(ant)
    moveBug(s1)
    moveBug(s2)
    moveBug(s3)
    drawBug(s1, color(255,0,0))
    drawBug(s2, color(255,0,0))
    drawBug(s3, color(255,0,0))
    drawBug(ant, color(0,255,0))
end

This gave us three red spiders and one green ant, running around randomly. They’d run right over each other so we decided to make the game stop when the ant collides with a spider:

local dead = false

function progress()
    if ( not dead ) then
        moveBug(ant)
        moveBug(s1)
        moveBug(s2)
        moveBug(s3)
    end
    dead = isAntDead()
    drawBug(s1, color(255,0,0))
    drawBug(s2, color(255,0,0))
    drawBug(s3, color(255,0,0))
    drawBug(ant, color(0,255,0))
end

function isAntDead()
    local radius = 10
    local pos = ant.pos
    if pos:dist(s1.pos) < radius then return true end
    if pos:dist(s2.pos) < radius then return true end
    if pos:dist(s3.pos) < radius then return true end
    return false
end

The isAntDead function just checks to see if the ant is within ten pixels!pixels of any spider and if it is, we stop moving (but keep drawing, so the screen doesn’t go blank).

This worked fine and results in the halt you see in the final video below.

But we noticed one more thing. Because the ant selects its edge randomly, it has a good chance of selecting an edge that has a spider coming the other way, with tragic results for our poor ant. So we changed things to give the ant its own way of selecting an edge. That turned out to be a bit tricky but not bad:

ant = {}
ant.start = 1
ant.stop = 2
ant.frac = math.random()
ant.speed = speed*3
ant.nextGoal = nextAntGoal

function nextAntGoal(index)
    local choice
    local choices = shuffle(cube[index])
    local try = 1
    while try < 3 do
        choice = choices[try]
        if safeEdge(index, choice) then 
            return choice 
        end
        try = try + 1
    end
    return choice
end

We give the ant its own way of selecting the next goal, as shown above. We create a shuffled selection of edge choices, because we’re going to go through them to find a safe one. Then we try the first two to see if they are safe. If they are, we choose them. If they are not safe, we take the third choice. (You could imagine a more clever ant. For example, it might choose the path where the spider is furthest away, then wait a while and double back. Or it might just check to see if the spider is moving away on any of those edge, and go down that one, slowing down. And so on. For now, the ant isn’t that smart.)

To shuffle the edges we made a list of the integers 1,2,3, selected one at random, picked that edge, repeated, and took the last:

function shuffle(tab)
    local dex = {1,2,3}
    local res = {}
    local next
    next = math.random(1,3)
    table.insert(res, tab[dex[next]])
    table.remove(dex, next)
    next = math.random(1,2)
    table.insert(res, tab[dex[next]])
    table.remove(dex, next)
    table.insert(res, tab[dex[1]])
    return res
end

function safeEdge(start, stop)
    return not spiderOn(start,stop)
end

function spiderOn(start, stop)
    return thisSpiderOn(s1, start, stop) or thisSpiderOn(s2, start, stop) or thisSpiderOn(s3,start,stop)
end

function thisSpiderOn(spider, start, stop)
    return (spider.start == start and spider.stop == stop) or (spider.stop == start and spider.start == stop)
end

The final run. Will the ant elude the spiders? The answer may surprise you!

“Final” program:

-- Ant and Spiders

corners = { 
    vec2(-400, -400), vec2(-400,400 ), vec2(400, 400), vec2(400, -400),
    vec2(-200, -200), vec2(-200,200 ), vec2(200, 200), vec2(200, -200)
}

cube = { {2,4,5}, {1,3,6}, {2,4,7}, {1,3,8}, {1,6,8}, {2,5,7}, {3,6,8}, {4,5,7} }

local speed = 0.005
local dead = false

function nextGoal(index)
    local choice = math.random(3)
    local choices = cube[index]
    return choices[choice]
end

function nextAntGoal(index)
    local choice
    local choices = shuffle(cube[index])
    --print("choices " .. choices[1] .. ", " .. choices[2] .. ", " .. choices[3])
    local try = 1
    while try < 3 do
        choice = choices[try]
        if safeEdge(index, choice) then 
            --print("safe " .. choice)
            return choice 
        end
        try = try + 1
    end
    print("forced ".. choice)
    return choice
end

function shuffle(tab)
    local dex = {1,2,3}
    local res = {}
    local next
    next = math.random(1,3)
    table.insert(res, tab[dex[next]])
    table.remove(dex, next)
    next = math.random(1,2)
    table.insert(res, tab[dex[next]])
    table.remove(dex, next)
    table.insert(res, tab[dex[1]])
    return res
end

function safeEdge(start, stop)
    return not spiderOn(start,stop)
end

function spiderOn(start, stop)
    return thisSpiderOn(s1, start, stop) or thisSpiderOn(s2, start, stop) or thisSpiderOn(s3,start,stop)
end

function thisSpiderOn(spider, start, stop)
    return (spider.start == start and spider.stop == stop) or (spider.stop == start and spider.start == stop)
end

ant = {}
ant.start = 1
ant.stop = 2
ant.frac = math.random()
ant.speed = speed*3
ant.nextGoal = nextAntGoal

s1 = {}
s1.start = 2
s1.stop = 6
s1.frac = math.random()
s1.speed = speed
s1.nextGoal = nextGoal

s2 = {}
s2.start = 7
s2.stop = 3
s2.frac = math.random()
s2.speed = speed
s2.nextGoal = nextGoal

s3 = {}
s3.start = 4
s3.stop = 1
s3.frac = math.random()
s3.speed = speed
s3.nextGoal = nextGoal

function setup()
    center = vec2(WIDTH/2, HEIGHT/2)
end

function draw()
    background(140, 140, 150)
    strokeWidth(5)
    drawCubes()
end

function drawCubes()
    rectMode(CENTER)
    fill(0,0,0,0)
    lineCapMode(SQUARE)
    rect(center.x, center.y, 400, 400)
    rect(center.x, center.y, 800, 800)
    translate(center:unpack())
    line(200,200, 400, 400)
    line(-200,-200, -400, -400)
    line(-200,200, -400, 400)
    line(200,-200, 400, -400)
    progress()
end

function progress()
    if ( not dead ) then
        moveBug(ant)
        moveBug(s1)
        moveBug(s2)
        moveBug(s3)
    end
    dead = isAntDead()
    drawBug(s1, color(255,0,0))
    drawBug(s2, color(255,0,0))
    drawBug(s3, color(255,0,0))
    drawBug(ant, color(0,255,0))
    --drawSpiderLines()
end

function drawSpiderLines()
    pushStyle()
    stroke(255,0,0)
    vline(corners[s1.start], corners[s1.stop])
    vline(corners[s2.start], corners[s2.stop])
    vline(corners[s3.start], corners[s3.stop])
    popStyle()
end

function vline(p,q)
    line(p.x, p.y, q.x, q.y)
end

function isAntDead()
    local radius = 10
    local pos = ant.pos
    if pos:dist(s1.pos) < radius then return true end
    if pos:dist(s2.pos) < radius then return true end
    if pos:dist(s3.pos) < radius then return true end
    return false
end

function moveBug(aBug)
    aBug.frac = aBug.frac + aBug.speed
    if aBug.frac > 1 then
        aBug.start = aBug.stop
        aBug.stop = aBug.nextGoal(aBug.start)
        aBug.frac = 0
    end
    aBug.pos = (1-aBug.frac)*corners[aBug.start] + aBug.frac*corners[aBug.stop]
end

function nextGoal(index)
    local choice = math.random(3)
    local choices = cube[index]
    return choices[choice]
end

function drawBug(aBug, col)
    pushMatrix()
    pushStyle()
    translate(aBug.pos.x, aBug.pos.y)
    stroke(col)
    fill(col)
    ellipse(0,0,20,20)
    popStyle()
    popMatrix()
end

function bline(x1, y1,x2, y2)
    pushMatrix()
    pushStyle()
    fill(0,0,0)
    translate(x1, y1)
    local t = x1 .. " " .. y1
    text(t, 0, 0)
    translate(-x1, -y1)
    translate(x2, y2)
    t = x2 .. " " .. y2
    text(t, 0,0)
    popStyle()
    popMatrix()
    
    line(x1, y1, x2, y2)
end