Eine Reihe von Herausforderungen # 2: Trennen Sie eine verschachtelte Reihe

36

Hinweis: Dies ist die Nummer 2 in einer Reihe von . Für die vorherige Herausforderung klicken Sie hier .

Geschachtelte Listen trennen

Um Werte in einer verschachtelten Liste zu trennen, reduzieren Sie diese und schließen Sie jeden Wert so ab, dass er dieselbe verschachtelte Tiefe aufweist wie zuvor.

Das heißt, diese Liste:

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

Würde werden:

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

Die Herausforderung

Ihre Aufgabe ist es, ein Programm zu schreiben, das eine verschachtelte Liste positiver Ganzzahlen (innerhalb der Grenzen Ihrer Sprache) verwendet und diese Trennoperation ausführt.

Sie können eine Funktion übergeben, die die Liste als Argument verwendet, oder ein vollständiges Programm, das E / A ausführt.

Da dies , gewinnt die kürzeste Einsendung (in Bytes)! *

* Standard-Golflöcher sind verboten. Sie kennen die Übung.


Testfälle

Eingabelisten enthalten immer nur Ganzzahlen in der Standard-Ganzzahlgröße Ihrer Sprache. Um zu vermeiden, dass die Einschränkungen der Sprachen den Wettbewerb behindern, werden die Werte nicht in Tiefen von mehr als 10 verschachtelt.

Sie können davon ausgehen, dass die Eingabe keine leeren Unterlisten enthält: Zum Beispiel - [[5, []]]wird nicht angegeben. Die Hauptliste könnte jedoch leer sein.

[]            ->  []

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

Zögern Sie nicht, einen Kommentar zu hinterlassen, wenn ich einen Eckfall verpasst habe.

Beispiel

Ich habe eine schnelle (ungolfed) Python 3-Lösung als Beispiel zusammengestellt - Sie können sie auf repl.it testen .

FlipTack
quelle
Fügen Sie einen Testfall mit mehr als einstelligen Zahlen für stringbasierte Antworten hinzu.
Orlp
@orlp gute Idee.
FlipTack
2
Können wir eine bestimmte maximale Tiefe annehmen? Sagen wir, 16?
Orlp
@orlp Ich sage ja, die maximal verschachtelte Tiefe beträgt 10, da ich mehr an Ihrem Algorithmus und Ihrer Methodenausführung als an den Einschränkungen Ihrer Sprache interessiert bin. Aktualisiert den Thread jetzt.
FlipTack
Darf ich als String ausgeben?
Rohan Jhunjhunwala

Antworten:

4

Brachylog , 16 Bytes

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

Probieren Sie es online!

Erläuterung

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]
Tödlich
quelle
Was macht das ZArgument auf TIO? Ohne es scheint dies mit true / false auszugeben, was es so erscheinen lässt, als ob Zes in der Byteanzahl notwendig ist.
FlipTack
@FlipTack Zteilt Brachylog mit, dass das Ausgabeargument eine Variable ist. Dies ist diese Variable, die mit der resultierenden Ausgabe vereinheitlicht wird. Wenn Sie es entfernen, wird Brachylog mitgeteilt, dass es sich bei der Ausgabe um eine anonyme Variable handelt. Stattdessen wird gedruckt, ob das Hauptprädikat erfolgreich ist oder fehlschlägt. Dies ist dasselbe wie in Prolog, wo das Ergebnis in eine Variable "geschrieben" wird.
Fatalize
Ok :) nette Antwort!
FlipTack
19

Mathematica, 24 21 Bytes

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

oder eines davon:

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

Erläuterung

Der Grund dafür ist, dass es sich im Grunde genommen um eine Rekursion handelt, für die kein expliziter Basisfall erforderlich ist.

Hier ist viel syntaktischer Zucker, also fangen wir damit an, dies zu beseitigen. &bezeichnet eine unbenannte davon übrig gebliebene Funktion, deren Argument als geschrieben ist #. Innerhalb dieser Funktion #0bezieht sich auf die Funktion selbst, mit der man unbenannte rekursive Funktionen schreiben kann. Beginnen wir aber damit, dass wir der inneren Funktion einen Namen geben und sie herausziehen:

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

