Biorąc pod uwagę sekwencję liczb, znajdź minimalną liczbę skoków, aby przejść od pozycji początkowej do końca i wrócić do pozycji początkowej.

Każdy element sekwencji oznacza maksymalną liczbę ruchów, które można przesunąć z tej pozycji.

W dowolnej pozycji możesz wykonać skok przy maks. K ruchach, gdzie k jest wartością zapisaną w tej pozycji. Po osiągnięciu końca możesz użyć tylko tych pozycji do skakania, które nie były wcześniej używane do skakania.

Dane wejściowe zostaną podane jako ciąg liczb oddzielonych pojedynczymi spacjami. Wyjście powinno być pojedynczą liczbą, która jest minimalną liczbą zastosowanych skoków. Jeśli nie można przejść do końca i wrócić do pozycji wyjściowej, wydrukuj -1

Wejście:

2 4 2 2 3 4 2 2

Wynik:

6 (3, aby dotrzeć do końca i 3, aby wrócić)

Wejście

1 0

Wynik

-1

Uwaga

• Załóż, że wszystkie liczby w sekwencji są nieujemne

EDYCJA 1

Wiersz „Zatem powinno być jasne, że zawsze można skoczyć z ostatniej pozycji”. może być mylące, więc usunąłem go z pytania. Nie będzie to miało wpływu na pytanie.

Zwycięskie kryteria:

Zwycięzcą zostanie ten z najkrótszym kodem.

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

Przypadki testowe

      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

Podejście

Podejście to polega na wyszukiwaniu brutalnej siły za pomocą funkcji rekurencyjnej.

Zaczynając od pozycji 1, ustaw wartość w bieżącej pozycji na 0 i wygeneruj tablicę pozycji, do których można przeskoczyć z bieżącej pozycji. Przekaż nową pozycję i zmodyfikowaną tablicę do siebie. Przypadki podstawowe występują wtedy, gdy wartość w bieżącej pozycji wynosi 0 (nie można skoczyć) lub dochodzi do końca.

Następnie dla każdej wygenerowanej tablicy odwróć ją i wykonaj wyszukiwanie ponownie. Ponieważ pozycje skakania są ustawione na 0, nie możemy ponownie skakać z tego miejsca.

Dla tablic, które osiągnęliśmy do końca, znajdź te, które mają minimalną liczbę zer. Odejmując od niej liczbę zer w tablicy początkowej, podaje rzeczywistą liczbę wykonanych skoków.

Mathematica, 197 193 znaków

Brutalna siła.

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

[Uwaga: To nie jest jeszcze w pełni golfa; Ponadto dane wejściowe należy dostosować, aby pasowały do ​​wymaganego formatu. I należy wprowadzić zasadę „nie skakać na tej samej pozycji dwa razy”. Istnieją również problemy z formatowaniem kodu, które wymagają rozwiązania. Ale to początek.]

Wykres składa się z węzłów odpowiadających każdej pozycji, tj. Każdej cyfrze wejściowej reprezentującej skok. DirectedEdge[node1, node2]oznacza, że ​​możliwe jest przejście od węzła 1 do węzła 2. Najkrótsze ścieżki znajdują się od początku do końca, a następnie od końca do początku.

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

Stosowanie

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

6
3
-1

Python 304

Myślę, że to nowe podejście rozwiązuje (mam nadzieję!) Wszystkie problemy dotyczące przypadku [2,0] i podobne:

W tej wersji sekwencja wejściowa jest przechodzona (jeśli to możliwe) do końca, a następnie ponownie rozpoczynamy proces odwróconą sekwencją. Teraz możemy zagwarantować, że dla każdego poprawnego rozwiązania jeden ze skoków ląduje na ostatnim elemencie.

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

Oto wersje gry w golfa:

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

I kilka przykładów:

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)

Symulacja:

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

Gra w golfa:

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

to jest moje rozwiązanie:

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

Przykłady:

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

A są to (częściowo do tej pory) wersje gry w golfa:

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

Kilka przykładów:

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

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

Symulacja:

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

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

0
-1

1
0

Ruby - około 700 golfistów. Zacząłem grę w golfa z jednoznakowymi nazwami zmiennych i metod, ale po pewnym czasie bardziej zainteresowałem się algorytmem niż golfem, więc przestałem próbować optymalizować długość kodu. Nie martwiłem się też o ciąg wejściowy. Mój wysiłek jest poniżej.

Aby pomóc ci zrozumieć, jak to działa, zamieściłem komentarze pokazujące, w jaki sposób manipulowany jest określony ciąg (u = "2 1 4 3 0 3 4 4 3 5 0 3"). Wymieniam kombinacje „skał w strumieniu”, które można przeskoczyć. Są one reprezentowane przez ciąg binarny. W komentarzach podam przykład 0b0101101010 i pokazuję, jak by go wykorzystano. Te 1 odpowiadają pozycjom skał dostępnych podczas pierwszej podróży; zera dla podróży powrotnej. Do każdego takiego przydziału używam programowania dynamicznego, aby określić minimalną liczbę przeskoków wymaganych w każdym kierunku. Przeprowadzam również kilka prostych optymalizacji, aby wcześnie wyeliminować niektóre kombinacje.

Uruchomiłem go z ciągami podanymi w innych odpowiedziach i uzyskałem te same wyniki. Oto kilka innych wyników, które uzyskałem:

"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

Chciałbym dowiedzieć się, czy inni uzyskają takie same wyniki dla tych ciągów. Wydajność jest dość dobra. Na przykład znalezienie rozwiązania dla tego ciągu zajęło mniej niż minutę:

„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”

Kod następuje.

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 bajtów, 159 bajtów w GHCi

Oto normalna wersja:

importuj 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

Oto odpowiedź GHCi (wstaw wiersz po kolei):

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

Po prostu brutalna siła. Wygeneruj możliwą odpowiedź. (tj. permutacja [0..n-1] z pominiętym zerem i następującym po nim elementem. Następnie sprawdź, czy odpowiedź jest poprawna. Uzyskaj minimalną długość i dodaj jeden. (Ponieważ zera wiodące i końcowe zera są usuwane).

Jak używać: j[3,4,0,0,6]->3