Inspiriert von Ermitteln Sie die Größe einer Liste .

Definieren Sie die rekursive Größe RSeiner Liste, die keine Listen enthält, als Länge (Anzahl der enthaltenen Elemente) und die rekursive Größe einer Liste, die Listen enthält, als Summe ihrer Länge und der rekursiven Größe dieser Listen.

Herausforderung

Schreiben Sie ein Programm oder eine Funktion, die die rekursive Größe einer Liste in möglichst wenigen Bytes ausgibt.

Die Eingabe ist eine Liste und kann Zahlen, Zeichenfolgen (sofern in Ihrer Sprache verfügbar) und ähnliche Listen enthalten.

Beispielsweise:

RS([]) = 0

RS([[]]) = 1

RS([4, 5, 6]) = 3
RS(["four", "five", "six"]) = 3
RS(["[[[[]]]]", "[][][][][]", "][][[[]]][]["]) = 3

RS([[4, 5, 6]]) = 4
RS([["four", "five", "six"]]) = 4
RS([["[[[[]]]]", "[][][][][]", "][][[[]]][]["]]) = 4

RS([[4], [5], [6]]) = 6
RS([["four"], ["five"], ["six"]]) = 6
RS([["[[[[]]]]"], ["[][][][][]"], ["][][[[]]][]["]]) = 6

RS([[[[[[[[[]]]]]]]]]) = 8

RS([[],[],[],[],[],[],[],[]]) = 8

RS([[],[],[[]],[[[[]]]]]) = 8

RS([0,[-1],[2.3,-4.3],[5,[6]],[7,[8,9,[10,11,[12,13,14]]]]]) = 22

Beachten Sie: Wenn Ihre Sprache keine Zeichenfolgen enthält, jedoch eine Liste von Zeichen enthält, können die oben aufgeführten Beispiele "strings"tatsächlich eine Liste von Zeichen sein und zu größeren Ergebnissen führen. Als Beispiel:

RS([['f','o','u','r'], ['f','i','v','e'], ['s','i','x']]) = 14

Das ist Code-Golf , also gewinnt die kürzeste Antwort in Bytes; kein witziges Geschäft, wie immer.

Eine nicht aufgeführte Eingabe kann eine beliebige Ausgabe erzeugen.
I / O ist wie gewohnt flexibel .

Gelee , 8 Bytes

߀-ŒḊ?‘S

Probieren Sie es online!

Wie es funktioniert

߀-ŒḊ?‘S  Main link. Argument: x

   ŒḊ?    If x has non-zero depth:
߀          Recursively map the main link over its elements.
  -         Else, yield -1.
      ‘   Increment all integers in the result.
       S  Compute the sum of the result.
          If x is an array, incrementing before adding is equivalent to computing
          the sum of the elements and the length.
          If x is an integer/character, incrementing -1 yields 0, as desired.

Python, 42 Bytes

f=lambda x:x*0==[]and len(x)+sum(map(f,x))

Geben Sie für eine Nicht-Liste 0 aus. Geben Sie für eine Liste ihre Länge plus die Summe der rekursiven Ausgaben für ihre Elemente aus.

Listen werden in der Python 2-Reihenfolge nach Bedarf über und unter Zeichenfolgen angezeigt []<=x<''. Stattdessen überprüfen wir x*0==[], während das Ergebnis 0für eine Zahl oder ''für eine Zeichenfolge.

JavaScript (ES6), 39 37 Bytes

2 Bytes gespart dank @ edc65

f=a=>a.map&&a.map(x=>a-=~f(x),a=0)&&a

Mathematica, 20 Bytes

