http://code.google.com/p/frogger-game/source/browse/trunk/
can it be interview question??
the frong will wait and this would vary at run time, the car_times is
storing just one value, multiple cars can come in a lane so it should be
hash map
one thought: for each lane we know when the car would not be there
we only need to consider the time t+delta in a lane when frong is in lane n
at time t
so it implies that if there are n lanes, and we know all the time when the
car is not at the crossing point, we need to find a monotonically increasing
sequence
eg
lane1 4 7 10
lane2 2 5 9
lane3 3 6 11
lane4 1 4 7
so the times when the car is not there will be
lan1 1 2 3 5 6 8 9 11 12
lan2 1 3 4 6 7 8 10 11 12
lan3 1 2 4 5 7 8 9 10 12
lan4 2 3 5 6 8 9 10 11 12
so 1->3>4>5 gives one solution
2->3->4->5 another solution
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Thu, Jul 15, 2010 at 9:56 PM, Tech Id <tech.login....@gmail.com> wrote:
> 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 <akjlucky4...@gmail.com> 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 <tech.login....@gmail.com>
> 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 algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> <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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
