APL(Dyalog), 116

f←{{⊃,/{2>|≡⍵:⊂⍵⋄⍵}¨⍵}⍣≡1{(⍴⍵)≤y←⊃⍺:⍵⋄⍵[y]=0:0⋄x←⍵⋄x[y]←0⋄∇∘x¨,∘⍺¨y+⍳y⌷⍵},⍵} {0≡+/⍵:¯1⋄(⌊/+/0=⍵)-+/0=x}↑⊃,/f¨⌽¨f x←⎕ 

Test cases

 2 4 2 2 3 4 2 2 6 1 0 ¯1 1 1 1 1 ¯1 3 1 2 0 4 3 1 0 

Approach

The approach is a brute force search using a recursive function.

Starting from position 1, set value at the current position to 0 and generate an array of the positions which can be jumped to from the current position. Pass the new position and the modified array to itself. Base cases are when the value at the current position is 0 (can't jump) or reaching the end.

Then, for each of the array generated, reverse it and do the search again. Because jumped positions are set to 0, we can't jump from there again.

For those array which we reached the end, find the ones which have the minimum number of 0's. Subtracting from it the number of 0's in the initial array gives the actual number of jumps performed.

Mathematica, 197 193 chars

Brute force.

Min[Length/@Select[Join[{1},#,{n},Reverse@#2]&@@@Tuples[Subsets@Range[3,n=Length[i=FromDigits/@StringSplit@InputString[]]]-1,2],{}⋃#==Sort@#∧And@@Thread[i[[#]]≥Abs[#-Rest@#~Append~1]]&]]/.∞->-1 

Mathematica 351

[Note: This is not yet fully golfed; Also, the input needs to be adjusted to fit the required format. And the no-jumping-on-the-same-position-twice rule needs to be implemented. There are also some code formatting issues that need addressing. But it's a start.]

A graph is constructed with nodes corresponding to each position, i.e. each input digit representing a jump. DirectedEdge[node1, node2] signifies that it is possible to jump from node1 to node 2. Shortest paths are found from start to end and then from end to start.

f@j_:= (d={v=FromCharacterCode/@(Range[Length[j]]+96),j}\[Transpose]; w[n_,o_:"+"]:={d[[n,1]],FromCharacterCode/@(ToCharacterCode[d[[n,1]]][[1]]+Range[d[[n,2]]] If[o=="+",1,-1])}; y=Graph[Flatten[Thread[DirectedEdge[#1,#2]]&@@@(Join[w[#]&/@Range[8],w[#,3]&/@Range[8]])]]; (Length[Join[FindShortestPath[y,v[[1]],v[[-1]]],FindShortestPath[y,v[[-1]],v[[1]]]]]-2) /.{0-> -1}) 

Usage

f[{2,4,2,2,3,4,2,2}] f[{3,4,0,0,6}] f[{1,0}] 

6
3
-1

Python 304

I think this new approach solves (I hope!) all the issues regarding the [2,0] case and similar:

In this version the input sequence is traversed (if possible) until the end and then we start the process again with the reversed sequence. Now we can garantee that for every valid solution one of the the jumps lands on the last element.

## Back and forward version # Changed: now the possible jumps from a given L[i] position # are at most until the end of the sequence def AvailableJumps(L,i): return range(1,min(L[i]+1,len(L)-i)) # In this version we add a boolean variable bkw to keep track of the # direction in which the sequence is being traversed def Jumps(L,i,n,S,bkw): # If we reach the end of the sequence... # ...append the new solution if going backwards if (bkw & (i == len(L)-1)): S.append(n) else: # ...or start again from 0 with the reversed sequence if going forward if (i == len(L)-1): Jumps(L[::-1],0,n,S,True) else: Laux = list(L) # Now we only have to disable one single position each time Laux[i] = 0 for j in AvailableJumps(L,i): Jumps(Laux,i+j,n+1,S,bkw) def MiniJumpBF(L): S = [] Jumps(L,0,0,S,False) return min(S) if (S) else -1 

These are the golfed versions:

def J(L,i,n,S,b): if (i == len(L)-1): S.append(n) if b else J(L[::-1],0,n,S,True) else: L2 = list(L) L2[i] = 0 for j in range(1,min(L[i]+1,len(L)-i)): J(L2,i+j,n+1,S,b) def MJ(L): S = [] J(L,0,0,S,False) return min(S) if (S) else -1 

And some examples:

MJ( [2, 4, 2, 2, 3, 4, 2, 2] ) --> 6 MJ( [0, 2, 4, 2, 2, 3, 4, 2, 2] ) --> -1 MJ( [3, 0, 0, 1, 4] ) --> 3 MJ( [2, 0] ) --> -1 MJ( [1] ) --> 0 MJ( [10, 0, 0, 0, 0, 0, 10, 0, 0, 0, 10, 0, 0, 0, 0, 0, 10] ) --> 4 MJ( [3, 2, 3, 2, 1] ) --> 5 MJ( [1, 1, 1, 1, 1, 1, 6] ) --> 7 MJ( [7, 1, 1, 1, 1, 1, 1, 7] ) --> 2 

R - 195

x=scan(nl=1) L=length n=L(x) I=1:(2*n-1) P=n-abs(n-I) m=0 for(l in I)if(any(combn(I,l,function(i)all(P[i[c(1,k<-L(i))]]==1,n%in%i,L(unique(P[i]))==k-1,diff(i)<=x[P][i[-k]])))){m=l;break} cat(m-1) 

Simulation:

1: 2 4 2 2 3 4 2 2 # everything after 1: is read from stdin 6 # output is printed to stdout 1: 1 0 # everything after 1: is read from stdin -1 # output is printed to stdout 

De-golfed:

x = scan(nlines = 1) # reads from stdin n = length(x) index = 1:(2*n-1) # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 position = c(1:n, (n-1):1) # 1 2 3 4 5 6 7 8 7 6 5 4 3 2 1 value = x[position] # 2 4 2 2 3 4 2 2 2 4 3 2 2 4 2 is_valid_path = function(subindex) { k = length(subindex) position[subindex[1]] == 1 & # starts at 1 position[subindex[k]] == 1 & # ends at 1 n %in% subindex & # goes through n (end of vector) length(unique(position[subindex])) == k - 1 & # visits each index once (except 1) all(diff(subindex) <= value[subindex[-k]]) } min_length = 0 for(len in index) { valid_paths = combn(index, len, FUN = is_valid_path) if (any(valid_paths)) { min_length = len break } } min_jumps = min_length - 1 cat(min_jumps) # outputs to stout 

Python 271

this is my solution:

## To simplify the process we unfold the forward-backward sequence def unfold(L): return L + L[:-1][::-1] ## Possible jumps from a given L[i] position def AvailableJumps(L,i): return range(1,L[i]+1) # To disable a used position, in the forward and backward sites # (the first one is not really necessary) def Use(L,i): L[i] = 0 L[ len(L) - i - 1] = 0 return L def Jumps(L,i,n,S): if (i >= len(L)-1): S.append(n) else: Laux = list(L) Use(Laux,i) for j in AvailableJumps(L,i): Jumps(Laux,i+j,n+1,S) def MiniJump(L): S = [] Jumps(unfold(L),0,0,S) return min(S) if (S) else -1 

Examples:

print MiniJump([2,4,2,2,3,4,2,2]) print MiniJump([0,2,4,2,2,3,4,2,2]) 

And these are the (partially by now) golfed versions:

def J(L,i,n,S): if (i >= len(L)-1): S.append(n) else: La = list(L) La[len(La) - i - 1] = 0 for j in range(1,L[i]+1): J(La,i+j,n+1,S) def MJ(L): S = [] J(L + L[:-1][::-1],0,0,S) return min(S) if (S) else -1 

Some examples:

print MJ([2,4,2,2,3,4,2,2]) print MJ([0,2,4,2,2,3,4,2,2]) print MJ([3,4,0,0,6]) 

Ruby - 246

a=gets.split.map &:to_i L=a.size;r=[];a.collect!{|v|([1,v].min..v).to_a};S=a[0].product *a[1..-1];S.each{|s|i=0;b=L==1&&s[i]!=0 ?0:1;(L*2).times{|c|r<<c if i==L-1&&b==0;break if !s[i]||s[i]==0;if i==L-1;b=i=0;s.reverse!end;i+=s[i]}} puts r.min||-1 

Simulation:

2, 4, 2, 2, 3, 4, 2, 2 6 0, 2, 4, 2, 2, 3, 4, 2, 2 -1 0 -1 1 0 

Ruby - about 700 golfed. I started a golfed version, with single-character names for variables and methods, but after awhile I got more interested in the algorithm than the golf, so stopped trying to optimize code length. Nor did I worry about getting the input string. My effort is below.

To help you understand how it works I've included comments that show how a particular string (u = "2 1 4 3 0 3 4 4 3 5 0 3") is manipulated. I enumerate combinations of "rocks in the stream" that are available to hop on. These are represented with a binary string. I give the example 0b0101101010 in the comments and show how it would be used. The 1's correspond to the positions of rocks available for the initial trip; the 0's for the return trip. For each such allocation, I use dynamic programming to determine the minimal number of hops required in each direction. I also perform a few simple optimizations to eliminate some combinations early on.

I've run it with the strings given in other answers and get the same results. Here are some other results I obtained:

"2 1 4 3 0 3 4 4 3 5 0 3" # => 8 "3 4 3 5 6 4 7 4 3 1 5 6 4 3 1 4" # => 7 "2 3 2 4 5 3 6 3 2 0 4 5 3 2 0 3" # => 10 "3 4 3 0 4 3 4 4 5 3 5 3 0 4 3 3 0 3" # => 11 "2 3 2 4 5 3 6 3 2 0 4 5 3 2 0 3 4 1 6 3 8 2 0 5 2 3" # => 14 

I would be interested in hearing whether others get the same results for these strings. Performance is reasonable good. For example, it took less than a minute to get a solution for this string:

"3 4 3 0 4 3 4 4 5 3 5 3 0 4 3 3 0 3 4 5 3 2 0 3 4 1 6 3 2 0 4 5 3 2 0 3 4 1 6 3 0 4 3 4 4 5 0 1"

The code follows.

I=99 # infinity - unlikely we'll attempt to solve problems with more than 48 rocks to step on def leap!(u) p = u.split.map(&:to_i) # p = [2,1,4,3,0,3,4,4,3,5,0,3] s = p.shift # s=2, p = [1,4,3,0,3,4,4,3,5,0,3] # start f = p.pop # f=3, p = [1,4,3,0,3,4,4,3,5,0] # finish q = p.reverse # q = [0,5,3,4,4,3,0,3,4,1] # reverse order # No path if cannot get to a non-zero rock from s or f return -1 if t(p,s) || t(q,f) @n=p.size # 10 rocks in the stream r = 2**@n # 10000000000 - 11 binary digits j = s > @n ? 0 : 2**(@n-s) # 100000000 for s = 2 (cannot leave start if combo number is smaller than j) k=r-1 # 1111111111 - 10 binary digits b=I # best number of hops so far (s->f + f->s), initialized to infinity (j..k).each do |c| # Representative combo: 0b0101101010, convert to array c += r # 0b10 1 0 1 1 0 1 0 1 0 c = c.to_s(2).split('').map(&:to_i) # [1,0,1,0,1,1,0,1,0,1,0] c.shift # [0,1,0,1,1,0,1,0,1,0] s->f: rock offsets available: 1,3,4,6,8 d = c.map {|e|1-e}.reverse # [1,0,1,0,1,0,0,1,0,1] f->s: rock offsets available: 0,2,5,7,9 c = z(c,p) # [0,4,0,0,3,0,4,0,5,0] s->f: max hops by offset for combo c d = z(d,q) # [0,0,3,0,4,0,0,3,0,1] f->s: max hops by offset for combo c # Skip combo if cannot get from to a rock from f, or can't # get to the end (can always get to a rock from s if s > 0). next if [s,f,l(c),l(d)].max < @n && t(d,f) # Compute sum of smallest number of hops from s to f and back to s, # for combo c, and save it if it is the best solution so far. b = [b, m([s]+c) + m([f]+d)].min end b < I ? b : -1 # return result end # t(w,n) returns true if can conclude cannot get from sourch n to destination def t(w,n) n==0 || (w[0,n].max==0 && n < @n) end def l(w) w.map.with_index {|e,i|i+e}.max end def z(c,p) c.zip(p).map {|x,y| x*y} end def m(p) # for s->f: p = [2,0,4,0,0,3,0,4,0,5,0] - can be on rock offsets 2,5,7,9 # for f->s: p = [3,0,0,3,0,4,0,0,3,0,1] - can be on rock offsets 3,5,8,10 a=[{d: 0,i: @n+1}] (0..@n).each do |j| i=@n-j v=p[i] if v > 0 b=[I] a.each{|h| i+v < h[:i] ? break : b << (1 + h[:d])} m = b.min a.unshift({d: m,i: i}) if m < I end end h = a.shift return h[:i]>0 ? I : h[:d] end 

Haskell, 173 166 bytes, 159 bytes in GHCi

Here is the normal version:

import Data.List

t=length j[_]=0 j l=y[t f|f<-fst.span(>0)<$>permutations[0..t l-1],u<-f,u==t l-1,all(\(a,b)->abs(b-a)<=l!!a)$zip(0:f)$f++[0]] y[]=0-1 y l=minimum l+1 

Here is the GHCi answer (put the line one at a time):

t=length y[]=0-1;y l=minimum l+1 j[_]=0;j l=y[t f|f<-fst.span(>0)<$>Data.List.permutations[0..t l-1],u<-f,u==t l-1,all(\(a,b)->abs(b-a)<=l!!a)$zip(0:f)$f++[0]] 

Just a bruteforce. Generate the possible answer. (i.e. permutation of [0..n-1] with zero and following element dropped. Then check if the answer is correct. Get the minimum length and add by one. (Since the leading and trailing zeroes is delete).

How to use: j[3,4,0,0,6] -> 3