[bonanova]

Four frogs are enjoying their favorite pastime of hopscotch.

One of them, Alex by name, proposes a new game.

Not surprisingly, it involves a challenge.

Look here fellas, he croaked, as he drew four X's on the

ground so that they formed the four corners of a square.

We all start out on one of these corners. Then we take

turns jumping over each other. The object is to end up

sitting on new spots that form a larger square. The frog

who makes the final jump to form the square is the winner.

Here are the rules:

[1] We can jump another frog from any distance.

[2] We land an equal distance away from the jumped frog: if he's 2 feet away, I land 2 feet beyond him.

[3] Jumps are in a straight line: initial position, jumped frog and landing position are in a straight line.

One of the other frogs, amazingly named Jamey, wondered

why they had to take turns. Maybe I want to think about

my next jump for a bit, I don't want to hold up the game.

OK, then, we'll jump one at a time, but not necessarily in order,

Alex agreed.

Can you prove that it's possible to win the game ... or not?

If so, how many jumps will it take?

[Guest]

I believe it is impossible (for me), but have no idea how to find the math to prove it. So, basically, I cannot finish this puzzle.

[Guest]

It is the angles that mess me up. Maybe I just do not have the patience to figure out how long it would take to two frogs leaping over each other at different angles to get back to a 90 degree angle with two other frogs. I did however get to draw lots of hopscotching dots in my notepad and got yelled at once by my boss. That's worth at least three stars.

[Guest]

