Варенье не добавляй

16

Фон

Арифметические атомы желе векторизуются автоматически. На самом деле, 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 .

Деннис
источник
Что если наш язык не поддерживает рваные массивы? Разрешено ли нам реструктурировать ввод или мы должны использовать рваные массивы? Или, может быть, просто использовать другой язык?
миль
Что вы подразумеваете под реструктуризацией входа ?
Деннис
Если подумать дальше, я понимаю, что это не сработает для реструктуризации входных данных, но в любом случае я суммирую то, что я имел в виду раньше. Я подумал об использовании значения заполнения для заполнения, что исключило бы некоторую работу, но также создало бы другую проблему (возможно, отличную от заданного вами вопроса), но теперь я понимаю, что ваши тестовые примеры также содержат отрицательные числа.
миль
Массивы также могут быть неоднородными, поэтому значений заполнения недостаточно, чтобы сделать их прямоугольными. В крайнем случае, всегда есть возможность работать со строками, но это, вероятно, слишком сложно.
Деннис
3
Эй, хороший заголовок! .. теперь, когда Google помог мне получить его :-)
Луис Мендо

Ответы:

3

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.
isaacg
источник
7

APL, 44 байта

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

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

Объяснение:

  • 1=≡⍺⍵:⍺+⍵: если обе глубины равны нулю (и, следовательно, глубина ⍺ ⍵равна 1), добавьте их.
  • ∆←|≡¨⍺⍵: Взять абсолютные глубины как и и хранить их в . ( дает отрицательное значение, если не все элементы имеют одинаковую глубину.)
  • =/∆: если они имеют одинаковую глубину:
    • ↓↑⍺⍵: заполнить кратчайший массив нулями, чтобы он соответствовал длинному массиву
    • ⊃∇¨/: распределить функцию по обоим массивам
  • </∆: если глубина меньше, чем глубина :
    • ⍺∘∇¨⍵: bind, а затем наносить на карту
  • ⍵∇⍺: если больше ничего (так глубже ), поменяйте местами аргументы и попробуйте снова.
Мэринус
источник
3
Иногда я думаю, что хорошо знаю APL. Потом я вижу такой шедевр и понимаю, что почти не знаю его.
Алекс А.
Действительно ли символы APL считаются байтами?
Металим
@metalim APL имеет устаревшие кодовые страницы, которые предшествуют Unicode на несколько десятилетий. В них каждый символ представляет собой один байт.
Деннис
Затем тип кодирования должен быть предоставлен с решением. Просто ИМО.
Металим
@ Metalim Я добавил ссылку.
Адам
5

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

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

Мартин Эндер
источник
5

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

Линн
источник
Я просто исправил это тоже ^^ (я поменял строки на удобочитаемость, но сделал это неправильно…) Дело в importтом, что у Ideone есть старый компилятор на Haskell. Современные версии GHC поместить <$>в Prelude, так что вам не нужно импортировать , Control.Applicativeчтобы использовать его в эти дни.
Линн
Слишком много правок одновременно с другими моими действиями: P И, конечно, сейчас все в порядке, но я нахожу довольно странным, что это вызывает ошибку компиляции. Должны ли все биты сопоставления с образцом функции быть последовательными?
FryAmTheEggman
Это точно верно.
Линн
Хорошо, спасибо за вашу помощь :) «Я когда-нибудь познакомлюсь с этим языком» - FryAmTheEggman 7 лет назад.
FryAmTheEggman
4

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 в заключительной части.

Значение чернил
источник
Это поразительно.
Деннис
Я думаю, что если вы замените свои циклы массивом из цикла foreach через массив символов, полученный из строки, вы можете сэкономить довольно много байтов.
user902383
1
Errr ... Java поддерживает рваные массивы; Я не уверен, что вы подразумеваете под этим. Использование Object[], которое содержит либо вложенный, Object[]либо Integer. Или просто неуниверсальный список.
Роберт Фрейзер
4

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.7 и написатьz==[]or`z`>']'and ...
Lynn
Кроме того, я думаю, что замена max(d(a)+1for a in z)на -~max(d(a)for a in z)экономит байт (потому что вы можете удалить пространство раньше max). Что тогда просто -~max(map(d,z)).
Линн
Переход на Python 2 экономит еще больше, поскольку вы можете перейти [p(a,b)for a,b in zip(x,y)]на map(p,x,y). Вы все еще можете сделать это в 3, но вам нужно добавить вызов list. Я думаю, вы могли бы также улучшить предложение Линн z>=[]. Независимо от этого, вы также должны иметь возможность менять typeпорядок сравнения, чтобы сэкономить место.
FryAmTheEggman
Я имел в виду or`z`>'[', конечно, но больше не могу менять свой комментарий. Но на самом деле, z>[]еще короче ( ==дело уже решено)!
Линн
Карта @FryAmTheEggman не работает, когда списки имеют разные размеры; почтовый индекс урезан правильно. Я обновлю с проверкой списка tho
Blue
3

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 ) нулями и возвращает сумму результирующих целых чисел.

Деннис
источник
1

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>

Нил
источник
1

Рубин 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]]}
Значение чернил
источник
Это очень интересно - я никогда раньше не видел эту ошибку для этой функции. Я все еще исправлял некоторые вещи из-за других ошибок сейчас, но кроме этого это работает для меня (но все еще не работает на ideone). Я думаю, это потому, что ideone запускает 2.1, а у меня 2.3, поэтому, возможно, 2.1 не может просто использовать mapфункцию с двумя аргументами, как я ее настроил в конце. Вот версия, отредактированная для 2.1, которая работает, которая настраивает mapвызов в конце, чтобы работать. ideone.com/q1jqTA
Value Ink
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 .

Деннис
источник