tło

Arytmetyczne atomy galaretki wektoryzują się automatycznie. W rzeczywistości, suma x + y jest dobrze określone, gdy x i y są liczbami lub nierównych tablice liczb. Kod źródłowy Jelly implementuje to zachowanie za pomocą ogólnego wektoryzatora, ale w przypadku tego wyzwania rozważymy tylko dodanie liczb całkowitych i zagnieżdżonych tablic liczb całkowitych.

Definicje

Zdefiniuj głębokość x jako 0, jeśli x jest liczbą całkowitą, jako 1, jeśli jest (być może pustą) płaską tablicą liczb całkowitych, i jako n + 1, jeśli zawiera co najmniej jeden element głębokości n i brak elementów głębokości k> n .

W ten sposób 1 ma głębokość 0 , [] i [1], a [1, 1] ma głębokość 1 , [[], []] i [[1], [1]] i [[1]] i [1 , []] ma głębokość 2 , [1, [1, [1]]] ma głębokość 3 itd.

Operacja x + y jest zdefiniowana w następujący sposób.

1. Jeśli x i y mają głębokość 0 , powrót ich sumę.

2. Jeśli x i y mają równe ale pozytywne głębokości, rekurencyjnie zastosować + do wszystkich elementów X i odpowiednich elementów y .

   Jeśli x i y mają różne długości, dodać ogon dłuższym tablicy w tablicy sum.

   Zwróć wynik.

3. Jeśli głębokość x jest ściśle mniejsza niż głębokość y , rekurencyjnie zastosuj + do x i wszystkich elementów y , i zwróć wynik.

   Zrobić odwrotnie, jeśli y „s głębokość jest ściśle mniejsze niż x ” s.

Rozważmy na przykład operację [1, [2, 3], [4]] + [[[10, 20], [30], 40, 50], 60] .

