_{Примечание. Это №2 в серии задач по манипулированию массивами . Для предыдущего вызова нажмите здесь .}

Разделение вложенных списков

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

То есть этот список:

[1, [2, 3], [4, 4, [5, 2], 1]]

Станет:

[1, [2], [3], [4], [4], [[5]], [[2]], [1]]

Соревнование

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

Вы можете отправить функцию, которая принимает список в качестве аргумента, или полную программу, которая выполняет ввод / вывод.

Поскольку это код-гольф , выигрывает самое короткое представление (в байтах)! *

_{* Стандартные лазейки для гольфа запрещены. Вы знаете, что делать.}

Тестовые случаи

Входные списки будут содержать только целые числа в стандартном целочисленном размере вашего языка. Чтобы избежать языковых ограничений, мешающих им конкурировать, значения не будут вкладываться на глубину более 10.

Вы можете предположить, что входные данные не будут иметь пустых подсписков: например, - [[5, []]]не будет дано. Тем не менее, основной список может быть пустым.

[]            ->  []

[[1, 2]]      ->  [[1], [2]]
[3, [4, 5]]   ->  [3, [4], [5]]
[3, [3, [3]]] ->  [3, [3], [[3]]]
[[6, [[7]]]]  ->  [[6], [[[7]]]]
[[5, 10], 11] ->  [[5], [10], 11]

Не стесняйтесь оставлять комментарии, если я пропустил угловой случай.

пример

Я бросил вместе быстрый (ungolfed) Python решение 3 в качестве примера - вы можете проверить его на repl.it .

Брахилог , 16 байт