My guess is that it is impossible, i have tests this week, but if i've got time upcoming weekend i'll try to prove it using math (or write a program which tries an x number of steps and leave that running for an hour or so, though that isn't a proof it is safe to say that there 'll probably not be a solution if it isn't found then).

[Guest]

My guess is that it is impossible, i have tests this week, but if i've got time upcoming weekend i'll try to prove it using math (or write a program which tries an x number of steps and leave that running for an hour or so, though that isn't a proof it is safe to say that there 'll probably not be a solution if it isn't found then).

I agree that it's probably impossible, and since it's posted by bonanova there's no doubt an elegant way to prove it. Still, a programmatic test sounded fun. My first attempt used random selection and went deep, but I figured that was unlikely to succeed so this morning I modified it to use a brute force approach. With 12*11^(n -1) possibilities for each jump (I ruled out having a frog immediately jump back to his previous position), it doesn't take long to run into computing limitations. So far, however, I can say with a fair amount of certainty, barring a bug in my code, that there is not a solution in under 10 jumps.

[bonanova]

I agree that it's probably impossible, and since it's posted by bonanova there's no doubt an elegant way to prove it. Still, a programmatic test sounded fun. My first attempt used random selection and went deep, but I figured that was unlikely to succeed so this morning I modified it to use a brute force approach. With 12*11^(n -1) possibilities for each jump (I ruled out having a frog immediately jump back to his previous position), it doesn't take long to run into computing limitations. So far, however, I can say with a fair amount of certainty, barring a bug in my code, that there is not a solution in under 10 jumps.

The frogs will eat any bugs.

Your code must include a fairly tight test for "squareness".

Care to share that part of it?

I ran across a question that asked how efficiently that test could be implemented.

[Guest]

Your code must include a fairly tight test for "squareness".

Care to share that part of it?

I ran across a question that asked how efficiently that test could be implemented.

That did prove a bit more challenging than I expected. My test certainly ain't "tight," but I think it's workable. I would be happy to have it inspected by all y'all mathy people:

Here's the theory:

1. For each frog, get the distance to the other three frogs.

2. Get the max and min distances.

3. If all four frogs share the same max and min distances, they must form a square. (an unproven supposition, but I believe it should hold)

[C#]


bool IsLargerSquare()

{

    List<double> lengths = new List<double>();


    double firstMax = 0;

    double firstMin = 0;


    for (int i = 0; i < 4; i++)

    {

        lengths.Clear();

        lengths.Add(GetLength(frogs[i].Pos, frogs[((i + 1) % 4)].Pos));

        lengths.Add(GetLength(frogs[i].Pos, frogs[((i + 2) % 4)].Pos));

        lengths.Add(GetLength(frogs[i].Pos, frogs[((i + 3) % 4)].Pos));


        double max = Math.Round(MaxInList(lengths), PRECISION);

        double min = Math.Round(MinInList(lengths), PRECISION);


        if (i == 0) // max/min of first frog

        {

            firstMax = max;

            firstMin = min;

        }

        else // other frogs. compare to original max/min

        {

            if (firstMax != max) return false;

            if (firstMin != min) return false;

        }

    }


    if (firstMin > 1) return true; // make sure it's larger than the original square

    else return false;

}

[/codebox]

[bonanova]

I think there are only six ways four points can collectively have the same max and min distances.

In only one case [square] do the points individually have the same max and min.

So I think you're condition is correct.

Look at post #6 here

Look at post #15 [and others] here, also

[bonanova]

Alex and his froggy friends can reverse their jumps and return to the original square.

[Guest]

Before I look at bonanova's hint ...

After looking at those other forums I decided to revisit the square-checking algorithm. Although my updated solution still uses a lot of steps (and appears to require just as much code as my previous proposal), it is actually drastically more efficient, and I don't see how to optimize it much more using only high level code. Of course I'd love suggestions.

Here's the theory:

1. The x and y differences between any point and any two adjacent points are inverses with a perpendicular slope. For example: (1,2) and (-2,1), (1,2) and (2,-1), (0,1) and (1,0).

2. The x and y differences between any adjacent point and the opposite point must match the differences between the first point and the other adjacent point.

3. If those conditions are met ... it's a square!

That's it. No multiplication, division, or square roots needed other than to verify that a found square is actually larger than the original. Also, I learned a few things from my first attempt:

1. All values will be integers, so no floating point math is required.

2. We only need to examine two jumps of the 12 possible from the original position, since everything else is just symmetry.

3. The actual formula for the total possibilities is 2 + 2(11 + 11^2 + 11^3 ... 11^n-1) where n is the depth (i.e., number of jumps).

Using this approach my test evaluates 3.5 million jumps/sec. Unfortunately, that only yielded about one more ply to the testable depth. If I run it overnight, I will still only be able to examine 11 or perhaps 12 jumps deep. Of course, I could find ways to reduce the evaluation of the insane numbers of symmetrical positions, but that would just be OCD in action.

So, while I am fairly certain it's impossible, I naturally wanted a simpler expanation, so I applied what I had just learned ...

If a square starting on integer points can never end up on anything besides integer points, that means it can never get smaller, and ... if it can't get smaller, it can't get bigger, because you would always be able to reverse the order of the jumps.

Simple enough, but I'm sure even that can be reduced.

Just for fun, I present to you the code ...

    class FrogSim

    {

        const int MAX_DEPTH = 9;

        const int SLOPE_NEG = -2;

        const int SLOPE_ZERO = -1;

        const int SLOPE_ONE = 1;

        const int SLOPE_POS = 2;


        int result = 0;

        long tested = 0;

        FrogList frogs;


        public FrogSim()

        {

            // setup

            frogs = new FrogList();

            frogs.Add(new Frog(new Point(0, 0)));

            frogs.Add(new Frog(new Point(1, 0)));

            frogs.Add(new Frog(new Point(0, 1)));

            frogs.Add(new Frog(new Point(1, 1)));

        }


        public void RunSim()

        {

            DateTime start = DateTime.Now;


            bool success = false;


            // recursively call jump for only 2 jumps at base level

            if (Jump(0, 1, 1)) success = true;  // jump 1 and ...

            else if (Jump(0, 3, 1)) success = true; // jump 3. those are the only two necessary tests due to symmetry 


            // get total time

            TimeSpan duration = DateTime.Now.Subtract(start);

            string timeMessage = "\n\nTotal time: " + (int)duration.TotalSeconds + " seconds.";


            string message;


            if (success)

            {

                message = "Formed a larger square in " + result.ToString() + " jumps!" + timeMessage;

            }

            else

            {

                message = "Failed to achieve a square in " + MAX_DEPTH + " jumps.\n" +

                                "Attempted " + tested.ToString() + " possibilities." + timeMessage;

            }


            Debug.WriteLine(message);

            MessageBox.Show(message);

        }


        bool Jump(int jumper, int jumped, int depth)

        {

            tested++;


            int iLastJumper = jumper;

            int iLastJumped = jumped;


            Point startingPos = frogs[jumper].Pos;


            frogs[jumper].Jump(frogs[jumped]);


            if (IsLargerSquare())

            {

                result = depth;

                return true;

            }

            else

            {

                if (depth < MAX_DEPTH)

                {

                    for (int iJumper = 0; iJumper < 4; iJumper++)

                    {

                        for (int iOffset = 1; iOffset < 4; iOffset++)

                        {

                            int iJumped = (iJumper + iOffset) % 4;


                            if (! (iJumper == iLastJumper && iJumped == iLastJumped))

                            {

                                if (Jump(iJumper, iJumped, depth + 1))

                                {

                                    return true;

                                }

                            }

                        }

                    }

                }

            }

            // restore the previous position

            frogs[jumper].Pos = startingPos;


            return false;

        }


        bool IsLargerSquare()

        {

            // get x/y differences from first point to two other points

            int x1 = frogs[1].Pos.X - frogs[0].Pos.X;

            int y1 = frogs[1].Pos.Y - frogs[0].Pos.Y;

            int x2 = frogs[2].Pos.X - frogs[0].Pos.X;

            int y2 = frogs[2].Pos.Y - frogs[0].Pos.Y;

            // get their absolute values

            int absX1 = Math.Abs(x1);

            int absY1 = Math.Abs(y1);

            int absX2 = Math.Abs(x2);

            int absY2 = Math.Abs(y2);

            // get their relative slope (negative, positive, zero, or one)

            int slope1 = GetSlope(x1,y1);

            int slope2 = GetSlope(x2, y2);


            if (absX1 == absY2 && absY1 == absX2 && slope1 == -slope2)

            {

                // 1 and 2 are adjacent. frog 3 is distant (compare to 1)

                return IsValidOppositePoint(frogs[3].Pos, frogs[1].Pos, x2, y2) && IsLarger(x1, y1);

            }


            // get diffs to third point only if first two were not adjacent

            int x3 = frogs[3].Pos.X - frogs[0].Pos.X;

            int y3 = frogs[3].Pos.Y - frogs[0].Pos.Y;

            int absX3 = Math.Abs(x3);

            int absY3 = Math.Abs(y3);

            int slope3 = GetSlope(x3, y3);


            if (absX1 == absY3 && absY1 == absX3 && slope1 == -slope3)

            {

                // frog 2 is distant (compare to 1)

                return IsValidOppositePoint(frogs[2].Pos, frogs[1].Pos, x3, y3) && IsLarger(x1, y1);

            }

            else if (absX2 == absY3 && absY2 == absX3 && slope2 == -slope3)

            {

                // frog 1 is distant (compare to 2)

                return IsValidOppositePoint(frogs[1].Pos, frogs[2].Pos, x3, y3) && IsLarger(x1, y1);

            }


            return false;

        }


        int GetSlope(int x, int y)

        {

            if (x == 0)

            {

                return SLOPE_ONE;

            }

            else if (y == 0)

            {

                return SLOPE_ZERO;

            }

            else if (x > 0 == y > 0)

                return SLOPE_POS;

            else

            {

                return SLOPE_NEG;

            }

        }


        bool IsValidOppositePoint(Point ptOpp, Point ptAdj, int xDiff, int yDiff)

        {

            int x4 = ptOpp.X - ptAdj.X;

            int y4 = ptOpp.Y - ptAdj.Y;


            return (x4 == xDiff && y4 == yDiff);

        }


        bool IsLarger(int xDiff, int yDiff)

        {

            return Math.Sqrt((xDiff * xDiff) + (yDiff * yDiff)) > 1;

        }

    }


    class Frog

    {

        public Point Pos;


        public Frog(Point startingPosition)

        {

            Pos = startingPosition;

        }


        public void Jump(Frog jumpee)

        {

            Pos = new Point(((jumpee.Pos.X - Pos.X) * 2) + Pos.X, ((jumpee.Pos.Y - Pos.Y) * 2) + Pos.Y);

        }


        public override string ToString()

        {

            return Pos.ToString();

        }

    }


    class FrogList : List<Frog>

    {

        public override string ToString()

        {

            string sFrogs = "";

            foreach (Frog frog in this)

            {

                sFrogs += frog.ToString() + "\n";

            }

            return sFrogs;

        }

    }[/codebox]

[Guest]

Alex and his froggy friends can reverse their jumps and return to the original square.

Sure glad I didn't look, cause it was only while I was typing my response that I realized the solution, and seeing your hint would have deprived me of that moment. :-)

[Guest]

i didn't write any code or anything for this, i just printed off a grid from excel and used some screws lying around to represent my frogs.

the way i figured it out, there are a total of 12 moves. the frogs start in the position:

a b

c d

frog d jumps b, b jumps d, d returns to original position.

3 moves.

frog c jumps d, d jumps c, c jumps d, d returns to original position.

4 moves.

frog a jumps d, d jumps a, a jumps d, a jumps c, d returns to original position.

5 moves.

[Guest]

i didn't write any code or anything for this, i just printed off a grid from excel and used some screws lying around to represent my frogs.

the way i figured it out, there are a total of 12 moves. the frogs start in the position:

a b

c d

frog d jumps b, b jumps d, d returns to original position.

3 moves.

frog c jumps d, d jumps c, c jumps d, d returns to original position.

4 moves.

frog a jumps d, d jumps a, a jumps d, a jumps c, d returns to original position.

5 moves.

Your moves aren't possible i think...

[Guest]

4 Moves I can get 3 corners set-up. That is the best I can do so far.

A B

C D

C jumps B, D jumps A

B jumps, A, C

Now you have 3 corners of a square that are slightly bigger, so maybe someone can complete the last piece of the puzzle

[bonanova]

i didn't write any code or anything for this, i just printed off a grid from excel and used some screws lying around to represent my frogs.

the way i figured it out, there are a total of 12 moves. the frogs start in the position:

a b

c d

frog d jumps b, b jumps d, d returns to original position.

3 moves.

frog c jumps d, d jumps c, c jumps d, d returns to original position.

4 moves.

frog a jumps d, d jumps a, a jumps d, a jumps c, d returns to original position.

5 moves.

A frog doesn't get a free pass back to his original position.

He can get back, but only by undoing all the jumps that got him to a new spot.

The point I made a few posts ago is that all jumps are reversible, and that might help you find the answer.

[Guest]

A frog doesn't get a free pass back to his original position.

He can get back, but only by undoing all the jumps that got him to a new spot.

The point I made a few posts ago is that all jumps are reversible, and that might help you find the answer.

Hi, everyone, I'm kinda new here, but I've been reading lots of riddles on this website for the past couple weeks. First post (yay!) So anyway....

A B

C D

those are the frogs.

Frog A jumps over frog D, then jumps straight back to his spot. Due to frogs being very fidgety creatures, likely each one moved back, just a little, even frog A, since it's impossible to return to its exact spot. Nearly impossible, anway.

Therefore, two jumps are needed.

[Guest]

A frog doesn't get a free pass back to his original position.

He can get back, but only by undoing all the jumps that got him to a new spot.

The point I made a few posts ago is that all jumps are reversible, and that might help you find the answer.

But the frogs cannot get back to their original position without the other frogs also reversing their jumps. Therefore, D jumps C, C jumps D, D returns to it's original position is not following the rules of the game because he must have a frog between him and his original position to jump over.

[bonanova]

A frog doesn't get a free pass back to his original position.

He can get back, but only by undoing all the jumps that got him to a new spot.

The point I made a few posts ago is that all jumps are reversible, and that might help you find the answer.

This is a clue, not the solution.

[bonanova]

Suppose the frogs are on the points [0,0], [0,1], [1,1], [1,0].

Every jump they make from that point lands them on point

with integer-valued coordinates. So they could never land

on points that form a square that has sides whose length

is less than 1.

If they were able to jump to form a larger square,

say [0,0], [0.2], [2,2], [2,0], then reversing those jumps

would return them to the original unit square. That is, if

they could form a larger square, then they could also form

a smaller square.

But we showed that's impossible. Therefore, they cannot form a larger square.