• Głębokość lewego argumentu wynosi 2 , podczas gdy głębokość prawego argumentu wynosi 3 , więc obliczamy [1, [2, 3], [4]] + [[10, 20], [30], 40, 50 ] i [1, [2, 3], [4]] + 60 .

  • [1, [2, 3], [4]] i [[10, 20], [30], 40, 50] mają głębokość 2 , więc obliczamy 1 + [10, 20] , [2, 3] + [30] i [4] + 40 .

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

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

      Zauważ, że 3 pozostaje nietknięte, ponieważ nie ma pasującego elementu.

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

    W pobliżu
    50 nie posiada pasujący element, a więc jest [[[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]] , co daje [61, [62, 63], [64]] .

• Ostateczny wynik to [[[11, 21], [32, 3], [44], 50], [61, [62, 63], [64]]] .

Zadanie

Napisz program lub funkcję, która pobiera na wejściu dwie liczby całkowite, dwie zagnieżdżone tablice liczb całkowitych lub ich kombinację i zwraca ich sumę, jak zdefiniowano powyżej.

Jeśli twój język ma wiele typów tablicowych (listy, krotki, wektory itp.), Możesz wybrać dowolny z nich dla swojej odpowiedzi. Typ zwracany musi być zgodny z typem argumentu.

Aby zapobiec nudnym i bezkonkurencyjnym rozwiązaniom, jeśli język ma dokładnie taką operację jako wbudowaną, nie możesz używać tego języka.

Wszystkie wbudowane wszystkie pozostałe języki są dozwolone. Jeśli Twój język na to pozwala, możesz przeładować i / lub zmienić definicję wbudowanego dodatku.

To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach.

Przypadki testowe

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

Aby wygenerować więcej przypadków testowych, możesz użyć tego programu Jelly .

Pyth, 42 bajty

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

Zestaw testowy

Ostatnie 4 bajty po prostu uruchamiają funkcję na wejściu.

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 bajty

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

APL-y + rozprowadza również tablice, ale na tyle inaczej, że tak naprawdę nie można tego użyć. Istnieje jednak wbudowana funkcja głębokości ( ≡).

Wyjaśnienie:

• 1=≡⍺⍵:⍺+⍵: jeśli głębokości ⍺ ⍵są równe zero (a zatem głębokość ⍺ ⍵wynosi 1), dodaj je.
• ∆←|≡¨⍺⍵: Wziąć bezwzględna głębokości zarówno ⍺i ⍵i przechowywanie ich w ∆. ( ≡daje wartość ujemną, jeśli nie wszystkie elementy mają tę samą głębokość).
• =/∆: jeśli mają taką samą głębokość:
  • ↓↑⍺⍵: wstaw najkrótszą tablicę zerami, aby dopasować dłuższą tablicę
  • ⊃∇¨/: rozłóż funkcję na obie tablice
• </∆: jeżeli głębokość ⍺jest mniejsza niż ⍵:
  • ⍺∘∇¨⍵: powiązanie, ⍺a następnie mapowanie⍵
• ⍵∇⍺: jeśli nic innego (więc nie ⍵jest głębsze niż ⍺), zamień argumenty i spróbuj ponownie.

Mathematica, 122 bajty

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

Definiuje funkcję rekurencyjną, fktóra oblicza sumę. Korzystając z dopasowania wzorca Mathematica, funkcja ta składa się z czterech oddzielnych definicji:

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

Jeśli głębokość xjest większa niż głębokość y, zamień argumenty, abyśmy musieli obsługiwać rozkład tylko w jednym kierunku (co możemy zrobić, ponieważ dodawanie jest przemienne).

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

Jeśli głębokość xjest mniejsza niż thann ywymienić każdą wartość #w yz f[x,#], która dba o dystrybucję do argumentów o różnej głębokości.

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

W przeciwnym razie, jeśli jeden argument jest listą (co oznacza, że ​​drugi również jest listą, ponieważ wiemy, że mają tę samą głębokość), umieszczamy oba argumenty na liście, dopełniamy je na tej samej długości PadRight[..., Automatic](co po prostu wypełnia poszarpana tablica z zerami, aby była prostokątna), a następnie użyj, MapThreadaby zastosować fdo odpowiednich par z dwóch list.

I wreszcie podstawowy przypadek:

x_~f~y_=x+y

Jeśli żaden z pozostałych wzorów nie pasuje, musimy próbować dodać dwie liczby, więc po prostu to robimy.

Haskell, 150 bajtów

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

Wyjaśnienie

Pierwszy wiersz definiuje algebraiczny typ danych L, którym jest albo Scalar (zawierający an Int) lub ector (zawierający Vlistę Ls, do której można uzyskać dostęp za pomocą rejestratora v, który jest funkcją częściową L → [L]).

Druga linia określa funkcję głębokości : głębokość Vwektora wynosi jeden plus jego maksymalna głębokość. Przechodzę S 0do wartości w wektorze, więc takdepth [] == 1 + maximum [depth (S 0)] == 1 . Głębokość „wszystkiego innego” (skalara) jest 0.

Trzecia linia określa przypadek podstawowy ! (funkcja dodawania): suma skalarów jest po prostu skalarem.

Piąta linia określa wariant zipWith (!) który po prostu wybiera elementy z najdłuższej listy, gdy jeden z nich jest pusty.

Czwarta linia jest podzielona na trzy przypadki:

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

• Jeśli głębokość xjest ściśle mniejsza niż głębokość y, odwzoruj (x!)elementy y. (Korzystanie z vgwarantuje, że jest ważne, jak d(y) ≥ 1.)

• Jeśli głębokość xjest ściśle większa, odwróć argumenty i uruchom ponownie.

• Jeśli ich głębokości są równe, spakuj argumenty razem z (!). ( vGwarantowane jest użycie opcji , ponieważ sprawa d(x) = d(y) = 0była rozpatrywana jako sprawa podstawowa).

Przypadki testowe

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

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

Java, 802 794 754 746 bajtów

Zdecydowałem się podjąć @ Dennis ♦ za wyzwanie działania na łańcuchach „w ostateczności”, ponieważ prawdopodobnie było to „zbyt skomplikowane”. Również w najgorszym języku do gry w golfa.

Tablice na wejściu są oddzielone przecinkami, otoczone nawiasami kwadratowymi i bez białych znaków.

Pełny program z funkcjami zawartymi w klasie i przypadkami testowymi

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

Mógłbym tego portu do C ++ później, ponieważ jest to drugi język wiem, że nie obsługuje macierze poszarpane, ponieważ jestem całkiem pewny, że niemal pewne, że będzie krótsza niż tej odpowiedzi. Był to głównie dowód koncepcji, ale wszelkie wskazówki dotyczące gry w golfa nadal będą mile widziane!

-31 bajtów od @ user902383 sugerujących użycie foreach zamiast przekonwertowanej tablicy znaków, a potem zaoszczędziłem trochę na przestawieniu bloków if w końcowej części.

Python 2.7, 261 209 202 198 191 185 197 181 bajtów

FGITW trywialne rozwiązanie

EDYCJA: Oczywiście @Dennis bije to

Dzięki @LeakyNun za zapisanie 57 bajtów ze wskazówkami na temat wyrażeń lambda i 2 bajty z niepotrzebnych nawiasów.

Dzięki @Adnan za 4 bajty z powodu sugestii użycia typezamiastisinstance

Dzięki @Lynn za 7 bajtów z -~imap

Dzięki @FryAmTheEggman za z>=[]zamiasttype

+12 bajtów, aby przekonwertować lambda na if i naprawić poważny błąd

-16 bajtów dzięki @Kevin Lau - nie Kenny

Wypróbuj 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 bajtów

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)

