Einführung

Ich möchte eine Leiter bauen. Dafür habe ich zwei lange Bretter mit Löchern aus dem Schrottplatz geputzt, und ich möchte die Stufen in diese Löcher legen. Die Löcher sind jedoch nicht gleichmäßig platziert, so dass die Stufen ein wenig wackelig werden und ich es schwierig finde, die Menge an Ruten abzuschätzen, die ich für sie benötige. Ihre Aufgabe ist es, die Berechnungen für mich zu machen.

Eingang

Ihre Eingabe besteht aus zwei Bitvektoren, die als Arrays von Ganzzahlen angegeben werden und die zwei Karten darstellen. A 0repräsentiert ein Segment von einem Aud ( willkürliche Entfernungseinheit ) ohne ein Loch, und a 1repräsentiert ein Segment von einem Aud mit einem einzelnen Loch. Die Arrays können unterschiedlich lang sein und eine unterschiedliche Anzahl von 1s enthalten, sie sind jedoch nicht leer.

Ich werde meine Leiter wie folgt aufbauen. Zuerst platziere ich die beiden Platinen genau einen Aud auseinander und richte ihre linken Enden aus. Für jeden Index messe iich den Abstand zwischen dem iLoch der ersten Platte und dem iLoch der zweiten Platte, schneide ein Stück Stab ab und befestige es zwischen den beiden Löchern. Ich höre auf, sobald mir die Löcher in einem der Bretter ausgehen.

Ausgabe

Ihre Ausgabe ist die Gesamtmenge der Stange, die ich für die Schritte benötige, gemessen in Audits. Die Ausgabe sollte auf mindestens sechs Stellen genau sein.

Beispiel

Betrachten Sie die Eingänge [0,1,1,0,1,1,1,1,0,0]und [1,0,0,1,1,1,0,0,1]. Die resultierende Leiter sieht folgendermaßen aus:

Die Gesamtlänge der Stange in dieser Leiter beträgt 7.06449510224598auds.

Regeln

Sie können entweder eine Funktion oder ein vollständiges Programm schreiben. Die niedrigste Byteanzahl gewinnt, und Standardlücken sind nicht zulässig.

Testfälle

[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 Bytes

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

Es nutzt den Trick in MickyT Antwort in R .

(<0 1)|:Gibt die Diagonale einer Matrix an. Für die Erklärungen der anderen Teile siehe die Antwort von FUZxxl .

J, 22 Zeichen

Nicht durch die Antwort von Randomra inspiriert. Der I.Teil ist gleich, da dies der unmittelbar offensichtliche Weg ist, die Löcher zu finden.

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

• I. y- Alle Indizes von werden yso oft wiederholt wie der entsprechende Punkt von y. Wenn yübrigens ein Vektor von Booleschen Werten ist, I. yenthält er die Indizes, bei denen yist 1. Zum Beispiel,I. 1 0 0 1 1 1 0 0 1 Erträge 0 3 4 5 8.
• x u&v y- das gleiche wie (v x) u (v y). Angewandt alsx u&I. y bekommen wir (I. x) u (I. y). Fahren wir mit der transformierten Eingabe fort.
• x <.&# y - die geringere der Längen von x und y.
• x -/@,: y - die Differenz der Posten von x und y. Wenn ein Vektor länger ist, wird er mit Nullen aufgefüllt.
• x $ y- yin die von angegebene Form gebracht x. Insbesondere wenn xes sich um einen Skalar handelt, werden xElemente aus entnommeny . Stellen Sie bei dieser Verwendung x (<.&# $ -/@,:) ysicher, dass nachgestellte Löcher ignoriert werden.
• 4 o. y- die Funktion %: 1 + *: y, das heißt, sqrt (1 + y ²). Übrigens bildet diese Funktion vom Lochabstand zur Länge der Stangen ab.
• +/ y- die Summe der Elemente von 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]))

Dies stellte sich ähnlich wie bei der Mac-Lösung heraus . Konvertieren Sie die Listen der Nullen und Einsen in geordnete Listen der Ein-Indizes und addieren Sie dann den Abstand zwischen den jeweiligen Elementen.

J 32 28 Bytes

Das Verb I.gibt die Positionen von 1s in einer Binärzeichenfolge zurück, was eine große Hilfe darstellt.

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

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

Für eine bessere J-Lösung überprüfen Sie die Antwort von FUZxxl .

R 67

Verwendet Outer, um einen Unterschied für indizierte Löcher zu machen. Diag gibt die erforderlichen Differenzen zurück. Summieren Sie dann die berechneten Entfernungen

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

Probelauf in R Fiddle. Ich habe es in einen Druck eingewickelt, um zu zeigen, dass die Rücksendung den Spezifikationen entspricht.

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

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

Verwendung: [0,1,0,1] # [1,0,0,1]welche Ausgänge2.414213562373095

So funktioniert es: Die Funktion rliefert eine Liste der Positionen der Löcher einer Platine, zB r [0,1,0,1]-> [2,4]. #Zippt zwei dieser Listen und wandelt sie in eine Liste mit Abständen zwischen den entsprechenden Löchern um und summiert sie schließlich.

