Wprowadzenie

Chcę zbudować drabinę. W tym celu wyrzuciłem ze złomowiska dwie długie deski z dziurami i chcę w nich umieścić stopnie. Jednak dziury nie są równomiernie rozmieszczone, więc kroki będą trochę niepewne i trudno mi oszacować ilość potrzebnej mi wędki. Twoim zadaniem jest wykonanie dla mnie obliczeń.

Wkład

Twój wkład to dwa wektory bitowe, podane jako tablice liczb całkowitych, które reprezentują dwie tablice. A 0reprezentuje segment jednego audu ( arbitralna jednostka odległości ) bez otworu, a a 1reprezentuje segment jednego auda z pojedynczym otworem. Tablice mogą mieć różne długości i zawierać inną liczbę 1s, ale nie będą puste.

Zbuduję moją drabinę w następujący sposób. Najpierw umieszczam dwie plansze dokładnie jeden dźwięk oddzielnie i wyrównuję ich lewe końce. Dla każdego indeksu imierzę odległość między ith otworem pierwszej deski z ith otworem drugiej deski, wycinam kawałek pręta i mocuję go między dwoma otworami. Zatrzymuję się, gdy skończą mi się dziury w jednej z plansz.

Wydajność

Twój wynik to łączna ilość pręta potrzebna do wykonania kroków, mierzona w audytach. Dane wyjściowe powinny być poprawne do co najmniej sześciu cyfr znaczących.

Przykład

Rozważ dane wejściowe [0,1,1,0,1,1,1,1,0,0]i [1,0,0,1,1,1,0,0,1]. Powstała drabina wygląda następująco:

Całkowita długość pręta w tej drabinie to 7.06449510224598auds.

Zasady

Możesz napisać funkcję lub pełny program. Wygrywa najniższa liczba bajtów, a standardowe luki są niedozwolone.

Przypadki testowe

[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 bajtów

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

Używa trick w odpowiedzi MickyT w R .

(<0 1)|:daje przekątną macierzy. Wyjaśnienia innych części znajdują się w odpowiedzi FUZxxl .

J, 22 znaki

Nie zainspirowany odpowiedzią randomra. I.Część jest równa jak to jest oczywiste sposobem znalezienia dziury.

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

• I. y- wszystkie wskaźniki ypowtórzone tak często, jak odpowiadająca im pozycja y. Nawiasem mówiąc, jeśli yjest wektorem wartości logicznych, I. yzawiera wskaźniki, przy których yjest 1. Na przykład I. 1 0 0 1 1 1 0 0 1daje 0 3 4 5 8.
• x u&v y- to samo co (v x) u (v y). Stosowane jako x u&I. yotrzymujemy (I. x) u (I. y). Kontynuujmy przekształcone dane wejściowe.
• x <.&# y- mniejsza długość xi y.
• x -/@,: y- różnica pozycji xi y. Jeśli jeden wektor jest dłuższy, jest wypełniany zerami.
• x $ y- yprzekształcony do kształtu określonego przez x. W szczególności, jeśli xjest skalarem, xelementy są pobierane z y. W tym zastosowaniu x (<.&# $ -/@,:) yupewnij się, że końcowe dziury są ignorowane.
• 4 o. y- funkcja %: 1 + *: y, to znaczy sqrt (1 + y ²). Nawiasem mówiąc, ta funkcja mapuje odległość otworów do długości prętów.
• +/ y- suma elementów 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]))

Okazało się to podobne do rozwiązania dla komputerów Mac . Konwertuj listy zer i jedynek na uporządkowane listy wskaźników o jednym indeksie, a następnie zsumuj odległość między poszczególnymi elementami.

J, 32 28 bajtów

Czasownik I.zwraca pozycje 1s w ciągu binarnym, co jest ogromną pomocą.

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

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

Aby uzyskać lepsze rozwiązanie J, sprawdź odpowiedź FUZxxl .

R, 67

Używa wartości zewnętrznej, aby zrobić różnicę dla indeksowanych otworów. Diag zwraca wymagane różnice. Następnie zsumuj obliczone odległości

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

Uruchomienie testowe w skrzypcach R. Owinąłem go nadrukiem, aby pokazać, że zwrot jest zgodny ze specyfikacją.

> 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 bajtów

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

Zastosowanie: [0,1,0,1] # [1,0,0,1]które wyjścia2.414213562373095

Jak to działa: funkcja rzwraca listę pozycji otworów w tablicy, np. r [0,1,0,1]-> [2,4]. #zamyka dwie z tych list i zamienia je w listę odległości między odpowiadającymi dziurami i na koniec sumuje.

CJam, 36 33 bajtów

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

Bardzo naiwne podejście ... oczekuje danych wejściowych jako tablic w stylu CJam na STDIN

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

