fundo

Os átomos aritméticos da geléia se vetorizam automaticamente. De fato, x + y é bem definido sempre que x e y são números ou matrizes irregulares de números. O código fonte do Jelly implementa esse comportamento usando um vetorizador genérico, mas para esse desafio, consideraremos apenas a adição de números inteiros e matrizes inteiras aninhadas.

Definições

Defina a profundidade de x como 0 se x for um número inteiro, como 1 se for uma matriz plana (possivelmente vazia) de números inteiros e como n + 1 se contiver pelo menos um elemento de profundidade n e nenhum elemento de profundidade k> n .

Dessa forma, 1 tem profundidade 0 , [] e [1] e [1, 1] têm profundidade 1 , [[], []] e [[1], [1]] e [[1]] e [1 , []] possui profundidade 2 , [1, [1, [1]]] possui profundidade 3 , etc.

A operação x + y é definida da seguinte forma.

1. Se x e y tem profundidade 0 , volte sua soma.

2. Se x e y têm profundidades iguais, mas positivas, de forma recursiva aplicam + a todos os itens de x e os itens correspondentes do y .

   Se x e y têm diferentes comprimentos, acrescentar a cauda da matriz de mais tempo para a série de somas.

   Retorne o resultado.

3. Se a profundidade de x for estritamente menor que a profundidade de y , aplique recursivamente + a x e todos os itens de y e retorne o resultado.

   Faça o oposto se a profundidade de y for estritamente menor que x .

Por exemplo, considere a operação [1, [2, 3], [4]] + [[[10, 20], [30], 40, 50], 60] .

• A profundidade do argumento da esquerda é 2 , enquanto a profundidade do argumento da direita é 3 , portanto calculamos [1, [2, 3], [4]] + [[10, 20], [30], 40, 50 ] e [1, [2, 3], [4]] + 60 .

  • [1, [2, 3], [4]] e [[10, 20], [30], 40, 50] têm profundidade 2 , então calculamos 1 + [10, 20] , [2, 3] + [30] e [4] + 40 .

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

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

      Observe que 3 permanece intocado, pois não possui um elemento correspondente.

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

    
    50 não tem um elemento correspondente, de modo que o resultado é [[[11, 21], 44 [32, 3], [], 50]] .

  • [1, [2, 3], [4]] + 60 = [1 + 60, [2, 3] + 60, [4] + 60] = [61, [2 + 60, 3 + 60], [ 4 + 60]] , resultando em [61, [62, 63], [64]] .

• O resultado final é [[[11, 21], [32, 3], [44], 50], [61, [62, 63], [64]]] .

Tarefa

Escreva um programa ou uma função que use dois números inteiros, duas matrizes aninhadas de números inteiros ou uma combinação dos mesmos como entrada e retorne sua soma, conforme definido acima.

Se o seu idioma tiver vários tipos de array (listas, tuplas, vetores, etc.), você poderá escolher qualquer um deles para sua resposta. O tipo de retorno deve corresponder ao tipo de argumento.

Para evitar soluções chatas e imbatíveis, se um idioma tiver essa operação exata como um built-in, você não poderá usá-lo.

Todos os built-ins de todos os outros idiomas são permitidos. Se o seu idioma de escolha permitir, você poderá sobrecarregar e / ou redefinir a adição interna.

Isso é código-golfe , então o código mais curto em bytes vence.

Casos de teste

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

Para gerar mais casos de teste, você pode usar este programa Jelly .

Pitão, 42 bytes

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

Suíte de teste

Os últimos 4 bytes simplesmente executam a função na entrada.

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 bytes

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

O APL também +distribui por matrizes, mas de uma maneira diferente o suficiente para que isso realmente não possa ser usado. No entanto, há uma função interna de profundidade (≡ ).

Explicação:

