Zainspirowany przez Znajdź „rozpakowany rozmiar” listy .

Zdefiniuj rozmiar rekurencyjny RSdla listy nie zawierającej list jako jego długości (liczby zawartych elementów) i rozmiar rekurencyjny dla listy zawierającej dowolne listy jako sumę jego długości i rozmiar rekurencyjny tych list.

Wyzwanie

Napisz program lub funkcję, która wyświetla rekurencyjny rozmiar dowolnej listy w jak najmniejszej liczbie bajtów.

Dane wejściowe to lista, która może zawierać liczby, ciągi znaków (jeśli je posiada Twój język) i podobne listy.

Na przykład:

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

Zauważ, że jeśli twój język nie ma ciągów znaków, ale ma listy znaków, przykłady zawierające "strings"powyższe mogą faktycznie być listami znaków i mieć większe wyniki. Jako przykład:

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

To jest golf golfowy , więc wygrywa najkrótsza odpowiedź w bajtach; jak zwykle nie ma śmiesznego interesu.

Dane wejściowe inne niż lista mogą dawać dowolne dane wyjściowe.
I / O jest tak elastyczny jak zwykle .

Galaretka , 8 bajtów

߀-ŒḊ?‘S

Wypróbuj online!

Jak to działa

߀-ŒḊ?‘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 bajty

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

W przypadku listy innej niż wartość wyjściowa 0. W przypadku listy wypisz jej długość plus sumę wyników rekurencyjnych dla jej elementów.

Listy spadają powyżej liczb i poniżej ciągów w kolejności w Pythonie 2, co jest wymagane []<=x<''. Zamiast tego sprawdzamy x*0==[], podczas gdy wynik 0dla liczby lub ''ciągu.

JavaScript (ES6), 39 37 bajtów

Zaoszczędzono 2 bajty dzięki @ edc65

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

Mathematica, 20 bajtów

