Введение

Я хочу построить лестницу. Для этого я вычистил из свалки две длинные доски с отверстиями в них, и я хочу поместить ступени в эти отверстия. Тем не менее, отверстия расположены неравномерно, поэтому шаги будут немного шаткими, и мне сложно оценить количество необходимого для них стержня. Твоя работа - делать расчеты за меня.

вход

Ваш ввод состоит из двух битовых векторов, представленных в виде массивов целых чисел, которые представляют две платы. A 0представляет сегмент одного aud ( произвольная единица расстояния ) без отверстия, а a 1представляет сегмент одного aud с одним отверстием. Массивы могут быть разной длины и содержать разное число 1s, но они не будут пустыми.

Я построю свою лестницу следующим образом. Сначала я размещаю две доски ровно на одной стороне и выравниваю их левые концы. Для каждого индекса iя измеряю расстояние между iотверстием первой доски и iотверстием второй доски, режу кусок стержня и прикрепляю его между двумя отверстиями. Я останавливаюсь, когда у меня кончаются дыры в одной из досок.

Выход

Ваш вывод - это общее количество стержня, которое мне понадобится для шагов, измеренное в ауд. Вывод должен быть не менее шести значащих цифр.

пример

Рассмотрим входы [0,1,1,0,1,1,1,1,0,0]и [1,0,0,1,1,1,0,0,1]. Результирующая лестница выглядит так:

Общая длина стержня в этой лестнице составляет 7.06449510224598ауд.

правила

Вы можете написать либо функцию, либо полную программу. Побеждает меньшее количество байтов, и стандартные лазейки запрещены.

Тестовые случаи

[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 байт

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

Он использует трюк в ответ MickyT в R .

(<0 1)|:дает диагональ матрицы. Для объяснения других частей, см . Ответ FUZxxl .

J, 22 символа

Не вдохновлен ответ Рандомера. I.Часть равна , как это сразу же очевидный способ нахождения отверстий.

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

• I. y- все показатели yповторяются так часто, как соответствующий пункт y. Между прочим, если yэто вектор логических значений, I. yсодержит индексы, на которых yесть 1. Например, I. 1 0 0 1 1 1 0 0 1урожайность 0 3 4 5 8.
• x u&v y- так же, как (v x) u (v y). Применим как x u&I. y, мы получим (I. x) u (I. y). Давайте продолжим с преобразованным вводом.
• x <.&# y- меньшая из длин xи y.
• x -/@,: y- разница предметов xи y. Если один вектор длиннее, он дополняется нулями.
• x $ y- yпреобразован в форму, указанную x. В частности, если xэто скаляр, xэлементы взяты из y. В этом случае x (<.&# $ -/@,:) yубедитесь, что замыкающие отверстия игнорируются.
• 4 o. y- функция %: 1 + *: y, то есть sqrt (1 + y² ). Кстати, эта функция отображает расстояние от отверстия до длины стержней.
• +/ y- сумма элементов 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]))

Это оказалось похоже на решение Mac . Преобразуйте списки 0 и 1 в упорядоченные списки одноиндексных, а затем суммируйте расстояние между соответствующими элементами.

J, 32 28 байт

Глагол I.возвращает позиции 1s в двоичной строке, что очень помогает.

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

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

Для лучшего решения J проверьте ответ FUZxxl .

Р, 67

Использует внешний, чтобы сделать разницу для индексированных отверстий. Diag возвращает необходимые различия. Затем сложите рассчитанные расстояния

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

Тестовый прогон в R Fiddle. Я завернул его в печать, чтобы показать, что возврат соответствует спецификации.

> 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 байта

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

Использование: [0,1,0,1] # [1,0,0,1]какие выводы2.414213562373095

Как это работает: функция rвозвращает список позиций отверстий на доске, например r [0,1,0,1]-> [2,4]. #сжатие двух из этих списков и превращение его в список расстояний между соответствующими отверстиями и, наконец, суммирование.

CJam, 36 33 байта

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