CJam, 36 33 Bytes

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

Sehr naiver Ansatz ... es erwartet die Eingabe als Arrays im CJam-Stil auf STDIN

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

Hier ist ein Testkabelbaum für alle Beispieleingaben. Die Ergebnisse im Eingabefeld werden verwendet, bevor der eigentliche Code aufgerufen wird. Sie können sie entfernen, wenn Sie mir nicht vertrauen. ;)

Erläuterung

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

Eine einfache und naive rekursive Lösung ohne Listensuche.

Die Eingabelisten sind aund b. Wenn eine leer ist, kehre zurück0 .

Andernfalls lassen Sie xund yseien Sie ihre ersten Elemente (der Code weist diese nicht tatsächlich zu, weil Sie Zuweisungen in a nicht ausführen können lambda, aber es erleichtert das Erklären). Wenn beide 1 sind, dh ihr Produkt 1 ist, tragen sie zum Stababstand bei. Wir verfolgen die Entfernung in der komplexen Zahl i, so dass die Entfernung der absolute Wert ist. Tatsächlich berechnen wir es unabhängig davon und multiplizieren es dann mit x*y.

Dann rekursieren wir. Die Idee ist, beide Listen um einen Schritt zu verschieben, es sei denn, eine Liste beginnt mit einer 0 und die andere mit einer Eins. In diesem Fall verschieben wir nur die 0-Liste. Auf diese Weise werden Einsen immer paarweise konsumiert. Wir könnten diese Bedingungen mit x<yund überprüfen y<x, aber es ist kürzer, den Listenvergleich als zu nutzen a[:1]<=b. Schließlich passen wir die komplexe Verschiebung zwischen den aktuellen Elementen um an x-y.

Python, 105 102 100 Bytes

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

Ziemlich einfach, konvertiert einfach die Eingabelisten in Listen mit Lochindizes und berechnet dann den Abstand zwischen jedem Paar solcher Indizes.

Testfall:

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

Wir danken @FryAmTheEggman für ein paar Vorschläge zum Speichern von Bytes. Es hat sich herausgestellt, dass dies weiter verbessert werden kann, wie in der Antwort von xnor gezeigt .

Pyth, 30 Bytes

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

Probieren Sie es online mit der Eingabe [0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1].

Erläuterung:

Ich konvertiere die Listen in Listen von Indizes [2, 3, 5, 6, 7, 8]und [1, 4, 5, 6, 9]und zip sie zusammen [(2,1), (3,4), (5,5), (6,6), (7,9)]. Dann subtrahiere ich die Werte, quadriere sie, addiere 1 und summiere über alle Quadratwurzeln.

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

Schade, dass sumfür leere Listen nicht funktioniert.

Python, 116 115 Bytes

Dies ist eine rekursive Lösung.

Es wurde ziemlich ärgerlich, als ich herausfand, dass index()nur ein Fehler ausgegeben wird, wenn kein Wert gefunden wird, aber ich habe dafür gesorgt, dass es funktioniert. Leider kann ich kein Lambda verwenden. Es hat mich auch geärgert, dass list.remove()die Liste nicht zurückgegeben wird, sondern zurückgegeben wird 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)

Hier online ausführen: http://repl.it/c5L/2

Clip 3 , 55 47 38

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

Für die Liste mit den weniger Löchern durchläuft das Programm sie und verbindet jedes Loch mit dem entsprechenden Loch der anderen Liste. Die Größen werden berechnet und summiert.

>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

Erläuterung

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

Wenn wir das Eingabeformat sehr liberal finden, können wir es durch Entfernen auf 36 Byte reduzieren k. Dies setzt voraus, dass die Eingabe eine Zeichenfolge aus den Steuerzeichen \0und ist \1.

ECMAScript 6, 86 Bytes

Dies begann ursprünglich mit der Verwendung von Reduce (ich wollte sehen, ob es in einer Schleife im Gegensatz zu @ edc65 Antwort durchgeführt werden kann).

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)

Aber mit @ edc65 für mapund &&tum den Wert zurückzugeben, konnte ich ihn ziemlich verkürzen.

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

Dies geht nur auf der aSuche nach denen und geht dann weiter, bwenn es eine findet. Wenn die floatGenauigkeit akzeptabel ist, könnte ich ein paar Bytes einsparen, aber ich habe doubledie Testausgabe angepasst.

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

Mit Leerzeichen:

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

Der Hauptpunkt ist die f-Funktion, die die Eingangs-0..1-Arrays in Arrays von Lochpositionen abbildet. Dann werden die Arrays gescannt, wobei eine Gesamtlänge der Stäbe unter Verwendung des pythagoreischen Theorems berechnet wird. Das |0Ende wird benötigt, um NaNs zu konvertieren, die entstehen können, wenn das Treiberarray (das erste) länger als das zweite ist.

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

Test In der Firefox / FireBug-Konsole

;[[[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,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,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

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

Lesbar:

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
}

Testen:

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 Bytes

Verwendet einen ähnlichen Algorithmus wie die J-Lösung, APL verfügt jedoch über weniger integrierte Funktionen.

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

Beispiel Eingabe:

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