Minimum river crossing time

Question

The frog is trying to get to the other side of the river. First, on the bank side (position -1) and wants to get on the other side of the bank (position N).

The frog can jump any distance between 1 and D. If D is less than N, the frog cannot jump directly. There are stones to help the frog jumper, but they will be out of the water only after a certain time, since the water is constantly decreasing. A frog can jump on and off stones only when the stone comes out of the water. The stones in the river are described in array A, consisting of N integers. A [K] represents the time when the stone in position K will be removed from the water. A [K] = - 1 means the absence of stone in this position. The goal is to find the earliest time when the frog can reach another bank.

Example D = 3, N = 6.
A [0] = 1

A [1] = - 1

A [2] = 0

A [3] = 2

A [4] = 3

A [5] = 5

At time 2, 3 stones will be removed from the water, and the frog can jump to the other shore in 3 jumps.

Can someone help me with this approach? I cannot come up with an effective approach to solving this.

Answer 1

Here's a pretty simple implementation.

Use an array that represents the number of stones plus 2: -1 = a bank of frogs, and N = another bank.

Note the use of access macros A and J to allow a negative index:

 // frogjmp/frogjmp -- jump frog across river #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #include <errno.h> #define sysfault(_fmt...) \ do { \ printf(_fmt); \ exit(1); \ } while (0) FILE *xfin; int Dmax; // maximum allowable jump distance int Nmax; // number of stones // list of positions in river: // value is number of rounds needed to uncover a stone as valid jump-to place // -1 -- no stone at position // position is usable as jump-to point iff value is zero // // special index values: // A(-1) is initial frog position (starting river bank) // A(Nmax) is the destination river bank // // the layout of this [and J] are: // frog bank position | stones[Nmax] | other bank position int *Aptr; // river state #define A(_idx) Aptr[(_idx) + 1] int jmpcnt; // number of jumps used int *Jptr; // jump history #define J(_idx) Jptr[(_idx) + 1] int Tcur; // current time period / round int Tmax; // maximum time for all stones uncovered // getval -- read in numeric value int getval(const char *sym,int idx) { char prompt[100]; char *bp; char linebuf[1000]; int val; bp = prompt; bp += sprintf(bp,"%s",sym); if (idx >= 0) bp += sprintf(bp,"[%d]",idx); bp += sprintf(bp,": "); // interactive -- show prompt if (xfin == stdin) { fputs(prompt,stdout); fflush(stdout); } // get line bp = fgets(linebuf,sizeof(linebuf),xfin); if (bp == NULL) sysfault("getval: premature EOF\n"); // isolate the number bp = strtok(linebuf," \t\n"); if (bp == NULL) sysfault("getval: empty line\n"); // get the number value val = atoi(bp); // file input -- show prompt and value read if (xfin != stdin) { fputs(prompt,stdout); printf("%d\n",val); } return val; } // chkbad -- check for impossible (too many -1 values in a row) void chkbad(int lo) { int hi; int idx; int badflg; badflg = 1; hi = lo + Dmax; if (hi > Nmax) { hi = Nmax; badflg = 0; } for (idx = lo; idx < hi; ++idx) { if (A(idx) >= 0) { badflg = 0; break; } } if (badflg) sysfault("chkbad: impossible\n"); } // jmpshow -- show river state with jumps void jmpshow(void) { int idx; int val; printf("A:"); for (idx = 0; idx <= Nmax; ++idx) { val = A(idx); printf(" %d=%d%s",idx,val,J(idx) ? "<" : " "); } printf("\n"); } // frogjmp -- jump the frog to the farthest reachable position from current one // RETURNS: new frog position (-1=nothing valid) int frogjmp(int frogcur) // frogcur -- current frog position { int idx; int lo; int hi; int val; int best; // get range of possible jump-to positions from the current frog position lo = frogcur + 1; hi = frogcur + Dmax; if (hi > Nmax) hi = Nmax; // find the farthest/best jump (ie the _last_ valid jump we find here) // A values: // <0 -- no stone in position // 0 -- stone/position can be jumped to now // >0 -- stone can't be jumped to now -- will be uncovered in future round best = -1; for (idx = lo; idx <= hi; ++idx) { val = A(idx); if (val == 0) best = idx; } // found a landing point -- advance jump count and mark it as being jumped // to if (best >= 0) { jmpcnt += 1; J(best) = 1; } return best; } // dotime -- process current time period // RETURNS: 1=frog on other side int dotime(void) { int frogcur; int idx; int doneflg; printf("dotime: time %d\n",Tcur); // reset the jump history jmpcnt = 0; for (idx = -1; idx <= Nmax; ++idx) J(idx) = 0; J(-1) = 1; // show state at start of time period jmpshow(); // frog always starts here frogcur = -1; doneflg = 0; while (1) { // find the best position (farthest) to jump to from the current // position // bug out if no place to jump to found within this round (ie we // can't get to the other side without a new drain operation) frogcur = frogjmp(frogcur); if (frogcur < 0) break; // stop when frog gets to the other side -- we're done if (frogcur >= Nmax) { doneflg = 1; printf("dotime: frog landed at time %d after %d jumps\n", Tcur,jmpcnt); jmpshow(); break; } // show state after current jump jmpshow(); } return doneflg; } // dodrain -- drain river by one level void dodrain(void) { int idx; int val; // bump down the level for each stone: the time remaining before it becomes // accessible/usable // we only do this for "covered" stones, never for non-existent ones or // ones that are already "uncovered" for (idx = 0; idx < Nmax; ++idx) { val = A(idx); if (val > 0) A(idx) = val - 1; } } // dofile -- process test void dofile(void) { int idx; // get the maximum jump the frog can do Dmax = getval("D",-1); // get the number of stones/positions in the river Nmax = getval("N",-1); // get enough space for the [in river] stone positions + the bank positions Aptr = malloc(sizeof(int) * (Nmax + 2)); Jptr = malloc(sizeof(int) * (Nmax + 2)); // get values for all the stones in the river Tmax = -1; for (idx = 0; idx < Nmax; ++idx) { Tcur = getval("A",idx); A(idx) = Tcur; if (Tcur > Tmax) Tmax = Tcur; } // the river banks are always accessible jump points (ie they're _not_ // "covered") A(-1) = 0; A(Nmax) = 0; // show the initial state after reading inpu jmpshow(); // check for impossible river for (idx = 0; idx < Nmax; ++idx) chkbad(idx); // do all possible time periods for (Tcur = 0; Tcur <= Tmax; ++Tcur) { // test the current river state to see if frog can make it across now // stop when we're done if (dotime()) break; // we were blocked by some inaccessible jump // drain the river by a level in prep for next time period // this makes _some_ stones [based on their updated values] as valid // jump-to points for the next round that may not have been accessible // during the current round dodrain(); } free(Aptr); free(Jptr); } // main -- main program int main(int argc,char **argv) { char *cp; --argc; ++argv; if (argc <= 0) { xfin = stdin; dofile(); } for (; argc > 0; --argc, ++argv) { cp = *argv; xfin = fopen(cp,"r"); if (xfin == NULL) sysfault("main: unable to open '%s' -- %s\n",cp,strerror(errno)); dofile(); fclose(xfin); } } 

