Введение

Рассмотрим два непустых целочисленных массива, скажем, A = [0 3 2 2 8 4] и B = [7 8 7 2] . Чтобы выполнить выравнивание на них, мы делаем следующее:

1. Повторите каждый массив достаточно раз, чтобы иметь общую длину lcm (длина (A), длина (B)) . Здесь lcm обозначает наименьший общий множитель .

   A -> [0 3 2 2  8 4][0 3  2 2 8 4]
   B -> [7 8 7 2][7 8  7 2][7 8 7 2]
   

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

   A -> [0  3 2 2   8  4][0 3  2  2  8 4]
   B -> [7  8 7 2][ 7  8  7 2][7  8  7 2]
     -> [7 11 9 4][15 12][7 5][9 10 15 6]
   

3. Этот массив массивов - ваш результат.

Задание

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

Правила и оценки

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

Контрольные примеры

[1] [4] -> [[5]]
[1,2,-3,-4] [15] -> [[16],[17],[12],[11]]
[0,-4] [2,1,0,-3] -> [[2,-3],[0,-7]]
[0,3,2,2,8,4] [7,8,7,2] -> [[7,11,9,4],[15,12],[7,5],[9,10,15,6]]
[18,17,16] [-1,-2,-3,-4] -> [[17,15,13],[14],[16,14],[15,13],[15],[16,14,12]]
[18,17,16,15] [-1,-2,-3,-4] -> [[17,15,13,11]]
[1,1,1,1,1] [6,5,6,5,6,5,6,2,1] -> [[7,6,7,6,7],[6,7,3,2],[7],[6,7,6,7,6],[7,3,2],[7,6],[7,6,7,6,7],[3,2],[7,6,7],[6,7,6,7,3],[2],[7,6,7,6],[7,6,7,3,2]]
[1,1,1,1,1,1] [6,5,6,5,6,5,6,2,1] -> [[7,6,7,6,7,6],[7,3,2],[7,6,7],[6,7,6,7,3,2]]
[1,1,1,1,1,1,1] [6,5,6,5,6,5,6,2,1] -> [[7,6,7,6,7,6,7],[3,2],[7,6,7,6,7],[6,7,3,2],[7,6,7],[6,7,6,7,3,2],[7],[6,7,6,7,6,7,3],[2],[7,6,7,6,7,6],[7,3,2],[7,6,7,6],[7,6,7,3,2],[7,6],[7,6,7,6,7,3,2]]

JavaScript (ES6), 101 99 байт

Принимает ввод как 2 массива. Возвращает строку.

f=(a,b,j=0,s='')=>a.map((v,i)=>(s+=i*j?' ':s&&'][',s+=b[j]+v,j=++j%b.length))|j?f(a,b,j,s):`[${s}]`

Как это работает

Мы перебираем первый массив aс указателем i, обновляя другой указатель jво второй массив b. Суммы a[i] + b[j]добавляются к выходной строке s. Разделитель вставляется каждый раз i == 0или j == 0. Мы повторяем этот процесс, пока jне вернемся точно в начале и bв конце итерации.

Примечание: Когда применяется |оператор, применяется a.map(...)либо NaN(если aсодержит более одного элемента), либо к текущему значению j(если aсодержит ровно один элемент). Поэтому a.map(...)|j == jво всех случаях и здесь можно безопасно пользоваться.

Контрольные примеры

f=(a,b,j=0,s='')=>a.map((v,i)=>(s+=i*j?' ':s&&'][',s+=b[j]+v,j=++j%b.length))|j?f(a,b,j,s):`[${s}]`

console.log(f([1], [4]));
console.log(f([1,2,-3,-4], [15]));
console.log(f([0,-4], [2,1,0,-3]));
console.log(f([0,3,2,2,8,4], [7,8,7,2]));
console.log(f([18,17,16], [-1,-2,-3,-4]));
console.log(f([18,17,16,15], [-1,-2,-3,-4]));
console.log(f([1,1,1,1,1], [6,5,6,5,6,5,6,2,1]));
console.log(f([1,1,1,1,1,1], [6,5,6,5,6,5,6,2,1]));
console.log(f([1,1,1,1,1,1,1], [6,5,6,5,6,5,6,2,1]));

