_{Uwaga: Jest to numer 2 w serii wyzwań dotyczących manipulacji tablicami . Aby zobaczyć poprzednie wyzwanie, kliknij tutaj .}

Rozdzielanie list zagnieżdżonych

Aby oddzielić wartości na liście zagnieżdżonej, spłaszcz ją, a następnie zawiń każdą wartość, aby znajdowała się na tej samej głębokości zagnieżdżenia, co poprzednio.

To znaczy, ta lista:

[1, [2, 3], [4, 4, [5, 2], 1]]

Stanie się:

[1, [2], [3], [4], [4], [[5]], [[2]], [1]]

Wyzwanie

Twoim zadaniem jest napisanie programu, który pobierze dowolną zagnieżdżoną listę liczb całkowitych dodatnich (w granicach twojego języka) i wykona tę operację separacji.

Możesz przesłać funkcję, która przyjmuje listę jako argument, lub pełny program wykonujący operacje we / wy.

Ponieważ jest to kod-golf , wygrywa najkrótsza przesyłka (w bajtach)! *

_{* Standardowe luki w grze w golfa są zakazane. Znasz zasady.}

Przypadki testowe

Listy wejściowe zawsze będą zawierać liczby całkowite w standardowym rozmiarze całkowitym twojego języka. Aby uniknąć ograniczeń języków uniemożliwiających im konkurowanie, wartości nie będą zagnieżdżane na głębokościach większych niż 10.

Możesz założyć, że dane wejściowe nie będą miały pustych list podrzędnych: na przykład - [[5, []]]nie zostaną podane. Jednak główna lista może być pusta.

[]            ->  []

[[1, 2]]      ->  [[1], [2]]
[3, [4, 5]]   ->  [3, [4], [5]]
[3, [3, [3]]] ->  [3, [3], [[3]]]
[[6, [[7]]]]  ->  [[6], [[[7]]]]
[[5, 10], 11] ->  [[5], [10], 11]

Nie wahaj się zostawić komentarza, jeśli przegapiłem skrzynkę.

Przykład

Rzuciłem razem szybki (ungolfed) Pythonie 3 rozwiązanie jako przykład - można go przetestować na repl.it .

Brachylog , 16 bajtów

