The 538 Riddler: A Dog and a Duck in Purgatory

UPDATED 2/15 2:09 PM: Gonna save you the suspense on this one, folks. I was wrong, very wrong. See the follow up here.

Things are turning a bit dark at the 538 Riddler as this week Ollie imagines a frantic dog and a beleaguered duck trapped in a never-ending Kafkaesque chase. My answer for last week’s puzzle was correct, but as I said later, it was much more complicated than it needed to be.

This week, however, I don’t think I will even get a correct-but-overly-complex answer. I’m positive that my answer is wrong.

Here’s the scenario for these poor creatures:

There is a duck paddling in a perfectly circular pond, and a Nova Scotia duck tolling retriever prowling on the pond’s banks. The retriever very much wants to catch the duck. The dog can’t swim, and this particular duck can’t take flight from water. But the duck does want to fly away, which means it very much wants to make it safely to land without meeting the dog there. Assume the dog and the duck are both very smart and capable of acting perfectly in their best interests — they’re both expert strategists and tacticians. Say the duck starts in the center of the pond, and the dog somewhere right on the pond’s edge. To ensure that the duck could never escape safely, how many times faster would the dog have to be able to run relative to how fast the duck can swim? (Assume the dog is a good boy, yes he is, and thus very patient. The duck can’t simply wait him out. Also assume both animals can change direction without losing speed, and that the duck can take flight safely immediately after reaching shore if the dog isn’t there.)

Okay, so obviously there’s a mathy solution to this problem, but I don’t know it. I wrote a program to simulate the dog and duck and gave the duck some different strategies for getting to the shore. One thing that is obvious: the dog will never catch the duck. Either the duck will escape because the dog is too slow, or the dog will circle the pond forever as the duck swims back in forth in vain. Geez, Ollie, next to this, last week’s nightmare traffic problem is looking downright cheerful.

Designing the simulation was pretty fun, even if I don’t think it led me to the right solution. I basically came up with four different strategies that the duck might take to escape the pond. I call these Dumb, Cowardly, Clever, and Smart. Each strategy has a threshold at which it stops working, which is question being asked.

The Dumb strategy simply involves moving due west and hoping the dog is too slow. It will succeed as long as the dog is moving slower than PI * the duck’s speed.

duckvdog_Dumb

The Cowardly strategy just tries to avoid the dog at all costs, changing the duck’s direction to be away from the dog. Interestingly, the Cowardly strategy does worse than the dumb strategy for the duck! The dog can “scare” the duck into remaining in the pond by getting close enough to scare it back towards the center of the pond, even when moving slower (0.9483) than PI * the duck’s speed. All ducks die, but a cowardly duck is doomed to swim in a pond forever or something.

duckvdog_Cowardly

The Clever strategy works like the Cowardly strategy except that the duck is constantly calculating how long it will take to reach the shore in a straight line, and whether the dog can make it there first. If the duck can make it to the edge first, it makes a beeline for the shore. The Clever strategy requires the dog to travel 1.2093 * PI * the duck’s speed to prevent takeoff.

duckvdog_Clever

Finally, my last strategy was the Smart strategy. This is what I submitted for an answer, but I will be shocked if it is right. The Smart strategy acts like the Clever strategy except the duck will scan a range of spots on the shore and if ANY of them can be reached before the dog, it will beeline. It represents only a small improvement over Clever, requiring the dog to travel 1.2552 * PI * the duck’s speed to trap the fowl.

duckvdog_Smart

A couple of things to note here. When the duck escapes, the dog is often so close that it looks like they are overlapping, but this is an abstract duck with no size, only a location, so unless the dog is exactly at the right spot, the duck escapes if it crosses the 1 unit border of the pond. Also, my strategy for the dog is to just go to the point on the edge of the pond that is closest to the duck and wait like a good boy, who’s a good boy, you’re a good boy. I’m not sure if that’s optimal but any movement from that spot seems like a mistake until the duck changes course or crosses the center point. This is one are where I think I am probably wrong.

