CareerCup

1. Build graph of reachable stones from every stone
2. Find shortest path in graph using dijkstra algorithm.

Here is my solution

def min_rabbit_jumps(js, rs):
    """Find minimum number of jumps to cross river

    js - possible jumps
    rs - distance between adjacent rocks starting from first

    >>> min_rabbit_jumps([3,1], [1,2,1])
    2
    >>> min_rabbit_jumps([3,1], [2,1,2])
    3
    >>> min_rabbit_jumps([3,1], [1,4])
    inf
    """
    ns = to_graph(js, rs)  # index -> children

    # using dijkstra algorithm find shortest path in graph `ns`
    i2d = {i: float("inf") for i in range(len(ns))}
    i2d[0] = 0
    q = set(range(len(ns))) # unprocessed nodes queue
    while q:
        # find closest elemnt
        d, i = min((i2d[i], i) for i in q)
        q.remove(i)

        for n in ns[i]:
            if i2d[n] > d + 1:
                i2d[n] = d + 1
    return i2d[len(rs)]


def to_graph(js, rs):
    """Convert jumps `js` and rocks `rs` to graph

    Returns graph of possible positions and available jumps from them.
    """
    # index to distance and vice versa
    d, i2d, d2i  = 0, {0: 0}, {0: 0}
    for i, r in enumerate(rs):
        d += r
        i2d[i + 1] = d
        d2i[d] = i + 1

    # nodes of the graph
    ns = [[] for _ in i2d]
    for i, d in i2d.items():
        for j in js:
            ji = d2i.get(d + j) # jump index
            if ji is not None:
                ns[i].append(ji)
                ns[ji].append(i)
    return ns

1. represent the rocks in an array rocks [n]( where n= (m2-m1) + (m3-m2).......) such that rocks[i]=1 if a rock is present at i distance from m1 else
2. Take another array jumps[n]. Initialize all jumps[i]= infinity and jumps[0]=0
3. now start
from i=1 to i=n
............if(rocks [i] != 0)
.................. jumps[i]= min( jumps[i-Wj]) where Wj is the array containing Ways to jump
............else
...................jumps[i]= infinity
4. jumps[n] contains your minimum jumps

How rabbit can perfrom jump of length 3 if N=2.

Let A be the array for storing results which has been initialized to a highest integer value, Let D be the array for storing diff, eg. D[1] contains m2-m1 and so on. Let R contains the list of possible values where rabbit can jump.

for(i=1;i<N;i++) {
  diff =0;
  for(j=i;j>0;j--) {
    diff+=D[j];
    if(R.exists(diff)) {
      if(A[i]>A[j]+1) {//careful about the overflow
        A[i]=A[j]+1;
      }
    }
  }
}

And A[N-1] contains the minimum value. :)

You actually don't need Djisktra for this. The Length of the Jump doesn't need to be optimized, just the number of them.

We can create a graph, with edge I->J abd J<-I if j can be reached from I based on the number of Steps between I and J and what is allowed. And then we just find the shortest path from S - E in terms of number of nodes using BFS (Mark visited node, else will fail).

I am still wondering on the reason for the "can also jump backwards", if the number of jump lengths possible backwards is the same as forwards, I don't see how a shortest path will have a jump backwards. Even if the Jump backwards were different than forwards, I don't see how a shortest path will include a cycle. Added to confuse ?

try below test case to understand "can also jump backwards"

Input
For each test case, the first line contains 2 space separated integers, M and N. The second line contains M-1 space separated integers denoting the distance between consecutive rocks in the river. The third line contains N space separated integers denoting the possible jump lengths.
4 3
12 3 2
15 5 3