Length@Level[#,∞]&

Anonyme Funktion. Nimmt einen Ausdruck als Eingabe und gibt eine Zahl als Ausgabe zurück. Das Unicode-Zeichen ist U + 221E INFINITY für \[Infinity]. Level[#,∞]Gibt eine Liste der Unterausdrücke der Eingabe aus und Length@zählt sie.

Mathematica, 14 Bytes

LeafCount@#-1&

Kleinere Änderung meiner vorherigen Antwort . Wie ich dort erklärt habe, LeafCountkümmert es sich bereits um verschachtelte Atomwerte, zählt aber auch die äußerste Liste, die wir vom Ergebnis abziehen müssen.

Perl, 34 Bytes

Eine rekursive Funktion! Ja, Perl hat nicht nur Regex, sondern auch Funktionen!

sub f{@_+f(map ref?@$_:(),@_)if@_}

Wenn Sie es testen möchten, können Sie Folgendes ausführen:

perl -pE 'sub f{@_+f(map ref?@$_:(),@_)if@_}$_=f@{+eval}' <<< '[["four"], ["five"], ["six"]]'

Mathematica, 32 Bytes

Length@#+Tr[#0/@#~Select~ListQ]&

Unbenannte rekursive Funktion. Der Auszug #0/@#~Select~ListQruft die Funktion für jedes Element der Eingabe, das eine Liste ist, erneut auf und Trfasst diese Werte zusammen. Glücklicherweise ist es in Mathematica in Ordnung, die Länge der leeren Liste zu nehmen und nach qualifizierenden Elementen aus der leeren Liste zu suchen, sodass kein Basisfall erforderlich ist.

Haskell, 52 Bytes

data L a=E a|N[L a]
r(N n)=1+sum(r<$>n)
r _=1
pred.r

Anwendungsbeispiel:

*Main> pred.r $ N[E 0,N[E(-1)],N[E 2.3,E(-4.3)],N[E 5,N[E 6]],N[E 7,N[E 8,E 9,N[E 10,E 11,N[E 12,E 13,E 14]]]]] 
22

Haskell unterstützt keine gemischten Listen (z. B. Int und Liste von Int), daher gehe ich von einem benutzerdefinierten Listentyp aus, Lder entweder ein Element eines Typs a (-> E a) oder eine Liste anderer Ls (-> N[L a]) ist. Die Berechnung der RS ​​ist eine einfache Rekursion, bei der eine EAnzahl 1und eine NEins plus die Summe der rekursiven Größen ihrer Elemente addiert werden. Die ganze Summe ist um 1 verschoben, also subtrahiere ich sie über pred.

Randnotiz: Die genauen Typen und Werte der Elemente sind für den Algorithmus nicht wichtig, daher können wir den Polymorphismus entfernen und uns nur mit abstrakten Elementen befassen data L=E|N[L].

Faktor 105 Bytes

Rekursive Funktion g.

: g ( o -- l ) [ dup [ sequence? ] [ string? not ] bi and [ [ g ] map sum 1 + ] [ drop 1 ] if ] map sum ;

Ungolfed (irgendwie):

: g ( o -- l ) 
[ dup 
  [ sequence? ] 
  [ string? not ] 
  bi and 
  [ [ g ] map sum 1 + ] 
  [ drop 1 ] 
  if 
] map sum ;

Sie werden feststellen, dass es keine Aufrufe für gibt, lengthda die integrierte Länge drop 1nicht in Zeichenfolgen und Nicht-Sequenzen implementiert wird.

Mathematica, 18 Bytes

(c=-1;++c&//@#;c)&

Noch ein weiterer Mathematica-Ansatz. Nicht so kurz wie die Verwendung des eingebauten, LeafCountaber immer noch ziemlich prägnant. Dies nutzt den MapAllOperator, //@der eine Funktion für jeden Knoten eines Ausdrucks aufruft, und wir verwenden diese Funktion, um einen Zähler zu erhöhen c. Wie im LeafCountFall gibt dies mehr, als wir brauchen, da es auch den äußeren Listenkopf zählt, also starten wir den Zähler ab -1.

C # (Visual C # Interactive Compiler) , 50 Byte

int f(Array a)=>a.Length+a.OfType<Array>().Sum(f);

Probieren Sie es online!

Verwendet dieselbe Technik wie die zuvor übermittelte Java-Antwort , nutzt jedoch LINQ, um die Antwortlänge zu verringern.

Erläuterung:

// f is a method that a accepts
// an array of any underlying type
int f(Array a)=>
  // include the length of the
  // current array in the total
  a.Length+
  // filter the current list to elements
  // that are also arrays
  a.OfType<Array>()
    // recursively call f on each child
    // array and add to cumulative total
    .Sum(f);

05AB1E (Legacy), 22 - 17 Byte

"ε¼D¸D˜Êi®.V"©.V¾

Probieren Sie es online aus oder überprüfen Sie alle Testfälle .

Erläuterung:

Diese Herausforderung ist in 05AB1E mit mehreren Herausforderungen verbunden:

1. Obwohl 05AB1E seit dem Elixir rewrite ( λ) eine rekursive Funktion hat , ist sie nur für Ganzzahlsequenzen nützlich. Hier ist eine Antwort von mir als Beispiel für die rekursive 05AB1E-Funktion. Aus diesem Grund musste ich eine Alternative für rekursive Aufrufe finden, indem ich einen Teil des Codes in eine Zeichenfolge einbaute und diese Zeichenfolge rekursiv als 05AB1E-Code ausführte.
2. isListIn 05AB1E gibt es auch keinen Befehl. Daher musste ich einige Problemumgehungen verwenden, um dies zu überprüfen, indem ich das Umbrechen in eine Liste, die Tiefenreduzierung und die Überprüfung auf Gleichheit verwendete.
3. Und drittens gibt es keine Abflachung für nur eine Ebene einer mehrdimensionalen Liste. Die Abflachungsfunktion ˜ist eine Tiefenabflachung, die alle Ebenen entfernt und eine mehrdimensionale Liste zu einer einzigen Liste mit allen innersten Werten macht. (dh [[1,2],[[[3]],4]]wird [1,2,3,4]).

Am Ende befand sich der Code oben, um alle drei oben genannten Probleme zu lösen. Es ist in drei Hauptteile aufgeteilt. Zuerst haben wir folgendes:

"..."        # Create a string with 05AB1E code
     ©       # Save this string in the register (without popping)
      .V     # Execute the string as 05AB1E code

Die Zeichenfolge enthält den folgenden Code:

ε            # Map each value in the given list by:
             # (this uses the input-list implicitly with the initial call)
 ¼           #  Increase the counter_variable by 1
 D           #  Duplicate the map-value
             #   i.e. STACK "A" becomes "A","A"
             #   i.e. STACK [["B","C"]] becomes [["B","C"]],[["B","C"]]
  ¸          #  Wrap it into a list
             #   i.e. "A" → ["A"]
             #   i.e. [["B","C"]] → [[["B","C"]]]
   D         #  Duplicate that again
             #   i.e. STACK "A",["A"] becomes "A",["A"],["A"]
             #   i.e. STACK [["B","C"]],[[["B","C"]]]
             #    becomes [["B","C"]],[[["B","C"]]],[[["B","C"]]]
    ˜        #  Flatten it
             #   i.e. ["A"] → ["A"]
             #   i.e. [[["B","C"]]] → ["B","C"]
     Ê       #  Check if the wrapped and wrapped+flattened lists are NOT equal
             #   i.e. ["A"] and ["A"] → 0 (falsey)
             #   i.e. [[["B","C"]]] and ["B","C"] → 1 (truthy)
      i      #  If they are:
       ®     #   Push the string from the register
        .V   #   Execute it as 05AB1E code
             #   (this is basically our recursive call, mapping the current value
             #    we duplicated initially again)

Eine Map wird anstelle einer foreach-Schleife verwendet, da die Map implizit yist und eine foreach-Schleife explizit benötigt y. Das interessiert uns aber nur counter_variable.

Und schließlich, nachdem alle Karten und inneren Karten fertig sind, werden wir:

¾           # Push the counter_variable (which is output implicitly as result)

R , 65 Bytes

R=function(L,`*`=sapply)"if"(any(L*is.list),sum(1+L*R),length(L))

Probieren Sie es online!

Offensichtliche rekursive Implementierung der Spezifikation.

C 174 167 152 Bytes

Rekursive Funktion f, die Speicher verliert ( 152 ):

#include"object.h"
size_t f(array_t*a){size_t t=0,i=0;for(;i<array_length(a);i++){object_t*o=array_get_copy(a,i,0);t+=o->type==6?f(o->ary):1;}return t;}

Rekursiv, fdas unter Verwendung von Referenzen bei 167 nicht leckt :

#include"object.h"
size_t f(array_t*a){size_t t=0,i=0;for(;i<array_length(a);i++){object_t**o=array_get_ref(a,i,0);t+=*o->type==t_array?f(*o->ary):1;}return t;}

Ungolfed:

size_t get_recursize (const array_t* const a) {
  pfn();

  object_failnull(a);

  size_t out = 0;

  for (size_t i = 0; i < array_length(a); i++) {

    object_t** o = array_get_ref(a, i, NULL);

    if ( (*o)->type == t_array ) {

      out += get_recursize((*o)->ary);

    } else {
      ++out;
    }
  }
  return out;
}

"Aber wie", fragen Sie, "kann dies in C beantwortet werden? Sicherlich gibt es in C keine verwalteten Arrays, und Sie können wirklich keine heterogenen Arrays haben ...?"

"Aha", erwidere ich, "denn ich habe an einem einfachen System von" Objekten "für (GNU-ish) C11 und ISO C ++ 11 gearbeitet".

Das vollständige Demo-Programm für diese Funktion ist:

#include "../calc/object/object.h"

size_t get_recursize (const array_t* const a);

define_array_new_fromctype(ssize_t);

int main (void) {

  size_t len = 6;

  static const ssize_t h[6] = { -1, 3, -5, 7, -9, 11 };

  array_t* a = array_new_from_ssize_t_lit(h, len, t_realint);

  size_t rsize = get_recursize(a);

  printf("Recursive size of a: %zu\n", rsize);

  object_t* asobj = object_new(t_array, a);
  array_destruct(a);

  array_t* b = array_new(NULL, -1);

  for (size_t j = 0; j < 10; j++) {
    array_append(b, asobj);
  }

  object_destruct(asobj);

  rsize = get_recursize(b);

  printf("Recursive size of b: %zu\n", rsize);

  asobj = object_new(t_array, b);
  array_destruct(b);

  array_t* c = array_new(NULL, -1);

  for (size_t i = 0; i < 100; i++) {
    array_append(c, asobj);
  }

  object_destruct(asobj);

  rsize = get_recursize(c);

  printf("Recursive size of c: %zu\n", rsize);

  array_destruct(c);

  return EXIT_SUCCESS;
}

size_t get_recursize (const array_t* const a) {
  pfn();

  object_failnull(a);

  size_t out = 0;

  for (size_t i = 0; i < array_length(a); i++) {

    object_t** o = array_get_ref(a, i, NULL);

    if ( (*o)->type == t_array ) {

      out += get_recursize((*o)->ary);

    } else {
      ++out;
    }
  }
  return out;
}

Im Moment lebt es hier und du brauchst dieses Repo, um es zu benutzen.

Sie benötigen außerdem die libfnvfür Ihre Plattform kompilierte Fowler-Noll-Vo-Hash-Bibliothek . Es befindet sich in diesem Repository und kann auch hier abgerufen werden .

Dann kannst du machen cc -DNODEBUG size.c path/to/libfnv.a -o size.

Die Implementierung ist nicht unbedingt effizient:

$ valgrind --leak-check=full --track-origins=yes --show-leak-kinds=all ./size
==24127== Memcheck, a memory error detector
==24127== Copyright (C) 2002-2015, and GNU GPL'd, by Julian Seward et al.
==24127== Using Valgrind-3.12.0.SVN and LibVEX; rerun with -h for copyright info
==24127== Command: ./size
==24127== 
Recursive size of a: 6
Recursive size of b: 60
Recursive size of c: 6000
==24127== 
==24127== HEAP SUMMARY:
==24127==     in use at exit: 0 bytes in 0 blocks
==24127==   total heap usage: 22,900 allocs, 22,900 frees, 615,584 bytes allocated
==24127== 
==24127== All heap blocks were freed -- no leaks are possible
==24127== 
==24127== For counts of detected and suppressed errors, rerun with: -v
==24127== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Aber es funktioniert! Das letzte Commit an Master (auf dem dieses Programm kompiliert wurde) war vor 2 Tagen, was bedeutet, dass diese Einreichung gültig ist.

Axiom 118 Bytes

RS(a:Union(List(Any),Any)):INT==(a case List(Any)=>(g:List(Any):=a;leaf? g=>0;r:=#g;for i in g repeat r:=r+RS(i);r);0)

ungolfed

RS(a:Union(List(Any),Any)):INT==
  a case List(Any)=>
          g:List(Any):=a
          leaf? g=>0
          r:=#g
          for i in g repeat r:=r+RS(i)
          r
  0

Ergebnisse

(25) -> RS([])=0
   (25)  0= 0
                                        Type: Equation NonNegativeInteger
(26) -> RS([[]]) = 1
   (26)  1= 1
                                           Type: Equation PositiveInteger
(27) -> RS([4, 5, 6]) = 3
   (27)  3= 3
                                           Type: Equation PositiveInteger
(28) -> RS(["four", "five", "six"]) = 3
   (28)  3= 3
                                           Type: Equation PositiveInteger
(29) -> RS(["[[[[]]]]", "[][][][][]", "][][[[]]][]["]) = 3
   (29)  3= 3
                                           Type: Equation PositiveInteger
(30) -> RS([[4, 5, 6]]) = 4
   (30)  4= 4
                                           Type: Equation PositiveInteger
(31) -> RS([["four", "five", "six"]]) = 4
   (31)  4= 4
                                           Type: Equation PositiveInteger
(32) -> RS([["[[[[]]]]", "[][][][][]", "][][[[]]][]["]]) = 4
   (32)  4= 4
                                           Type: Equation PositiveInteger
(33) -> RS([[4], [5], [6]]) = 6
   (33)  6= 6
                                           Type: Equation PositiveInteger
(34) -> RS([["four"], ["five"], ["six"]]) = 6
   (34)  6= 6
                                           Type: Equation PositiveInteger
(35) -> RS([["[[[[]]]]"], ["[][][][][]"], ["][][[[]]][]["]]) = 6
   (35)  6= 6
                                           Type: Equation PositiveInteger
(36) -> RS([[[[[[[[[]]]]]]]]]) = 8
   (36)  8= 8
                                           Type: Equation PositiveInteger
(37) -> RS([[],[],[],[],[],[],[],[]]) = 8
   (37)  8= 8
                                           Type: Equation PositiveInteger
(38) -> RS([[],[],[[]],[[[[]]]]]) = 8
   (38)  8= 8
                                           Type: Equation PositiveInteger
(39) -> RS([0,[-1],[2.3,-4.3],[5,[6]],[7,[8,9,[10,11,[12,13,14]]]]]) = 22
   (39)  22= 22
                                           Type: Equation PositiveInteger
(40) -> RS([['f','o','u','r'], ['f','i','v','e'], ['s','i','x']]) = 14
   (40)  14= 14
                                           Type: Equation PositiveInteger

APL (NARS), 24 Zeichen, 48 Byte

{⍬≡⍵:0⋄×≡⍵:(≢⍵)++/∇¨⍵⋄0}

Dies wäre die wörtliche Übersetzung von "meiner" Axiom-Antwort hier ... In APL wäre die leere Liste "Zilde", die Sie mit "[]" angeben, "ist" [[] "," 1 2 3´ ist ´ [1,2,3] ´ ecc Einige Tests:

  RS←{⍬≡⍵:0⋄×≡⍵:(≢⍵)++/∇¨⍵⋄0}
  RS ⍬
0
  RS ⊂⍬
1
  RS  4 5 6
3
  RS ("four")("five")("six")
14
  RS ('f' 'o' 'u' 'r') ('f' 'i' 'v' 'e') ('s' 'i' 'x')
14
  RS ("(((())))")("()()()()()")(")()((()))()(")
33
  RS (⊂4 5 6)
4
  RS (⊂("four")("five")("six")) 
15
  RS (⊂("(((())))")("()()()()()")(")()((()))()(") )
34
  RS (,4) (,5) (,6)
6
  RS ⊂¨("four")("five")("six")
17
  RS ⊂¨("(((())))")("()()()()()")(")()((()))()(") 
36
  RS ⊂⊂⊂⊂⊂⊂⊂⊂⍬
8
  RS ⍬⍬⍬⍬⍬⍬⍬⍬
8
  RS ⍬⍬(⊂⍬)(⊂(⊂(⊂⍬)))
8
  RS 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))  
22     

Für den Ausdruck der anderen Art von Ergebnissen schlägt die Übung vor, dass wir eine weitere Funktion benötigen (beide Funktionen RS und Rs sollten für die Übung in Ordnung sein).

  Rs←{⍬≡⍵:0⋄(''≡0↑⍵)∨0=≡⍵:0⋄(≢⍵)++/∇¨⍵}
  Rs ("four")("five")("six")
3
  Rs ("(((())))")("()()()()()")(")()((()))()(")
3
  Rs (⊂("four")("five")("six"))
4
  Rs (⊂("(((())))")("()()()()()")(")()((()))()(") )
4
  Rs ⊂¨("four")("five")("six")
6
  Rs ⊂¨("(((())))")("()()()()()")(")()((()))()(")
6
  Rs 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))
22
  Rs ('f' 'o' 'u' 'r') ('f' 'i' 'v' 'e') ('s' 'i' 'x')
3

Um zu sehen, wie einige Eingaben erscheinen, verwenden wir die o-Funktion:

  o←⎕fmt
  o 0(,¯1)(2.3 ¯4.3)(5 (,6))(7 (8 9 (10 11 (12 13 14))))
┌5─────────────────────────────────────────────────────────┐
│  ┌1──┐ ┌2────────┐ ┌2─────┐ ┌2──────────────────────────┐│
│0 │ ¯1│ │ 2.3 ¯4.3│ │  ┌1─┐│ │  ┌3──────────────────────┐││
│~ └~──┘ └~────────┘ │5 │ 6││ │7 │    ┌3────────────────┐│││
│                    │~ └~─┘2 │~ │8 9 │      ┌3────────┐││││
│                    └∊─────┘ │  │~ ~ │10 11 │ 12 13 14│││││
│                             │  │    │~~ ~~ └~────────┘2│││
│                             │  │    └∊────────────────┘3││
│                             │  └∊──────────────────────┘4│
│                             └∊──────────────────────────┘5
└∊─────────────────────────────────────────────────────────┘

Diese gedruckte Zilde und eine 8-Zilde-Liste:

  o ⍬
┌0─┐
│ 0│
└~─┘
  o ⍬⍬⍬⍬⍬⍬⍬⍬
┌8──────────────────────────────────────┐
│┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐ ┌0─┐│
││ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0│ │ 0││
│└~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘ └~─┘2
└∊──────────────────────────────────────┘

Java, 96 Bytes

int c(Object[]a){int r=a.length;for(var i:a)r+=i instanceof Object[]?c((Object[])i):0;return r;}

Probieren Sie es online aus.

Erläuterung:

int c(Object[]a){  // Recursive method with Object-array parameter and integer return-type
  int r=a.length;  //  Result-sum, starting at the size of the input-array
  for(var i:a)     //  Loop over the input-array:
    r+=            //   Increase the result-sum by:
       i instanceof Object[]?
                   //    If the current item is an array:
        c((Object[])i) 
                   //     A recursive call with this item
       :           //    Else:
        0;         //     0 (so leave the result-sum the same)
  return r;}       //  Return the result-sum

Attache , 21 Bytes

{#_+Sum!$=>IsArray\_}

Probieren Sie es online!

Es stellt sich heraus, dass der C # -Ansatz in Attache ziemlich kurz ist.

Alternativen

25 Bytes f[x]:=#x+Sum!f=>IsArray\x

26 Bytes f[x]:=#x+Sum[f=>IsArray\x]

35 Bytes f:=Sum##{If[IsArray@_,1+f@_,1]}=>Id

35 Bytes f:=Sum@Map[{If[IsArray@_,1+f@_,1]}]

37 Bytes f[x]:=Sum[{If[IsArray@_,1+f@_,1]}=>x]

Clojure, 79 77 51 Bytes

Die Eingabe muss eine Liste sein, kein Vektor. Beides würde durch Verwendung von unterstützt sequential?.

(defn f[i](if(seq? i)(apply +(count i)(map f i))0))

Bisherige:

(defn f[i](if(seq? i)(if(some seq? i)(apply +(count i)(map f i))(count i))0))

Python, 72 Bytes

l=lambda a:0if len(a)==0else len(a)+sum(l(i)for i in a if type(i)==list)