The other area where I could be am probably wrong is in the way that I have the Smart duck scan the shore for a likely escape route. I just choose a range of shoreline and increment test locations in discrete chunks looking for a candidate. At the very least, a mathy solution would do that continuously, not discretely.

I wrote this app using MFC and Gdiplus so I’m not going to include the whole project here. I’ll just post the pond.h and pond.cpp files, which is where all the calculations and simulation are being done. Everything else is just presentation.

First off, I assume the pond has a radius of 1 unit with its center at 0,0, and that the duck moves at a rate of 1 unit/second. I store an x- and y-variable for the duck and start it at the center of the pond.

I could have used x- and y-variables for the dog, but since it always moves along the edge of the circular pond, I instead store its position as a single real value from -PI to PI. (It really should be 0 to TAU, because PI is wrong, no really, but whatevs.) I start the dog at 0, meaning the East edge of the pond.

The dog’s speed is expressed in terms of the duck’s speed (1/sec) * TAU/2 (okay, fine, PI.) So if the dog moves at PI * the duck’s speed, he can make a half orbit of the pond by the time the duck moves from the center to the edge. Using these basic units makes the code very simple since the time required for the duck to reach the edge is equal to 1 minus its distance from the center of the pond. The time required for the dog to reach any point of the pond’s edge is simply the angle to that point minus the dog’s position divided by the dog’s speed.

I also created a simple DPoint class with some convenient operators to make things a little easier. 

// Pond.h

#pragma once
#include <math.h>

#define PI 3.1415926535897932384626433832
#define TAU (PI * 2)

enum EDuck {
    DumbDuck,
    CowardlyDuck,
    CleverDuck,
    SmartDuck,
};

struct DPoint
{
    double  x;
    double  y;

    void   Set(double _x, double _y) {x = _x; y = _y;}
    double Magnitude() const
    {
        return sqrt(x * x + y * y);
    }
};
static DPoint operator -(const DPoint &l, const DPoint &r)
{
    DPoint pt;
    pt.x = l.x - r.x;
    pt.y = l.y - r.y;
    return pt;
}
static DPoint operator +(const DPoint &l, const DPoint &r)
{
    DPoint pt;
    pt.x = l.x + r.x;
    pt.y = l.y + r.y;
    return pt;
}
static DPoint operator *(const DPoint &l, const DPoint &r)
{
    DPoint pt;
    pt.x = l.x * r.x;
    pt.y = l.y * r.y;
    return pt;
}
static DPoint operator *(const DPoint &l, double scalar)
{
    DPoint pt;
    pt.x = l.x * scalar;
    pt.y = l.y * scalar;
    return pt;
}

class Pond;

class DuckStrategy
{
public:
    virtual DPoint  GetDestinationVector(Pond *pond) = 0;
};

class DumbDuckStrategy : public DuckStrategy
{
public:
    virtual DPoint  GetDestinationVector(Pond *)
    {
        DPoint pt;
        pt.x = -1.0;
        pt.y = 0;
        return pt;
    }
};

class CowardlyDuckStrategy : public DuckStrategy
{
public:
    virtual DPoint  GetDestinationVector(Pond *pond);
};

class CleverDuckStrategy : public CowardlyDuckStrategy
{
public:
    virtual DPoint  GetDestinationVector(Pond *pond);
};

class SmartDuckStrategy : public CowardlyDuckStrategy
{
public:
    virtual DPoint  GetDestinationVector(Pond *pond);
};

class Pond
{
    double  m_dogPos;   // in radians, 0-tau
    double  m_dogSpeed; // in radians/sec
    DPoint  m_duckPos;    
    DPoint  m_lastDuckVector;
    EDuck   m_behavior;
    bool    m_escaped;
    bool    m_beeline;
    double  m_elapsed;
    double  m_beelineTime;

    CowardlyDuckStrategy    m_cowardly;
    DuckStrategy    *m_strategy;

public:
    Pond() : m_dogPos(0)
    {
        SetStrategy(&m_cowardly);
        Restart(PI);
        m_escaped = true;   // so we have to hit restart to start
    }

