Jam no agrega así

16

Antecedentes

Los átomos aritméticos de Jelly se vectorizan automáticamente. De hecho, x + y está bien definido cuando x e y son números o matrices desiguales de números. El código fuente de Jelly implementa este comportamiento usando un vectorizador genérico, pero para este desafío, solo consideraremos la adición de enteros y matrices de enteros anidados.

Definiciones

Defina la profundidad de x como 0 si x es un número entero, como 1 si es un conjunto plano (posiblemente vacío) de enteros, y como n + 1 si contiene al menos un elemento de profundidad n y ningún elemento de profundidad k> n .

De esta manera, 1 tiene profundidad 0 , [] y [1] y [1, 1] tienen profundidad 1 , [[], []] y [[1], [1]] y [[1]] y [1 , []] tiene profundidad 2 , [1, [1, [1]]] tiene profundidad 3 , etc.

La operación x + y se define de la siguiente manera.

  1. Si x e y tienen profundidad 0 , devuelve su suma.

  2. Si X y Y tienen profundidades iguales pero positivos, aplicar de forma recursiva + a todos los artículos de x y los artículos correspondientes de y .

    Si x y y tienen diferentes longitudes, añadir la cola de la matriz más tiempo para la matriz de sumas.

    Devuelve el resultado.

  3. Si la profundidad de x es estrictamente menor que la profundidad de y , aplique recursivamente + a x y todos los elementos de y , y devuelva el resultado.

    Hacer lo contrario, si Y 's profundidad es estrictamente menor que x ' s.

Por ejemplo, considere la operación [1, [2, 3], [4]] + [[[10, 20], [30], 40, 50], 60] .

  • La profundidad del argumento izquierdo es 2 , mientras que la profundidad del argumento derecho es 3 , entonces calculamos [1, [2, 3], [4]] + [[10, 20], [30], 40, 50 ] y [1, [2, 3], [4]] + 60 .

    • [1, [2, 3], [4]] y [[10, 20], [30], 40, 50] tienen profundidad 2 , por lo que calculamos 1 + [10, 20] , [2, 3] + [30] y [4] + 40 .

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

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

        Tenga en cuenta que 3 permanece intacto, ya que no tiene un elemento coincidente.

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


      50 no tiene un elemento de adaptación, por lo que el resultado es [[[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]] , lo que resulta en [61, [62, 63], [64]] .

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

Tarea

Escriba un programa o una función que tome dos enteros, dos matrices anidadas de enteros o una combinación de los mismos como entrada y devuelva su suma, como se definió anteriormente.

Si su idioma tiene múltiples tipos de matriz (listas, tuplas, vectores, etc.), puede elegir cualquiera de ellos para su respuesta. El tipo de retorno debe coincidir con el tipo de argumento.

Para evitar soluciones aburridas e inmejorables, si un idioma tiene esta operación exacta como una función incorporada, no puede usar ese idioma.

Todos los elementos integrados de todos los demás idiomas están permitidos. Si su idioma de elección lo permite, puede sobrecargar y / o redefinir la adición incorporada.

Este es el , por lo que gana el código más corto en bytes.

Casos de prueba

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 generar más casos de prueba, puede usar este programa Jelly .

Dennis
fuente
¿Qué pasa si nuestro idioma no admite matrices irregulares? ¿Se nos permite reestructurar la entrada o debemos implementar matrices irregulares? ¿O tal vez solo use un idioma diferente?
millas
¿Qué quieres decir con reestructurar la entrada ?
Dennis
Al pensar más, me doy cuenta de que no funcionaría reestructurar la entrada, pero de todos modos resumiré lo que quise decir antes. Pensé en usar un valor de relleno para rellenar, lo que eliminaría algo de trabajo pero también crearía un problema diferente (probablemente diferente de su pregunta prevista), pero ahora me doy cuenta de que sus casos de prueba también incluyen números negativos.
millas
Las matrices también pueden ser heterogéneas, por lo que los valores de relleno no serían suficientes para hacerlas rectangulares. Como último recurso, siempre existe la opción de operar con cadenas, pero eso probablemente sea demasiado complicado.
Dennis
3
¡Hola, buen título! ... ahora que Google me ayudó a conseguirlo :-)
Luis Mendo

