Вдохновленный найти «развернутый размер» списка .

Определите Рекурсивный размер RSсписка, не содержащего списков, в качестве его длины (количество содержащихся элементов) и Рекурсивный размер списка, содержащего любые списки, в виде суммы его длины и Рекурсивного размера этих списков.

Вызов

Напишите программу или функцию, которая выводит Рекурсивный Размер любого заданного списка в минимально возможном количестве байтов.

Входные данные являются списком и могут содержать числа, строки (если они есть на вашем языке) и аналогичные списки.

Например:

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

Обратите внимание, что если в вашем языке нет строк, но есть списки символов, приведенные "strings"выше примеры могут фактически быть списками символов и иметь большие результаты. В качестве примера:

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

Это код-гольф , поэтому выигрывает самый короткий ответ в байтах; без смешных дел, как всегда.

Не входящий в список ввод может привести к любому выводу.
Ввод / вывод такой же гибкий, как обычно .

Желе , 8 байт

߀-ŒḊ?‘S

Попробуйте онлайн!

Как это устроено

߀-ŒḊ?‘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 байта

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

Для не-списка выведите 0. Для списка выведите его длину плюс сумму рекурсивных выходов для его элементов.

Списки располагаются над числами и под строками в порядке Python 2, требуя []<=x<''. Вместо этого мы проверяем x*0==[], тогда как результат 0для числа или ''для строки.

JavaScript (ES6), 39 37 байт

Сохранено 2 байта благодаря @ edc65

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

Mathematica, 20 байтов

