Follow up to Duck vs. Dog

Okay, well, my luck has officially run out. I was definitely, most certainly wrong wrong wrong about how much faster the dog could travel and still allow the duck to escape. Thanks once again to commenters Alex Mahdavi and Lego Haryanto who found the right answer. Alex pointed me to this DataGenetics blog post from a few years ago that answered the question with a monster and a rower in a boat. As I suspected the answer was more mathy than my simulation could handle, although a lot of it was algebra and trig, with a bit of calculus.

The nice thing was that once I understood the solution, it was really easy to rewrite the SmartDuckStrategy to use the “J” strategy outlined in the post. The result is exactly what was predicted by Datagenetics. Here’s a GIF:

duckvdog_Correct

Yay! It’s nice when things work out, even if I didn’t solve this one (or get close) myself. The new code is a little simplistic in that it assumes the dog will start at a position of 0 degrees, but here it is:

DPoint SmartDuckStrategy::GetDestinationVector(Pond *pond)
{
    if(pond->GetBeeline())
        return pond->GetLastDuckVector();

    DPoint focus(0, -1 / (pond->GetDogSpeed() * 2.0));

    DPoint duckPos = pond->GetDuckPos();

    DPoint delta = duckPos - focus;

    double angleFromFocus = atan2(delta.y, delta.x);

    if(angleFromFocus > -PI / 2.0 && angleFromFocus < 0)
    {
        pond->SetBeeline();
        return DPoint(1, 0);
    }
    angleFromFocus += PI / 2.0;

    DPoint vec(cos(angleFromFocus), sin(angleFromFocus));

    return vec;
}

So I take some comfort that my underlying simulation was solid enough that just changing the behavior of the duck was sufficient to illustrate the right answer. It’s not much, but it’s all I have!

Thanks again to Alex and Lego for posting comments. It means a lot.

Author: Wiesman

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

5 thoughts on “Follow up to Duck vs. Dog”

  1. Nice one. This code certainly dictates the dog/duck behaviour that is given as the correct answer in the ‘how to escape a monster’ blog post and other versions of the puzzle (http://www.jstor.org/stable/2688876?seq=1#page_scan_tab_contents). However I’m not sure (and from his comment I don’t think Lego is either), that the dog couldn’t be a little ‘smarter’. Is there any way to test whether the dog can improve his strategy by NOT moving for a moment or two after the duck leaves its inner circle so that it can make a smarter guess as to where the duck is planning to land?
    My instinct is that such a strategy would result in an answer between Pi+1 and 4.6. In the original version of the question, it is stated as obvious that the dog cannot gain an advantage by changing direction, which I can just about accept without proof, but I haven’t seen an explanation of why the dog can’t just pause for a moment to observe the duck (after all, we are giving the duck an infinitely small amount of time to observe the dog’s behaviour, so why not vice versa.) My instinct may be totally wrong, however!

    1. That thought was nagging at me when I read the post and while I was writing the code. It sure seems like the dog commits too early to its direction. However, I did not alter the dog’s behavior for the final version. I just gave the duck a better strategy. The dog is still making the most rational choice at any given time in the simulation, based on, and this is important, ZERO cost for changing direction (instant acceleration). This is one of those times when you are writing code and you have no idea what the result will be, and then you run it and it does EXACTLY what the design says it should do and you’re like, woah, cool.

      1. I think I’ll have to take that as proof enough! This is one of those puzzles where I feel I need to break out a math textbook and get up to speed on trig and calculus. Or maybe learn how to code! I’ve never done any coding before and I’m fascinated by the way you’ve been using it to solve/explain these puzzles. Can you point me in the direction of a good starting point to learn? Is there a website or (gasp!) book that could provide a good foundation in coding?

      2. I think the Khan Academy stuff on programming is pretty cool. They use a web interface that allows you to change code and see immediate results right in your browser. It will get you started on learning all the fundamentals and then if you want to step up your game, you could look for a compiler/language/IDE that best suits your interests. I’ve been a C++ person mostly, although lately all my work has been done in objective-C and C# and I have quite a bit of experience in Lua.

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