Учитывая последовательность чисел, найдите минимальное количество прыжков, чтобы пройти от начальной позиции до конца и снова вернуться в исходную позицию.

Каждый элемент последовательности обозначает максимальное количество ходов, которое можно переместить из этой позиции.

В любой позиции вы можете совершить скачок при максимальных k ходах, где k - это значение, сохраненное в этой позиции. Достигнув конца, вы можете использовать только те позиции для прыжков, которые ранее не использовались для прыжков.

Ввод будет дан как последовательность чисел, разделенных пробелами. Выходными данными должно быть одно число, которое является минимальным количеством используемых прыжков. Если невозможно дойти до конца и вернуться в исходное положение, выведите -1

Входные данные:

2 4 2 2 3 4 2 2

Выход:

6 (3 до конца и 3 до возвращения)

вход

1 0

Выход

-1

Заметка

• Предположим, что все числа последовательности неотрицательны

РЕДАКТИРОВАТЬ 1

Строка «Таким образом, должно быть понятно, что всегда можно прыгнуть с последней позиции». может быть запутанным, поэтому я убрал его из вопроса. Это не повлияет на вопрос.

Критерии победы:

Победителем станет тот, у кого самый короткий код.

АПЛ (Дьялог), 116

f←{{⊃,/{2>|≡⍵:⊂⍵⋄⍵}¨⍵}⍣≡1{(⍴⍵)≤y←⊃⍺:⍵⋄⍵[y]=0:0⋄x←⍵⋄x[y]←0⋄∇∘x¨,∘⍺¨y+⍳y⌷⍵},⍵}
{0≡+/⍵:¯1⋄(⌊/+/0=⍵)-+/0=x}↑⊃,/f¨⌽¨f x←⎕

Контрольные примеры

      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

Подходить

Подход - это перебор с использованием рекурсивной функции.

Начиная с позиции 1, установите значение в текущей позиции равным 0 и сгенерируйте массив позиций, к которым можно перейти с текущей позиции. Передайте новую позицию и измененный массив себе. Базовые случаи - это когда значение в текущей позиции равно 0 (невозможно прыгать) или достигает конца.

Затем для каждого сгенерированного массива поверните его и выполните поиск снова. Поскольку прыжковые позиции установлены в 0, мы не можем прыгать оттуда снова.

Для тех массивов, которые мы достигли конца, найдите те, которые имеют минимальное количество 0. Вычитая из него количество нулей в исходном массиве, получаем фактическое количество выполненных прыжков.

Mathematica, 197 193 символа

Грубая сила.

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

[Примечание: это еще не полностью игра в гольф; Кроме того, ввод должен быть скорректирован в соответствии с требуемым форматом. И должно быть реализовано правило «не прыгать на той же позиции дважды». Есть также некоторые проблемы с форматированием кода, которые необходимо устранить. Но это начало.]

Граф строится с узлами, соответствующими каждой позиции, то есть каждой входной цифре, представляющей скачок. DirectedEdge[node1, node2]означает, что можно перейти с узла 1 на узел 2. Кратчайшие пути находятся от начала до конца, а затем от конца к началу.

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

использование

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

6
3
-1

Python 304

Я думаю, что этот новый подход решает (я надеюсь!) Все проблемы, касающиеся случая [2,0] и подобных:

В этой версии входная последовательность обходит (если возможно) до конца, а затем мы снова запускаем процесс с обратной последовательностью. Теперь мы можем гарантировать, что для каждого правильного решения один из прыжков приземлится на последний элемент.

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

Это версии для гольфа:

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

И несколько примеров:

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)

Моделирование:

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

Де-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

Python 271

это мое решение:

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

Примеры:

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

И это (частично уже) версии для гольфа:

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

Несколько примеров:

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

Рубин - 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

Моделирование:

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

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

0
-1

1
0

Рубин - около 700 в гольф. Я запустил гольф-версию с односимвольными именами для переменных и методов, но через некоторое время я стал больше интересоваться алгоритмом, чем гольфом, поэтому перестал пытаться оптимизировать длину кода. Я также не беспокоился о получении входной строки. Мои усилия ниже.

Чтобы помочь вам понять, как это работает, я включил комментарии, которые показывают, как обрабатывается определенная строка (u = "2 1 4 3 0 3 4 4 3 5 0 3"). Я перечисляю комбинации "камней в потоке", на которые можно прыгать. Они представлены в виде двоичной строки. Я даю пример 0b0101101010 в комментариях и показываю, как он будет использоваться. 1 соответствуют позициям камней, доступных для начальной поездки; 0 для обратной поездки. Для каждого такого распределения я использую динамическое программирование, чтобы определить минимальное количество прыжков, необходимое в каждом направлении. Я также выполняю несколько простых оптимизаций, чтобы устранить некоторые комбинации на ранних этапах.

Я запустил его со строками, приведенными в других ответах, и получил те же результаты. Вот некоторые другие результаты, которые я получил:

"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

Мне было бы интересно услышать, получают ли другие те же результаты для этих строк. Производительность достаточно хорошая. Например, решение этой строки заняло менее минуты:

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

Код следует.

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

Хаскелл, 173 166 байт, 159 байт в GHCi

Вот нормальная версия:

импортировать 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

Вот ответ GHCi (поставить строку по одному):

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

Просто грубая сила. Генерация возможного ответа. (т.е. перестановка [0..n-1] с нулем и последующим пропущенным элементом. Затем проверьте, верен ли ответ. Получите минимальную длину и прибавьте единицу. (Поскольку передний и конечный нули удаляются).

Как использовать: j[3,4,0,0,6]->3