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
3
Thus, it should be clear that one can always jump from the last position.
- isn't1 0
a counterexample? – Daniel Lubarov – 2013-10-20T19:36:19.900@Daniel No. Number of jumps will be equal to the value stored at that position. The last position is always a candidate from which one can jump since this position was not used previously for jumping. – Coding man – 2013-10-20T19:38:33.173
1This description is confusing because "jumps" is used to mean two different things, and with only one actual example, it's difficult to disambiguate which meaning goes with which usage. I'd prefer a description which referred to, say, "jumps" and "moves". With this terminology, you would say that each move consists of some number of jumps. The numbers in the input provide the maximum number of jumps, and the output can be unambiguously described as reporting the minimum number of moves. – breadbox – 2013-10-22T04:54:29.530
1What is the winning criterion? As you tagged [tag:code-golf] as well as [tag:code-challenge] it is not clear. – Howard – 2013-10-22T07:33:37.887
@breadbox Yes. I agree, its ambiguous. I will update the question soon. – Coding man – 2013-10-22T07:52:47.117
@Howard I removed the tag code-challenge – Coding man – 2013-10-22T07:56:17.263
Answer to [2] is 0 ? And, what is the answer to [0]? – TwiNight – 2013-10-25T21:59:54.847
What should happen if you go beyond the last spot? Will you move back right away? 1 2 2 3 2. Would it go to the following positions
1 2 4 3 1
or should that print -1? – Teun Pronk – 2014-06-11T15:23:35.163