• 1=≡⍺⍵:⍺+⍵: se as profundidades de ⍺ ⍵são zero (e, portanto, a profundidade ⍺ ⍵é 1), adicione-as.
• ∆←|≡¨⍺⍵: Tomar o absoluto da profundidade de ambos ⍺e ⍵e armazená-los em ∆. ( ≡fornece um valor negativo se nem todos os elementos tiverem a mesma profundidade.)
• =/∆: se eles tiverem a mesma profundidade:
  • ↓↑⍺⍵: preencha a matriz mais curta com zeros para corresponder à matriz mais longa
  • ⊃∇¨/: distribuir a função pelas duas matrizes
• </∆: se a profundidade de ⍺for menor que a de ⍵:
  • ⍺∘∇¨⍵: ligar ⍺e depois mapear sobre⍵
• ⍵∇⍺: se nada mais (por isso ⍵é mais profundo que ⍺), troque os argumentos e tente novamente.

Mathematica, 122 bytes

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

Define uma função recursiva fque calcula a soma. Utilizando a correspondência de padrões do Mathematica, essa função é composta de quatro definições separadas:

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

Se a profundidade de xfor maior que a de y, troque os argumentos para que apenas tenhamos de lidar com a distribuição em uma direção (o que podemos fazer, pois a adição é comutativa).

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

Se a profundidade xé menor thann a de y, substituir cada valor #no ycom f[x,#], que cuida da distribuição para os argumentos de profundidade desigual.

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

Caso contrário, se um argumento for uma lista (o que implica que o outro também seja uma lista, já que sabemos que eles têm a mesma profundidade), colocaremos os dois argumentos em uma lista, preenchê-los com o mesmo comprimento PadRight[..., Automatic](que simplesmente preenche um matriz irregular com zeros para torná-lo retangular) e, em seguida, use MapThreadpara aplicar faos pares correspondentes das duas listas.

E, finalmente, o caso base:

x_~f~y_=x+y

Se nenhum dos outros padrões corresponder, devemos estar tentando adicionar dois números, então fazemos isso.

Haskell, 150 bytes

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

Explicação

A primeira linha define um tipo de dados algébrico L, que é um Scalar (contendo um Int) ou um Vector (contendo uma lista de Ls, acessados ​​usando um gravador de registros v, que é uma função parcial L → [L]).

A segunda linha define a função de profundidade : a profundidade de um Vetor é uma mais a sua profundidade máxima. Eu prefiro S 0os valores no vetor, de modo que depth [] == 1 + maximum [depth (S 0)] == 1. A profundidade de "qualquer outra coisa" (um escalar) é 0.

A terceira linha define o caso base para !(a função de adição): a soma dos escalares é simplesmente um escalar.

A quinta linha define uma variante zipWith (!)que apenas seleciona elementos da lista mais longa quando um deles está vazio.

A quarta linha é dividida em três casos:

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

• Se a profundidade de xfor estritamente menor que a profundidade de y, mapeie (x!)os elementos de y. (O uso de vé garantido como válido, como d(y) ≥ 1.)

• Se a profundidade de xfor estritamente maior, inverta os argumentos e reinicie.

• Se a profundidade for igual, junte os argumentos (!). (O uso de vé garantido como válido, pois o caso d(x) = d(y) = 0foi tratado como um caso base.)

Casos de teste

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

Então show (lArg ! rArg) == "[[11,[21]],[[12,[22]],[13,[24]]]]".

Java, 802 794 754 746 bytes

Decidi aceitar @ Dennis ♦ para o desafio de operar com cordas "como último recurso" porque provavelmente era "muito complicado". Além disso, no pior idioma para jogar golfe.

As matrizes na entrada são separadas por vírgula, entre colchetes e sem espaço em branco.

Programa completo com funções agrupadas em uma classe e com casos de teste

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

Eu poderia porta isso para C ++ mais tarde, uma vez que é a outra língua que eu sei que não suporta matrizes irregulares, desde que eu sou certeza quase certo que vai ser mais curto do que esta resposta. Isso era principalmente uma prova de conceito, mas qualquer dica de golfe ainda seria apreciada!

-31 bytes de @ user902383, sugerindo o uso de um foreach sobre uma matriz de caracteres convertida e, em seguida, salvei um pouco mais de reorganizar os blocos if na parte final.

