pengantar

Saya ingin membangun tangga. Untuk ini, saya telah memungut dari tempat barang rongsokan dua papan panjang dengan lubang di dalamnya, dan saya ingin menempatkan langkah-langkah ke dalam lubang ini. Namun, lubang tidak ditempatkan secara merata, sehingga langkah-langkahnya akan sedikit miring, dan saya merasa sulit untuk memperkirakan jumlah batang yang saya butuhkan untuk mereka. Tugas Anda adalah melakukan perhitungan untuk saya.

Memasukkan

Input Anda adalah dua vektor bit, diberikan sebagai array bilangan bulat, yang mewakili dua papan. A 0mewakili segmen satu aud ( unit jarak sewenang-wenang ) tanpa lubang, dan 1mewakili segmen dari satu aud dengan lubang tunggal. Array mungkin memiliki panjang yang berbeda dan mengandung jumlah 1s yang berbeda , tetapi array tersebut tidak akan kosong.

Saya akan membangun tangga saya sebagai berikut. Pertama, saya menempatkan kedua papan tepat satu audit terpisah, dan sejajarkan ujung kiri mereka. Untuk setiap indeks i, saya mengukur jarak antara ilubang ke-1 papan pertama dengan ilubang ke-2 untuk papan kedua, memotong sepotong batang, dan memasangnya di antara dua lubang. Saya berhenti begitu saya kehabisan lubang di salah satu papan.

Keluaran

Output Anda adalah jumlah total batang yang saya perlukan untuk langkah-langkahnya, diukur dalam audit. Outputnya harus benar setidaknya enam digit signifikan.

Contoh

Pertimbangkan input [0,1,1,0,1,1,1,1,0,0]dan [1,0,0,1,1,1,0,0,1]. Tangga yang dihasilkan terlihat seperti ini:

Panjang total batang di tangga ini adalah 7.06449510224598aud.

Aturan

Anda dapat menulis fungsi atau program lengkap. Hitungan byte terendah menang, dan celah standar tidak diizinkan.

Uji Kasus

[0] [0] -> 0.0
[0] [1,0] -> 0.0
[1,0,0] [1,1,1,1,1] -> 1.0
[0,1,0,1] [1,0,0,1] -> 2.414213562373095
[0,1,1,0,1,1,1,1,0,0] [1,0,0,1,1,1,0,0,1] -> 7.06449510224598
[1,1,1,1,1] [0,0,1,1,0,1,0,0,1] -> 12.733433128760744
[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0] [0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1] -> 20.38177416534678

J, 20 byte

4+/@:o.(<0 1)|:-/&I.

Ia menggunakan trik di jawaban MickyT di R .

(<0 1)|:memberikan diagonal dari sebuah matriks. Untuk penjelasan bagian lain, lihat jawaban FUZxxl .

J, 22 karakter

Tidak terinspirasi oleh jawaban randomra. Bagian I.itu sama karena itu adalah cara langsung yang jelas untuk menemukan lubang.

