Introdução

Eu quero construir uma escada. Para isso, peguei no ferro-velho duas tábuas compridas com buracos e quero colocar os degraus nesses buracos. No entanto, os furos não são colocados uniformemente, portanto os passos serão um pouco instáveis ​​e acho difícil estimar a quantidade de haste necessária para eles. Seu trabalho é fazer os cálculos para mim.

Entrada

Sua entrada são vetores de dois bits, dados como matrizes de números inteiros, que representam as duas placas. A 0representa um segmento de um aud ( unidade arbitrária de distância ) sem um orifício e a 1representa um segmento de um aud com um único orifício. As matrizes podem ter diferentes comprimentos e conter um número diferente de 1s, mas não estarão vazias.

Vou construir minha escada da seguinte maneira. Primeiro, coloco as duas pranchas exatamente a um aud e alinhe as extremidades esquerdas. Para cada índice i, medo a distância entre o iorifício da primeira prancha e o iorifício da segunda prancha, corte um pedaço de haste e prenda-o entre os dois orifícios. Paro assim que ficar sem furos em uma das tábuas.

Saída

Sua saída é a quantidade total de haste necessária para as etapas, medidas em auditorias. A saída deve estar correta para pelo menos seis dígitos significativos.

Exemplo

Considere as entradas [0,1,1,0,1,1,1,1,0,0]e [1,0,0,1,1,1,0,0,1]. A escada resultante fica assim:

O comprimento total da haste nesta escada é 7.06449510224598auds.

Regras

Você pode escrever uma função ou um programa completo. A menor contagem de bytes vence e as brechas padrão não são permitidas.

Casos de teste

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

Ele usa o truque na resposta de MickyT em R .

(<0 1)|:dá a diagonal de uma matriz. Para as explicações das outras partes, consulte a resposta do FUZxxl .

J, 22 caracteres

Não é inspirado pela resposta da randomra. A I.peça é igual, pois é a maneira imediatamente óbvia de encontrar os orifícios.

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

• I. y- todos os índices de yrepetidos tantas vezes quanto o item correspondente de y. Aliás, se yé um vetor de booleano, I. ycontém os índices em que yestá 1. Por exemplo, I. 1 0 0 1 1 1 0 0 1produz 0 3 4 5 8.
• x u&v y- o mesmo que (v x) u (v y). Aplicado como x u&I. ychegamos (I. x) u (I. y). Vamos continuar com a entrada transformada.
• x <.&# y- o menor dos comprimentos de xe y.
• x -/@,: y- a diferença dos itens de xe y. Se um vetor for maior, será preenchido com zeros.
• x $ y- yremodelado para a forma especificada por x. Especificamente, se xfor um escalar, os xelementos serão retirados y. Neste uso, x (<.&# $ -/@,:) yverifique se os orifícios à direita são ignorados.
• 4 o. y- a função %: 1 + *: y, isto é, sqrt (1 + y² ). Aliás, essa função é mapeada da distância do furo ao comprimento das hastes.
• +/ y- a soma dos elementos de 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]))

Isso ficou semelhante à solução do Mac . Converta as listas de 0 e 1 em listas ordenadas dos índices um e depois some a distância entre os respectivos elementos.

J, 32 28 bytes

O verbo I.retorna as posições de 1s em uma string binária, o que é uma grande ajuda.

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

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

Para uma solução J melhor, verifique a resposta do FUZxxl .

R, 67

Usa externo para fazer a diferença para furos indexados. Diag retorna as diferenças necessárias. Soma então as distâncias calculadas

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

Teste executado no R Fiddle. Enrolei-o em uma impressão para mostrar que o retorno está em conformidade com as especificações.

> 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

Uso: [0,1,0,1] # [1,0,0,1]quais saídas2.414213562373095

Como funciona: a função rretorna uma lista das posições dos furos de uma placa, por exemplo r [0,1,0,1]- -> [2,4]. #fecha duas dessas listas e a transforma em uma lista de distâncias entre os furos correspondentes e, finalmente, soma-as.