Respuestas:

3

Pyth, 42 bytes

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

Banco de pruebas

Los últimos 4 bytes simplemente ejecutan la función en la 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.
isaacg
fuente
7

APL, 44 bytes

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

APL también se +distribuye en matrices, pero de una manera lo suficientemente diferente como para que esto realmente no se pueda usar. Sin embargo, hay una función de profundidad incorporada ( ).

Explicación:

  • 1=≡⍺⍵:⍺+⍵: si las profundidades de son ambas cero (y por lo tanto la profundidad de ⍺ ⍵es 1), agréguelas
  • ∆←|≡¨⍺⍵: Tomar el absoluto de la profundidad de ambos y y almacenarlos en . ( da un valor negativo si no todos los elementos tienen la misma profundidad).
  • =/∆: si tienen la misma profundidad:
    • ↓↑⍺⍵: rellena la matriz más corta con ceros para que coincida con la matriz más larga
    • ⊃∇¨/: distribuye la función en ambas matrices
  • </∆: si la profundidad de es menor que la de :
    • ⍺∘∇¨⍵: enlazar y luego mapear
  • ⍵∇⍺: si nada más ( es más profundo que ), intercambie los argumentos e intente nuevamente.
marinus
fuente
3
A veces creo que sé APL bien. Entonces veo una obra maestra como esta y me doy cuenta de que apenas la conozco.
Alex A.
¿Los caracteres APL cuentan como bytes realmente?
metalim
@metalim APL tiene páginas de códigos heredadas que son anteriores a Unicode por algunas décadas. En esos, cada carácter es un solo byte.
Dennis
Entonces, el tipo de codificación debe proporcionarse con una solución. Solo OMI.
metalim
@metalim agregué un enlace.
Adám
5

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 una función recursiva fque calcula la suma. Haciendo uso de la coincidencia de patrones de Mathematica, esta función se compone de cuatro definiciones separadas:

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

Si la profundidad de xes mayor que la de y, intercambie los argumentos para que solo tengamos que manejar la distribución en una dirección (lo que podemos hacer, ya que la suma es conmutativa).

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

Si la profundidad de xes menos thann la de y, reemplazar cada valor #en ycon f[x,#], que se encarga de la distribución para los argumentos de profundidad desigual.

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

De lo contrario, si un argumento es una lista (lo que implica que el otro también es una lista, ya que sabemos que tienen la misma profundidad), colocamos ambos argumentos en una lista, los rellenamos con la misma longitud PadRight[..., Automatic](que simplemente llena un matriz irregular con ceros para hacerlo rectangular), y luego usar MapThreadpara aplicar fa los pares correspondientes de las dos listas.

Y finalmente, el caso base:

x_~f~y_=x+y

Si ninguno de los otros patrones coincide, debemos tratar de sumar dos números, así que solo hacemos eso.

Martin Ender
fuente
5

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

Explicación

La primera línea define un tipo de datos algebraicos L, que es un Scalar (que contiene un Int) o un Vector (que contiene una lista de Ls, al que se accede mediante un captador de registros v, que es una función parcialL → [L] ).

La segunda línea define la función de profundidad : la profundidad de un Vector es uno más su profundidad máxima. Antepongo S 0los valores en el vector, de modo que depth [] == 1 + maximum [depth (S 0)] == 1. La profundidad de "cualquier otra cosa" (un escalar) es0 .

La tercera línea define el caso base para !(la función de suma): la suma de escalares es simplemente un escalar.

La quinta línea define una variante de zipWith (!) que solo selecciona elementos de la lista más larga cuando uno de ellos está vacío.

La cuarta línea se divide en tres casos:

x!y | d x<d y = V$(x!)<$>v y
    | d x>d y = y!x
    | True    = V$v x#v y
  • Si la profundidad de xes estrictamente menor que la profundidad de y, mapee (x!)sobre los elementos de y. (El uso de vestá garantizado como válido, como d(y) ≥ 1.)

  • Si la profundidad de xes estrictamente mayor, voltee los argumentos y reinicie.

  • Si sus profundidades son iguales, junta los argumentos con (!). (Se vgarantiza que el uso de es válido, ya que el caso d(x) = d(y) = 0se trató como un caso base).