:{##:0&:ga|g}ac|

Wypróbuj online!

Wyjaśnienie

Example input: [1:[2:3]]

:{          }a     Apply the predicate below to each element of the list: [[1]:[[2]:[3]]]
              c    Concatenate: Output = [1:[2]:[3]]
               |   Or: Input = Output = []

  ##                 Input is a list: e.g. Input = [2:3]
    :0&              Call recursively the main predicate with this input: [2:3]
       :ga           Group each element in a list: Output = [[2]:[3]]
          |          Or (not a list): e.g. Input = 1
           g         Group into a list: Output = [1]

Mathematica, 24 21 bajtów

##&@@List/@#0/@#&/@#&

lub jeden z tych:

##&@@List/@#&/@#0/@#&
##&@@List@*#0/@#&/@#&
##&@@List/@#&@*#0/@#&

Wyjaśnienie

Jest to tak krótkie, że jest to w zasadzie rekurencja, która nie wymaga jednoznacznego przypadku podstawowego.

Jest tu dużo cukru syntaktycznego, więc zacznijmy od odkrycia tego. &oznacza pozostawioną po niej nienazwaną funkcję, której argument zapisano jako #. Wewnątrz tej funkcji #0odnosi się do samej funkcji, która umożliwia pisanie nienazwanych funkcji rekurencyjnych. Ale zacznijmy od nadania funkcji wewnętrznej nazwy i wyciągnięcia jej:

f[x_] := ##& @@ List /@ f /@ x
f /@ # &

Innym ważnym cukrem syntaktycznym f/@xjest skrót, Map[f, x]który wywołuje fkażdy element x. Powodem, dla którego f[x_] := ... f /@ xnie prowadzi do nieskończonej rekurencji jest to, że mapowanie czegoś na atomie pozostawia atom bez zmian bez faktycznego wywoływania funkcji. Dlatego nie musimy jawnie sprawdzać przypadku podstawowego (bieżącym elementem jest liczba całkowita).

Więc funkcja fnajpierw powraca do najgłębszej listy w środku x, w którym to momencie f/@staje się brakiem operacji . Następnie nazywamy użycie ##& @@ List /@w tym celu. Mapowanie Listlisty po prostu otacza każdy element osobną listą, więc {1, 2, 3}staje się {{1}, {2}, {3}}. Następnie stosujemy się ##& do niego, co oznacza, że ​​głowa (tj. Zewnętrzna lista) zostaje zastąpiona przez ##&, więc zmienia się w ##&[{1}, {2}, {3}]. Ale ##&po prostu zwraca argumenty jako Sequence(które można traktować jako niepakowaną listę lub rodzaj operatora „splat” w innych językach).

Tak więc ##& @@ List /@zamienia listę {1, 2, 3}w {1}, {2}, {3}(coś w rodzaju, że ostatnia rzecz jest rzeczywiście owinięta w głowę Sequence, ale znika, gdy tylko użyjemy tej wartości w dowolnym miejscu).

To pozostawia pytanie, dlaczego fsamo to nie jest rozwiązaniem tego wyzwania. Problem polega na tym, że najbardziej zewnętrzna lista powinna być traktowana inaczej. Jeśli mamy wkład {{1, 2}, {3, 4}}, chcemy, {{1}, {2}, {3}, {4}}a nie chcemy {{1}}, {{2}}, {{3}}, {{4}}. Moje oryginalne rozwiązanie naprawiło to, przekazując końcowy wynik jako listę argumentów, Joinktóre przywróciłyby zewnętrzny poziom list, ale ten po prostu pomija zewnętrzny poziom, używając f siebie w mapie na wyjściu. Dlatego fjest stosowany tylko do poszczególnych elementów listy najbardziej oddalonych i nigdy nie dotyka tej listy.

Jeśli chodzi o pozostałe trzy rozwiązania, pierwsze z nich po prostu stosuje rekurencję, poza fktórą równie dobrze działa. Pozostałe dwa rozwiązania pozwalają uniknąć powtarzanej Mapoperacji, najpierw łącząc dwie funkcje, a następnie odwzorowując wynik tylko raz.

J , 19 18 bajtów

(<@]/@,~>)S:0 1{::

Jest to anonimowy czasownik, który przyjmuje i zwraca tablice w ramkach, które są (raczej nieporęczną) wersją zagnieżdżonych tablic. Zobacz, jak przejdzie wszystkie testy.

Wyjaśnienie

Wykorzystuje to nieco egzotyczne operacje {::( mapa ) i S:( rozkładanie ), które działają na tablicach pudełkowych. {::zastępuje każdy liść ścieżką pudełkową do tego liścia. S:stosuje dany czasownik na danej głębokości zagnieżdżenia, a następnie dzieli wyniki na tablicę.

(<@]/@,~>)S:0 1{::  Input is y.
(        )          Let's look at this verb first.
        >           Open the right argument,
      ,~            append the left argument to it,
    /               then reduce by
 <@]                boxing. This puts the left argument into as many nested boxes
                    as the right argument is long.
                    This verb is applied to y
               {::  and its map
            0 1     at levels 0 and 1.
                    This means that each leaf of y is paired with its path,
                    whose length happens to be the nesting depth of y,
                    and the auxiliary verb is applied to them.
          S:        The results are spread into an array.

R, 199 bajtów

function(l){y=unlist(l);f=function(x,d=0){lapply(x,function(y){if(class(y)=='list'){f(y,d=d+1)}else{d}})};d=unlist(f(l));lapply(1:length(d),function(w){q=y[w];if(d[w]){for(i in 1:d[w])q=list(q)};q})}

To pytanie było trudne. Listy R są trochę dziwne i absolutnie nie jest łatwo zapętlić wszystkie elementy list podrzędnych. Nie jest również łatwe określenie głębokości tej listy. Następnie wyzwaniem staje się odtworzenie listy z oddzielonymi wszystkimi elementami, dlatego potrzebujemy również sposobu na adaptacyjne utworzenie listy o określonej głębokości.

Rozwiązanie składa się z dwóch dużych części. Funkcja rekurencyjna, która zapętla wszystkie listy i rejestruje głębokość:

  f=function(x,d=0){
    lapply(x,function(y){
      if(class(y)=='list'){
        f(y,d=d+1)
      } else {
        d
      }})
  }

Gdy mamy unlist(l)zapisane głębokości każdego wpisu wektora , ddomyślnie tworzymy listę poprzez lapplyi wypełniamy ją następującą funkcją:

  lapply(1:length(d),function(w){
    q=y[w]
    if(d[w]){
      for(i in 1:d[w]){
        q=list(q)
      }
    }
    q
  })

W tym wywołaniu Apply tworzymy obiekt qo wartości wpisu na liście, sprawdzamy jego głębokość i sprawdzamy, czy jest on niezerowy. Jeśli wynosi zero, możemy po prostu zostawić to jako wartość liczbową. Jeśli jest niezerowa, musimy zagnieździć ją na takiej liczbie list. Więc wywołujemy dczasy pętli for i wielokrotnie dzwonimy q=list(q).

lapplynastępnie umieszcza wszystkie te wartości qna liście, tworząc pożądany wynik.

Kompletny program z odpowiednimi odstępami i takimi:

function(our.list){
  values <- unlist(our.list)
  f <- function(part.list, depth = 0){
    lapply(part.list, function(y){
      if(class(y)=='list'){
        f(y, depth <- depth + 1)
      } else {
        return(depth)
      }})
  }
  depths <- unlist(f(our.list))
  new.list <- lapply(1:length(depths), function(w){
    q <- values[w]
    if(depths[w] != 0){
      for(i in 1:depths[w]){
        q <- list(q)
      }
    }
    return(q)
  })
  return(new.list)
}

Retina , 34 bajty

+`(.(?>()\[|(?<-2>)]|.)+)\2,
$1],[

Wypróbuj online!

C (gcc), 147 bajtów

d=0,l,i;
P(n,c){for(;n--;)putchar(c);}
main(c){for(;~(c=getchar());l=i)i=isdigit(c),P((l<i)*d,91),P(i,c),P((l>i)*d,93),P(l>i,32),d+=(92-c)*(c>90);}

Przykładowe dane wejściowe:

1 [23 3] [40 4 [5 2] 1]

Przykładowe dane wyjściowe:

1 [23] [3] [40] [4] [[5]] [[2]] [1]

ułożone w stos , niekonkurencyjne, 25 bajtów

{e d:e$wrap d 1-*}cellmap

Jest to funkcja polegająca na modyfikacji górnego elementu stosu. Jeśli chcesz skorzystać z funkcji bonafide, po prostu dodaj [i ]na początku i na końcu.Wypróbuj tutaj!

Oto czytelna wersja:

{ arr :
  arr { ele depth :
    ele   $wrap depth 1- * (* execute wrap n times, according to the depth *)
  } cellmap (* apply to each cell, then collect the results in an array *)
} @:a2
(1 (2 3) (4 4 (5 2) 1)) a2 out

Przypadek testowy:

(1 (2 3) (4 4 (5 2) 1))    (* arg on TOS *)
{e d:e$wrap d 1-*}cellmap
out                        (* display TOS *)

Wyjście bez nowych linii:

(1 (2) (3) (4) (4) ((5)) ((2)) (1))

PHP, 101 94 bajtów

zapisano 1 bajt dzięki @Christoph, zapisano kolejne 6 zainspirowanych tym.

function s($a){foreach($a as$b)if($b[0])foreach(s($b)as$c)$r[]=[$c];else$r[]=$b;return$r?:[];}

funkcja rekurencyjna, całkiem prosta

awaria

function s($a)
{
    foreach($a as$b)                // loop through array
        if($b[0])                       // if element is array
            foreach(s($b)as$c)$r[]=[$c];    // append separated elements to result
        else$r[]=$b;                    // else append element to result
    return$r?:[];                   // return result, empty array for empty input
}

Python 2, 122 106 bajtów

Całkiem okropny wynik, po prostu prosta implementacja.

Dzięki @Zachary T za pomoc w oszczędzaniu 16 bajtów!

def x(l,a=[],d=0):
 n=lambda b:b and[n(b-1)]or l
 if'['in`l`:[x(e,a,d+1)for e in l];return a
 else:a+=n(d)

Zadzwoń xz jednym argumentem, aby uruchomić. Z jakiegoś powodu można go uruchomić tylko raz.

JavaScript (Firefox 30-57), 53 bajty

f=a=>[for(e of a)for(d of e.map?f(e):[e])e.map?[d]:d]

Najlepsza dotychczasowa odpowiedź na ES6 to 76 bajtów:

f=(a,r=[],d=0)=>a.map(e=>e.map?f(e,r,d+1):r.push((n=d=>d?[n(d-1)]:e)(d)))&&r

Pyth - 29 bajtów

.b]FYt-F/LN`[)PsM._:`Q"\d"3.n

Pakiet testowy .

Perl 6 , 60 47 bajtów

sub f{[$_~~List??|([$_] for .&f)!!$_ for |$^a]}

( Wypróbuj online. )

Wyjaśnienie:

1. [... for |$^a]: Iteruj po tablicy wejściowej i stwórz z niej nową tablicę.
2. $_ ~~ List ?? ... !! ...: Dla każdego elementu sprawdź, czy sam jest tablicą.
3. |([$_] for .&f): Jeśli element jest tablicą, zastosuj do niego rekurencyjnie funkcję, iteruj po elementach nowej tablicy zwróconej z tego wywołania rekurencyjnego, zawiń każdy element we własną tablicę i wsuń je na zewnętrzną listę.
4. $_: Jeśli element nie jest tablicą, przekaż go takim, jaki jest.

Haskell, 71 bajtów

data L=N Int|C[L] 
d#C l=((C .pure.d)#)=<<l
d#n=[d n]
f(C l)=C$(id#)=<<l

Znów muszę zdefiniować własny typ listy, ponieważ list tubylców Haskella nie można dowolnie zagnieżdżać. Ten nowy typ Lmoże zostać zwrócony z funkcji, ale nie może być domyślnie drukowany, więc aby zobaczyć wynik, definiuję showinstancję dla L:

instance Show L where
  show (N n)=show n
  show (C l)=show l

Teraz możemy wykonać test w REPL:

*Main> f $ C[N 1, C[N 2, N 3], C[N 4, N 4, C[N 5, N 2], N 1]]
[1,[2],[3],[4],[4],[[5]],[[2]],[1]]

*Main> f $ C[C[N 6, C[C[N 7]]]]
[[6],[[[7]]]]

Jak to działa: prosta rekurencja, która przechodzi poziom zagnieżdżenia jako funkcja Ckonstruktorów. Zaczynamy od funkcji tożsamości idi ilekroć jest lista (-> dopasowanie do wzorca d#C l=), dodajemy kolejną warstwę C(-> C .pure.d) do rekurencyjnego wywołania #wszystkich elementów listy. Jeśli napotkamy liczbę, po prostu zastosujemy do niej funkcję poziomu zagnieżdżenia d.

APL (Dyalog) , 44 bajty *

Anonimowa ukryta funkcja prefiksu. Pobiera zagnieżdżoną listę APL jako argument i zwraca zagnieżdżoną tablicę APL.

∊{⊃⊂⍣⍵,⍺}¨{⊃¨(j∊⎕D)⊆+\-⌿'[]'∘.=j←⎕JSON⍵}

Wypróbuj online!

{… } Zastosuj następującą jawną funkcję, w której argument jest reprezentowany przez⍵ :

 ⎕JSON⍵ przekonwertować argument na JSON

 j← przechowywać j

 '[]'∘.= tabela, w której jrówna się nawiasy otwierające (górny rząd) i zamykające (dolny rząd)

 -⌿ górny rząd minus dolny rząd (zmniejszenie różnicy pionowej)

 +\ suma skumulowana (daje to poziom zagnieżdżenia dla każdej postaci)

 (… )⊆ Partycja, rozpoczynanie nowej partycji za każdym razem, gdy 1 nie jest poprzedzony 1 w…

  j∊⎕D gdzie każda postać jjest członkiem zbioru D. igits

 ⊃¨ wybierz pierwszy z nich (daje to poziom zagnieżdżenia na liczbę wielocyfrową)

∊{… }¨ Zastosuj następującą funkcję do każdego poziomu zagnieżdżenia ( ⍵), używając odpowiedniego elementu z ϵ nlistowanego (spłaszczonego) argumentu jako lewego argumentu (⍺ ):

 ,⍺ ravel (listify) liczbę (ponieważ skalary nie mogą być zamknięte)

 ⊂⍣⍵ ująć ⍵ czasy

 ⊃ ujawnij (ponieważ sama najbardziej wewnętrzna lista jest załącznikiem)

^{* Korzystanie Dyalog Classic z ⎕ML←3(domyślnie w wielu systemach), zastępując ⊂na ⊆i ↑na ⊃. Tio!}