Python 2.7, 261 209 202 198 191 185 197 181 bytes

Solução trivial FGITW

EDIT: Claro que @Dennis vence

Agradecemos ao @LeakyNun por salvar 57 bytes com dicas sobre expressões lambda e 2 bytes entre colchetes desnecessários.

Obrigado a @Adnan por 4 bytes devido à sugestão de usar em typevez deisinstance

Graças a @Lynn por 7 bytes com -~emap

Obrigado a @FryAmTheEggman em z>=[]vez detype

+12 bytes para converter lambda em if else e corrigir um erro grave

-16 bytes graças a @Kevin Lau - não Kenny

Experimente online

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 bytes

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)

Teste em Ideone .

Como funciona

No Python 2, todos os números inteiros são menores que todos os dicionários, mas todas as listas são maiores. d calcula recursivamente a profundidade de t retornando 0 para números inteiros ou o máximo incrementado das profundidades de seus elementos e 0 .t+[0]evita que a lista vazia seja colocada em maiúsculas e minúsculas.

s calcula recursivamente a soma da geléia de x e y .

Se a profundidade de y excede x , s(y,x)chama s com argumentos trocados, certificando-se de que d (x) ≤ d (y) .

Se y tiver profundidade positiva, map(s,(x,[x]*len(y))[d(x)<d(y)],y)faça o seguinte.

• Se as profundidades de x e y coincidirem, ele será executado map(s,x,y), mapeando s sobre todos os elementos de x e os elementos correspondentes de y .

  No caso de listas de tamanhos diferentes, o mapa passará None como argumento esquerdo ou direito para elementos ausentes na lista mais curta.

• Se a profundidade de x for menor que a de y , ela será executada map(s,[x]*len(y),y), mapeando s (x, ·) sobre y .

Se y (e, portanto, x ) tiver profundidade 0 , (x or 0)+(y or 0)substitui argumentos falsos ( Nenhum ou 0 ) por zeros e retorna a soma dos números inteiros resultantes.

JavaScript (ES6), 152 bytes

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>

Ruby 2.3, 143 145 148 149 bytes

Ruby tem todas essas pequenas peculiaridades de como zipfunciona com matrizes de comprimento diferente e mapcom funções com vários argumentos, tornando isso muito divertido jogar golfe.

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

Julia, 113 bytes

~=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

Experimente online!

Como funciona

~=endof

cria um alias de 1 byte para endof , que retorna o comprimento de uma matriz.

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

define uma função de profundidade. A profundidade de t é zero se e somente se 0t == 0 . Caso contrário, t é uma matriz e sua profundidade é calculada como o máximo incrementado das profundidades de seus elementos e 0 . [t;0]anexa um 0 à matriz t , evitando assim a necessidade de criar um caso especial para a matriz vazia.

A soma interna de Julia + já se comporta como a soma de Jelly se um (ou ambos) de seus argumentos for um número inteiro. No entanto, a soma de duas matrizes ( + ) requer matrizes da mesma forma e até a soma vetorizada ( . + ) Requer matrizes que podem ser transmitidas para uma forma comum.

Redefinimos + para um par de matrizes via

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

Isso não afeta a definição de + para argumentos inteiro / inteiro, matriz / número inteiro ou número inteiro / matriz.

(!x,~x)>(!y,~y)lexicograficamente compara os pares de profundidades e comprimentos de ambos x e y . Se a profundidade de x exceder y , ou se a profundidade corresponder e o comprimento de x exceder y , y+xrecursivamente chamará + com argumentos trocados.

Caso contrário, !x<!ytesta se a profundidade de x é menor que a de y . Se for, map(t->x+t,y)mapeia x + · sobre y .

Se as profundidades coincidirem, ~x<~ytesta se x é menor que y . Se estiver, [x;0]+ychama recursivamente + após anexar um 0 ao argumento esquerdo.

Finalmente, se as profundidades e os comprimentos forem idênticos, x.+ymapeia + todos os elementos de x e os elementos correspondentes de y .