Haskell, 84 79 байтов

a#b=a%b where(c:d)%(e:f)|(x:y)<-d%f=(c+e:x):y;[]%[]=[[]];c%[]=[]:c%b;_%d=[]:a%d

Моя первая версия была такой же в более читаемом виде:

a#b=a%b where
 (c:d)%(e:f)|(x:y)<-d%f=(c+e:x):y
 []%[]=[[]]
 c%[]=[]:c%b
 _%d=[]:a%d

Использование локального определения, чтобы избежать необходимости давать (%)дополнительные аргументы для aи b. Удивительно, но это почти то же самое решение, что и в то же время, что и у @ nimi, у которого я взял идею использовать только одну строку для локального определения.

Использование:

*Main> [0,3,2,2,8,4] # [7,8,7,2]
[[7,11,9,4],[15,12],[7,5],[9,10,15,6]]

PHP, 126 120 байт

function($a,$b){do{$c[$j][]=$a[$i%$x=count($a)]+$b[$i%$y=count($b)];++$i%$x&&$i%$y?:$j++;}while($i%$x|$i%$y);return$c;};

Попробуй это здесь!

Анонимная функция, которая возвращает полученный массив массивов.

По сути, мы перебираем содержимое обоих наших массивов, модифицируя наш итератор по длине массива, чтобы имитировать «копирование» их. Взяв каждое из значений из массивов, мы суммируем их и добавляем в массив в $c. Если мы достигнем конца одного из наших входных массивов (разделение, с точки зрения задачи), мы начнем присваивать новый массив в $c.

Причина do whileцикла в том, что наше условие основано на том $i, что начинается с 0. Если мы используем цикл, где условие проверяется в начале, цикл не будет работать

Мы заканчиваем суммирование, только когда достигаем конца обоих массивов одновременно, что подразумевает LCM.

Haskell, 87 84 байта

a#b=a%b where[]%[]=[[]];(e:f)%(g:h)=f%h!(e+g);e%[]=[]:e%b;_%g=[]:a%g
(m:n)!l=(l:m):n

Пример использования: [0,3,2,2,8,4] # [7,8,7,2]-> [[7,11,9,4],[15,12],[7,5],[9,10,15,6]].

Простая рекурсия. Базовый случай: оба списка пусты. Если только один из них пуст, перезапустите с полной версией и запустите новый кластер в выходных данных. Если ни один не пуст, добавьте сумму к элементу from.

Взгляните также на ответ @Christian Sievers , который почти идентичен и был опубликован несколькими секундами ранее.

Октава, 113 байт

@(a,b)mat2cell(sum([repmat(a,1,(L=lcm(A=numel(a),B=numel(b)))/A);repmat(b,1,L/B)]),1,diff(unique([0:A:L,0:B:L])))

эта функция может вызываться напрямую, вызывать ее, ставить в скобки и называть (@ (a, b) ...) ([1 2 3 4], [6 4 5])

CJam , 30 байтов

{Sf*Laf+_s,f*:.+La/0=S2*a-Sa/}

Попробуйте онлайн!

Принимает ввод в виде пары списков.

объяснение

Идея состоит в том, чтобы вставить некоторые маркеры во входные массивы (в виде коротких строк), которые указывают, где заканчивается выровненный массив и где нам нужно вставить разрывы в массивах. Таким образом, мы можем избежать вычисления LCM.

Sf*    e# Riffle each list with spaces. These are just place holders, so that having
       e# an array-end marker between two elements doesn't misalign subsequent elements.
Laf+   e# Append an empty string to each list. This is the array-end marker.
_s,    e# Convert the pair of lists to a string and get its length. This is always
       e# greater than the number of elements in either input.
f*     e# Repeat either array that many times. This is definitely more than necessary
       e# to reach the LCM (since multiplying by the length of the other list always
       e# gives a common multiple).