Length@Level[#,∞]&

Анонимная функция. Принимает выражение в качестве ввода и возвращает число в качестве вывода. Символ Unicode имеет значение U + 221E INFINITY для \[Infinity]. Level[#,∞]дает список подвыражений ввода и Length@считает их.

Mathematica, 14 байтов

LeafCount@#-1&

Незначительная модификация моего предыдущего ответа . Как я объяснил там, он LeafCountуже заботится о вложенных атомарных значениях, но он также учитывает самый внешний список, который нам нужно вычесть из результата.

Perl, 34 байта

Рекурсивная функция! Да, в Perl есть не только регулярные выражения, но и функции!

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

Если вы хотите проверить это, вы можете запустить что-то вроде:

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

Mathematica, 32 байта

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

Безымянная рекурсивная функция. Отрывок #0/@#~Select~ListQснова вызывает функцию для каждого элемента ввода, являющегося списком, и Trсуммирует эти значения. К счастью, Mathematica хорошо берет длину пустого списка и ищет подходящие элементы из пустого списка, поэтому базовый случай не требуется.

Haskell, 52 байта

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

Пример использования:

*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 не поддерживает смешанные списки (например, Int и список Int), поэтому я использую пользовательский тип списка, Lкоторый является элементом некоторого типа a (-> E a) или списком других Ls (-> N[L a]). Вычисление RS представляет собой простую рекурсию, в которой Eсчетчик 1и Nединица плюс сумма рекурсивных размеров его элементов. Вся сумма на 1, поэтому я вычитаю ее через pred.

Примечание: точные типы и значения элементов не важны для алгоритма, поэтому мы можем удалить полиморфизм, заключив сделку только с абстрактными элементами, и продолжить data L=E|N[L].

Фактор, 105 байт

Рекурсивная функция g.

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

Ungolfed (вроде):

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

Вы обнаружите, что здесь нет вызовов, lengthпотому что вместо встроенной длины он реализован drop 1для строк и непоследовательностей.

Mathematica, 18 байт

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

Еще один подход Mathematica. Не так коротко, как при использовании встроенного, LeafCountно все же довольно лаконично. Это использует MapAllоператор, //@который вызывает функцию на каждом узле выражения, и мы используем эту функцию для увеличения счетчика c. Как и в LeafCountслучае, это дает на один больше, чем нам нужно, потому что он также считает внешний список, поэтому мы начинаем счетчик с -1.

C # (интерактивный компилятор Visual C #) , 50 байтов

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

Попробуйте онлайн!

Использует ту же технику, что и ранее представленный ответ Java , но использует LINQ для уменьшения длины ответа.

Объяснение:

// 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 (наследие), 22 17 байт

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

Попробуйте онлайн или проверьте все контрольные примеры .

Объяснение:

Эта проблема ставит множество проблем, которые необходимо преодолеть в 05AB1E:

1. Хотя 05AB1E имеет рекурсивную функцию после Elixir rewrite ( λ), она полезна только для целочисленных последовательностей. Вот мой ответ в качестве примера рекурсивной функции 05AB1E. Из-за этого мне пришлось найти альтернативу для выполнения рекурсивных вызовов, что я сделал, поместив часть кода в строку, и рекурсивно выполнил эту строку как код 05AB1E.
2. В isList05AB1E также нет команды, поэтому мне пришлось использовать некоторые обходные пути, чтобы проверить это, используя перенос в список, глубокое выравнивание и проверку на равенство.
3. И, в-третьих, не существует единого уровня для одного уровня многомерного списка. Функция flatten ˜- это функция глубокого сглаживания, которая удаляет все слои и делает многомерный список одним списком со всеми самыми внутренними значениями. (то есть [[1,2],[[[3]],4]]становится [1,2,3,4]).

Я закончил с кодом наверху, чтобы преодолеть все три вышеупомянутых проблемы. Он разделен на три основные части. Сначала мы имеем следующее:

"..."        # Create a string with 05AB1E code
     ©       # Save this string in the register (without popping)
      .V     # Execute the string as 05AB1E 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)

Карта используется вместо цикла foreach, потому что карта имеет неявный y, а цикл foreach требует явного y. Мы заботимся только о counter_variable.

И, наконец, после того, как все карты и внутренние карты будут готовы, мы:

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

R 65 байт

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

Попробуйте онлайн!

Очевидная рекурсивная реализация спец.

C 174 167 152 байта

Рекурсивная функция с fутечкой памяти ( 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;}

Рекурсив, fкоторый не пропускает, используя ссылки, на 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;
}

«Но как, - спросите вы, - можно ли ответить на это в C? Конечно, в C нет управляемых массивов, и вы не можете иметь гетерогенные массивы…?»

«Ага, - отвечаю я, - потому что я работал над простой системой« объектов »для (GNU-ish) C11 и ISO C ++ 11».

Полная демонстрационная программа для этой функции:

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

Прямо сейчас, он живет здесь, и вам понадобится репо, чтобы использовать это.

Вам также понадобится хеш-библиотека Fowler-Noll-Vo, libfnvскомпилированная для вашей платформы. Он находится в этом хранилище, и вы также можете получить его здесь .

Тогда вы можете сделать cc -DNODEBUG size.c path/to/libfnv.a -o size.

Реализация не обязательно эффективна:

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

Но это работает! Последний коммит на мастере (на котором скомпилирована эта программа) был 2 дня назад, что означает, что это утверждение действительно.

Аксиома 118 байт

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

Результаты

(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 символа, 48 байтов

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

Это было бы буквальным переводом ответа «моя» Аксиома здесь ... В APL список недействительности будет «Zilde», который вы укажете с помощью ´ [] ´, ´ is´ is ´ [[]] ´, ´ 1 2 3´ is ´ [1,2,3] ´ ecc Некоторые тесты:

  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     

для печати результатов другого типа, предложенных в упражнении, нам нужна еще одна функция (обе функции RS и R должны быть в порядке для упражнения)

  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

чтобы увидеть, как появляются некоторые входные данные, мы используем функцию 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
└∊─────────────────────────────────────────────────────────┘

это печать Zilde и один список 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 байт

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

Попробуйте онлайн.

Объяснение:

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

Атташе , 21 байт

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

Попробуйте онлайн!

Оказывается, подход C # довольно короток в Attache.

альтернативы

25 байт f[x]:=#x+Sum!f=>IsArray\x

26 байт f[x]:=#x+Sum[f=>IsArray\x]

35 байт f:=Sum##{If[IsArray@_,1+f@_,1]}=>Id

35 байт f:=Sum@Map[{If[IsArray@_,1+f@_,1]}]

37 байт f[x]:=Sum[{If[IsArray@_,1+f@_,1]}=>x]

Clojure, 79 77 51 байт

Входные данные должны быть списком, а не вектором. Оба будут поддерживаться с помощью sequential?.

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

Предыдущая:

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

Python, 72 байта

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