Construct a Ladder

Question

Introduction

I want to build a ladder. For this, I have scavenged from the junkyard two long boards with holes in them, and I want to place the steps into these holes. However, the holes are not evenly placed, so the steps will be a little wonky, and I find it hard to estimate the amount of rod I need for them. Your job is to do the calculations for me.

Input

Your input is two bit vectors, given as arrays of integers, which represent the two boards. A 0 represents a segment of one aud (arbitrary unit of distance) without a hole, and a 1 represents a segment of one aud with a single hole. The arrays may be of different lengths and contain a different number of 1s, but they will not be empty.

I will construct my ladder as follows. First, I place the two boards exactly one aud apart, and align their left ends. For each index i, I measure the distance between the ith hole of the first board with the ith hole of the second board, cut a piece of rod, and attach it between the two holes. I stop once I run out of holes in one of the boards.

Output

Your output is the total amount of rod I'll need for the steps, measured in auds. The output should be correct to at least six significant digits.

Example

Consider the inputs [0,1,1,0,1,1,1,1,0,0] and [1,0,0,1,1,1,0,0,1]. The resulting ladder looks like this:

The total length of the rod in this ladder is 7.06449510224598 auds.

Rules

You can write either a function or a full program. The lowest byte count wins, and standard loopholes are disallowed.

Test Cases

[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

Answer 1

J, 22 characters

Not inspired by the answer of randomra. The I. part is equal as that is the immediately obvious way of finding the holes.

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

• I. y – all the indices of y repeated as often as the corresponding item of y. Incidentally, if y is a vector of booleans, I. y contains the indices at which y is 1. For instance, I. 1 0 0 1 1 1 0 0 1 yields 0 3 4 5 8.
• x u&v y – the same as (v x) u (v y). Applied as x u&I. y, we get (I. x) u (I. y). Let's continue with the transformed input.
• x <.&# y – the lesser of the lengths of x and y.
• x -/@,: y – the difference of the items of x and y. If one vector is longer, it is padded with zeroes.
• x $ y – y reshaped to the shape specified by x. Specifically, if x is a scalar, x elements are taken from y. In this usage, x (<.&# $ -/@,:) y makes sure that trailing holes are ignored.
• 4 o. y – the function %: 1 + *: y, that is, sqrt(1 + y²). Incidentally, this function maps from hole distance to length of rods.
• +/ y – the sum of the elements of y.

Answer 2

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

This turned out similar to Mac's solution. Convert the lists of 0's and 1's to ordered lists of the one-indices, and then sum the distance between respective elements.

Answer 3

J, 32 28 bytes

The verb I. returns the positions of 1s in a binary string which is a huge help.

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

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

For a better J solution check FUZxxl's answer.

Answer 4

R, 67

Uses outer to do a difference for indexed holes. Diag returns required differences. Then sum the calculated distances

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

Test run in R Fiddle. I have wrapped it in a print to show the return complies with spec.

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

Answer 5

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

Usage: [0,1,0,1] # [1,0,0,1] which outputs 2.414213562373095

How it works: the function r returns a list of the positions of the holes of a board, e.g. r [0,1,0,1] -> [2,4]. # zips two of those lists and turns it into a list of distances between corresponding holes and finally sums it.

Answer 6

CJam, 36 33 bytes

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

Very naive approach... it expects the input as CJam-style arrays on STDIN

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

Here is a test harness for all the example inputs. The results in the input field are used before the actual code is called. You can remove them if you don't trust me. ;)

Explanation

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

Answer 7

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

A low-level and naive recursive solution without any list searching.

The input lists are a and b. If either is empty, return 0.

Otherwise, let x and y be their first elements (the code doesn't actually assign these because you can't do assignments in a lambda, but it will make explaining easier). If both are 1, i.e. their product is 1, then they contribute rod distance. We keep track of distance in the complex number i, so that distance is the absolute value. Actually, we compute it regardless, then multiply it by x*y.

Then, we recurse. The idea is to shift both lists one step, unless one list starts with a 0 and the other with a one, in which case we shift only the 0 list. That way, 1's are always consumed in pairs. We could check these conditions with x<y and y<x, but it's shorter to take advantage of list comparison as a[:1]<=b. Finally, we adjust the complex displacement between the current elements by x-y.

Answer 8

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

Pretty basic, just converts the input lists to lists of hole indices, then computes distance between each pair of such indices.

Test case:

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

Credit to @FryAmTheEggman for a couple of byte-saving suggestions. Turns out this can be golfed further, as demonstrated in xnor's answer.

Answer 9

J, 20 bytes

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

It uses the trick in MickyT's answer in R.

(<0 1)|: gives the diagonal of a matrix. For the explanations of the other parts, see FUZxxl's answer.

Answer 10

Pyth, 30 bytes

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

Try it online with the input [0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1].

Explanation:

I convert the lists into lists of indices [2, 3, 5, 6, 7, 8] and [1, 4, 5, 6, 9] and zip them together [(2,1), (3,4), (5,5), (6,6), (7,9)]. Then I subtract the values, square them, add 1 and sum over all square roots.

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

Shame that sum doesn't work for empty lists.

Answer 11

Python, 116 115 bytes

This is a recursive solution.

It became pretty annoying when I found that index() just throws an error when no value is found, but I made it work. Unfortunately, I cannot use a lambda. It also annoyed me that list.remove() doesn't return the list, but instead returns 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)

Run online here: http://repl.it/c5L/2

Answer 12

Clip 3, 55 47 38

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

For the list with the fewer holes, the program iterates through it, and connects each hole with the corresponding hole of the other list. The sizes are calculated and summed.

>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

Explanation

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

If we are very liberal about the input format, we can reduce this to 36 bytes by removing each k. This requires the input to be a string of the control characters characters \0 and \1.

Answer 13

ECMAScript 6, 86 bytes

This originally started out using reduce (I wanted to see if it could be done in one loop as opposed to @edc65 answer).

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)

But using @edc65 for map and &&t to return the value I was able to shorten it quite a bit.

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

Answer 14

Java, 151

This just walks along a looking for ones, then walks along b when it finds one. If float accuracy is acceptable I could save a couple bytes, but I went with double to match the test output.

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

With whitespace:

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

Answer 15

JavaScript (ES6) 108

The main point is the f function that maps the input 0..1 arrays in arrays of holes positions. Then the arrays are scanned computing a total rods length using the pythagorean theorem. The |0 near the end is needed to convert NaNs that can result when the driver array (the first) is longer than the second.

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 Firefox / FireBug console

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

Answer 16

Octave, 60 59 42

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

Answer 17

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}

Readable:

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
}

Testing:

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

Answer 18

APL, 35 28 bytes

Uses a similar algorithm to the J solution, but APL has fewer builtins.

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

Example input:

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