Фон

Арифметические атомы желе векторизуются автоматически. На самом деле, x + y четко определено всякий раз, когда x и y являются числами или рваными массивами чисел. Исходный код Jelly реализует это поведение с использованием универсального векторизатора, но для этой задачи мы рассмотрим только добавление целых и вложенных целочисленных массивов.

Определения

Определите глубину x как 0, если x является целым числом, как 1, если это (возможно, пустой) плоский массив целых чисел, и как n + 1, если он содержит хотя бы один элемент глубины n и не имеет элементов глубины k> п .

Таким образом, 1 имеет глубину 0 , [] и [1] и [1, 1] имеют глубину 1 , [[], []] и [[1], [1]] и [[1]] и [1 , []] имеют глубину 2 , [1, [1, [1]]] имеют глубину 3 и т. д.

Операция x + y определяется следующим образом.

1. Если x и y имеют глубину 0 , вернуть их сумму.

2. Если x и y имеют одинаковую, но положительную глубину, рекурсивно примените + ко всем элементам x и соответствующим элементам y .

   Если x и y имеют разную длину, добавьте хвост более длинного массива к массиву сумм.

   Вернуть результат.

3. Если глубина x строго меньше, чем глубина y , рекурсивно примените + к x и всем элементам y и верните результат.

   Сделайте обратное, если глубина y строго меньше, чем x .

Например, рассмотрим операцию [1, [2, 3], [4]] + [[[10, 20], [30], 40, 50], 60] .

• Глубина левого аргумента равна 2 , а глубина правого аргумента равна 3 , поэтому мы вычисляем [1, [2, 3], [4]] + [[10, 20], [30], 40, 50 ] и [1, [2, 3], [4]] + 60 .

  • [1, [2, 3], [4]] и [[10, 20], [30], 40, 50] оба имеют глубину 2 , поэтому мы вычисляем 1 + [10, 20] , [2, 3] + [30] и [4] + 40 .

    • 1 + [10, 20] = [1 + 10, 1 + 20] = [11, 21]

    • [2, 3] + [30] = [2 + 30, 3] = [32, 3]

      Обратите внимание, что 3 остается нетронутым, поскольку у него нет соответствующего элемента.

    • [4] + 40 = [4 + 40] = [44]

    
    50 не имеет соответствующий элемент, так что результат [[[11, 21], [32, 3], [44], 50]] .

  • [1, [2, 3], [4]] + 60 = [1 + 60, [2, 3] + 60, [4] + 60] = [61, [2 + 60, 3 + 60], [ 4 + 60]] , что приводит к [61, [62, 63], [64]] .

• Окончательный результат [[[11, 21], [32, 3], [44], 50], [61, [62, 63], [64]]] .

задача

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

Если ваш язык имеет несколько массивоподобных типов (списки, кортежи, векторы и т. Д.), Вы можете выбрать любой из них для ответа. Тип возвращаемого значения должен соответствовать типу аргумента.

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

Все встроенные модули всех других языков разрешены. Если ваш язык позволяет это сделать, вы можете перегрузить и / или переопределить встроенное дополнение.

Это код-гольф , поэтому выигрывает самый короткий код в байтах.

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

0 + 0                           = 0
[-1, 0, -1] + [1]               = [0, 0, -1]
[] + [0]                        = [0]
[] + 0                          = []
[] + []                         = []
[[], 0] + []                    = [[], []]
[1, 2, 3] + 10                  = [11, 12, 13]
[1, 2, 3] + [10]                = [11, 2, 3]
[1, 2, 3] + [10, [20]]          = [[11, 12, 13], [21, 2, 3]]
[1, 2, 3, []] + [10, [20]]      = [11, [22], 3, []]
[1, [2, [3, [4]]]] + [10, [20]] = [[11, [21]], [[12, [22]], [13, [24]]]]

Чтобы создать больше тестовых случаев, вы можете использовать эту программу Jelly .

Pyth, 42 байта

L?sIb0heSyM+b0M?qFyMJ,GH?yGgM.tJ0+GHgLFyDJ

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

Последние 4 байта просто запускают функцию на входе.

L?sIb0heSyM+b0M?qFyMJ,GH?yGgM.tJ0+GHgLFyDJ

L?sIb0heSyM+b0
                  Define y(b), a helper function to calculate the depth.
 ?                Ternary:
  sIb             If b is invariant under the s function, which is only the case
                  if s is an int.
     0            The depth is 0.
           +b0    Add a 0 on to b. This handles the edge case where b is [].
         yM       Map each to their depth
       eS         Take the max.
      h           Add one.

