Jumlah minimum Lompatan

14

Diberikan urutan angka, temukan jumlah minimum lompatan untuk pergi dari posisi awal ke akhir dan kembali ke posisi awal lagi.

Setiap elemen dari urutan menunjukkan jumlah maksimum gerakan yang dapat bergerak dari posisi itu.

Di posisi mana pun, Anda dapat melakukan lompatan pada gerakan maks k, di mana k adalah nilai yang disimpan di posisi itu. Setelah mencapai akhir, Anda hanya dapat menggunakan posisi tersebut untuk melompat yang belum pernah digunakan sebelumnya untuk melompat.

Input akan diberikan sebagai urutan angka yang dipisahkan oleh spasi tunggal. Output harus berupa angka tunggal yang merupakan jumlah minimum lompatan yang digunakan. Jika tidak mungkin untuk pergi ke ujung dan kembali ke posisi awal, maka cetak -1

Memasukkan:

2 4 2 2 3 4 2 2

Keluaran:

6 (3 untuk mencapai ujung dan 3 untuk kembali)

Memasukkan

1 0

Keluaran

-1

Catatan

  • Anggap semua angka urutannya adalah non-negatif

EDIT 1

Garis "Jadi, harus jelas bahwa seseorang selalu dapat melompat dari posisi terakhir." mungkin membingungkan, jadi saya menghapusnya dari pertanyaan. Itu tidak akan berpengaruh pada pertanyaan.

Kriteria Menang:

Pemenang akan menjadi orang dengan kode terpendek.

Pria pengkodean
sumber
3
Thus, it should be clear that one can always jump from the last position.- bukankah 1 0sampel balik?
Daniel Lubarov
@Aniel No. Jumlah lompatan akan sama dengan nilai yang disimpan di posisi itu. Posisi terakhir selalu merupakan kandidat tempat seseorang dapat melompat karena posisi ini sebelumnya tidak digunakan untuk melompat.
Pengodean pria
1
Deskripsi ini membingungkan karena "lompatan" digunakan untuk mengartikan dua hal yang berbeda, dan dengan hanya satu contoh aktual, sulit untuk menyatukan arti mana yang cocok dengan penggunaan yang mana. Saya lebih suka deskripsi yang mengacu pada, katakanlah, "melompat" dan "bergerak". Dengan terminologi ini, Anda akan mengatakan bahwa setiap gerakan terdiri dari beberapa jumlah lompatan. Angka-angka dalam input memberikan jumlah lompatan maksimum, dan output dapat secara jelas digambarkan sebagai melaporkan jumlah minimum gerakan.
kotak roti
1
Apa kriteria kemenangan? Saat Anda menandai kode-golf dan juga kode-tantangan , tidak jelas.
Howard
@breadbox Ya. Saya setuju, ini ambigu. Saya akan segera memperbarui pertanyaan.
Pengodean pria

Jawaban:

4

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

Uji kasus

      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

Pendekatan

Pendekatannya adalah pencarian brute force menggunakan fungsi rekursif.

Mulai dari posisi 1, tetapkan nilai pada posisi saat ini ke 0 dan hasilkan array posisi yang dapat dilompati dari posisi saat ini. Pass posisi baru dan array yang dimodifikasi itu sendiri. Kasus dasar adalah ketika nilai pada posisi saat ini adalah 0 (tidak bisa melompat) atau mencapai akhir.

Kemudian, untuk setiap array yang dihasilkan, balikkan dan lakukan pencarian lagi. Karena posisi melompat diatur ke 0, kita tidak bisa melompat dari sana lagi.

Untuk array yang kami capai akhirnya, cari yang memiliki jumlah minimum 0's. Dengan mengurangkannya, angka 0 pada larik awal memberikan jumlah lompatan aktual yang dilakukan.

TwiNight
sumber
4

Mathematica, 197 193 karakter

Paksaan.

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
sumber
Pekerjaan yang sangat mengesankan. Ini mungkin kekuatan kasar tetapi sangat elegan, tetap saja.
DavidC
3

Mathematica 351

[Catatan: Ini belum sepenuhnya bermain golf; Juga, input perlu disesuaikan agar sesuai dengan format yang diperlukan. Dan aturan no-jumping-on-the-same-position-2x perlu diimplementasikan. Ada juga beberapa masalah pemformatan kode yang perlu diatasi. Tapi ini awal.]

Grafik dibuat dengan simpul yang sesuai dengan setiap posisi, yaitu setiap digit input mewakili lompatan. DirectedEdge[node1, node2]menandakan bahwa adalah mungkin untuk melompat dari node1 ke node 2. Jalur terpendek ditemukan dari awal hingga akhir dan kemudian dari ujung ke awal.

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

Pemakaian

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

6
3
-1

DavidC
sumber
Ini sebagian salah karena tidak menerapkan no jumping pada aturan angka dua kali, tapi ini awal, jadi saya akan mendukungnya. Saya tidak tahu apakah ini mungkin :)
Gagang Pintu
Anda benar. Saya mengabaikan aturan no-jump-on-a-number-two Besok saya akan mencoba untuk memperbaikinya.
DavidC
3

Python 304

Saya pikir pendekatan baru ini menyelesaikan (saya harap!) Semua masalah tentang kasus [2,0] dan yang serupa:

