14
\$\begingroup\$

Given a sequence of numbers, find the minimum number of jumps to go from the starting position to the end and come back to the starting position again.

Each element of the sequence denotes the maximum number of moves that one can move from that position.

At any position, you can make a jump of at max k moves, where k is the value stored at that position. After reaching the end, you can use only those positions for jumping which have not been used previously for jumping.

The input will be given as a sequence of numbers separated by single-spaces. Output should be a single number which is the minimum number of jumps used. If its not possible to go to the end and come back to the starting position, then print -1

Input:

2 4 2 2 3 4 2 2

Output:

6 (3 to reach end and 3 to come back)

Input

1 0

Output

-1

Note

  • Assume all the numbers of the sequence are non-negative

EDIT 1

The line "Thus, it should be clear that one can always jump from the last position." might be confusing, so I removed it from the question. It will have no effect on the question.

Winning Criteria :

The winner will be the one with the shortest code.

\$\endgroup\$
  • 3
    \$\begingroup\$ Thus, it should be clear that one can always jump from the last position. - isn't 1 0 a counterexample? \$\endgroup\$ – Daniel Lubarov Oct 20 '13 at 19:36
  • \$\begingroup\$ @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. \$\endgroup\$ – Coding man Oct 20 '13 at 19:38
  • 1
    \$\begingroup\$ This 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. \$\endgroup\$ – breadbox Oct 22 '13 at 4:54
  • 1
    \$\begingroup\$ What is the winning criterion? As you tagged code-golf as well as code-challenge it is not clear. \$\endgroup\$ – Howard Oct 22 '13 at 7:33
  • \$\begingroup\$ @breadbox Yes. I agree, its ambiguous. I will update the question soon. \$\endgroup\$ – Coding man Oct 22 '13 at 7:52
4
\$\begingroup\$

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.

\$\endgroup\$
4
\$\begingroup\$

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 
\$\endgroup\$
  • \$\begingroup\$ Very impressive work. It may be brute force but it is very elegant, nonetheless. \$\endgroup\$ – DavidC Oct 22 '13 at 19:11
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ This is partially wrong since it doesn't enforce the no jumping on a number twice rule, but it's a start, so I'll upvote for that. I had no idea if this was even possible :) \$\endgroup\$ – Doorknob Oct 22 '13 at 3:44
  • \$\begingroup\$ You are correct. I overlooked the no-jumping-on-a number-twice rule Tomorrow I'll try to correct that. \$\endgroup\$ – DavidC Oct 22 '13 at 3:51
3
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ Has huge potential for further golfing. But there's no handling of input and output, which is part of this problem. \$\endgroup\$ – WolframH Oct 23 '13 at 12:40
  • 1
    \$\begingroup\$ you have tons of unnecessary whitespace... \$\endgroup\$ – Doorknob Oct 23 '13 at 21:40
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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])
\$\endgroup\$
  • \$\begingroup\$ Wrong. At input [1], output should be 0(your output is 1). At input [3,0,0,1,4], output should be 3 (your output is -1) \$\endgroup\$ – Coding man Oct 22 '13 at 7:31
  • \$\begingroup\$ @Coding man: Oops, sorry. There was an exrtra jump check. if (i >= len(L)-1): S.append(n) seems to solve the problem \$\endgroup\$ – Triadic Oct 22 '13 at 7:51
  • \$\begingroup\$ Still giving wrong outputs. Ex: [2,0] ---> 1 (should be -1). \$\endgroup\$ – Coding man Oct 22 '13 at 8:54
  • \$\begingroup\$ @Coding man: I think my solution is in conflict with the "Thus, it should be clear that one can always jump from the last position.", as I consider [2,0] ---> 1 a valid solution, since it jumps across the end. \$\endgroup\$ – Triadic Oct 22 '13 at 9:30
  • 1
    \$\begingroup\$ I apologize for all these mistakes. The line "Thus, it should be clear that one can always jump from the last position." has been removed. It was used just to mean that last position was never used when we move forward in the sequence. So, it can always be used for jumping when we move backward. But, in [2,0] the value at last position is 0, you can make a jump of at max 0 moves. Hence, you can never reach the starting position. The question has been updated. \$\endgroup\$ – Coding man Oct 22 '13 at 10:56
2
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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
\$\endgroup\$
0
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ Data.List.permutations does not work in GHC, but only in GHCi. According to our Guide to Golfing Rules in Haskell, you should either add the import or mark your answer as "Haskell GHCi". The first option is generally preferred by Haskell golfers on this site. \$\endgroup\$ – Laikoni Jan 5 '18 at 14:40
  • \$\begingroup\$ Instead of a<-permutations[0..t l-1],let f=takeWhile(/=0)a, you can write f<-map(takeWhile(/=0))(permutations[0..t l-1]), which again can be golfed to f<-fst.span(>0)<$>permutations[0..t l-1]. With this you are back to 166 bytes even by adding the import: Try it online! \$\endgroup\$ – Laikoni Jan 5 '18 at 14:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.