    void    Restart(double dogSpeed)
    {
        m_beeline = false;
        m_elapsed = 0;
        m_beelineTime = 0;
        m_dogPos = 0;
        m_dogSpeed = dogSpeed;
        m_escaped = false;
        m_duckPos.Set(0, 0);
        m_lastDuckVector.Set(0, 0);
    }

    void    SetStrategy(DuckStrategy *strat)
    {
        m_strategy = strat;
    }

    void    SetBeeline() {m_beeline = true; m_beelineTime = m_elapsed;}
    bool    GetBeeline() const {return m_beeline;}
    double  GetElapsed() const {return m_elapsed;}
    DPoint  GetDuckPos() const {return m_duckPos;}
    double  GetDogPolar() const {return m_dogPos;}
    double  GetDogSpeed() const {return m_dogSpeed;}
    DPoint  GetLastDuckVector() const {return m_lastDuckVector;}
    DPoint  GetDogPos() const 
    {
        DPoint pos;
        pos.x = cos(m_dogPos);
        pos.y = sin(m_dogPos);
        return pos;
    }
    double  GetDogTimeToDest(double dest) const;
    double  GetDuckTimeToDest(double dest) const;

    void    Process(double sec)
    {
        if(m_escaped || m_strategy == NULL)
            return;


        // get duck vector
        DPoint duckVec = m_strategy->GetDestinationVector(this);
        m_lastDuckVector = duckVec;

        // get dog destination
        double mag = m_duckPos.Magnitude();
        double dogDest = PI;
        if(mag != 0.0)
        {
            double s = m_duckPos.y / mag;
            double c = m_duckPos.x / mag;
            dogDest = atan2(s, c);
        }

        // update duck position
        duckVec = duckVec * sec;
        m_duckPos = duckVec + m_duckPos;
        mag = m_duckPos.Magnitude();
        if(mag >= 1.0)
        {
            double overage = mag - 1.0;
            m_duckPos = m_duckPos * (1 / mag);
            sec -= overage;
            m_escaped = true;
        }
        m_elapsed += sec;
        if(mag < sec)
        {
            m_duckPos.Set(0, 0);
        }
        

        // update dog position
        double dogDelta = dogDest - m_dogPos;
        if(dogDelta < -TAU)
            dogDelta += TAU;
        else if(dogDelta > TAU)
            dogDelta -= TAU;

        double dogProgress = m_dogSpeed * sec;
        if(dogProgress > abs(dogDelta))
        {
            m_dogPos = dogDest;
        }
        else
        {
            m_dogPos += dogProgress;
            if(m_dogPos > PI)
                m_dogPos -= TAU;
            else if(m_dogPos < -PI)
                m_dogPos += TAU;
        }
    }
};

pond.h

// Pond.cpp

#include "stdafx.h"
#include "Pond.h"

DPoint CowardlyDuckStrategy::GetDestinationVector(Pond *pond)
{
    DPoint dogPos = pond->GetDogPos();
    DPoint duckPos = pond->GetDuckPos();

    DPoint pt = duckPos - dogPos;

    double mag = pt.Magnitude();
    if(mag == 0)
    {
        pt.x = -1.0;
        pt.y = 0;
    }
    else
    {
        pt.x /= mag;
        pt.y /= mag;
    }
    return pt;
}

DPoint CleverDuckStrategy::GetDestinationVector(Pond *pond)
{
    DPoint curVec = pond->GetDuckPos();
    double mag = curVec.Magnitude();

    if(mag == 0)
        return CowardlyDuckStrategy::GetDestinationVector(pond);

    double toGoal = 1.0 - mag;

    double dogPos = pond->GetDogPolar();
    double s = curVec.y / mag;
    double c = curVec.x / mag;
    double dogDest = atan2(s, c);

    double dogTime = pond->GetDogTimeToDest(dogDest);

    if(dogTime > toGoal)
    {
        pond->SetBeeline();
        curVec = curVec * (1 / mag);
        return curVec;
    }

    return CowardlyDuckStrategy::GetDestinationVector(pond);
}