M?qFyMJ,GH?yGgM.tJ0+GHgLFyDJ
M                               Define g(G, H), which calculates the Jelly +.
 ?                              Ternary:
       ,GH                      Form [G, H].
      J                         Save it to J.
    yM                          Map each to its depth.
  qF                            Check if they are equal.
          ?yG                   If so, check if the depth is nonzero.
               .tJ0             If so, transpose J, pairing each element of each
                                argument with the corresponding element of the
                                other. Pad with zeroes.
             gM                 Map each to its Jelly +.
                   +GH          If the depths are zero, return the normal sum.
                         yDJ    If the depths are different, order J by depth.
                      gLF       Apply the function which left-maps the Jelly +
                                function to the two values. The first is
                                treated as a constant, while the second varies
                                over elements over the second values.

APL, 44 байта

{1=≡⍺⍵:⍺+⍵⋄=/∆←|≡¨⍺⍵:⊃∇¨/↓↑⍺⍵⋄</∆:⍺∘∇¨⍵⋄⍵∇⍺}

APL также +распределяет по массивам, но достаточно по-другому, так что это не может быть использовано. Однако есть встроенная функция глубины ( ≡).

Объяснение:

• 1=≡⍺⍵:⍺+⍵: если ⍺ ⍵обе глубины равны нулю (и, следовательно, глубина ⍺ ⍵равна 1), добавьте их.
• ∆←|≡¨⍺⍵: Взять абсолютные глубины как ⍺и ⍵и хранить их в ∆. ( ≡дает отрицательное значение, если не все элементы имеют одинаковую глубину.)
• =/∆: если они имеют одинаковую глубину:
  • ↓↑⍺⍵: заполнить кратчайший массив нулями, чтобы он соответствовал длинному массиву
  • ⊃∇¨/: распределить функцию по обоим массивам
• </∆: если глубина ⍺меньше, чем глубина ⍵:
  • ⍺∘∇¨⍵: bind, ⍺а затем наносить на карту⍵
• ⍵∇⍺: если больше ничего (так ⍵глубже ⍺), поменяйте местами аргументы и попробуйте снова.

Mathematica, 122 байта

d=Depth
x_~f~y_/;d@x>d@y:=y~f~x
x_~f~y_/;d@x<d@y:=x~f~#&/@y
x_List~f~y_:=MapThread[f,{x,y}~PadRight~Automatic]
x_~f~y_=x+y

Определяет рекурсивную функцию, fкоторая вычисляет сумму. Используя сопоставление с образцом Mathematica, эта функция состоит из четырех отдельных определений:

x_~f~y_/;d@x>d@y:=y~f~x

Если глубина xбольше, чем глубина y, поменяйте местами аргументы, чтобы мы могли обрабатывать распределение только в одном направлении (что мы можем сделать, так как сложение коммутативно).

x_~f~y_/;d@x<d@y:=x~f~#&/@y

Если глубина xменьше Thann , что из y, заменить каждое значение #в yс f[x,#], который заботится о распределении для аргументов неравной глубины.

x_List~f~y_:=MapThread[f,{x,y}~PadRight~Automatic]

В противном случае, если один аргумент является списком (что подразумевает, что другой также является списком, поскольку мы знаем, что они имеют одинаковую глубину), мы помещаем оба аргумента в список, дополняем их одинаковой длиной PadRight[..., Automatic](что просто заполняет рваный массив с нулями, чтобы сделать его прямоугольным), а затем использовать MapThreadдля применения fк соответствующим парам из двух списков.

И, наконец, базовый вариант:

x_~f~y_=x+y

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

Haskell, 150 байт

data L=S Int|V{v::[L]}
d(V z)=1+maximum(d<$>S 0:z);d _=0
S x!S y=S$x+y
x!y|d x<d y=V$(x!)<$>v y|d x>d y=y!x|1<2=V$v x#v y
(x:a)#(y:b)=x!y:a#b;a#b=a++b

объяснение

Первая строка определяет алгебраический тип данных L, который является либо Scalar (содержащий Int), либо Vector (содержащий список Ls, доступ к которому осуществляется с помощью средства получения записи v, которое является частичной функцией L → [L].)

Вторая строка определяет функцию глубины : глубина Vэктора равна единице плюс ее максимальная глубина. Я добавляю S 0значения в векторе, так что depth [] == 1 + maximum [depth (S 0)] == 1. Глубина «всего остального» (скаляр) есть 0.

Третья строка определяет базовый случай для !(функция сложения): сумма скаляров просто скаляр.

