Dada uma sequência de números, encontre o número mínimo de saltos para ir da posição inicial até o final e volte à posição inicial.

Cada elemento da sequência indica o número máximo de movimentos que se pode mover a partir dessa posição.

Em qualquer posição, você pode saltar no máximo de k movimentos, em que k é o valor armazenado nessa posição. Depois de chegar ao fim, você pode usar apenas as posições para pular que não foram usadas anteriormente para pular.

A entrada será dada como uma sequência de números separados por espaços simples. A saída deve ser um número único, que é o número mínimo de saltos usados. Se não for possível ir até o fim e voltar à posição inicial, imprima -1

Entrada:

2 4 2 2 3 4 2 2

Resultado:

6 (3 para chegar ao fim e 3 para voltar)

Entrada

1 0

Resultado

-1

Nota

• Suponha que todos os números da sequência não sejam negativos

EDIT 1

A linha "Assim, deve ficar claro que sempre se pode pular da última posição". pode ser confuso, então eu o removi da pergunta. Não terá efeito sobre a questão.

Critérios de vencimento:

O vencedor será aquele com o código mais curto.

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←⎕

Casos de teste

      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

Abordagem

A abordagem é uma pesquisa de força bruta usando uma função recursiva.

A partir da posição 1, defina o valor na posição atual como 0 e gere uma matriz das posições que podem ser saltadas para a partir da posição atual. Passe a nova posição e a matriz modificada para si mesma. Os casos básicos são quando o valor na posição atual é 0 (não é possível pular) ou está chegando ao fim.

Em seguida, para cada matriz gerada, inverta-a e faça a pesquisa novamente. Como as posições saltadas estão definidas como 0, não podemos pular de lá novamente.

Para os vetores que atingimos o final, encontre os que possuem o número mínimo de 0's. Subtraindo dele o número de 0 na matriz inicial fornece o número real de saltos executados.

Mathematica, 197 193 caracteres

Força bruta.

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

[Nota: isto ainda não está totalmente jogado; Além disso, a entrada precisa ser ajustada para se ajustar ao formato necessário. E a regra de não pular na mesma posição duas vezes precisa ser implementada. Há também alguns problemas de formatação de código que precisam ser resolvidos. Mas é um começo.]

Um gráfico é construído com nós correspondentes a cada posição, ou seja, cada dígito de entrada representando um salto. DirectedEdge[node1, node2]significa que é possível pular do nó1 para o nó 2. Os caminhos mais curtos são encontrados do início ao fim e do fim ao início.

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})

Uso

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

6
3
-1

Python 304

Eu acho que essa nova abordagem resolve (espero!) Todos os problemas relacionados ao caso [2,0] e similares:

Nesta versão, a sequência de entrada é percorrida (se possível) até o final e, em seguida, iniciamos o processo novamente com a sequência invertida. Agora podemos garantir que, para cada solução válida, um dos saltos caia no último elemento.

## 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

Estas são as versões golfed:

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

E alguns exemplos:

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)

Simulação:

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-golfe:

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

esta é a minha solução:

## 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

Exemplos:

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

E estas são as versões (parcialmente até agora) do golfe:

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

Alguns exemplos:

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

Simulação:

2, 4, 2, 2, 3, 4, 2, 2
6

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

0
-1

1
0

Ruby - cerca de 700 jogadores de golfe. Comecei uma versão golf, com nomes de caracteres únicos para variáveis ​​e métodos, mas depois de um tempo fiquei mais interessado no algoritmo do que no golf, então parei de tentar otimizar o comprimento do código. Também não me preocupei em obter a string de entrada. Meu esforço está abaixo.

Para ajudar você a entender como funciona, incluí comentários que mostram como uma string específica (u = "2 1 4 3 0 3 4 4 3 5 0 3") é manipulada. Enumero combinações de "rochas no fluxo" que estão disponíveis para saltar. Estes são representados com uma cadeia binária. Dou o exemplo 0b0101101010 nos comentários e mostro como ele seria usado. Os 1s correspondem às posições das rochas disponíveis para a viagem inicial; os 0 para a viagem de volta. Para cada alocação, uso a programação dinâmica para determinar o número mínimo de saltos necessários em cada direção. Também realizo algumas otimizações simples para eliminar algumas combinações desde o início.

Eu o executei com as strings fornecidas em outras respostas e obtenho os mesmos resultados. Aqui estão alguns outros resultados que obtive:

"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

Eu estaria interessado em saber se outras pessoas obtêm os mesmos resultados para essas strings. O desempenho é bom razoável. Por exemplo, levou menos de um minuto para obter uma solução para essa sequência:

"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"

O código segue.

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 em GHCi

Aqui está a versão normal:

importar 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

Aqui está a resposta do GHCi (coloque a linha uma de cada vez):

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]]

Apenas uma força bruta. Gere a resposta possível. (ou seja, permutação de [0..n-1] com zero e o elemento seguinte eliminado. Em seguida, verifique se a resposta está correta. Obtenha o comprimento mínimo e adicione um. (Como os zeros à esquerda e à direita são excluídos).

Como usar: j[3,4,0,0,6]->3