DPoint SmartDuckStrategy::GetDestinationVector(Pond *pond)
{
    DPoint curVec = pond->GetDuckPos();
    double mag = curVec.Magnitude();

    if(pond->GetBeeline())
    {
        return pond->GetLastDuckVector();
    }

    if(mag == 0)
        return CowardlyDuckStrategy::GetDestinationVector(pond);

    double s = curVec.y / mag;
    double c = curVec.x / mag;
    double dest = atan2(s, c);

    double start = dest;
    double end = dest + PI / 8.0;
    double inc = (end - start) / 100;

    for(double test = start; test <= end; test += inc)
    {
        double duckTime = pond->GetDuckTimeToDest(test);
        double dogTime = pond->GetDogTimeToDest(test);
        if(duckTime < dogTime)
        {
            DPoint pt;
            pt.Set(cos(test), sin(test));

            pt = pt - curVec;

            pt = pt * (1 / pt.Magnitude());
            double one = pt.Magnitude();
            pond->SetBeeline();
            return pt;
        }
    }

    return CowardlyDuckStrategy::GetDestinationVector(pond);
}



double Pond::GetDuckTimeToDest(double dest) const
{
    DPoint pt;
    pt.x = cos(dest);
    pt.y = sin(dest);

    pt = pt - m_duckPos;
    return pt.Magnitude();
}

double Pond::GetDogTimeToDest(double dogDest) const
{
    double dogPos = GetDogPolar();

    double dogDelta = dogDest - dogPos;
    if(dogDelta < -PI)
        dogDelta += TAU;
    else if(dogDelta > PI)
        dogDelta -= TAU;

    double degrees = dogDelta * 360.0/PI;

    dogDelta = abs(dogDelta);
    ASSERT(dogDelta <= PI);

    double dogTime = dogDelta / GetDogSpeed();
    return dogTime;
}

pond.cpp

I chose to wrap most of the code for my pond in a single object that owns the duck and the dog. I could have chosen to make separate classes for the duck and dog and maybe have multiple ducks and multiple dogs each taking different approaches but then I thought, what if I didn’t instead.

As I said, I don’t think I got this one right, so I’ll be really interested to see what Ollie posts as the answer next Friday. Thanks for reading!

Author: Wiesman

Husband, father, video game developer, liberal, and perpetual Underdog.

