Bestimmen Sie bei einer gegebenen Zahlenfolge die Mindestanzahl der Sprünge von der Startposition bis zum Ende und kehren Sie wieder zur Startposition zurück.

Jedes Element der Sequenz gibt die maximale Anzahl von Zügen an, die man von dieser Position aus ausführen kann.

An jeder Position können Sie einen Sprung von maximal k Zügen ausführen, wobei k der Wert ist, der an dieser Position gespeichert ist. Nach Erreichen des Endes können Sie nur die Positionen zum Springen verwenden, die zuvor nicht zum Springen verwendet wurden.

Die Eingabe erfolgt als Folge von Zahlen, die durch einzelne Leerzeichen voneinander getrennt sind. Die Ausgabe sollte eine einzelne Zahl sein, die die Mindestanzahl der verwendeten Sprünge darstellt. Wenn es nicht möglich ist, bis zum Ende zu gehen und zur Startposition zurückzukehren, drucken Sie -1

Eingang:

2 4 2 2 3 4 2 2

Ausgabe:

6 (3, um das Ende zu erreichen und 3, um zurückzukommen)

Eingang

1 0

Ausgabe

-1

Hinweis

• Angenommen, alle Zahlen der Sequenz sind nicht negativ

EDIT 1

Die Zeile "Somit sollte klar sein, dass man immer von der letzten Position springen kann." könnte verwirrend sein, also habe ich es von der Frage entfernt. Es wird keine Auswirkung auf die Frage haben.

Gewinnkriterien:

Der Gewinner ist der mit dem kürzesten Code.

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

Testfälle

      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

Ansatz

Der Ansatz ist eine Brute-Force-Suche unter Verwendung einer rekursiven Funktion.

Setzen Sie ab Position 1 den Wert an der aktuellen Position auf 0 und generieren Sie eine Reihe von Positionen, die von der aktuellen Position aus angesprungen werden können. Übergeben Sie die neue Position und das geänderte Array an sich selbst. Basisfälle sind, wenn der Wert an der aktuellen Position 0 ist (kann nicht springen) oder das Ende erreicht.

Kehren Sie dann für jedes erzeugte Array es um und führen Sie die Suche erneut durch. Da Sprungpositionen auf 0 gesetzt sind, können wir von dort nicht mehr springen.

Für das Array, das wir am Ende erreicht haben, finden Sie diejenigen, die die Mindestanzahl von Nullen haben. Das Subtrahieren der Anzahl der Nullen in dem anfänglichen Array ergibt die tatsächliche Anzahl der durchgeführten Sprünge.

Mathematica, 197–193 Zeichen

Rohe Gewalt.

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

[Hinweis: Dies ist noch nicht vollständig Golf; Außerdem muss die Eingabe an das erforderliche Format angepasst werden. Und die Regel, dass nicht zweimal auf dieselbe Position gesprungen wird, muss implementiert werden. Es gibt auch einige Probleme bei der Code-Formatierung, die behoben werden müssen. Aber es ist ein Anfang.]

Ein Graph wird mit Knoten konstruiert, die jeder Position entsprechen, dh jede eingegebene Ziffer repräsentiert einen Sprung. DirectedEdge[node1, node2]bedeutet, dass es möglich ist, von Knoten 1 zu Knoten 2 zu springen. Die kürzesten Pfade werden von Anfang bis Ende und dann von Ende bis Anfang gefunden.

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

Verwendung

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

6
3
-1

Python 304

Ich denke, dieser neue Ansatz löst (ich hoffe!) Alle Probleme im Zusammenhang mit dem [2,0] -Fall und ähnlichem:

In dieser Version wird die Eingabereihenfolge (wenn möglich) bis zum Ende durchlaufen und dann der Vorgang mit der umgekehrten Reihenfolge erneut gestartet. Jetzt können wir garantieren, dass für jede gültige Lösung einer der Sprünge auf dem letzten Element landet.

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

Dies sind die Golf-Versionen:

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

Und einige Beispiele:

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

Entgolft:

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

Das ist meine Lösung:

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

Beispiele:

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

Und das sind die (teilweise mittlerweile) Golf-Versionen:

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

Einige Beispiele:

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

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 - etwa 700 Golfer. Ich begann eine Golf-Version mit Namen aus einem Zeichen für Variablen und Methoden, aber nach einer Weile interessierte ich mich mehr für den Algorithmus als für das Golfspiel, also hörte ich auf, zu versuchen, die Codelänge zu optimieren. Ich habe mich auch nicht darum gekümmert, die Eingabezeichenfolge zu bekommen. Meine Anstrengung ist unten.

Um Ihnen das Verständnis der Funktionsweise zu erleichtern, habe ich Kommentare hinzugefügt, die zeigen, wie eine bestimmte Zeichenfolge (u = "2 1 4 3 0 3 4 4 3 5 0 3") manipuliert wird. Ich zähle Kombinationen von "Felsen im Bach" auf, auf die man springen kann. Diese werden mit einer Binärzeichenfolge dargestellt. Ich gebe das Beispiel 0b0101101010 in den Kommentaren an und zeige, wie es verwendet werden würde. Die Einsen entsprechen den Positionen der Steine, die für die erste Reise zur Verfügung stehen. die 0en für die Rückfahrt. Für jede dieser Zuordnungen verwende ich dynamische Programmierung, um die minimale Anzahl von Hops zu bestimmen, die in jeder Richtung erforderlich sind. Ich führe auch ein paar einfache Optimierungen durch, um einige Kombinationen frühzeitig zu eliminieren.

Ich habe es mit den in anderen Antworten angegebenen Zeichenfolgen ausgeführt und erhalte die gleichen Ergebnisse. Hier sind einige andere Ergebnisse, die ich erhalten habe:

"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

Mich würde interessieren, ob andere für diese Saiten die gleichen Ergebnisse erzielen. Die Leistung ist angemessen gut. Beispielsweise dauerte es weniger als eine Minute, um eine Lösung für diese Zeichenfolge zu finden:

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 5 0 1

Der Code folgt.

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

Hier ist die normale Version:

Datenliste importieren

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

Hier ist die GHCi-Antwort (setzen Sie die Zeile nacheinander):

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

Nur eine rohe Kraft. Generieren Sie die mögliche Antwort. (dh die Permutation von [0..n-1] mit Null und nachfolgendem Element wurde verworfen. Überprüfen Sie dann, ob die Antwort korrekt ist. Ermitteln Sie die Mindestlänge und addieren Sie sie um eins. Da die führenden und nachfolgenden Nullen gelöscht werden).

Wie benutzt man: j[3,4,0,0,6]->3