Inspirado en Buscar el "tamaño sin envolver" de una lista .

Defina el tamaño recursivo RS, de una lista que no contiene listas como su longitud (número de elementos contenidos) y el tamaño recursivo de una lista que contiene listas como la suma de su longitud y el tamaño recursivo de esas listas.

Desafío

Escriba un programa o función que genere el tamaño recursivo de cualquier lista dada en el menor número de bytes posible.

La entrada es una lista y puede contener números, cadenas (si su idioma las tiene) y listas similares.

Por ejemplo:

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

Tenga en cuenta que si su idioma no tiene cadenas pero tiene listas de caracteres, los ejemplos que contienen "strings"arriba podrían ser listas de caracteres y tener resultados más grandes. Como ejemplo:

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

Este es el código de golf , por lo que gana la respuesta más corta en bytes; no es gracioso, como siempre.

Una entrada no listada puede producir cualquier salida.
I / O es tan flexible como de costumbre .

Jalea , 8 bytes

߀-ŒḊ?‘S

Pruébalo en línea!

Cómo funciona

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

Para una no lista, salida 0. Para una lista, envíe su longitud más la suma de las salidas recursivas para sus elementos.

Las listas están por encima de los números y debajo de las cadenas en el pedido de Python 2, lo que requiere []<=x<''. En cambio, verificamos x*0==[], mientras que el resultado de 0un número o ''una cadena.

JavaScript (ES6), 39 37 bytes

Guardado 2 bytes gracias a @ edc65

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

Mathematica, 20 bytes