:{##:0&:ga|g}ac|

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

объяснение

Example input: [1:[2:3]]

:{          }a     Apply the predicate below to each element of the list: [[1]:[[2]:[3]]]
              c    Concatenate: Output = [1:[2]:[3]]
               |   Or: Input = Output = []

  ##                 Input is a list: e.g. Input = [2:3]
    :0&              Call recursively the main predicate with this input: [2:3]
       :ga           Group each element in a list: Output = [[2]:[3]]
          |          Or (not a list): e.g. Input = 1
           g         Group into a list: Output = [1]

Mathematica, 24 21 байт

##&@@List/@#0/@#&/@#&

или один из них:

##&@@List/@#&/@#0/@#&
##&@@List@*#0/@#&/@#&
##&@@List/@#&@*#0/@#&

объяснение

Причина, по которой это так коротко, состоит в том, что это в основном рекурсия, которая не требует явного базового случая.

Здесь много синтаксического сахара, поэтому давайте начнем с того, что раскусим это. &обозначает безымянную функцию слева от нее, аргумент которой записывается как #. Внутри эта функция #0относится к самой функции, которая позволяет писать безымянные рекурсивные функции. Но давайте начнем с присвоения внутренней функции имени и извлечения его:

f[x_] := ##& @@ List /@ f /@ x
f /@ # &

Другим важным синтаксическим сахаром является то, f/@xчто является сокращением, Map[f, x]т. Е. Он вызывает fкаждый элемент x. Причина f[x_] := ... f /@ xне приводит к бесконечной рекурсии в том, что отображение чего-либо на атоме оставляет атом неизменным без фактического вызова функции. Следовательно, нам не нужно явно проверять базовый случай (текущий элемент - целое число).

Таким образом, функция fсначала возвращается к самому глубокому списку внутри x, после чего f/@становится недоступной . Тогда мы называем использование ##& @@ List /@на этом. Отображение Listпо списку просто оборачивает каждый элемент в отдельный список, поэтому {1, 2, 3}становится {{1}, {2}, {3}}. Затем мы применяем ##& к нему, что означает, что заголовок (то есть внешний список) заменяется на ##&, так что это превращается в ##&[{1}, {2}, {3}]. Но ##&просто возвращает свои аргументы какSequence (который вы можете рассматривать как развернутый список или своего рода оператор «splat» в других языках).

Таким образом, ##& @@ List /@превращает список {1, 2, 3}в {1}, {2}, {3}(вид, что последняя вещь на самом деле завернута в головуSequence , но она исчезает, как только мы используем значение где-либо).

Это оставляет вопрос, почему fсамо по себе не является решением проблемы. Проблема в том, что внешний список должен обрабатываться по-разному. Если у нас есть вклад, {{1, 2}, {3, 4}}мы хотим, {{1}, {2}, {3}, {4}}а нет {{1}}, {{2}}, {{3}}, {{4}} . Мое оригинальное решение исправило это, передав окончательный результат в виде списка аргументов, Joinкоторый восстановил бы внешний уровень списков, но этот просто пропускает внешний уровень, используя f себя в карте на выходе. Следовательно, fприменяется только к отдельным элементам внешнего списка и никогда не касается этого списка.

Что касается других трех решений, то первое просто применяет рекурсию, за пределами fкоторой работает так же хорошо. Два других решения избегают повторной Mapоперации, сначала объединяя две функции, а затем отображая результат только один раз.

J , 19 18 байт

(<@]/@,~>)S:0 1{::

Это анонимный глагол, который принимает и возвращает коробочные массивы, которые являются J (довольно громоздкой) версией вложенных массивов. Посмотрите, как пройти все тестовые случаи.

объяснение

При этом используются несколько экзотические операции {::( map ) и S:( spread ), которые работают с массивами в штучной упаковке. {::заменяет каждый лист в штучной упаковке путь к этому листу. S:применяет данный глагол к заданной глубине вложения, а затем разбивает результаты в массив.

(<@]/@,~>)S:0 1{::  Input is y.
(        )          Let's look at this verb first.
        >           Open the right argument,
      ,~            append the left argument to it,
    /               then reduce by
 <@]                boxing. This puts the left argument into as many nested boxes
                    as the right argument is long.
                    This verb is applied to y
               {::  and its map
            0 1     at levels 0 and 1.
                    This means that each leaf of y is paired with its path,
                    whose length happens to be the nesting depth of y,
                    and the auxiliary verb is applied to them.
          S:        The results are spread into an array.

R, 199 байт

function(l){y=unlist(l);f=function(x,d=0){lapply(x,function(y){if(class(y)=='list'){f(y,d=d+1)}else{d}})};d=unlist(f(l));lapply(1:length(d),function(w){q=y[w];if(d[w]){for(i in 1:d[w])q=list(q)};q})}

Этот вопрос был трудным. Списки R немного странные, и абсолютно не просто зациклить все элементы подсписков. Также непросто определить глубину этого списка. Затем возникает задача воссоздать список со всеми разделенными элементами, поэтому нам также необходим способ адаптивного создания списка определенной глубины.

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

  f=function(x,d=0){
    lapply(x,function(y){
      if(class(y)=='list'){
        f(y,d=d+1)
      } else {
        d
      }})
  }

Когда мы unlist(l)сохраняем глубину каждой записи вектора , dмы неявно создаем список lapplyи заполняем его следующей функцией:

  lapply(1:length(d),function(w){
    q=y[w]
    if(d[w]){
      for(i in 1:d[w]){
        q=list(q)
      }
    }
    q
  })

В этом вызове apply мы создаем объект qсо значением записи в списке, проверяем его глубину и проверяем, не равен ли он нулю. Если он равен нулю, мы можем просто оставить его как числовое значение. Если он ненулевой, нам нужно вложить его в такое количество списков. Таким образом, мы вызываем цикл for dи повторяем вызов q=list(q).

lapplyзатем помещает все эти значения qв список, создавая желаемый результат.

Полная программа с правильным интервалом и такими:

function(our.list){
  values <- unlist(our.list)
  f <- function(part.list, depth = 0){
    lapply(part.list, function(y){
      if(class(y)=='list'){
        f(y, depth <- depth + 1)
      } else {
        return(depth)
      }})
  }
  depths <- unlist(f(our.list))
  new.list <- lapply(1:length(depths), function(w){
    q <- values[w]
    if(depths[w] != 0){
      for(i in 1:depths[w]){
        q <- list(q)
      }
    }
    return(q)
  })
  return(new.list)
}

Сетчатка , 34 байта

+`(.(?>()\[|(?<-2>)]|.)+)\2,
$1],[

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

C (gcc), 147 байтов

d=0,l,i;
P(n,c){for(;n--;)putchar(c);}
main(c){for(;~(c=getchar());l=i)i=isdigit(c),P((l<i)*d,91),P(i,c),P((l>i)*d,93),P(l>i,32),d+=(92-c)*(c>90);}

Пример ввода:

1 [23 3] [40 4 [5 2] 1]

Пример вывода:

1 [23] [3] [40] [4] [[5]] [[2]] [1]

сложенный , неконкурентный, 25 байтов

{e d:e$wrap d 1-*}cellmap

Это функция, которая изменяет верхний элемент стека. Если вы хотите истинную функцию, просто добавьте [и ]в начало и в конец. Попробуй это здесь!

Вот читаемая версия:

{ arr :
  arr { ele depth :
    ele   $wrap depth 1- * (* execute wrap n times, according to the depth *)
  } cellmap (* apply to each cell, then collect the results in an array *)
} @:a2
(1 (2 3) (4 4 (5 2) 1)) a2 out

Прецедент:

(1 (2 3) (4 4 (5 2) 1))    (* arg on TOS *)
{e d:e$wrap d 1-*}cellmap
out                        (* display TOS *)

Вывод без перевода строки:

(1 (2) (3) (4) (4) ((5)) ((2)) (1))

PHP, 101 94 байта

спас 1 байт благодаря @Christoph, сохранил еще 6 вдохновленных этим.

function s($a){foreach($a as$b)if($b[0])foreach(s($b)as$c)$r[]=[$c];else$r[]=$b;return$r?:[];}

рекурсивная функция, довольно прямолинейная

сломать

function s($a)
{
    foreach($a as$b)                // loop through array
        if($b[0])                       // if element is array
            foreach(s($b)as$c)$r[]=[$c];    // append separated elements to result
        else$r[]=$b;                    // else append element to result
    return$r?:[];                   // return result, empty array for empty input
}

Python 2, 122 106 байт

Довольно ужасная оценка, просто прямая реализация.

Спасибо @Zachary T за помощь в сохранении 16 байтов!

def x(l,a=[],d=0):
 n=lambda b:b and[n(b-1)]or l
 if'['in`l`:[x(e,a,d+1)for e in l];return a
 else:a+=n(d)

Вызов xс одним аргументом для запуска. По какой-то причине он может быть запущен только один раз.

JavaScript (Firefox 30-57), 53 байта

f=a=>[for(e of a)for(d of e.map?f(e):[e])e.map?[d]:d]

Лучший ответ ES6, который у меня есть, составляет 76 байт:

f=(a,r=[],d=0)=>a.map(e=>e.map?f(e,r,d+1):r.push((n=d=>d?[n(d-1)]:e)(d)))&&r

Pyth - 29 байт

.b]FYt-F/LN`[)PsM._:`Q"\d"3.n

Тестовый пакет .

Perl 6 , 60 47 байт

sub f{[$_~~List??|([$_] for .&f)!!$_ for |$^a]}

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

Объяснение:

1. [... for |$^a]: Переберите входной массив и создайте из него новый массив.
2. $_ ~~ List ?? ... !! ...: Для каждого элемента проверьте, является ли он самим массивом.
3. |([$_] for .&f)Если элемент является массивом, рекурсивно примените к нему функцию, переберите элементы нового массива, возвращенного этим рекурсивным вызовом, оберните каждый элемент в свой собственный массив и вставьте их во внешний список.
4. $_: Если элемент не является массивом, передайте его как есть.

Haskell, 71 байт

data L=N Int|C[L] 
d#C l=((C .pure.d)#)=<<l
d#n=[d n]
f(C l)=C$(id#)=<<l

Опять же, я должен определить свой собственный тип списка, потому что списки natives в Haskell не могут быть произвольно вложенными. Этот новый тип Lможет быть возвращен из функции, но не может быть напечатан по умолчанию, поэтому, чтобы увидеть результат, я определяю showэкземпляр для L:

instance Show L where
  show (N n)=show n
  show (C l)=show l

Теперь мы можем сделать тест в REPL:

*Main> f $ C[N 1, C[N 2, N 3], C[N 4, N 4, C[N 5, N 2], N 1]]
[1,[2],[3],[4],[4],[[5]],[[2]],[1]]

*Main> f $ C[C[N 6, C[C[N 7]]]]
[[6],[[[7]]]]

Как это работает: простая рекурсия, которая проходит уровень вложенности как функция Cконструкторов. Мы начинаем с функции идентификации idи всякий раз, когда есть список (-> сопоставление с образцом d#C l=), мы добавляем дополнительный слой C(-> C .pure.d) к рекурсивному вызову #всех элементов списка. Если мы встречаем число, мы просто применяем функцию nesting-level dк числу.

APL (Dyalog) , 44 байта *

Функция анонимного молчаливого префикса. Принимает вложенный список APL в качестве аргумента и возвращает вложенный массив APL.

∊{⊃⊂⍣⍵,⍺}¨{⊃¨(j∊⎕D)⊆+\-⌿'[]'∘.=j←⎕JSON⍵}

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

{… } Применить следующую явную функцию, где аргумент представлен ⍵:

 ⎕JSON⍵ преобразовать аргумент в JSON

 j← хранить в j

 '[]'∘.= таблица, в которой jравны открытые (верхний ряд) и закрытые (нижний ряд) скобки

 -⌿ верхний ряд минус нижний ряд (уменьшение вертикальной разности)

 +\ накопленная сумма (это дает уровень вложенности для каждого символа)

 (… )⊆ Раздел, начинающий новый раздел, если 1 не предшествует 1 в…

  j∊⎕D где каждый символ jявляется членом множества D igits

 ⊃¨ выберите первый из каждого (это дает уровень вложенности для каждого многозначного числа)

∊{… }¨ Применить следующую функцию к каждому уровню вложения ( ⍵), используя соответствующий элемент из аргумента ϵ nlisted (плоский) в качестве левого аргумента (⍺ ):

 ,⍺ ravel (listify) число (потому что скаляры не могут быть вложены)

 ⊂⍣⍵ приложить ⍵раз

 ⊃ раскрыть (потому что самый внутренний список сам по себе является приложением)

^{* Использование Dyalog Classic , с ⎕ML←3( по умолчанию на многих системах), подставляя ⊂для ⊆и ↑для ⊃. Тио!}