Casos de prueba

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

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

Lynn
fuente
También lo arreglé también ^^ (había cambiado las líneas por legibilidad, pero lo hice de la manera incorrecta ...) Esto importse debe a que Ideone tiene un viejo compilador Haskell. Las versiones modernas de GHC ponen <$>en Prelude, por lo que no es necesario importar Control.Applicativepara usarlo en estos días.
Lynn
Demasiadas ediciones al mismo tiempo que mis otras acciones: P Y claro, parece estar bien ahora, pero me parece bastante extraño que eso cause un error de compilación. ¿Todos los bits de coincidencia de patrones de una función tienen que ser consecutivos?
FryAmTheEggman
Eso es exactamente correcto.
Lynn
Muy bien, gracias por toda su ayuda :) "Algún día aprenderé este idioma" - FryAmTheEggman hace 7 años.
FryAmTheEggman
4

Java, 802 794 754 746 bytes

Decidí aceptar a @ Dennis ♦ para el desafío de operar con cuerdas "como último recurso" porque probablemente era "demasiado complicado". Además, en el peor idioma para jugar al golf.

Las matrices en la entrada están separadas por comas, rodeadas con corchetes y sin espacios en blanco.

Programa completo con funciones incluidas en una clase y con casos de prueba.

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

Yo podría puerto esta a C ++ más adelante ya que es el otro idioma Sé que no es compatible con matrices irregulares, ya que estoy bastante seguro de que casi seguro que va a ser más corta que esta respuesta. Esto fue principalmente una prueba de concepto, ¡pero cualquier consejo de golf aún sería apreciado!

-31 bytes de @ user902383 sugiriendo usar un foreach sobre una matriz de caracteres convertida, y luego ahorré un poco más de reorganizar los bloques if en la parte final.

Tinta de valor
fuente
Eso es impresionante.
Dennis
Creo que si reemplaza sus bucles con una matriz de caracteres de bucle foreach obtenida de una cadena, podría ahorrar una gran cantidad de bytes.
user902383
1
Errr ... Java admite matrices irregulares; No estoy seguro de lo que quieres decir con eso. Uso Object[], que contiene anidados Object[]o Integer. O simplemente Lista no genérica.
Robert Fraser
4

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

Solución trivial FGITW

EDITAR: Por supuesto, @Dennis lo supera

Gracias a @LeakyNun por guardar 57 bytes con consejos sobre expresiones lambda y 2 bytes de paréntesis innecesarios.

Gracias a @Adnan por 4 bytes debido a la sugerencia de usar en typelugar deisinstance

Gracias a @Lynn por 7 bytes con -~ymap

Gracias a @FryAmTheEggman por en z>=[]lugar detype

+12 bytes para convertir lambda a if else y corregir un error mayor

-16 bytes gracias a @Kevin Lau - no Kenny

Pruébalo en línea

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]
Azul
fuente
Es aún más corto cambiar a Python 2.7 y escribirz==[]or`z`>']'and ...
Lynn
Además, creo que reemplazar max(d(a)+1for a in z)con -~max(d(a)for a in z)guardar un byte (porque puede eliminar el espacio antes max). Que es entonces justo -~max(map(d,z)).
Lynn
El cambio a Python 2 ahorra aún más en el que se puede cambiar [p(a,b)for a,b in zip(x,y)]en map(p,x,y). Todavía puede hacer esto en 3 pero necesita agregar una llamada list. Creo que también podrías mejorar la sugerencia de Lynn de ser z>=[]. Sin relación, también debería poder intercambiar el typeorden de comparación para ahorrar un espacio.
FryAmTheEggman
Err, quise decir or`z`>'[', por supuesto, pero ya no puedo cambiar mi comentario. Pero, de hecho, ¡ z>[]es aún más corto (el ==caso ya está manejado)!
Lynn
El mapa @FryAmTheEggman no funciona cuando las listas son de diferentes tamaños; zip truncado correctamente. Voy a actualizar con la lista de verificación aunque
Azul
3

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)

