Jump to content


Welcome to BrainDen.com - Brain Teasers Forum

Welcome to BrainDen.com - Brain Teasers Forum. Like most online communities you must register to post in our community, but don't worry this is a simple free process. To be a part of BrainDen Forums you may create a new account or sign in if you already have an account.
As a member you could start new topics, reply to others, subscribe to topics/forums to get automatic updates, get your own profile and make new friends.

Of course, you can also enjoy our collection of amazing optical illusions and cool math games.

If you like our site, you may support us by simply clicking Google "+1" or Facebook "Like" buttons at the top.
If you have a website, we would appreciate a little link to BrainDen.

Thanks and enjoy the Den :-)
Guest Message by DevFuse
 

Photo
- - - - -


  • Please log in to reply
18 replies to this topic

#1 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5637 posts
  • Gender:Male
  • Location:New York

Posted 27 January 2008 - 12:25 AM

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?
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#2 Jkyle1980

Jkyle1980

    Advanced Member

  • Members
  • PipPipPip
  • 157 posts

Posted 27 January 2008 - 02:37 AM

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.
  • 0

#3 Jkyle1980

Jkyle1980

    Advanced Member

  • Members
  • PipPipPip
  • 157 posts

Posted 27 January 2008 - 09:57 AM

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.
  • 0

#4 Arie-

Arie-

    Newbie

  • Members
  • Pip
  • 13 posts

Posted 28 January 2008 - 11:15 AM

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).
  • 0

#5 Duh Puck

Duh Puck

    Advanced Member

  • Members
  • PipPipPip
  • 445 posts

Posted 29 January 2008 - 03:40 AM

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.
  • 0

#6 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5637 posts
  • Gender:Male
  • Location:New York

Posted 29 January 2008 - 04:04 AM

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.
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#7 Duh Puck

Duh Puck

    Advanced Member

  • Members
  • PipPipPip
  • 445 posts

Posted 29 January 2008 - 05:46 AM

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;}

  • 0

#8 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5637 posts
  • Gender:Male
  • Location:New York

Posted 29 January 2008 - 08:48 AM

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
  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#9 bonanova

bonanova

    bonanova

  • Moderator
  • PipPipPipPip
  • 5637 posts
  • Gender:Male
  • Location:New York

Posted 30 January 2008 - 12:17 PM

Spoiler for This may help you think about it.

  • 0
The greatest challenge to any thinker is stating the problem in a way that will allow a solution.
- Bertrand Russell

#10 Duh Puck

Duh Puck

    Advanced Member

  • Members
  • PipPipPip
  • 445 posts

Posted 31 January 2008 - 02:46 PM

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 ...
Spoiler for solution

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

Just for fun, I present to you the code ...
[codebox] 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]
  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users