:.+    e# Pairwise addition of the list elements. There are four cases:
       e# - Both elements are numbers, add them. This is the actual addition
       e#   we need for the problem.
       e# - Both elements are spaces. This is just a regular position between
       e#   list elements.
       e# - One is a space, one is empty: the result is a single space, and
       e#   this marks a position where one of the arrays ended, which means
       e#   we need to split here.
       e# - Both elements are empty. This happens at the LCM of both list lengths
       e#   and indicates where we need to stop the output.
La/0=  e# Split the input around empty strings and discard everything except
       e# the first chunk.
S2*a-  e# Remove the double-space strings, we no longer need them.
Sa/    e# Split the list around single spaces.

Желе , 21 20 18 байт

ṁ€L€æl/$S
J€ỊÇœṗÇḊ

Попробуйте онлайн!

Как это работает

ṁ€L€æl/$S  Helper link. Argument [X, Y] (arrays of integers).

       $   Combine the two links to the left into a monadic chain.
  L€       Length each; yield the lengths of X and Y.
    æl/    Reduce by least common multiple.
ṁ€         Mold each; cyclically repeat the elements of X and Y to extend them
           to length lcm(length(X), length(Y)).
        S  Compute the sum of the extended X and Y arrays.

J€ỊÇœṗÇḊ   Main link. Argument [A, B] (arrays of integers).

J€         Indices each; replace A and B by the arrays of there 1-based indices.
  Ị        Insignificant; map 1 to itself, all other indices to 0.
   Ç       Apply the helper link to the result.
           This yield a Boolean array with a 1 (or 2) at all indices where a new
           repetition of A or B (or both) begins.
      Ç    Apply the helper link to [A, B].
    œṗ     Partition; break the result to the right at truthy elements (1 or 2) in
           the result to the right.
       Ḋ   Dequeue; remove the first element of the partition (empty array).

Python 3,5 - ( 146 137 134 130 + 12) = 142 байта