Length@Level[#,∞]&

Funkcja anonimowa. Pobiera wyrażenie jako dane wejściowe i zwraca liczbę jako dane wyjściowe. Znak Unicode to U + 221E INFINITY dla \[Infinity]. Level[#,∞]podaje listę podwyrażeń danych wejściowych i Length@zlicza je.

Mathematica, 14 bajtów

LeafCount@#-1&

Drobna modyfikacja mojej poprzedniej odpowiedzi . Jak już wyjaśniłem, LeafCountzajmuje się już zagnieżdżonymi wartościami atomowymi, ale zlicza także najbardziej zewnętrzną listę, którą musimy odjąć od wyniku.

Perl, 34 bajty

Funkcja rekurencyjna! Tak, Perl ma nie tylko wyrażenie regularne, ale także funkcje!

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

Jeśli chcesz to przetestować, możesz uruchomić coś takiego:

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

Mathematica, 32 bajty

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

Nienazwana funkcja rekurencyjna. Fragment #0/@#~Select~ListQwywołuje funkcję ponownie na każdym elemencie wejściowym, który jest listą, i Trsumuje te wartości. Na szczęście Mathematica dobrze sobie radzi, biorąc długość pustej listy i szukając kwalifikujących się elementów z pustej listy, więc nie jest potrzebny żaden przypadek podstawowy.

Haskell, 52 bajty

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

Przykład użycia:

*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 nie obsługuje list mieszanych (np. Int i list Int), więc wybieram niestandardowy typ listy, Lktóry jest albo elementem jakiegoś typu a (-> E a), albo listą innych Ls (-> N[L a]). Obliczanie RS jest prostą rekurencją, w której Eliczy 1się Njeden i jeden plus suma rekurencyjnych rozmiarów jego elementów. Cała suma jest wyłączona o 1, więc odejmuję ją przez pred.

Uwaga dodatkowa: dokładne typy i wartości elementów nie są ważne dla algorytmu, więc moglibyśmy usunąć polimorfizm i zająć się wyłącznie elementami abstrakcyjnymi i iść dalej data L=E|N[L].

Współczynnik, 105 bajtów

Funkcja rekurencyjna g.

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

Ungolfed (kinda):

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

Przekonasz się, że nie ma żadnych wywołań, lengthponieważ zamiast używać wbudowanej długości, jest ona zaimplementowana drop 1na ciągach i niesekwencjach.

Mathematica, 18 bajtów

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

Jeszcze inne podejście Mathematica. Nie tak krótki, jak korzystanie z wbudowanego, LeafCountale wciąż dość zwięzły. Korzysta z MapAlloperatora, //@który wywołuje funkcję na każdym węźle wyrażenia, i używamy tej funkcji do zwiększania licznika c. Tak jak w LeafCountprzypadku, daje to o jeden więcej niż potrzebujemy, ponieważ liczy się również nagłówek listy zewnętrznej, więc zaczynamy od licznika -1.

C # (interaktywny kompilator Visual C #) , 50 bajtów

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

Wypróbuj online!

Używa tej samej techniki, co poprzednio przesłana odpowiedź Java , ale wykorzystuje LINQ, aby skrócić długość odpowiedzi.

Wyjaśnienie:

// 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 ( starsza wersja ), 22 17 bajtów

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

Wypróbuj online lub sprawdź wszystkie przypadki testowe .

Wyjaśnienie:

To wyzwanie stwarza wiele wyzwań do pokonania w 05AB1E:

1. Chociaż 05AB1E ma funkcję rekurencyjną od czasu przepisania Elixir ( λ), jest on użyteczny tylko dla sekwencji całkowitych. Oto moja odpowiedź jako przykład funkcji rekurencyjnej 05AB1E. Z tego powodu musiałem znaleźć alternatywę do wykonywania wywołań rekurencyjnych, co zrobiłem, umieszczając część kodu w ciągu i wykonując go jako kod 05AB1E rekurencyjnie.
2. W isList05AB1E nie ma również polecenia, więc musiałem zastosować pewne obejścia, aby to sprawdzić, wykorzystując zawijanie do listy, głębokie spłaszczenie i sprawdzenie równości.
3. Po trzecie, nie ma spłaszczenia tylko jednego poziomu listy wielowymiarowej. Funkcja spłaszczania˜ jest głębokim spłaszczeniem, które usuwa wszystkie warstwy i czyni wielowymiarową listę pojedynczą listą ze wszystkimi wewnętrznymi wartościami. (tj. [[1,2],[[[3]],4]]staje się [1,2,3,4]).

Skończyłem z kodem u góry, aby rozwiązać wszystkie trzy powyższe problemy. Jest podzielony na trzy główne części. Najpierw mamy następujące:

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

Ciąg zawiera następujący kod:

ε            # 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)

Zamiast pętli foreach używana jest mapa, ponieważ ma ona charakter niejawny y , a pętla foreach wymaga jawnej y. Dbamy tylko o to counter_variable.

I wreszcie, po wykonaniu wszystkich map i map wewnętrznych:

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

R , 65 bajtów

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

Wypróbuj online!

Oczywista rekurencyjna implementacja specyfikacji.

C 174 167 152 bajtów

Funkcja rekurencyjna f, która przecieka pamięć ( 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;}

Rekurencyjny, fktóry nie przecieka, przy użyciu referencji, w 167 :

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

Nie golfowany:

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

„Ale jak,„ pytasz ”, można na to odpowiedzieć w C? Z pewnością nie ma zarządzanych tablic w C i tak naprawdę nie możesz mieć heterogenicznych tablic ...?”

„Aha”, „odpowiadam”, ponieważ pracowałem nad prostym systemem „obiektów” dla (GNU-ish) C11 i ISO C ++ 11 ”.

Pełny program demonstracyjny dla tej funkcji to:

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

Obecnie mieszka tutaj i będziesz potrzebować tego repozytorium, aby z niego skorzystać.

Będziesz także potrzebować biblioteki skrótów Fowler-Noll-Vo libfnv, skompilowanej dla Twojej platformy. Jest w tym repozytorium i możesz go również pobrać tutaj .

To możesz zrobić cc -DNODEBUG size.c path/to/libfnv.a -o size .

Implementacja niekoniecznie jest wydajna:

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

Ale to działa! Ostatnie zatwierdzenie do masterowania (na którym skompilowano ten program) miało miejsce 2 dni temu, co oznacza, że ​​przesłanie jest prawidłowe.

Axiom 118 bajtów

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)

bez golfa

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

wyniki

(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 znaki, 48 bajtów

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

To byłoby dosłowne tłumaczenie „mojej” odpowiedzi Axiom tutaj… W APL lista pustek brzmiałaby „Zilde, którą wskazujesz za pomocą ´ [] ´, ´⊂⍬´ jest ´ [[]] ´, ´ 1 2 3´ jest ´ [1,2,3] ´ ecc Niektóre testy:

  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     

do wydrukowania innego rodzaju wyników, proponowane ćwiczenie wymaga jeszcze jednej funkcji (obie funkcje RS i Rs powinny być odpowiednie dla ćwiczenia)

  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

aby zobaczyć, jak pojawiają się niektóre dane wejściowe, używamy funkcji o:

  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
└∊─────────────────────────────────────────────────────────┘

ten druk Zilde i jedna lista 8 Zilde:

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

Java, 96 bajtów

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

Wypróbuj online.

Wyjaśnienie:

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

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

Wypróbuj online!

Okazuje się, że podejście C # jest dość krótkie w Attache.

Alternatywy

25 bajtów f[x]:=#x+Sum!f=>IsArray\x

26 bajtów f[x]:=#x+Sum[f=>IsArray\x]

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

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

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

Clojure, 79 77 51 bajtów

Wejście musi być listą, a nie wektorem. Oba byłyby obsługiwane przy użyciu sequential?.

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

Poprzedni:

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

Python, 72 bajty

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