Der andere wichtige syntaktische Zucker ist, f/@xwas kurz ist, Map[f, x]dh er ruft fjedes Element von auf x. Der Grund f[x_] := ... f /@ xfür die unendliche Rekursion ist nicht, dass die Abbildung von etwas über ein Atom das Atom unverändert lässt, ohne die Funktion aufzurufen. Daher müssen wir nicht explizit nach dem Basisfall suchen (aktuelles Element ist eine Ganzzahl).

Die Funktion fkehrt also zuerst zur tiefsten Liste im Inneren zurück x, an welcher Stelle f/@ein No-Op wird. Dann nennen wir das use ##& @@ List /@on. Mapping Listüber die Liste wickelt einfach jedes Element in einer separaten Liste, so {1, 2, 3}wird {{1}, {2}, {3}}. Dann wenden wir ##&es an, was bedeutet, dass der Kopf (dh die äußere Liste) durch ersetzt wird ##&, also wird dies zu ##&[{1}, {2}, {3}]. Aber ##&einfach gibt sie die Argumente als ein Sequence(die Sie als eine ungeöffnete Liste denken können, oder eine Art „Klecks“ Operator in anderen Sprachen).

Also ##& @@ List /@wandelt sich eine Liste {1, 2, 3}in {1}, {2}, {3}(Art, das letzte Ding wird tatsächlich in den Kopf gewickelt Sequence, aber das verschwindet, sobald wir den Wert irgendwo verwenden).

Das lässt die Frage offen, warum fselbst nicht schon die Lösung für die Herausforderung ist. Das Problem ist, dass die äußerste Liste anders behandelt werden sollte. Wenn wir Input {{1, 2}, {3, 4}}haben, wollen wir {{1}, {2}, {3}, {4}}und nicht {{1}}, {{2}}, {{3}}, {{4}} . Meine ursprüngliche Lösung hat dies behoben, indem das Endergebnis als eine Liste von Argumenten übergeben wurde, an Joindie die äußere Ebene von Listen wiederhergestellt werden soll. Diese überspringt jedoch die äußere Ebene, indem sie sich f selbst in einer Karte in der Ausgabe verwendet. Daher fwird es nur auf die einzelnen Elemente der äußersten Liste angewendet und darf diese Liste nie berühren.

Bei den anderen drei Lösungen wendet die erste einfach die Rekursion an, die auch außerhalb der Rekursion ffunktioniert. Die anderen beiden Lösungen vermeiden eine wiederholte MapOperation, indem sie zuerst zwei Funktionen zusammenstellen und dann das Ergebnis nur einmal abbilden.

Martin Ender
quelle
8

J , 19-18 Bytes

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

Dies ist ein anonymes Verb, das geschachtelte Arrays akzeptiert und zurückgibt. Dies ist Js (ziemlich umständliche) Version verschachtelter Arrays. Sehen Sie, wie alle Testfälle bestanden werden.

Erläuterung