Pruébalo en Ideone .

Cómo funciona

En Python 2, todos los enteros son menores que todos los diccionarios, pero todas las listas son mayores. d calcula recursivamente la profundidad de t devolviendo 0 para enteros o el máximo incrementado de las profundidades de sus elementos y 0 .t+[0]evita el uso de mayúsculas especiales en la lista vacía.

s calcula recursivamente la suma Jelly de x e y .

Si Y 'profundidad s excede x ' s, s(y,x)llamadas s con argumentos intercambiados, asegurándose de que d (x) ≤ d (y) .

Si y tiene profundidad positiva, map(s,(x,[x]*len(y))[d(x)<d(y)],y)hace lo siguiente.

  • Si las profundidades de x e y coinciden, se ejecuta map(s,x,y), asignando s sobre todos los elementos de x y los elementos correspondientes de y .

    En el caso de listas de diferentes longitudes, el mapa pasará Ninguno como argumento izquierdo o derecho para los elementos que faltan en la lista más corta.

  • Si la profundidad de x es menor que la de y , se ejecuta map(s,[x]*len(y),y), asignando s (x, ·) sobre y .

Si y (y, por lo tanto, x ) tiene profundidad 0 , (x or 0)+(y or 0)reemplaza los argumentos falsos ( Ninguno o 0 ) con ceros y devuelve la suma de los enteros resultantes.

Dennis
fuente
1

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>

Neil
fuente
1

Rubí 2,3, 143 145 148 149 bytes

Ruby tiene todas estas pequeñas peculiaridades sobre cómo zipfunciona con matrices de diferentes longitudes y mapcon funciones de múltiples argumentos, lo que hace que sea bastante divertido jugar golf.

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]]}
Tinta de valor
fuente
Eso es muy interesante: nunca antes había visto ese error para esta función. Todavía reparé algunas cosas debido a otros errores ahora, pero aparte de eso, funciona para mí (pero aún falla en ideone). Creo que es porque ideone ejecuta 2.1 y tengo 2.3, entonces quizás 2.1 no puede simplementemap en una función de dos argumentos de la forma en que la configuré al final. Aquí hay una versión editada para 2.1 que funciona que ajusta la mapllamada al final para que funcione. ideone.com/q1jqTA
Value Ink
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

Pruébalo en línea!

Cómo funciona

~=endof

crea un alias de 1 byte para endof , que devuelve la longitud de una matriz.

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

define una función de profundidad. La profundidad de t es cero si y solo si 0t == 0 . Si no, t es una matriz, y su profundidad se calcula como el máximo incrementado de las profundidades de sus elementos y 0 . [t;0]agrega un 0 a la matriz t , evitando así la necesidad de poner en especial la matriz vacía.

La suma incorporada de Julia + ya se comporta como la suma de Jelly si cualquiera (o ambos) de sus argumentos es un número entero. Sin embargo, la suma de dos matrices ( + ) requiere matrices de la misma forma, e incluso la suma vectorizada ( . + ) Requiere matrices que pueden transmitirse a una forma común.

Redefinimos + para un par de matrices a través de

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

Esto no afecta la definición de + para los argumentos de entero / entero, matriz / entero o entero / matriz.

(!x,~x)>(!y,~y)compara lexicográficamente los pares de profundidades y longitudes de x e y . Si la profundidad de x excede la de y , o si su profundidad coincide y la longitud de x excede y ' s, y+xllama recursivamente + con argumentos intercambiados.

De lo contrario, !x<!ycomprueba si la profundidad de x es menor que la de y . Si esto es,map(t->x+t,y) asigna x + · sobre y .

Si las profundidades coinciden, ~x<~ycomprueba si x es más corto que y . Si esto es,[x;0]+y recursivamente llama a + después de agregar un 0 al argumento izquierdo.

Finalmente, si ambas profundidades y longitudes son idénticas, x.+yasigna + sobre todos los elementos de x y los elementos correspondientes de y .

Dennis
fuente