Пятая строка определяет вариант, zipWith (!)который просто выбирает элементы из самого длинного списка, когда один из них пуст.

Четвертая строка разбита на три случая:

x!y | d x<d y = V$(x!)<$>v y
    | d x>d y = y!x
    | True    = V$v x#v y

• Если глубина xстрого меньше, чем глубина y, отобразите (x!)элементы y. (Использование vгарантированно будет действительным, как d(y) ≥ 1.)

• Если глубина xстрого больше, переверните аргументы и перезапустите.

• Если их глубина равна, заархивируйте аргументы вместе с (!). (Использование vгарантированно будет действительным, так как случай d(x) = d(y) = 0был обработан как базовый вариант.)

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

instance Show L where
  show (S x) = show x
  show (V x) = show x

lArg = V [S 1, V [S 2, V [S 3, V [S 4]]]]
rArg = V [S 10, V [S 20]]

Потом show (lArg ! rArg) == "[[11,[21]],[[12,[22]],[13,[24]]]]".

Java, 802 794 754 746 байт

Я решил взяться за @ Деннис ♦ за задачу поработать со строками «в крайнем случае», потому что это было, вероятно, «слишком сложно». Кроме того, на худшем языке для игры в гольф.

Массивы на входе разделены запятыми, заключены в квадратные скобки и без пробелов.

Полная программа с функциями, заключенными в класс и с тестовыми примерами

import java.util.*;
List<String>p(String s){List r=new ArrayList<String>();String p="";int l=0;for(char c:s.substring(1,s.length()-1).toCharArray()){l+=c=='['?1:c==']'?-1:0;if(c==','&&l<1){r.add(p);p="";}else p+=c;}if(p!="")r.add(p);return r;}
int d(String s){int l=0;if(s.contains("[")){for(String c:p(s))l=d(c)>l?d(c):l;l++;}return l;}
String f(String x,String y){int i=0;String r="";if(d(x)<1&&d(y)<1)r+=Integer.valueOf(x)+Integer.valueOf(y);else{r="[";if(d(x)<d(y))for(String k:p(y))r+=(i++<1?"":",")+f(x,k);else if(d(x)>d(y))for(String k:p(x))r+=(i++<1?"":",")+f(k,y);else for(;i<p(x).size()||i<p(y).size();i++)r+=(i<1?"":",")+(i<p(x).size()&&i<p(y).size()?f(p(x).get(i),p(y).get(i)):i<p(x).size()?p(x).get(i):p(y).get(i));r+="]";}return r;}

Я мог бы портировать это на C ++ позже, так как это другой язык, который я знаю, который не поддерживает рваные массивы, так как я почти уверен, что он будет короче, чем этот ответ. Это было главным образом доказательством концепции, но любые советы по игре в гольф все равно будут оценены!

-31 байт от @ user902383, предлагающего использовать foreach поверх преобразованного массива символов, а затем я немного сэкономил от перестановки блоков if в заключительной части.

Python 2.7, 261 209 202 198 191 185 197 181 байт

FGITW тривиальное решение

РЕДАКТИРОВАТЬ: Конечно @ Деннис бьет это

Спасибо @LeakyNun за сохранение 57 байтов с подсказками по лямбда-выражениям и 2 байта из ненужных скобок.

Спасибо @Adnan за 4 байта из-за предложения использовать typeвместоisinstance

Спасибо @Lynn за 7 байтов с -~иmap

Спасибо @FryAmTheEggman за z>=[]вместоtype

+12 байт для преобразования лямбды в if else и исправления серьезной ошибки

-16 байт благодаря @Kevin Lau - не Кенни

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

d=lambda z:z==[]or z>[]and-~max(map(d,z))
p=lambda x,y:p(y,x)if d(x)>d(y)else(x+y if d(x)<1 else[p(a,b)for a,b in zip(x,y)]+x[len(y):]+y[len(x):])if d(x)==d(y)else[p(a,x)for a in y]

Python 2, 145 136 байт

d=lambda t:t>{}and-~max(map(d,t+[0]))
s=lambda x,y:s(y,x)if d(y)<d(x)else map(s,(x,[x]*len(y))[d(x)<d(y)],y)if d(y)else(x or 0)+(y or 0)

Проверьте это на Ideone .

Как это устроено

В Python 2 все целые числа меньше всех словарей, но все списки больше. d рекурсивно вычисляет глубину t , возвращая 0 для целых чисел или увеличенный максимум глубин его элементов и 0 . t+[0]избегает специального случая пустого списка.

s рекурсивно вычисляет сумму желе x и y .