CJam, 36 33 bytes

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

Abordagem muito ingênua ... espera a entrada como matrizes no estilo CJam no STDIN

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

Aqui está um chicote de teste para todas as entradas de exemplo. Os resultados no campo de entrada são usados ​​antes que o código real seja chamado. Você pode removê-los se não confiar em mim. ;)

Explicação

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

Uma solução recursiva de baixo nível e ingênua sem nenhuma pesquisa na lista.

As listas de entrada são ae b. Se um estiver vazio, retorne 0.

Caso contrário, deixe xe ysejam seus primeiros elementos (o código não os atribui de fato porque você não pode fazer atribuições em a lambda, mas facilitará a explicação). Se ambos são 1, ou seja, seu produto é 1, eles contribuem com a distância da haste. Nós registramos a distância no número complexo i, de modo que a distância é o valor absoluto. Na verdade, nós o computamos independentemente e depois o multiplicamos x*y.

Então, nós recomendamos. A idéia é mudar as duas listas uma etapa, a menos que uma lista comece com 0 e a outra com uma, nesse caso, alteramos apenas a lista 0. Dessa forma, os 1s são sempre consumidos em pares. Poderíamos verificar essas condições com x<ye y<x, mas é mais curto aproveitar a comparação de listas como a[:1]<=b. Finalmente, ajustamos o deslocamento complexo entre os elementos atuais por 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)))

Bastante básico, apenas converte as listas de entrada em listas de índices de furos e calcula a distância entre cada par desses índices.

Caso de teste:

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

Os nossos agradecimentos a @FryAmTheEggman por algumas sugestões de economia de bytes. Acontece que isso pode ser melhorado, como demonstrado na resposta do xnor .

Pitão, 30 bytes

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

Experimente online com a entrada [0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1].

Explicação:

Converter as listas em listas de índices [2, 3, 5, 6, 7, 8]e [1, 4, 5, 6, 9]e zip-los juntos [(2,1), (3,4), (5,5), (6,6), (7,9)]. Subtraio os valores, quadramo-los, adicione 1 e somamos todas as raízes quadradas.

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

Vergonha que sumnão funciona para listas vazias.

Python, 116 115 bytes

Esta é uma solução recursiva.

Tornou-se bastante irritante quando descobri que index()apenas gera um erro quando nenhum valor é encontrado, mas o fiz funcionar. Infelizmente, não posso usar uma lambda. Também me incomodou o list.remove()fato de não retornar a lista, mas retornar 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)

Execute online aqui: http://repl.it/c5L/2

Clipe 3 , 55 47 38

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

Para a lista com menos orifícios, o programa percorre a conexão e conecta cada orifício ao orifício correspondente da outra lista. Os tamanhos são calculados e somados.

>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

Explicação

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

Se formos muito liberais sobre o formato de entrada, podemos reduzir isso para 36 bytes removendo cada um k. Isso requer que a entrada seja uma sequência de caracteres dos caracteres de controle \0e \1.

ECMAScript 6, 86 bytes

Inicialmente, isso começou com o uso de reduzir (eu queria ver se isso poderia ser feito em um loop, em oposição à @ 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)

Mas, usando @ edc65 para mape &&tpara retornar o valor, pude reduzi-lo um pouco.

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

Isso apenas caminha à aprocura de uns, depois caminha bquando encontra um. Se a floatprecisão for aceitável, eu poderia salvar alguns bytes, mas fui com doublea correspondência da saída do teste.

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

Com espaço em branco:

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

O ponto principal é a função f que mapeia as matrizes de entrada 0..1 em matrizes de posições de furos. Em seguida, as matrizes são digitalizadas computando um comprimento total de barras usando o teorema de Pitágoras. O |0próximo ao fim é necessário para converter NaNs que podem resultar quando a matriz do driver (o primeiro) é maior que o segundo.

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

Teste no console 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,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

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

Legível:

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
}

Teste:

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

Usa um algoritmo semelhante à solução J, mas o APL possui menos recursos internos.

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

Exemplo de entrada:

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