Очень наивный подход ... он ожидает ввода в виде массивов в стиле CJam на STDIN

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

Вот тестовая схема для всех входов примера. Результаты в поле ввода используются до вызова фактического кода. Вы можете удалить их, если не доверяете мне. ;)

объяснение

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

Питон, 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и b. Если один из них пуст, вернитесь 0.

Иначе, пусть xи yбудут их первыми элементами (код на самом деле не присваивает их, потому что вы не можете делать присваивания в a lambda, но это облегчит объяснение). Если оба равны 1, т.е. их произведение равно 1, то они вносят вклад в расстояние между стержнями. Мы отслеживаем расстояние в комплексном числе i, так что расстояние является абсолютным значением. На самом деле, мы вычисляем это независимо, а затем умножаем на x*y.

Затем мы возвращаемся. Идея состоит в том, чтобы сдвинуть оба списка на один шаг, если только один список не начинается с 0, а другой - с одного, и в этом случае мы сдвигаем только список 0. Таким образом, 1 всегда потребляются в парах. Мы могли бы проверить эти условия с помощью x<yи y<x, но короче использовать сравнение списка как a[:1]<=b. Наконец, мы корректируем сложное смещение между текущими элементами с помощью x-y.

Python, 105 102 100 байт

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

Довольно простой, просто конвертирует входные списки в списки индексов отверстий, а затем вычисляет расстояние между каждой парой таких индексов.

Прецедент:

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

Благодарим @FryAmTheEggman за несколько предложений по экономии байтов. Оказывается, это может быть продолжено, как показано в ответе xnor .

Pyth, 30 байт

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

Попробуйте онлайн с вводом [0,1,1,0,1,1,1,1,0,0], [1,0,0,1,1,1,0,0,1].

Объяснение:

Я конвертировать списки в списки индексов [2, 3, 5, 6, 7, 8]и [1, 4, 5, 6, 9]и пронестись их вместе [(2,1), (3,4), (5,5), (6,6), (7,9)]. Затем я вычитаю значения, возводю их в квадрат, добавляю 1 и суммирую по всем квадратным корням.

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

Позор, sumкоторый не работает для пустых списков.

Python, 116 115 байт

Это рекурсивное решение.

Это стало довольно раздражающим, когда я обнаружил, что index()просто выдает ошибку, когда значение не найдено, но я заставил его работать. К сожалению, я не могу использовать лямбду. Меня также раздражало, что list.remove()список не возвращается, а возвращается 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)

Запустите онлайн здесь: http://repl.it/c5L/2

Клип 3 , 55 47 38

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

Для списка с меньшим количеством отверстий программа проходит через него и соединяет каждое отверстие с соответствующим отверстием другого списка. Размеры рассчитываются и суммируются.

>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

объяснение

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

Если мы очень либерально относимся к формату ввода, мы можем уменьшить его до 36 байтов, удалив каждый k. Это требует ввода быть строка символов управляющих символов \0и \1.

ECMAScript 6, 86 байт

Первоначально это было начато с использованием Reduce (я хотел посмотреть, можно ли это сделать за один цикл, а не на @ 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)

Но используя @ edc65 для mapи &&tдля возврата значения, я смог немного его укоротить.

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

Ява, 151

Это просто ходит в aпоисках, а затем идет, bкогда находит. Если floatточность приемлема, я могу сэкономить пару байтов, но я согласился с doubleрезультатами теста.

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

С пробелами:

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

Основным моментом является функция f, которая отображает входные массивы 0..1 в массивах позиций отверстий. Затем массивы сканируют, вычисляя общую длину стержней, используя теорему Пифагора. |0Ближе к концу необходим для преобразования NaNs , которые могут возникнуть в результате , когда массив драйвера (первый) больше , чем второй.

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

Тест в консоли 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

Октава, 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}

Удобочитаемый:

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
}

Тестирование:

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 байт

Использует алгоритм, аналогичный J-решению, но APL имеет меньше встроенных функций.

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

Пример ввода:

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