import math
def s(a,b):
 l,k,*r=map(len,[a,b])
 for i in range(l*k//math.gcd(l,k)):
  r+=a[i%l]+b[i%k],
  if i%k==k-1or i%l==l-1:print(r);r=[]

Я не могу понять, как поместить весь цикл for в одну строку.

Редактирование:

• Спасибо zgarb за сохранение 9 байтов!
• Спасибо vaultah за сохранение 3 байта!
• Спасибо, математика, сэкономив 5 байт!

Python 2, 119 байт

a=input()
i,v,l=0,list(a),len
while 1:q=l(v[0])>l(v[1]);print map(sum,zip(*v)[i:]);i=l(v[q]);v[q]+=a[q];1/(i-l(v[q^1]))

Принимает ввод из стандартного ввода в виде двух кортежей, разделенных запятой, выводит полученные списки в стандартный вывод. Завершает работу, вызывая ZeroDivisionErrorисключение, поскольку это разрешено .

Например, если введено (0, 3, 2, 2, 8, 4), (7, 8, 7, 2), программа напечатает

[7, 11, 9, 4]
[15, 12]
[7, 5]
[9, 10, 15, 6]

в стандартный вывод и трассировку исключения в стандартный поток ошибок.

J , 34 32 байта

[:(<;.1~*)/[:+/*.&#$&>,:&(;2>#\)

Попробуйте онлайн!

объяснение

[:(<;.1~*)/[:+/*.&#$&>,:&(;2>#\)  Input: array A (LHS), array B (RHS)
                             #\   Length of each prefix of A and B
                           2>     Less than 2
                          ;       Link each with A and B
                      ,:&         Pair them
                  #               Length of A and B
               *.&                LCM of the lengths
                    &>            For each box
                   $              Reshape it to the LCM of the lengths
           [:+/                   Reduce by addition
[:        /                       Reduce by
        *                           Sign of RHS
   <;.1~                            Box each partition of LHS

Haskell, 166 байт

Это, вероятно, не самый элегантный подход: в основном, функция ?создает один список необходимой длины с суммами, и% снова сокращает эту сумму. !это последняя функция, которая объединяет эти два.

l=length
a?b=take(lcm(l a)$l b)$zipWith(+)(cycle a)$cycle b
l%(i:ind)|l==[]=[]|1>0=take i l:(drop i l)%(map(+(-i))ind)
a!b=(a?b)%[k|k<-[1..],k`mod`l a<1||k`mod`l b<1]

[PHP], 183 152 135 байтов

function O($A,$B){while($f<2){$O[$k][]=$A[+$i]+$B[+$j];$f=0;isset($A[++$i])?:$i=!++$k|!++$f;isset($B[++$j])?:$j=!++$k|!++$f;}return$O;}

Хорошая версия:

function O($A,$B)
{
    while($f<2) {
        $O[$k][]=$A[+$i]+$B[+$j];
        $f=0;
        isset($A[++$i])?:$i=!++$k|!++$f;
        isset($B[++$j])?:$j=!++$k|!++$f;
    }

    return$O;
}

Выход:

array (size=4)
  0 => 
    array (size=4)
      0 => int 7
      1 => int 11
      2 => int 9
      3 => int 4
  1 => 
    array (size=2)
      0 => int 15
      1 => int 12
  2 => 
    array (size=2)
      0 => int 7
      1 => int 5
  3 => 
    array (size=4)
      0 => int 9
      1 => int 10
      2 => int 15
      3 => int 6

PowerShell , 147 145 байт

param($a,$b)$o=@{};do{$o[+$j]+=,($a[+$i%($x=$a.count)]+$b[$i++%($y=$b.count)]);if(!($i%$x-and$i%$y)){$j++}}until(($x,$y|?{!($i%$_)}).count-eq2)$o

Попробуйте онлайн!

( Предложения по игре в гольф приветствуются. Я чувствую, что из этого можно выжать еще 10-15 байт. )

Принимает входные данные в виде двух явных массивов (с @(...)синтаксисом) в качестве аргументов командной строки. Возвращает хеш-таблицу полученных массивов, потому что многомерные массивы в PowerShell могут стать странными, и это более согласованно. Устанавливает некоторые начальные переменные, затем снова входит в цикл do/ untilс условным значением до тех пор, пока не $iбудет подсчитан lcm массива .

На каждой итерации цикла мы добавляем соответствующие значения $aи $bзначения вместе, обрабатываем его как массив ,(...)перед добавлением его в хеш-таблицу $oв соответствующем месте $j. Инкапсуляция массива необходима для предотвращения арифметического сложения - +=вместо этого это приводит к перегрузке в конкатенацию массивов. Затем, условное $xи $y(подсчитывает), чтобы определить, находимся ли мы на краю массива - если так, мы увеличиваем $j.

Наконец, мы оставляем $oна конвейере и вывод неявный.
(Примечание: из-за того, что PowerShell перечисляет хеш-таблицы со значениями по умолчанию Write-Output, это имеет тенденцию выводиться «в обратном направлении»; как, например, результирующий массив «0-й» находится в «нижней части» выходных данных. С самим хэшем все в порядке, и он будет используется просто отлично, если вы, например, инкапсулировали этот код в возвращаемую переменную ... он просто выглядит странно, когда печатается.)

Сохранение 2 байтов путем перемещения $ x и $ y в индексирование массива, а не по отдельности (сохраняется две точки с запятой).

Python 2, 113 байт

a,b=input()
i=m=n=0;r=[]
while(not i)+m+n:r+=[[]]*(not m*n);r[-1]+=[a[m]+b[n]];i+=1;m=i%len(a);n=i%len(b)
print r

Python 3.5, 210 176 173 169 158 байт

def f(a,b):
 x=[];e=f=0              
 while 1:
  if e==len(a):         
   print(x);x=[];e=0;
   if f==len(b):break
  if f==len(b):print(x);x=[];f=0
 x+=a[e]+b[f],;e+=1;f+=1

Принимает два списка в качестве входных данных и печатает все списки.

Это мой первый ответ, и я пока не знаю, как играть в гольф. Основная идея, которую я использовал, состоит в том, чтобы иметь два счетчика для каждого списка, которые указывают разделение, и текущий список, к которому добавляются добавленные значения; как только возникает разделение, мы печатаем текущий список и создаем новый пустой.

• Сохранено 34 байта : благодаря Деннису и TimmyD
• Сохранено 3 байта : использовались c и d для len (a) и len (b), но оказалось, что они не были полезны
• Сохранено 4 байта : благодаря orlp , удален нежелательный парантез
• Сохранено 11 байт : переставил несколько блоков и сжал их

Ракетка 373 байта

(let*((lg length)(fl flatten)(ml make-list)(t rest)(r reverse)(m modulo)(o cons)(ln(lg l))(jn(lg j))(c(lcm ln jn))(l2(fl(ml(/ c ln)l)))
(j2(fl(ml(/ c jn)j)))(ll(for/list((a l2)(b j2))(+ a b))))(let p((ll ll)(ol '())(tl '())(n 0))(cond[(empty? ll)(t(r(o(r tl)ol)))]
[(or(= 0(m n ln))(= 0(m n jn)))(p(t ll)(o(r tl)ol)(take ll 1)(+ 1 n))][(p(t ll)ol(o(first ll)tl)(+ 1 n))])))

Ungolfed:

(define(f l j)
  (let* ((ln (length l))
         (jn (length j))
         (c (lcm ln jn))
         (l2 (flatten (make-list (/ c ln) l)))
         (j2 (flatten (make-list (/ c jn) j)))
         (ll (for/list ((a l2)(b j2))
               (+ a b))))

    ; TO CUT LIST INTO PARTS: 
    (let loop ((ll ll)
               (ol '())
               (templ '())
               (n 0))
      (cond
        [(empty? ll) 
         (rest (reverse (cons (reverse templ) ol)))]
        [(or (= 0 (modulo n ln))
             (= 0 (modulo n jn)))
         (loop (rest ll)
               (cons (reverse templ) ol)
               (list (first ll))
               (add1 n))]
        [(loop (rest ll)
               ol
               (cons (first ll) templ)
               (add1 n))]))))

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

(f '[1]  '[4])
(f '[1 2 -3 -4] '[15])
(f '[0 3 2 2 8 4]  '[7 8 7 2])

Выход:

'((5))
'((16) (17) (12) (11))
'((7 11 9 4) (15 12) (7 5) (9 10 15 6))

Clojure, 280 206 байтов

(fn[a b](let[A(count a)B(count b)Q quot](map #(map last %)(partition-by first(take-while #((% 0)2)(map-indexed(fn[i s][[(Q i A)(Q i B)(or(= i 0)(>(mod i A)0)(>(mod i B)0))]s])(map +(cycle a)(cycle b))))))))

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

(def f (fn[a b]
         (let[A(count a)B(count b)Q quot]
           (->> (map +(cycle a)(cycle b))
                (map-indexed (fn [i s][[(Q i A)(Q i B)(or(= i 0)(>(mod i A)0)(>(mod i B)0))]s]))
                (take-while #((% 0)2))
                (partition-by first)
                (map #(map last %))))))

Оригинал: я надеюсь улучшить это, но это самое худшее, что у меня есть на данный момент.

(fn[a b](let [C cycle o count c(take-while #(or(=(% 0)0)(>(% 1)0)(>(% 2)0))(map-indexed(fn[i[A B]][i(mod i(o a))(mod i(o b))(+ A B)])(map(fn[& v]v)(C a)(C b))))](map #(map last %)(partition-by first(map(fn[p c][p(last c)])(reductions + (map #(if(or(=(% 1)0)(=(% 2)0))1 0)c))c)))))

Безголовый и многословный:

(def f (fn[a b]
         (let [c(->> (map (fn[& v]v) (cycle a) (cycle b))
                     (map-indexed (fn[i[A B]][i (mod i(count a)) (mod i(count b)) (+ A B)]))
                     (take-while #(or(=(% 0)0)(>(% 1)0)(>(% 2)0))))]
           (->> (map (fn[p c][p(last c)]) (reductions +(map #(if(or(=(% 1)0)(=(% 2)0))1 0)c)) c)
                (partition-by first)
                (map #(map last %))))))

Начинается с «слияния» бесконечного цикла коллекций aиb добавляет метаданные по индексу каждого элемента в коллекции, пока обе последовательности не начнут снова с индекса 0.

Эта коллекция cЗатем объединяется с данными раздела (совокупная сумма единиц и нулей), разделяется и выбирается последний элемент (являющийся суммой элементов).

Я думаю, что для значительных улучшений необходим совершенно иной подход.

PHP, 150 121 119 байт

function($a,$b){while($i<2|$x|$y)$r[$k+=!($x=$i%count($a))|!$y=$i++%count($b)][]=$a[$x]+$b[$y];array_pop($r);return$r;}

анонимная функция принимает входные данные как массивы.

сломать

while($i<2|$x|$y)   // loop while either $a or $b has NO cut
    $r[
                // if either $a or $b has a cut, increment $k; post-increment $i
        $k+=!($x=$i%count($a))|!$y=$i++%count($b)
                // append current $a + current $b to $r[$k]
    ][]=$a[$x]+$b[$y];
array_pop($r);  // $r has one element too much; remove it
return$r;

C ++ 14, 206 байт

Как безымянный общий лямбда, требующий ввод контейнеры P, Qи выходной контейнер , Rчтобы быть похожими vector<vector<int>>.

[](auto P,auto Q,auto&R){R.clear();auto a=P.begin(),b=Q.begin(),x=P.end(),y=Q.end();auto A=a,B=b;do{R.emplace_back();while(a!=x&&b!=y)R.back().push_back(*a+++*b++);a=a==x?A:a;b=b==y?B:b;}while(a!=A||b!=B);}

Ungolfed и использование:

#include<vector>
#include<iostream>

using namespace std;

auto f=
[](auto P,auto Q,auto&R){
 R.clear();               //just clear the output to be sure
 //a and b are the iterators, x and y is the end
 auto a=P.begin(),b=Q.begin(),x=P.end(),y=Q.end();
 //just some abbreviations for .begin()
 auto A=a,B=b;
 do{
  R.emplace_back();      //add new vector
  while(a!=x&&b!=y)      //while not at the end of one vector
   R.back().push_back(*a+++*b++);  //add the pointed elements and advance
  a=a==x?A:a;            //reset if at the end   
  b=b==y?B:b;
 }while(a!=A||b!=B);     //if both were resetted, then finish
}
;


int main(){
 vector<int> A = {0, 3, 2, 2, 8, 4};
 vector<int> B = {7, 8, 7, 2};
 vector<vector<int>> R;
 f(A,B,R);
 for (auto c:R){
  for (int x:c)
   cout << x << ", ";
  cout << endl;
 }
 cout << endl;
}

Mathematica 112 байт

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

Split[Table[{#[[1,(m=Mod[i,d=Length/@#,1])[[1]]]]+#[[2,m[[2]]]],Min@m},{i,LCM@@d}],#2[[2]]>#1[[2]]&][[;;,;;,1]]&

использование

%@{{0,3,2,2,8,4},{7,8,7,2}}

JavaScript (ES6), 131 байт

(a,b,g=(r,[n,...d]=a,[m,...e]=b,s=[])=>1/n?1/m?g(r,d,e,[...s,n+m]):g([...r,s],[n,...d]):1/m?g([...r,s],a,[m,...e]):[...r,s])=>g([])

Слегка разгульный

(a,b,r=[],[n,...d]=a,[m,...e]=b,s=[])
=>1/n?1/m?f(a,b,r,d,e,[...s,n+m])
         :f(a,b,[...r,s],[n,...d],b,[])
     :1/m?f(a,b,[...r,s],a,[m,...e],[])
         :[...r,s]

• Если оба массива dи eсодержат числа, сумма первого числа добавляется , sа остальные элементы обрабатываются рекурсивно
• Если один из массивов содержит числа, массив сумм sдобавляется к результату, rа другой массив сбрасывается в исходный массив.
• Если оба массива пусты, просто верните результат с последними добавленными суммами.

К сожалению, это решение не обладает безжалостной эффективностью @ Arnauld's, но, по крайней мере, я думаю, что это прекрасное решение.