Если глубина y превышает x , s(y,x)вызывает s с замененными аргументами, убедившись, что d (x) ≤ d (y) .

Если у имеет положительную глубину, map(s,(x,[x]*len(y))[d(x)<d(y)],y)делает следующее.

• Если х и у глубины совпадают, он выполняется map(s,x,y), отображая s по всем элементам x и соответствующим элементам y .

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

• Если X глубина «S ниже , чем у , выполняется map(s,[x]*len(y),y), отображая s (x, ·) над y .

Если у (и, следовательно, х ) имеет глубину 0 , (x or 0)+(y or 0)заменяет ложные аргументы ( Нет или 0 ) нулями и возвращает сумму результирующих целых чисел.

JavaScript (ES6), 152 байта

f=(a,b,g=a=>a.map?1+Math.max(0,...a.map(g)):0)=>g(a)<g(b)?f(b,a):g(b)<g(a)?a.map(e=>f(e,b)):g(a)?a.length<b.length?f(b,a):a.map((e,i)=>f(e,b[i]||0)):a+b
;t=(x,y,z)=>o.textContent+=`
${JSON.stringify(x)}
${JSON.stringify(y)}
${JSON.stringify(z)}
${JSON.stringify(f(x,y))}
`;`
0 + 0                           = 0
[-1, 0, -1] + [1]               = [0, 0, -1]
[] + [0]                        = [0]
[] + 0                          = []
[] + []                         = []
[[], 0] + []                    = [[], []]
[1, 2, 3] + 10                  = [11, 12, 13]
[1, 2, 3] + [10]                = [11, 2, 3]
[1, 2, 3] + [10, [20]]          = [[11, 12, 13], [21, 2, 3]]
[1, 2, 3, []] + [10, [20]]      = [11, [22], 3, []]
[1, [2, [3, [4]]]] + [10, [20]] = [[11, [21]], [[12, [22]], [13, [24]]]]`.slice(1).split`
`.map(l=>t(...l.split(/ [+=] /).map(a=>JSON.parse(a))));

<pre id=o></pre>

Рубин 2,3 143 145 148 149 байт

В Ruby есть все эти маленькие странности в zipработе с массивами разной длины и mapс несколькими аргументами, что делает это довольно забавным для игры в гольф.

f=->x,y{d=->a{-~(a.map(&d).max||0)rescue 0}
d[x]<d[y]?y.map{|e|f[x,e]}:d[x]>d[y]?x.map{|e|f[e,y]}:d[x]<1?x+(y||0):[*x.zip(y).map(&f),*y[x.size..-1]]}

Юлия, 113 байт

~=endof;!t=0t!=0&&1+maximum(!,[t;0])
x::Array+y::Array=(!x,~x)>(!y,~y)?y+x:!x<!y?map(t->x+t,y):~x<~y?[x;0]+y:x.+y

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

Как это устроено

~=endof

создает 1-байтовый псевдоним для endof , который возвращает длину массива.

!t=0t!=0&&1+maximum(!,[t;0])

определяет функцию глубины. Глубина t равна нулю тогда и только тогда, когда 0t == 0 . Если нет, то t является массивом, и его глубина рассчитывается как увеличенный максимум глубин его элементов и 0 . [t;0]добавляет 0 к массиву t , что исключает необходимость в специальном случае пустого массива.

Юлия встроенная сумма + уже ведет себя как сумма Джелли, если один из (или оба) ее аргументов является целым числом. Однако для суммирования двух массивов ( + ) требуются массивы одинаковой формы и даже векторизованная сумма ( . + ) Требуются массивы, которые можно транслировать в общую форму.

Мы переопределяем + для пары массивов через

x::Array+y::Array=(!x,~x)>(!y,~y)?y+x:!x<!y?map(t->x+t,y):~x<~y?[x;0]+y:x.+y

Это не влияет на определение + для аргументов целое число / целое число, массив / целое число или целое число / массив.

(!x,~x)>(!y,~y)лексикографически сравнивает пары глубин и длин как x, так и y . Если X глубина «S превышает у , или если их глубина совпадает, а длина x превышает y , y+xрекурсивно вызывает + с замененными аргументами.

В противном случае, !x<!yтесты, если х глубина ниже, чем y . Если это так, map(t->x+t,y)карты x + · над y .

Если глубина совпадает, ~x<~yпроверяет, х короче, чем y . Если это так, [x;0]+yрекурсивно вызывает + после добавления 0 к левому аргументу.

Наконец, если глубина и длина одинаковы, x.+yкарты + для всех элементов x и соответствующих элементов y .