An inefficient but working method is the brute force one.
Do a recursive test for all the cases possible and if you
find one which helps the frog cross the road, then that is it.
Let int car_times[numLanes] store the time each car will take to reach
the path where the frog is crossing the road.
Frog has 3 commands at his disposal:
a) jump_fwd
b) jump_back
c) wait
Let Vector <command> cmds be the desired sequence of commands to reach
the destination.
We need to write a function which will produce the above global vector
as its output.
enum command {F, B, W};
Vector <command> cmds;
int car_times[numLanes]; //given in the beginning
bool try_remaining_path (int lane_num, int time_passed) {
int orig_time = time_passed;
int orig_lanes = lane_num;
while (car_times[lane_num] - time_passed>= 1) {
cmds.push_back (F);
bool rest_is_possible = try_remaining_path (time_passed+1,
lane_num+1);
if (rest_is_possible)
return true;
cmds.pop();
cmds.push_back (W);
time_passed++;
}
// if we come here, means that there was no point
// in waiting in this lane_num, as the frog will be
// killed at one point or the other.
// let us try by jumping back one step.
time_passed = orig_time;
while (lane_num > 0) {
cmds.push_back (B);
time_passed++;
lane_num--;
bool rest_is_possible = try_remaining_path (time_passed,
lane_num);
if (rest_is_possible)
return true;
}
// Nothing is possible in this lane.
// Empty the commands B from the vector and try something else.
while (orig_lanes > 0 ) {
cmds.pop();
orig_lanes--;
}
return false;
}
Above seems very inefficient to me because it calculates all the
possible jumps at each lane.
Please help in improving it.
On Jul 15, 9:24 am, Ashish kumar Jain <[email protected]> wrote:
> I think this will help:
>
> http://en.wikipedia.org/wiki/Frogger
>
> Consider the roads to be n-laned and of constant width with constant time
> traffic coming on each lane.For example,say after 1 minute,a car comes on
> each lane but in a arithmetic sequence and not all at same time.To make it
> more clear,
>
> at t=1 minute,car at lane 1 travelling with constant velocity v and takes
> "T" time to cross the screen/lane1.
>
> at t=2 minute,another car comes now in lane 2 with same constant velocity
> and so on..........
>
> Now the frog can cross one lane either back or forth in one jump.These are
> the only movements allowed.The jump time is considerable(say in above case 1
> minute only).Note that times are all not correctly mentioned and consider
> times which are appropriate for the problem.The time details are mentioned
> to make everyone understand the problem.
>
> Design an algorithm to guarantee that the frog crosses the road safely.
>
> Think first..........................Hint is
> downwards.........................
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> ..
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
> .
>
> Hint: Think in terms of multithreading,semaphores,mutex and vectors
> etc..........
>
>
>
>
>
> On Wed, Jul 14, 2010 at 11:33 PM, Tech Id <[email protected]> wrote:
> > A frog has to cross a road to meet
> > its beloved she-frog at the other end.
>
> > The road however has cars coming and
> > can crush the frog.
>
> > Road is two lanes wide.
>
> > Devise an algorithm to help the frog carry on its family.
>
> > (I am sorry but it seems that I have missed
> > some parts of the problem here. If someone
> > remembers the complete question, please help me).
> > Thanks in advance!
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected]<algogeeks%2bunsubscr...@googlegroups
> > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Regards,
> Ashish
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