Dalam versi ini urutan input dilalui (jika mungkin) sampai akhir dan kemudian kita memulai proses lagi dengan urutan terbalik. Sekarang kita dapat menjamin bahwa untuk setiap solusi yang valid salah satu lompatan mendarat pada elemen terakhir.

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

Ini adalah versi golfnya:

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

Dan beberapa contoh:

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
Triadika
sumber
Memiliki potensi besar untuk bermain golf lebih lanjut. Tetapi tidak ada penanganan input dan output, yang merupakan bagian dari masalah ini.
Pasang kembali Monica
1
Anda memiliki banyak ruang kosong yang tidak perlu ...
Gagang Pintu
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)

Simulasi:

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

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
sumber
2

Python 271

ini solusi saya:

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

Contoh:

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

Dan ini adalah versi golf (sebagian sekarang):

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

Beberapa contoh:

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])
Triadika
sumber
Salah. Pada input [1], output harus 0 (output Anda adalah 1). Pada input [3,0,0,1,4], output harus 3 (output adalah -1)
Coding pria
@ Kode pria: Ups, maaf. Ada pemeriksaan lompatan ekstra. if (i> = len (L) -1): S.append (n) tampaknya menyelesaikan masalah
Triadic
Masih memberikan output yang salah. Contoh: [2,0] ---> 1 (harus -1).
Penulis kode
@ Kode pria: Saya pikir solusi saya bertentangan dengan "Jadi, harus jelas bahwa seseorang selalu dapat melompat dari posisi terakhir.", Seperti yang saya anggap [2,0] ---> 1 solusi yang valid, karena itu melompat di ujungnya.
Triadic
1
Saya minta maaf atas semua kesalahan ini. Garis "Jadi, harus jelas bahwa seseorang selalu dapat melompat dari posisi terakhir." telah dihapus. Itu hanya digunakan untuk berarti bahwa posisi terakhir tidak pernah digunakan ketika kita bergerak maju dalam urutan. Jadi, itu selalu bisa digunakan untuk melompat ketika kita bergerak mundur. Namun, dalam [2,0] nilai pada posisi terakhir adalah 0, Anda dapat melompat pada maks 0 bergerak. Karenanya, Anda tidak akan pernah bisa mencapai posisi awal. Pertanyaannya telah diperbarui.
Penulis kode
2

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

Simulasi:

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

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

0
-1

1
0
Thaha kp
sumber
2

Ruby - sekitar 700 golf. Saya memulai versi golf, dengan nama karakter tunggal untuk variabel dan metode, tetapi setelah beberapa saat saya lebih tertarik pada algoritma daripada golf, jadi berhenti mencoba mengoptimalkan panjang kode. Saya juga tidak khawatir tentang mendapatkan string input. Usaha saya di bawah.

Untuk membantu Anda memahami cara kerjanya, saya menyertakan komentar yang menunjukkan bagaimana string tertentu (u = "2 1 4 3 0 3 4 4 3 5 0 3") dimanipulasi. Saya menghitung kombinasi "batu di sungai" yang tersedia untuk naik. Ini diwakili dengan string biner. Saya memberi contoh 0b0101101010 di komentar dan menunjukkan bagaimana itu akan digunakan. Angka 1 sesuai dengan posisi batu yang tersedia untuk perjalanan awal; 0 untuk perjalanan kembali. Untuk setiap alokasi tersebut, saya menggunakan pemrograman dinamis untuk menentukan jumlah minimal hop yang diperlukan di setiap arah. Saya juga melakukan beberapa optimasi sederhana untuk menghilangkan beberapa kombinasi sejak dini.

Saya sudah menjalankannya dengan string yang diberikan dalam jawaban lain dan mendapatkan hasil yang sama. Berikut beberapa hasil lain yang saya peroleh:

"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

Saya akan tertarik mendengar apakah orang lain mendapatkan hasil yang sama untuk string ini. Performanya lumayan bagus. Misalnya, butuh waktu kurang dari satu menit untuk mendapatkan solusi untuk string ini:

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

Kode berikut.

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
Cary Swoveland
sumber
0

Haskell, 173 166 byte, 159 byte di GHCi

Ini versi normal:

impor 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

Inilah jawaban GHCi (letakkan baris satu per satu):

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

Hanya bruteforce. Hasilkan jawaban yang mungkin. (Yaitu permutasi [0..n-1] dengan nol dan elemen berikut dijatuhkan. Kemudian periksa apakah jawabannya benar. Dapatkan panjang minimum dan tambahkan satu. (Karena nol di depan dan di belakang dihapus).

Cara menggunakan: j[3,4,0,0,6]->3

Akangka
sumber
Data.List.permutationstidak bekerja di GHC, tetapi hanya di GHCi. Menurut Panduan kami untuk Aturan Golf di Haskell , Anda harus menambahkan impor atau menandai jawaban Anda sebagai "Haskell GHCi". Opsi pertama umumnya disukai oleh pegolf Haskell di situs ini.
Laikoni
Alih-alih a<-permutations[0..t l-1],let f=takeWhile(/=0)a, Anda bisa menulis f<-map(takeWhile(/=0))(permutations[0..t l-1]), yang lagi-lagi bisa di-golf-kan f<-fst.span(>0)<$>permutations[0..t l-1]. Dengan ini, Anda kembali ke 166 byte bahkan dengan menambahkan impor: Coba online!
Laikoni