Минимальное количество прыжков

14

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

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

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

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

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

2 4 2 2 3 4 2 2

Выход:

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

вход

1 0

Выход

-1

Заметка

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

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

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

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

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

Кодирующий человек
источник
3
Thus, it should be clear that one can always jump from the last position.- не 1 0контрпример?
Даниэль Любаров
@ Даниэль Нет. Количество прыжков будет равно значению, сохраненному в этой позиции. Последняя позиция всегда является кандидатом, с которого можно прыгнуть, поскольку эта позиция ранее не использовалась для прыжков.
кодирующий человек
1
Это описание сбивает с толку, потому что «прыжки» используются для обозначения двух разных вещей, и только с одним реальным примером трудно определить, какое значение имеет какое использование. Я бы предпочел описание, которое ссылается, скажем, на «прыжки» и «ходы». С этой терминологией вы бы сказали, что каждый ход состоит из некоторого количества прыжков. Числа на входе обеспечивают максимальное количество прыжков, и выход можно однозначно описать как отчет о минимальном количестве ходов.
хлебница
1
Какой критерий выигрыша? Как вы пометили код-гольф, так и код-вызов, это не ясно.
Говард
@breadbox Да. Я согласен, это неоднозначно. Я скоро обновлю вопрос.
Программист

Ответы:

4

АПЛ (Дьялог), 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. Вычитая из него количество нулей в исходном массиве, получаем фактическое количество выполненных прыжков.

TwiNight
источник
4

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 
alephalpha
источник
Очень впечатляющая работа. Это может быть грубой силой, но, тем не менее, это очень элегантно.
DavidC
3

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

DavidC
источник
Это частично неверно, поскольку не предписывает правило «не прыгать» на числе дважды, но это только начало, так что я за это проголосую. Я понятия не имел, было ли это вообще возможно :)
Дверная ручка
Ты прав. Я пропустил правило «не прыгать на число два». Завтра я попытаюсь это исправить.
DavidC
3

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
Триады
источник
Имеет огромный потенциал для дальнейшего игры в гольф. Но здесь нет обработки ввода и вывода, что является частью этой проблемы.
Восстановить Монику
1
у вас есть тонны ненужных пробелов ...
Дверная ручка
3

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
flodel
источник
2

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])
Триады
источник
Неправильно. На входе [1] вывод должен быть 0 (ваш вывод 1). На входе [3,0,0,1,4] вывод должен быть 3 (ваш вывод -1)
Coding man
@ Кодировщик: Ой, прости. Была дополнительная проверка прыжка. if (i> = len (L) -1): S.append (n), кажется, решает проблему
Triadic
Все еще дает неправильные выводы. Пример: [2,0] ---> 1 (должно быть -1).
кодирование человек
@ Кодировщик: я думаю, что мое решение находится в противоречии с «Таким образом, должно быть ясно, что всегда можно выпрыгнуть из последней позиции», поскольку я считаю [2,0] ---> 1 допустимым решением, поскольку это прыгает через конец.
Triadic
1
Я прошу прощения за все эти ошибки. Строка «Таким образом, должно быть понятно, что всегда можно прыгнуть с последней позиции». был удален. Он использовался только для того, чтобы означать, что последняя позиция никогда не использовалась, когда мы продвигаемся в последовательности. Таким образом, он всегда может быть использован для прыжков, когда мы движемся назад. Но в [2,0] значение в последней позиции равно 0, вы можете совершить прыжок на максимум 0 ходов. Следовательно, вы никогда не сможете достичь начальной позиции. Вопрос был обновлен.
кодирующий человек
2

Рубин - 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
Тха кп
источник
2

Рубин - около 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
Кэри Свовеланд
источник
0

Хаскелл, 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

Akangka
источник
Data.List.permutationsне работает в GHC, а только в GHCi. Согласно нашему Руководству по правилам игры в гольф на Haskell , вы должны либо добавить импорт, либо пометить свой ответ как «Haskell GHCi». На этом сайте гольфисты Haskell предпочитают первый вариант.
Лайкони
Вместо a<-permutations[0..t l-1],let f=takeWhile(/=0)a, вы можете написать f<-map(takeWhile(/=0))(permutations[0..t l-1]), что снова можно играть в гольф f<-fst.span(>0)<$>permutations[0..t l-1]. Благодаря этому вы вернетесь к 166 байтам, даже добавив импорт: попробуйте онлайн!
Лайкони