Dies nutzt die etwas exotischen Operationen {::( map ) und S:( spread ), die auf Boxed Arrays ausgeführt werden. {::Ersetzt jedes Blatt durch den eingepackten Pfad zu diesem Blatt. S:Wendet ein bestimmtes Verb auf eine bestimmte Verschachtelungstiefe an und teilt die Ergebnisse in ein Array auf.

(<@]/@,~>)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.
Zgarb
quelle
3

R, 199 Bytes

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

Diese Frage war hart. Die Listen von R sind etwas seltsam und es ist absolut nicht einfach, alle Elemente von Unterlisten zu durchlaufen. Es ist auch nicht einfach, dann die Tiefe dieser Liste zu bestimmen. Dann besteht die Herausforderung darin, die Liste mit allen getrennten Elementen neu zu erstellen. Daher benötigen wir auch eine Möglichkeit, eine Liste mit einer bestimmten Tiefe adaptiv zu erstellen.

Die Lösung besteht aus zwei großen Teilen. Eine rekursive Funktion, die alle Listen durchläuft und die Tiefe aufzeichnet:

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

Wenn wir die Tiefen jedes Eintrags des Vektors unlist(l)gespeichert haben d, erstellen wir implizit eine Liste lapplyund füllen sie mit der folgenden Funktion:

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

In diesem Aufruf von apply erstellen wir ein Objekt qmit dem Wert des Eintrags in der Liste, überprüfen seine Tiefe und prüfen, ob er ungleich Null ist. Wenn es Null ist, können wir es einfach als numerischen Wert belassen. Wenn es nicht Null ist, müssen wir es in dieser Anzahl von Listen verschachteln. Also rufen wir dmal eine for-Schleife auf und rufen immer wieder auf q=list(q).

lapplyDann werden alle diese Werte von qin eine Liste aufgenommen und die gewünschte Ausgabe erstellt.

Vollständiges Programm mit dem richtigen Abstand und so weiter:

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)
}
JAD
quelle
Schön, das ist die Methode, die ich mit meiner anfänglichen Python-Lösung für die Testfälle verwendet habe :)
FlipTack
is.list(y)statt class(y)=='list'? Ich kann nicht überprüfen, ob dies tatsächlich funktioniert.
Giuseppe
180 Bytes
Giuseppe
3

Retina , 34 Bytes

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

Probieren Sie es online!

Martin Ender
quelle
Wie funktioniert die (?<-2>)Arbeit?
Kritixi Lithos
@KritixiLithos Es ist eine Bilanzgruppe . Es wird vom Erfassungsstapel 2 abgerufen, sodass ich die aktuelle Verschachtelungstiefe verfolgen kann.
Martin Ender
2

C (gcc) 147 Bytes

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

Beispiel Eingabe:

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

Beispielausgabe:

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

gestapelt , nicht konkurrierend, 25 Bytes

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

Dies ist eine Funktion, die das oberste Element des Stapels ändert. Wenn Sie eine Bonafide-Funktion wünschen, fügen Sie einfach [und ]an den Anfang und das Ende. Probieren Sie es hier aus!

Hier ist eine lesbare Version:

{ 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

Testfall:

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

Ausgabe ohne Zeilenumbruch:

(1 (2) (3) (4) (4) ((5)) ((2)) (1))
Conor O'Brien
quelle
Ist *wie ein Argument zum Codeblock?
Downgoat
@Downgoat in diesem Fall umschließt es das Argument d-1mal. $funcist eine manipulierbare Funktion.
Conor O'Brien
2

PHP, 101 94 Bytes

1 Byte dank @Christoph gespeichert, weitere 6 davon inspiriert.

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

rekursive Funktion, ziemlich einfach

Nervenzusammenbruch

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
}
Titus
quelle
Wo wird das Ergebnis initialisiert?
Neil
@Neil: PHP benötigt keine explizite Initialisierung. Ruft entweder $rElemente in der Schleife ab oder die Funktion gibt ein leeres Array zurück. Es kann Hinweise geben, die jedoch nicht mit der Standardkonfiguration gedruckt werden.
Titus
Bedeutet das nicht, dass Sie es nur einmal anrufen können?
Neil
1
Genauso gut könnte man bekommen verrückt: !cos(). cos()kehrt nulljedes Array für und einen Schwimmer! = 0 für jede positiv ganze Zahl ist . Ich meine ... wer kümmert sich um Warnungen?
Christoph
1
@Christoph: Warnungen werden gedruckt, Hinweise nicht (in der Standardkonfiguration). Aber es ist eine großartige Idee! Ein is_int: Das Umkehren der Bedingung speichert nichts. Ich brauche ein Leerzeichen zwischen elseund foreach. ABER: $b[0]für eine ganze Zahl ist NULL.
Titus
2

Python 2, 122 106 Bytes

Ziemlich schreckliche Punktzahl, nur eine einfache Implementierung.

Vielen Dank an @Zachary T für die Unterstützung beim Speichern von 16 Bytes!

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)

Rufen Sie xmit einem Argument auf, um auszuführen. Aus irgendeinem Grund kann es nur einmal ausgeführt werden.