Przetestuj na Ideone .

Jak to działa

W Pythonie 2 wszystkie liczby całkowite są mniejsze niż wszystkie słowniki, ale wszystkie listy są większe. d rekurencyjnie oblicza głębokość t , zwracając 0 dla liczb całkowitych lub zwiększonego maksimum głębokości jej elementów i 0 .t+[0]unika się specjalnego umieszczania pustej listy.

s rekurencyjnie oblicza sumę galaretki x i y .

Jeżeli Y głębokość „S przekracza X ” s, s(y,x)rozmowy s , dzięki czemu z zamienionych argumentów, czy d (x) ≤ d (r) .

Gdyby y ma dodatnią głębokość, map(s,(x,[x]*len(y))[d(x)<d(y)],y)wykonuje następujące czynności.

• Jeśli głębokości x i y są zgodne, wykonuje się map(s,x,y), odwzorowując s na wszystkich elementach xi odpowiednich elementach y .

  W przypadku list o różnych długościach mapa przekaże None jako lewy lub prawy argument za brakujące elementy na krótszej liście.

• Jeśli głębokość x jest mniejsza niż y , wykonuje się map(s,[x]*len(y),y), odwzorowując s (x, ·) na y .

Jeśli y (a zatem x ) ma głębokość 0 , (x or 0)+(y or 0)zastępuje falsy argumenty ( Brak lub 0 ) z zer i zwraca sumę otrzymanych liczb całkowitych.

JavaScript (ES6), 152 bajty

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 bajtów

Ruby ma wszystkie te małe dziwactwa, jak zipdziała z tablicami o różnych długościach i mapfunkcjami wieloparumentowymi, co sprawia, że ​​gra w golfa jest przyjemnością.

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 bajtów

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

Wypróbuj online!

Jak to działa

~=endof

tworzy 1-bajtowy alias dla endof , który zwraca długość tablicy.

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

definiuje funkcję głębokości. Głębokość t wynosi zero wtedy i tylko wtedy, gdy 0t == 0 . Jeśli nie, t jest tablicą, a jego głębokość jest obliczana jako przyrostowe maksimum głębokości jej elementów i 0 . [t;0]dodaje 0 do tablicy t , unikając w ten sposób potrzeby specjalnego pustej tablicy.

Wbudowana suma Julii + już zachowuje się jak suma Jelly, jeśli jeden (lub oba) z jej argumentów jest liczbą całkowitą. Jednak suma dwóch tablic ( + ) wymaga tablic o tym samym kształcie, a nawet wektoryzowana suma ( . + ) Wymaga tablic, które mogą być nadawane do wspólnego kształtu.

Przedefiniowujemy + dla pary tablic za pośrednictwem

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

Nie ma to wpływu na definicję + dla argumentów liczba całkowita / liczba całkowita, tablica / liczba całkowita lub liczba całkowita / tablica.

(!x,~x)>(!y,~y)leksykograficznie porównuje pary głębokości i długości zarówno x, jak i y . Jeśli głębokość x przekracza y lub jeśli ich głębokość jest zgodna, a długość x przekracza y , y+xrekurencyjnie wywołuje + z zamienionymi argumentami.

W przeciwnym razie sprawdź, !x<!yczy głębokość x jest mniejsza niż y . Jeśli tak, map(t->x+t,y)odwzorowuje x + · na y .

Jeśli głębokości pasują, ~x<~ysprawdź, czy x jest krótszy niż y . Jeśli tak, [x;0]+yrekursywnie wywołuje + po dodaniu 0 do lewego argumentu.

Wreszcie, jeśli zarówno głębokości, jak i długości są identyczne, x.+yodwzorowuje + wszystkie elementy x i odpowiadające im elementy y .