Length@Level[#,∞]&

Función anónima. Toma una expresión como entrada y devuelve un número como salida. El carácter Unicode es U + 221E INFINITY para \[Infinity]. Level[#,∞]da una lista de subexpresiones de entrada y las Length@cuenta.

Mathematica, 14 bytes

LeafCount@#-1&

Modificación menor de mi respuesta anterior . Como expliqué allí, LeafCountya se encarga de los valores atómicos anidados, pero también cuenta la lista más externa, que debemos restar del resultado.

Perl, 34 bytes

Una función recursiva! Sí, Perl no solo tiene expresiones regulares sino que también tiene funciones.

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

Si quieres probarlo, puedes ejecutar algo como:

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

Mathematica, 32 bytes

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

Función recursiva sin nombre. El extracto #0/@#~Select~ListQllama a la función nuevamente en cada elemento de la entrada que es una lista, y Trresume esos valores. Afortunadamente, Mathematica está bien tomando la longitud de la lista vacía y buscando elementos calificativos de la lista vacía, por lo que no se necesita un caso base.

Haskell, 52 bytes

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

Ejemplo de uso:

*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 no admite listas mixtas (por ejemplo, Int y lista de Int), por lo que voy con un tipo de lista personalizada Lque es un elemento de algún tipo a (-> E a) o una lista de otras L (-> N[L a]). Calcular el RS es una recursión simple donde un Erecuento 1y Nuno más la suma de los tamaños recursivos de sus elementos. Toda la suma está desactivada en 1, así que la resto vía pred.

Nota al margen: los tipos y valores exactos de los elementos no son importantes para el algoritmo, por lo que podríamos eliminar el polimorfismo y tratar solo con elementos abstractos data L=E|N[L].

Factor, 105 bytes

Función recursiva g.

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

Sin golf (un poco):

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

Verá que no hay llamadas lengthporque, en lugar de usar la longitud incorporada, se implementa a través drop 1de cadenas y no secuencias.

Mathematica, 18 bytes

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

Sin embargo, otro enfoque de Mathematica. No es tan corto como usar el incorporado, LeafCountpero sigue siendo bastante conciso. Esto hace uso del MapAlloperador //@que llama a una función en cada nodo de una expresión, y usamos esa función para incrementar un contador c. Como en el LeafCountcaso, esto da uno más de lo que necesitamos, porque también cuenta el encabezado de la lista externa, por lo que comenzamos el contador desde -1.

C # (compilador interactivo de Visual C #) , 50 bytes

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

Pruébalo en línea!

Utiliza la misma técnica que la respuesta Java presentada anteriormente , pero aprovecha LINQ para reducir la longitud de la respuesta.

Explicación:

// 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 (heredado), 22 17 bytes

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

Pruébelo en línea o verifique todos los casos de prueba .

Explicación:

Este desafío plantea múltiples desafíos a superar en 05AB1E:

1. Aunque 05AB1E tiene una función recursiva desde el Elixir rewrite ( λ), solo es útil para secuencias enteras. Aquí hay una respuesta mía como ejemplo de la función recursiva 05AB1E. Debido a eso, tuve que encontrar una alternativa para hacer llamadas recursivas, lo que hice al poner parte del código en una cadena, y ejecutar esa cadena como código 05AB1E de forma recursiva.
2. Tampoco hay un isListcomando en 05AB1E, por lo que tuve que usar algunas soluciones para verificar esto mediante el ajuste en una lista, el aplanamiento profundo y la verificación de la igualdad.
3. Y tercero, no hay un aplanamiento para un solo nivel de una lista multidimensional. La función de aplanar ˜es un aplanamiento profundo que elimina todas las capas y convierte una lista multidimensional en una lista única con todos los valores más internos. (es decir, se [[1,2],[[[3]],4]]convierte [1,2,3,4]).

Terminé con el código en la parte superior para superar los tres problemas anteriores. Se divide en tres partes principales. Primero tenemos lo siguiente:

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

La cadena contiene el siguiente código:

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

Se utiliza un mapa en lugar de un bucle foreach, porque el mapa tiene un implícito yy un bucle foreach necesita un explícito y. Sin counter_variableembargo, solo nos preocupamos por el .

Y finalmente, después de que todos los mapas y mapas internos estén hechos, nosotros:

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

Pruébalo en línea!

Obvia implementación recursiva de la especificación.

C, 174 167 152 bytes

Función recursiva f, que pierde memoria ( 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;}

Recursivo fque no pierde, usando referencias, en 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;}

Sin golf:

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

"¿Cómo?", Preguntas, "¿se puede responder esto en C? Seguramente, no hay matrices administradas en C, y realmente no se pueden tener matrices heterogéneas ..."

"Ajá", respondo, "porque he estado trabajando en un sistema simple de" objetos "para (GNU-ish) C11 e ISO C ++ 11".

El programa de demostración completo para esta función es:

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

En este momento, vive aquí y necesitarás ese repositorio para usar esto.

También necesitará la biblioteca de hash Fowler-Noll-Vo libfnv, compilada para su plataforma. Está en ese repositorio y también puede obtenerlo aquí .

Entonces puedes hacer cc -DNODEBUG size.c path/to/libfnv.a -o size.

La implementación no es necesariamente eficiente:

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

¡Pero funciona! El último commit a master (que compiló este programa) fue hace 2 días, lo que significa que este envío es válido.

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

sin golf

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

resultados

(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 caracteres, 48 ​​bytes

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

Esta sería la traducción literal de 'my' Axiom answer here ... En APL, la lista vacía sería ´⍬´ Zilde, que usted indica con ´ [] ´, ´⊂⍬´ es ´ [[]] ´, ´ 1 2 3´ es ´ [1,2,3] ´ ecc Algunas pruebas:

  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     

para imprimir el otro tipo de resultados que propone el ejercicio necesitamos otra función (ambas funciones RS y R deberían estar bien para el ejercicio)

  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

para ver cómo aparecen algunas entradas usamos la función 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
└∊─────────────────────────────────────────────────────────┘

esta impresión de Zilde, y una lista de 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 bytes

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

Pruébalo en línea.

Explicación:

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

Adjunto , 21 bytes

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

Pruébalo en línea!

Resulta que el enfoque de C # es bastante corto en Attache.

Alternativas

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

La entrada tiene que ser una lista, no un vector. Ambos serían compatibles con el uso sequential?.

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

Anterior:

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