Inspirado em Encontre o "tamanho desembrulhado" de uma lista .

Defina o Tamanho Recursivo RS, de uma lista que não contém listas como seu comprimento (número de itens contidos) e o Tamanho Recursivo de uma lista que contém quaisquer listas como a soma de seu comprimento e o Tamanho Recursivo dessas listas.

Desafio

Escreva um programa ou função que produza o Tamanho Recursivo de qualquer lista em tão poucos bytes quanto possível.

A entrada é uma lista e pode conter números, seqüências de caracteres (se o seu idioma os possuir) e listas semelhantes.

Por exemplo:

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

Observe que, se o seu idioma não tiver strings, mas possuir listas de caracteres, os exemplos que contêm "strings"acima podem realmente ser listas de caracteres e ter resultados maiores. Como um exemplo:

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

Isso é código-golfe , então a resposta mais curta em bytes vence; nenhum negócio engraçado, como sempre.

Uma entrada que não seja da lista pode produzir qualquer saída.
A E / S é tão flexível como de costume .

Gelatina , 8 bytes

߀-ŒḊ?‘S

Experimente online!

Como 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 uma não lista, saída 0. Para uma lista, imprima seu comprimento mais a soma das saídas recursivas para seus elementos.

As listas ficam acima dos números e das strings abaixo na ordem do Python 2, exigindo []<=x<''. Em vez disso, verificamos x*0==[], enquanto o resultado de 0para um número ou ''para uma string.

JavaScript (ES6), 39 37 bytes

Guardado 2 bytes graças a @ edc65

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

Mathematica, 20 bytes

Length@Level[#,∞]&

Função anônima. Pega uma expressão como entrada e retorna um número como saída. O caractere Unicode é U + 221E INFINITY para \[Infinity]. Level[#,∞]fornece uma lista das subexpressões da entrada e as Length@conta.

Mathematica, 14 bytes

LeafCount@#-1&

Modificação menor da minha resposta anterior . Como expliquei lá, LeafCountjá cuida de valores atômicos aninhados, mas também conta a lista mais externa, que precisamos subtrair do resultado.

Perl, 34 bytes

Uma função recursiva! Sim, o Perl não apenas possui regex, mas também possui funções!

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

Se você quiser testá-lo, pode executar algo como:

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

Mathematica, 32 bytes

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

Função recursiva sem nome. O trecho #0/@#~Select~ListQchama a função novamente em cada elemento da entrada que é uma lista e Trresume esses valores. Felizmente, o Mathematica não se preocupa em pegar o comprimento da lista vazia e procurar elementos qualificados da lista vazia, portanto, nenhum caso básico é necessário.

Haskell, 52 bytes

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

Exemplo 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 não suporta listas mistas (por exemplo, Int e lista de Int), então eu vou com um tipo de lista personalizado Lque é um elemento de algum tipo a (-> E a) ou uma lista de outros Ls (-> N[L a]). O cálculo do RS é uma recursão simples em que um Econta 1e Num mais a soma dos tamanhos recursivos de seus elementos. A soma total é reduzida em 1, então eu a subtraio via pred.

Nota lateral: os tipos e valores exatos dos elementos não são importantes para o algoritmo, portanto, podemos remover o polimorfismo e lidar apenas com elementos abstratos e prosseguir data L=E|N[L].

Fator, 105 bytes

Função recursiva g.

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

Ungolfed (tipo):

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

Você encontrará que não há chamadas para, lengthporque, em vez de usar o comprimento interno, ele é implementado através drop 1de strings e não-sequências.

Mathematica, 18 bytes

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

Mais uma abordagem do Mathematica. Não é tão curto quanto usar o built-in, LeafCountmas ainda bastante conciso. Isso faz uso do MapAlloperador //@que chama uma função em todos os nós de uma expressão e usamos essa função para incrementar um contador c. Como no LeafCountcaso, isso fornece mais um do que precisamos, porque conta também a cabeça da lista externa e, portanto, iniciamos o contador -1.

C # (compilador interativo do Visual C #) , 50 bytes

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

Experimente online!

Utiliza a mesma técnica que a enviada anteriormente resposta Java , mas utiliza o LINQ para reduzir o tamanho da resposta.

Explicação:

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

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

Experimente online ou verifique todos os casos de teste .

Explicação:

Esse desafio apresenta vários desafios a serem superados no 05AB1E:

1. Embora 05AB1E tenha uma função recursiva desde a reescrita do Elixir ( λ), é útil apenas para seqüências inteiras.Aqui está uma resposta minha como exemplo da função recursiva 05AB1E. Por causa disso, tive que encontrar uma alternativa para fazer chamadas recursivas, o que fiz colocando parte do código em uma sequência e execute essa sequência como código 05AB1E recursivamente.
2. Também não há um isList comando no 05AB1E, então tive que usar algumas soluções alternativas para verificar isso utilizando quebra automática em uma lista, achatamento profundo e verificação de igualdade.
3. E terceiro, não há um achatamento para apenas um nível de uma lista multidimensional. A função de nivelamento ˜é um nivelamento profundo que remove todas as camadas e transforma uma lista multidimensional em uma única lista com todos os valores mais internos. (ou seja, [[1,2],[[[3]],4]]torna-se [1,2,3,4]).

Acabei com o código na parte superior para superar todos os três problemas acima. Está dividido em três partes principais. Primeiro, temos o seguinte:

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

A sequência contém o seguinte 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)

Um mapa é usado em vez de um loop foreach, porque o mapa está implícito ye um loop foreach precisa de um explícito y. Nós nos preocupamos apenas com ocounter_variable .

E finalmente, depois que todos os mapas e mapas internos estiverem prontos, nós:

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

Experimente online!

Implementação recursiva óbvia das especificações.

C, 174 167 152 bytes

Função recursiva f, que vaza memória ( 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;}

Recursiva fque não vaza, usando referências, em 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;}

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

"Mas como, você pergunta," isso pode ser respondido em C? Certamente, não há matrizes gerenciadas em C e você não pode realmente ter matrizes heterogêneas ...? "

"Aha", respondo, "pois tenho trabalhado em um sistema simples de" objetos "para (GNU-ish) C11 e ISO C ++ 11".

O programa de demonstração completo para esta função é:

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

No momento, ele mora aqui e você precisará desse repositório para usar isso.

Você também precisará da biblioteca de hash Fowler-Noll-Vo libfnv, compilada para sua plataforma. Está nesse repositório e você também pode acessá-lo aqui .

Então você pode fazer cc -DNODEBUG size.c path/to/libfnv.a -o size.

A implementação não é necessariamente 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)

Mas funciona! O último commit no master (no qual este programa foi compilado) foi 2 dias atrás, o que significa que esse envio é 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)

destroçado

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 seria a tradução literal da resposta 'my' Axiom aqui ... Na APL, a lista de nulos seria 'Zilde, que você indica com' [], '' é '' ['],' 1 2 3´ é ´ [1,2,3] ´ ecc Alguns testes:

  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 o outro tipo de resultado, o exercício propõe que precisamos de outra função (ambas as funções RS e Rs devem estar ok para o exercício)

  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 como aparecem algumas entradas, usamos a função 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
└∊─────────────────────────────────────────────────────────┘

imprima Zilde e uma 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;}

Experimente online.

Explicação:

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

Anexo , 21 bytes

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

Experimente online!

Acontece que a abordagem C # é bastante curta no 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

A entrada deve ser uma lista, não um vetor. Ambos seriam suportados usando 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)