Blau
quelle
Sie können ändern , a+=[n(l,d)]um a+=n(l,d),(das folgende Komma beachten)
FlipTack
Müssen Sie überhaupt zuweisen t?
Zacharý
Funktioniert das, wenn Sie es mehrmals aufrufen?
Zacharý
Sie können nzur Funktion wechseln und das erste Argument entfernen, da dies immer der Fall sein wird l.
Zacharý
repl.it/EwPz
Zacharý
2

JavaScript (Firefox 30-57), 53 Byte

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

Die beste Antwort auf ES6, die ich bisher habe, ist 76 Byte:

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
Neil
quelle
2
Ich denke, Sie haben in beiden Codeblöcken das führende weggelassen f=.
Conor O'Brien
@ ConorO'Brien Noch einmal ...
Neil
1

Perl 6 , 60 47 Bytes

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

( Probieren Sie es online. )

Erläuterung:

  1. [... for |$^a]: Iterieren Sie über das Eingabearray und erstellen Sie daraus ein neues Array.
  2. $_ ~~ List ?? ... !! ...: Überprüfen Sie für jedes Element, ob es selbst ein Array ist.
  3. |([$_] for .&f): Wenn das Element ein Array ist, wenden Sie die Funktion rekursiv darauf an, iterieren Sie über die Elemente des neuen Arrays, die von diesem rekursiven Aufruf zurückgegeben wurden, umschließen Sie jedes Element in einem eigenen Array und fügen Sie sie in die äußere Liste ein.
  4. $_: Wenn das Element kein Array ist, geben Sie es so wie es ist weiter.
smls
quelle
1

Haskell, 71 Bytes

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

Wieder muss ich meinen eigenen Listentyp definieren, da Haskells native Listen nicht beliebig verschachtelt werden können. Dieser neue Typ Lkann von einer Funktion zurückgegeben, aber nicht standardmäßig gedruckt werden. Um ein Ergebnis zu erhalten, definiere ich eine showInstanz für L:

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

Jetzt können wir einige Tests in der REPL machen:

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

So funktioniert es: Eine einfache Rekursion, die die Verschachtelungsebene als Funktion von CKonstruktoren übergibt . Wir beginnen mit der Identitätsfunktion idund d#C l=fügen bei jeder Liste (-> Musterübereinstimmung ) eine weitere Ebene C(-> C .pure.d) zum rekursiven Aufruf #aller Elemente der Liste hinzu. Wenn wir auf eine Zahl stoßen, wenden wir einfach die Funktion der Verschachtelungsebene dauf die Zahl an.

nimi
quelle
0

APL (Dyalog) , 44 Byte *

Anonyme implizite Präfixfunktion. Nimmt die verschachtelte APL-Liste als Argument und gibt ein verschachteltes APL-Array zurück.

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

Probieren Sie es online!

{} Wende die folgende explizite Funktion an, in der das Argument dargestellt wird durch :

⎕JSON⍵ Konvertieren Sie das Argument in JSON

j← speichern in j

'[]'∘.= Tabelle mit joffenen (obere Reihe) und geschlossenen (untere Reihe) Klammern

-⌿ obere Reihe minus untere Reihe (vertikale Differenzreduzierung)

+\ kumulative Summe (gibt die Verschachtelungsebene für jedes Zeichen an)

()⊆ Partition, beginnt eine neue Partition, wenn vor einer 1 in… keine 1 steht

  j∊⎕D wobei jedes Zeichen der jein Mitglied des Satzes von D igits

⊃¨ wähle den ersten von jedem (dies gibt die Verschachtelungsebene pro mehrstelliger Zahl)

∊{… Wenden Sie  auf jede Verschachtelungsebene ( ) die folgende Funktion an , wobei Sie das entsprechende Element aus dem Argument ϵ nlisted (abgeflacht) als linkes Argument ( ) verwenden:

,⍺ ravel (listify) die Zahl (weil Skalare nicht eingeschlossen werden können)

⊂⍣⍵mal  beilegen

 enthüllen (weil die innerste Liste selbst ein Gehege ist)


* Verwenden von Dyalog Classic mit ⎕ML←3(Standardeinstellung bei vielen Systemen), Ersetzen von und für . Tio!

Adam
quelle