7 thoughts on “The 538 Riddler: A Dog and a Duck in Purgatory”

  1. Impressive coding as ever. I came up with the answer that the dog needs to travel Pi+1 (or 4.1415… or 1.318 Pi) times as fast as the duck.
    My thinking went something like this:
    Both the duck and the dog have ideal positions in relation to each other for any of the duck’s distances from the center of the pond. The duck will want to be closest to a point on the bank directly opposite the dog- this will give the duck the longest time to reach the bank for any given dog speed. The dog will want to be at the point on the bank closest to the duck, to be there when the duck arrives!
    Both of these types of positions are harder or easier for the duck and dog to reach depending on how far the duck is from the centre. For example, in a pond with a 1 meter radius, if the duck is very close to the centre (say 1 cm off centre), the dog would have to be incredibly fast to maintain it’s ideal position, travelling 100 times the duck’s speed to maintain it’s ideal position. If the duck is even closer to the center, the dog’s speed has to rise to infinity for it to maintain that ideal position. The equation can be expressed as Pi/Pi*X where X is the duck’s distance from the centre. As that distance falls to 0, the dog’s speed rises to infinitely faster than the duck, whereas if X rises to 1, the dog’s speed merely has to match the duck. Because of the difficulty of maintaining its ideal position when the duck is near the centre, the dog won’t ‘care’ about getting to its ideal position when the duck is close to the centre.
    So how far should the dog allow the duck to stray from the centre before moving to get into its ideal position?
    Well, imagine if the dog allowed the duck to stray nearly to the edge of the pond, in the duck’s ideal position (which, remember, is opposite the dog). If the duck was 1 cm away from the bank in its ideal position, the dog would have to travel Pi*100 times the duck’s speed to get to the right point on the bank in time. As duck gets even closer to the bank, the dog’s necessary speed rises to being infinitely faster than the duck. This equation can be expressed as Pi/(1-X) where again X is the duck’s distance from the centre.
    Clearly the dog cannot afford to let the duck stray too far from the centre before it can be bothered to get into its ideal position. So when should the dog start caring? I think the answer lies with the intersection of these two equations. When Pi/(1-X)=Pi/Pi*X you find the point at which the duck isn’t so close to the centre that the dog has to run too fast to maintain a perfect position, and not so close to the bank that the dog has to run too fast to compensate for the duck’s ideal position.
    When you solve the above equation, you get X=1/(Pi+1) again where X is the duck’s distance from the center. If you then plug this answer into either of the separate equations, the answer is Pi+1.
    I am confident that the dog’s speed must be AT LEAST Pi+1. It would have to be faster than that to prevent the duck getting into it’s ideal position at a smaller X, and also faster if it let the duck get to a larger X.
    However, what I am not sure of is, given the dog’s speed of Pi+1, is whether there is any strategy the duck can take to require the dog to go even faster?
    For example, let’s say the duck is at our chosen X (that’s 1/(Pi+1) distance from the center) and starts to take a direct route towards the bank. We know that the dog will be travelling around the pond at Pi+1, but what if the duck veers off the direct route to be slightly further away from the dog. Will the extra distance the duck have to travel be enough to beat the dog travelling at Pi+1? My instinct is that the duck’s extra distance will be more than enough for the dog to catch it in time without speeding up, but my math skills are hitting their limit in doing the calculations. Maybe someone could help!

    1. Wow, Alex, that is fantastic analysis. It sure seems like that could be the answer. Sadly for me, my answer of PI * 1.2552 comes out to 3.9432. If it had been 4.1415 I would have been really excited! I think you are on the right track and your math approach is definitely superior to my simulation approach. I’ll try to find some time to tweak the duck’s behavior and see if I’m missing something. Maybe I’ll get to PI + 1 somehow.

      Thanks again for reading and posting!

  2. I’ve been looking online for confirmation that Pi+1 is correct, and unfortunately… is seems that it is not. The actual solution seems to rely on some heavy trig and calculus which is beyond my math skills. However, the first part of the solution is correct (the duck choosing to maneuver to an ideal position somewhat off center). But instead of swimming to the closest point on the bank, the duck should swim perpendicular to the radius. You can find the solution by googling ‘how to escape a monster’ but I won’t post the link here in case you don’t want spoilers. I would still be really interested in seeing a coded simulation of the duck’s behavior if you can figure it out. I’m a little disappointed that the answer relies on such difficult math (for me), I prefer when the 538 Riddler relies more on logic than calculators!

  3. After the analysis of outmanuevering the dog, we need to have the duck swim as fast as it can at an angle, … http://pastebin.com/bHWnRHNV

    I’m really bad at calculus, so brute force and binary search my way there as per above Python code, … the last print out was something like this:
    Testing 4.60333153318
    Testing 4.60334461455
    Testing 4.60333807387
    Testing 4.60334134421
    Testing 4.60333970904
    Testing 4.60333889145
    Testing 4.60333848266
    Testing 4.60333868706
    Testing 4.60333878925
    Testing 4.60333884035
    4.60333884035

    Not sure if it is the correct answer, though.

    1. Additional info on the approach on my Python code in previous comment, … right after outmanuevering the doggie, that is, the dog is at point (-1, 0) and duck is at (1/vdog, 0) … assuming radius of pond is 1; and duck just swims straight to shore towards point (1, 0) without worrying about any angle, … then the Python code above will also give PI+1 as the answer.

      I’m not sure that the answer of 4.6033 is the right one because in order to achieve that, the angle alpha that the duck swims is too big, in my opinion, … which makes me believe that if the dog is smart enough, it should avoid trying to cover (PI+alpha) angular distance and instead should go for PI-alpha using the other direction to reach the same point on the shore.

      I can buy that a little alpha would help increase the answer from PI+1 to slightly higher number than that … but I can’t imagine it will reach 4.6033 … I hope I know calculus enough to be able to be certain, though.

Disagree?

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s