---

Here is the output of the program to enter your example:

 D: 3 N: 6 A[0]: 1 A[1]: -1 A[2]: 0 A[3]: 2 A[4]: 3 A[5]: 5 A: 0=1 1=-1 2=0 3=2 4=3 5=5 6=0 dotime: time 0 A: 0=1 1=-1 2=0 3=2 4=3 5=5 6=0 A: 0=1 1=-1 2=0< 3=2 4=3 5=5 6=0 dotime: time 1 A: 0=0 1=-1 2=0 3=1 4=2 5=4 6=0 A: 0=0 1=-1 2=0< 3=1 4=2 5=4 6=0 dotime: time 2 A: 0=0 1=-1 2=0 3=0 4=1 5=3 6=0 A: 0=0 1=-1 2=0< 3=0 4=1 5=3 6=0 A: 0=0 1=-1 2=0< 3=0< 4=1 5=3 6=0 dotime: frog landed at time 2 after 3 jumps A: 0=0 1=-1 2=0< 3=0< 4=1 5=3 6=0< 

---

Update:

The program iterates over time periods, from the initial state to the last round (ie, the highest value of "stone"): T0, T1, ...

In each round, the frog begins on the banks of the river. For a given frog position, the farthest “jump” position is calculated based on the maximum possible range of frog jumps and the current state of the stones in this range. If such a valid transition position is found (that is, the transition point to the initial position has a zero value), the process is repeated until the frog is on the other side.

If no transition position is found (i.e. progress is blocked by non-existent and / or covered stones), the levels of "coverage" of the stone are reduced by one. Then a new round begins.

Answer 2

Here a solution is possible:

Iterate the array by moving index ( i ) to the stone ( A[i] ) with the smallest time in the range A[i+1..i+D] . At each step, keep the maximum time found so far ( maxTime = max(maxTime, A[i] ). Repeat this process until i < ND . When the process runs, the maximum time is found in maxTime .

Complexity O ((ND) D) .