(4+/@:o.<.&#$-/@,:)&I.

• I. y- semua indeks ydiulang sesering item yang sesuai dari y. Kebetulan, jika yadalah vektor dari boolean, I. yberisi indeks di mana yadalah 1. Misalnya, I. 1 0 0 1 1 1 0 0 1hasil 0 3 4 5 8.
• x u&v y- sama seperti (v x) u (v y). Diterapkan sebagai x u&I. y, kita dapatkan (I. x) u (I. y). Mari kita lanjutkan dengan input yang diubah.
• x <.&# y- lebih kecil dari panjang xdan y.
• x -/@,: y- perbedaan item xdan y. Jika satu vektor lebih panjang, itu diisi dengan nol.
• x $ y- ydibentuk kembali ke bentuk yang ditentukan oleh x. Secara khusus, jika xskalar, xelemen diambil dari y. Dalam penggunaan ini, x (<.&# $ -/@,:) ypastikan lubang trailing diabaikan.
• 4 o. y- fungsi %: 1 + *: y, yaitu, sqrt (1 + y ²). Secara kebetulan, fungsi ini memetakan dari jarak lubang ke panjang batang.
• +/ y- jumlah elemen y.

Python, 85

lambda*A:sum(abs(x-y+1j)for x,y in zip(*[[i for i,x in enumerate(l)if x]for l in A]))

Ini ternyata mirip dengan solusi Mac . Konversikan daftar 0 dan 1 ke daftar indeks satu-urutan, dan kemudian menjumlahkan jarak antara elemen masing-masing.

J, 32 28 byte

Kata kerja I.mengembalikan posisi 1s dalam string biner yang sangat membantu.

   +/@,@(=/&(#\)*[:>:&.*:-/)&I.

   0 1 0 1 (+/@,@(=/&(#\)*[:>:&.*:-/)&I.) 1 0 0 1
2.41421

Untuk solusi J yang lebih baik periksa jawaban FUZxxl .

R, 67

Gunakan bagian luar untuk melakukan perbedaan pada lubang yang diindeks. Diag mengembalikan perbedaan yang diperlukan. Kemudian jumlah jarak yang dihitung

function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5)

Tes dijalankan di R Fiddle. Saya telah membungkusnya dalam cetakan untuk menunjukkan pengembalian sesuai dengan spesifikasi.

> print((function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5))(c(0,1,1,0,1,1,1,1,0,0),c(1,0,0,1,1,1,0,0,1)),digits=10)
[1] 7.064495102
> print((function(a,b)sum((diag(outer(which(a==1),which(b==1),"-"))^2+1)^.5))(c(1,1,1,1,1),c(0,0,1,1,0,1,0,0,1)),digits=10)
[1] 12.73343313
>

Haskell, 77 73 byte

r x=[a|(a,1)<-zip[1..]x]
i#j=sum$zipWith(\n m->sqrt((n-m)**2+1))(r i)$r j

Penggunaan: [0,1,0,1] # [1,0,0,1]output mana2.414213562373095

Cara kerjanya: fungsi rmengembalikan daftar posisi lubang papan, misalnya r [0,1,0,1]-> [2,4]. #ritsleting dua dari daftar tersebut dan mengubahnya menjadi daftar jarak antara lubang yang sesuai dan akhirnya menjumlahkannya.

CJam, 36 33 byte

l~]{:L,{L=},}%z{,(},0\{~-_*)mq+}/

Pendekatan yang sangat naif ... mengharapkan input sebagai array gaya CJam pada STDIN

[0 1 1 0 1 1 1 1 0 0] [1 0 0 1 1 1 0 0 1]

Berikut ini adalah test harness untuk semua input contoh. Hasil di bidang input digunakan sebelum kode aktual dipanggil. Anda dapat menghapusnya jika Anda tidak mempercayai saya. ;)

Penjelasan

l~]                               "Read and eval input, wrap in an array.";
   {        }%                    "Map this block onto both input arrays.";
    :L,                           "Store array in L, get its length N.";
       {L=},                      "In the range [0 .. N-1] get all elements where L is 1.";
                                  "At this point we've converted each array into a list of its
                                   non-zero indices.";
              z                   "Transpose the array, pairing up indices at the same position.";
               {,(},              "Filter the extraneous elements of the longer input.";
                    0\            "Put a 0 before the array.";
                      {        }/ "For each pair of holes...";
                       ~-         "Unwrap the pair, take the difference.";
                         _*)mq    "Square, increment, square root.";
                              +   "Add to the running total.";

Python, 86

f=lambda a,b,i=1j:a>[]<b and a[0]*b[0]*abs(i)+f(a[a[:1]<=b:],b[b[:1]<=a:],i+a[0]-b[0])

Solusi rekursif tingkat rendah dan naif tanpa pencarian daftar.

Daftar input adalah adan b. Jika salah satu kosong, kembali 0.

Kalau tidak, biarkan xdan ymenjadi elemen pertama mereka (kode tidak benar-benar menetapkan ini karena Anda tidak dapat melakukan tugas dalam lambda, tetapi itu akan membuat menjelaskan lebih mudah). Jika keduanya 1, yaitu produk mereka 1, maka mereka berkontribusi jarak batang. Kami melacak jarak dalam bilangan kompleks i, sehingga jarak adalah nilai absolut. Sebenarnya, kami menghitungnya apa pun, lalu mengalikannya dengan x*y.

Kemudian, kita muncul kembali. Idenya adalah untuk menggeser kedua daftar satu langkah, kecuali satu daftar dimulai dengan 0 dan yang lainnya dengan satu, dalam hal ini kita hanya menggeser daftar 0. Dengan begitu, 1 selalu dikonsumsi berpasangan. Kami dapat memeriksa kondisi ini dengan x<ydan y<x, tetapi lebih pendek untuk memanfaatkan perbandingan daftar sebagai a[:1]<=b. Akhirnya, kami menyesuaikan perpindahan kompleks antara elemen saat ini dengan x-y.

Python, 105 102 100 byte

i=lambda l:(i for i,h in enumerate(l)if h)
l=lambda*a:sum(((a-b)**2+1)**.5for a,b in zip(*map(i,a)))

Cukup mendasar, cukup konversi daftar input ke daftar indeks lubang, lalu hitung jarak antara setiap pasangan indeks tersebut.

Kasus cobaan:

>>> print l([0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1])
7.06449510225

Kredit ke @FryAmTheEggman untuk beberapa saran penghematan byte. Ternyata ini bisa di-golf lebih lanjut, seperti yang ditunjukkan dalam jawaban xnor .

Pyth, 30 byte

s+0m^h^-hded2 .5CmfTm*hb@kblkQ

Cobalah online dengan input [0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1].

Penjelasan:

Saya mengkonversi daftar menjadi daftar indeks [2, 3, 5, 6, 7, 8]dan [1, 4, 5, 6, 9]dan ritsleting bersama-sama [(2,1), (3,4), (5,5), (6,6), (7,9)]. Lalu saya kurangi nilainya, kuadratkan, tambahkan 1 dan jumlahkan semua akar kuadrat.

CmfTm*hb@kblkQ
 m           Q     map each list k in input() to the following list:
    m      lk         map each value b of [0, 1, 2, ..., len(k)-1] to the value:
     *hb@kb              (b + 1) * k[b]
  fT                  filter the list for positive values
C                  zip these two resulting lists

s+0m^h^-hded2 .5...
   m            ...  map each pair of values d to: 
    ^h^-hded2 .5         ((d[0] - d[1])^2 + 1)^0.5
 +0                  insert 0 at the front of the list
s                    sum

Rasa malu yang sumtidak berfungsi untuk daftar kosong.

Python, 116 115 byte

Ini adalah solusi rekursif.

Itu menjadi sangat menjengkelkan ketika saya menemukan bahwa index()hanya melempar kesalahan ketika tidak ada nilai ditemukan, tetapi saya membuatnya bekerja. Sayangnya, saya tidak bisa menggunakan lambda. Itu juga mengganggu saya yang list.remove()tidak mengembalikan daftar, tetapi sebaliknya kembali None.

def f(x,y,r=0):
    try:i,j=x.index(1),y.index(1)
    except:return r
    x.pop(i);y.pop(j);return f(x,y,r+((i-j)**2+1)**.5)

Jalankan online di sini: http://repl.it/c5L/2

Klip 3 , 55 47 38

[cr+`j[v[w#)#mvw2B}}(c)c]sl`{%ky1%kx1`

Untuk daftar dengan lubang yang lebih sedikit, program akan memutarnya, dan menghubungkan setiap lubang dengan lubang yang sesuai dari daftar lainnya. Ukurannya dihitung dan dijumlahkan.

>java -jar Clip3.jar ladder.clip
{0,1,1,0,1,1,1,1,0,0}
{1,0,0,1,1,1,0,0,1}
7.064495102245980096000721459859050810337066650390625

Penjelasan

[c          .- Assign c to the lists, in order of size    -.
  r+`       .- The sum of...                              -.
   j[v[w    .- Join the lists with a function on v, w     -.
     #      .- Square root                                -.
      )     .- 1 plus                                     -.
       #    .- The square of                              -.
        mvw .- The distance between v and w               -.
       2
     B      .- (one-half, so #...B means square root)     -.
   }}(c)c   .- Apply joining function to the lists        -.
  ]sl`{     .- c is the (sorted by size) list of...       -.
    %ky1    .- Indices of y (the second input) which are 1-.
    %kx1    .- Indices of x (the first input) which are 1 -.
  `

Jika kami sangat liberal tentang format input, kami dapat mengurangi ini menjadi 36 byte dengan menghapus masing-masing k. Ini membutuhkan input untuk menjadi string karakter kontrol \0dan karakter \1.

ECMAScript 6, 86 byte

Ini awalnya dimulai dengan mengurangi (saya ingin melihat apakah itu bisa dilakukan dalam satu loop sebagai lawan dari jawaban @ edc65).

f=(c,b,a=[0,...c],j)=>a.reduce((c,v,i)=>c+=v&&(j=b.indexOf(1,j)+1,v=i-j,j)?Math.sqrt(1+v*v):0)

Tetapi menggunakan @ edc65 untuk mapdan &&tmengembalikan nilai, saya dapat mempersingkatnya sedikit.

f=(a,b,j,c=0)=>a.map((v,i)=>c+=v&&(j=b.indexOf(1,j)+1,v=i+1-j,j)&&Math.sqrt(1+v*v))&&c

f=(a,b,j,c=0)        //variables note the j can be undefined
=>a.map((v,i)=>      //loop through the first array
c+=                  //add 
v&&                  //test to see if we have a hole
(j=b.indexOf(1,j)+1, //if so see if there is a whole on the other board
v=i+1-j,             //calculate index difference
j)                   //the last var gets evaluated so check to see if indexOf returned -1
&&Math.sqrt(1+v*v))  //calculate 
&&c                  //return sum

Jawa, 151

Ini hanya berjalan amencari, lalu berjalan bketika menemukan satu. Jika floatakurasi dapat diterima saya bisa menghemat beberapa byte, tetapi saya pergi doubleuntuk mencocokkan hasil tes.

double d(int[]a,int[]b){double z=0;for(int x=-1,y=0,d=b.length;x++<a.length&y<d;z+=a[x]>0?Math.sqrt((y-x)*(y++-x)+1):0)for(;y<d&&b[y]<1;y++);return z;}

Dengan spasi putih:

double d(int[]a,int[]b){
    double z=0;
    for(int x=-1,y=0,d=b.length;
            x++<a.length&y<d;
            z+=a[x]>0?Math.sqrt((y-x)*(y++-x)+1):0)
        for(;y<d&&b[y]<1;y++);
    return z;
}

JavaScript (ES6) 108

Titik utama adalah fungsi f yang memetakan array input 0..1 dalam array posisi hole. Kemudian array dipindai menghitung panjang batang total menggunakan teorema pythagoras. The |0dekat akhir diperlukan untuk NaN mengkonversi yang dapat terjadi ketika pengemudi array (yang pertama) lebih panjang daripada yang kedua.

F=(a,b,f=a=>a.map(v=>++u*v,u=0).filter(x=>x))=>
  f(a,b=f(b)).map((v,i)=>t+=Math.sqrt((w=b[i]-v)*w+1|0),t=0)&&t

Uji di Firefox / konsol FireBug

;[[[0],[0]]
 ,[[0],[1,0]]
 ,[[1,0,0],[1,1,1,1,1]]
 ,[[0,1,0,1],[1,0,0,1]]
 ,[[0,1,1,0,1,1,1,1,0,0],[1,0,0,1,1,1,0,0,1]]
 ,[[1,1,1,1,1],[0,0,1,1,0,1,0,0,1]]
 ,[[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0],[0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1]]]
.forEach(v=>console.log('['+v[0]+']','['+v[1]+']',F(...v)))

[0] [0] 0
[0] [1,0] 0
[1,0,0] [1,1,1,1,1] 1
[0,1,0,1] [1,0,0 , 1] 2.414213562373095
[0,1,1,0,1,1,1,1,0,0] [1,0,0,1,1,1,0,0,1] 7,06449510224598
[1,1 1,1,1] [0,0,1,1,0,1,0,0,1] 12,733433128760744
[0,0,0,1,0,1,1,0,0,0,0,1,1,1 , 1,0,0,1,0,1,1,0,0,0,1,0] [0,0,1,1,0,1,1,1,0,0,0,0,0, 0,1,1,0,1,1,0,0,0,1] 20,38177416534678

Oktaf, 60 59 42

@(a,b)trace(sqrt((find(a)'-find(b)).^2+1))

Perl 98

sub l{$r=0;@a=grep$a->[$_],0..$#$a;@b=grep$b->[$_],0..$#$b;$r+=sqrt 1+(shift(@a)-shift@b)**2 while@a&&@b;$r}

Dapat dibaca:

sub l {
    $r = 0;
    @a = grep $a->[$_], 0 .. $#$a;
    @b = grep $b->[$_], 0 .. $#$b;
    $r += sqrt 1 + (shift(@a) - shift @b) ** 2 while @a && @b;
    $r
}

Pengujian:

use Test::More;
for (<DATA>) {
    my ($A, $B, $r) = /\[ ([0-9,]+) \] \s \[ ([0-9,]+) \] \s -> \s ([0-9.]+) /x;
    $a = [split /,/, $A];
    $b = [split /,/, $B];
    cmp_ok l(), '==', $r, "test $_";
}
done_testing($.);
__DATA__
[0] [0] -> 0.0
[0] [1,0] -> 0.0
[1,0,0] [1,1,1,1,1] -> 1.0
[0,1,0,1] [1,0,0,1] -> 2.414213562373095
[0,1,1,0,1,1,1,1,0,0] [1,0,0,1,1,1,0,0,1] -> 7.06449510224598
[1,1,1,1,1] [0,0,1,1,0,1,0,0,1] -> 12.733433128760744
[0,0,0,1,0,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,0,1,0] [0,0,1,1,0,1,1,1,0,0,0,0,0,1,1,0,1,1,0,0,0,1] -> 20.38177416534678

APL, 35 28 byte

Menggunakan algoritma yang mirip dengan solusi J, tetapi APL memiliki lebih sedikit builtin.

{+/4○⊃-/{⍵⍴¨⍨⌊/⍴¨⍵}⍵/¨⍳¨⍴¨⍵}

Input contoh:

      {+/4○⊃-/{⍵⍴¨⍨⌊/⍴¨⍵}⍵/¨⍳¨⍴¨⍵}(1 0 0 1)(0 1 0 1)
2.414213562