Oto wiązka testowa dla wszystkich przykładowych danych wejściowych. Wyniki w polu wejściowym są używane przed wywołaniem rzeczywistego kodu. Możesz je usunąć, jeśli mi nie ufasz. ;)

Wyjaśnienie

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

Niskopoziomowe i naiwne rozwiązanie rekurencyjne bez przeszukiwania listy.

Listy wejściowe to ai b. Jeśli któryś jest pusty, wróć 0.

W przeciwnym razie pozwól xi ybądź ich pierwszymi elementami (kod w rzeczywistości ich nie przypisuje, ponieważ nie możesz wykonywać przypisań w lambda, ale ułatwi to wyjaśnianie). Jeśli oba mają wartość 1, tzn. Ich iloczyn wynosi 1, to mają wpływ na odległość pręta. Śledzimy odległość w liczbie zespolonej i, aby odległość była wartością bezwzględną. W rzeczywistości obliczamy to niezależnie, a następnie mnożymy przez x*y.

Potem wracamy. Chodzi o przesunięcie obu list o jeden krok, chyba że jedna lista zaczyna się od 0, a druga od jednego, w którym to przypadku przesuwamy tylko listę 0. W ten sposób jedynki są zawsze konsumowane w parach. Możemy sprawdzić te warunki za pomocą x<yi y<x, ale krócej skorzystać z porównania listy jako a[:1]<=b. Na koniec dostosowujemy złożone przesunięcie między bieżącymi elementami o x-y.

Python, 105 102 100 bajtów

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

Całkiem proste, po prostu konwertuje listy danych wejściowych na listy indeksów otworów, a następnie oblicza odległość między każdą parą takich indeksów.

Przypadek testowy:

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

Podziękowania dla @FryAmTheEggman za kilka sugestii dotyczących oszczędzania bajtów. Okazuje się, że można to pograć w golfa, jak pokazano w odpowiedzi Xnora .

Pyth, 30 bajtów

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

Wypróbuj online z danymi wejściowymi [0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1].

Wyjaśnienie:

Przekonwertować list do listy indeksów [2, 3, 5, 6, 7, 8]i [1, 4, 5, 6, 9]i zip je razem [(2,1), (3,4), (5,5), (6,6), (7,9)]. Następnie odejmuję wartości, wyrównaj je, dodaję 1 i sumuję wszystkie pierwiastki kwadratowe.

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

Szkoda, że sumnie działa na pustych listach.

Python, 116 115 bajtów

To jest rozwiązanie rekurencyjne.

Stało się dość irytujące, gdy odkryłem, że index()po prostu zgłasza błąd, gdy nie znaleziono żadnej wartości, ale sprawiłem, że zadziałała. Niestety nie mogę użyć lambda. Zirytowało mnie również to, że list.remove()nie zwraca listy, ale zamiast tego zwraca 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)

Uruchom online tutaj: http://repl.it/c5L/2

Klip 3 , 55 47 38

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

W przypadku listy z mniejszą liczbą otworów program dokonuje iteracji przez nią i łączy każdy otwór z odpowiednim otworem drugiej listy. Rozmiary są obliczane i sumowane.

>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

Wyjaśnienie

[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 -.
  `

Jeśli jesteśmy bardzo liberalni w kwestii formatu wejściowego, możemy go zmniejszyć do 36 bajtów, usuwając każdy z nich k. Wymaga to wprowadzenia ciąg znaków znaków kontrolnych \0i \1.

ECMAScript 6, 86 bajtów

To początkowo zaczęło się od redukcji (chciałem sprawdzić, czy można to zrobić w jednej pętli, w przeciwieństwie do odpowiedzi @ 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)

Ale używając @ edc65 dla mapi &&taby zwrócić wartość, byłem w stanie dość ją skrócić.

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

Java, 151

To po prostu idzie w aposzukiwaniu tych, a następnie idzie, bgdy je znajdzie. Jeśli floatdokładność jest akceptowalna, mogę zaoszczędzić kilka bajtów, ale poszedłem doubledopasować wynik testu.

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

Z białymi znakami:

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

Głównym punktem jest funkcja f, która odwzorowuje wejściowe tablice 0..1 w tablicach pozycji otworów. Następnie tablice są skanowane, obliczając całkowitą długość prętów za pomocą twierdzenia pitagorejskiego. |0Pod koniec jest potrzebny do Nans przekonwertować mogą wyniknąć, gdy kierowca array (pierwszy) jest dłuższa niż sekundę.

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

Przetestuj w konsoli Firefox / 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,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, 0,1,1,0,1,1,0,0,0,1] 20,38177416534678

Oktawa, 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}

Czytelny:

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
}

Testowanie:

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 bajtów

Używa algorytmu podobnego do rozwiązania J, ale APL ma mniej wbudowanych funkcji.

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

Przykładowe dane wejściowe:

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