В этой задаче ваша задача состоит в том, чтобы создать программу, которая принимает вложенный массив и возвращает одномерный плоский массив. Например [10,20,[30,[40]],50]должен выводить [10,20,30,40,50].

Входными данными будет вложенный массив (например, [10,20,[[[10]]]]). Он будет содержать только целые числа (как отрицательные, так и положительные), строки и массивы. Вы можете принять входные данные как аргумент функции, STDIN или любой другой, который подходит вашему языку. Вы можете предположить, что входной массив не будет иметь пустой массив.

Выход

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

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

[10,20,30] -> [10,20,30]
[[10]] -> [10]
[["Hi"],[[10]]] -> ["Hi",10]
[[[20],["Hi"],"Hi",20]] -> [20,"Hi","Hi",20]
[[["[]"],"[]"]] -> ["[]","[]"]

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

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

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

К, 3 байта

,//

Это довольно распространенная идиома. «Присоединяйся, сходись».

попробуйте здесь с ОК .

Как это работает:

Join ( ,) объединяет атомы или списки для создания списка. Over ( /) принимает глагол (в данном случае соединение) и применяет его между каждым элементом списка слева направо. Таким образом, соединение ,/сгладит все элементы верхнего уровня списка. Символ на /самом деле имеет разные значения в зависимости от валентности (числа аргументов) глагола, с которым он составлен. Когда мы предоставляем ,/глагол, финал /действует как «сходящийся» - он многократно применяется ,/к вводу, пока не прекратит изменяться. Некоторые другие языки называют такую ​​функцию «комбинатором с фиксированной точкой». Повторяя слияние списков нижнего уровня, вы в конечном итоге получите единый плоский список, и ни одна из операций не изменит порядок элементов. Кажется, это решает проблему.

JavaScript (ES6), 35 байт

Вдохновленный ответом @ user81655 :

f=a=>a.map?[].concat(...a.map(f)):a

Mathematica, 16 14 байтов

{##&@@#&//@#}&

Безымянная функция, которая принимает и возвращает список, например:

{##&@@#&//@#}& @ {{{20}, {"Hi"}, "Hi", 20}}
(* {20, "Hi", "Hi", 20} *)

объяснение

Синтаксическая сахарная вечеринка!

Чтобы понять , как это работает, обратите внимание , что каждое выражение в Mathematica является либо атом (например , числа, строки, символы) или соединение выражение вида f[a, b, c, ...], где f, a, b, cсами являются произвольными выражениями. Здесь fназывается глава выражения. Все остальное помимо этого - просто синтаксический сахар. Например, {a, b, c}это просто List[a, b, c].

Мы начнем с того, //@что отображает функции на всех уровнях списка. Например:

f //@ {{{20}, {"Hi"}, "Hi", 20}}
(* f[{f[{f[{f[20]}], f[{f["Hi"]}], f["Hi"], f[20]}]}] *)

Обратите внимание, что это сопоставляет fатомы, а также составные выражения. Сейчас мы ищем способ избавиться от заголовков списка и сохранить все остальное.

ApplyФункция обычно используется для подачи элементов списка в виде отдельных аргументов функции, но его фактическое определение является более общим и просто заменяет главу выражения. Например Apply[g, f[a, b]]дает g[a, b].

Теперь есть специальная «голова» под названием, Sequenceкоторая просто исчезает. Например, {a, Sequence[b, c], d}просто оценивает {a, b, c, d}. Идея выравнивания списка состоит в том, чтобы заменить заголовки всех внутренних списков Sequenceтак, чтобы они попали в окружающий их список. Так что мы хотим, чтобы Applyголова Sequenceк спискам. Удобно, если мы Applyчто- то добавляем к атому, он просто оставляет атом неизменным, поэтому нам вообще не нужно различать типы выражений.

Наконец, есть одна маленькая проблема: fтакже применяется к внешнему уровню, так что он также удаляет самый внешний List, что нам не нужно. Самый короткий способ противостоять этому - просто снова обернуть результат в список, чтобы окружение Sequenceмогло безопасно исчезнуть.

Обратите внимание, что нет Applyни Sequenceв коде. @@является операторской формой Applyи ##&является стандартной игрой в гольф для сокращения длинного встроенного имени Sequence. Так что немного раскусывая, мы получаем что-то вроде:

flatten[list_] := { MapAll[Apply[Sequence], list] }

Для получения более подробной информации о том, как и почему ##&работает, см. Раздел «Последовательности аргументов» в моем ответе на советы Mathematica .

Python 2, 43 байта

f=lambda l:[l]*(l*0!=[])or sum(map(f,l),[])

В списке рекурсивно обращается к элементам и объединяет результаты. На строке или числе, в единственном списке.

К сожалению, Python 2 упорядочивает типы int < list < stringсэндвичей listмежду остальными, что требует проверки двух неравенств. Таким образом, вместо этого l*0проверяется пустой список [], в противном случае дает 0или "".

Рубин, 43 42 34 байта

Рекурсивное решение. Теперь с обработкой исключений! (можно также отдать должное @akostadinov за поддержку изменений)

f=->a{a.map(&f).inject:+rescue[a]}

IDEOne ссылка

JavaScript (ES6), 41 байт

f=a=>[].concat(...a.map(v=>v.pop?f(v):v))

<textarea id="input" rows="6" cols="40">[[[20],["Hi"],"Hi",20]]</textarea><br /><button onclick="result.textContent=JSON.stringify(f(eval(input.value)))">Go</button><pre id="result"></pre>

Perl 6 , 24 байта

{gather {$_».&{.take}}}

Объяснение:

{ # has $_ as an implicit parameter

  gather {

    $_\ # the parameter from the outer block
    »\  # for each single value in the structure
    .&( # call the following block as if it was a method
      { # this block has its own $_ for a parameter
        .take # call the .take method implicitly on $_
      }
    )
  }
}

Тест:

#! /usr/bin/env perl6

use v6.c;
use Test;

my &flatten = {gather {$_».&{.take}}}

my @tests = (
  [10,20,30], [10,20,30],
  [[10,],], [10,],
  [["Hi",],[[10,],],], ["Hi",10],
  [[["[]",],"[]"],], ["[]","[]"],
);

plan @tests / 2;

for @tests -> $input, $expected {
  # is-deeply cares about the exact type of its inputs
  # so we have to coerce the Seq into an Array
  is-deeply flatten($input).Array, $expected, $input.perl;
}

1..4
ok 1 - $[10, 20, 30]
ok 2 - $[[10],]
ok 3 - $[["Hi"], [[10],]]
ok 4 - $[[["[]"], "[]"],]

Haskell, 43 байта

data D a=L a|N[D a]
f(L x)=[x]
f(N l)=f=<<l

У Haskell нет ни вложенных списков с различной глубиной подсписков, ни смешанных типов для элементов списка. Для вложения я определяю пользовательский тип данных, Dкоторый является либо листом, Lкоторый содержит некоторый элемент, либо узлом, Nкоторый является списком Ds. Для смешанных элементов здесь используется предопределенный тип данных, Eitherкоторый объединяет два типа в один Either String Integer. Новый типD и функция flatten fполностью полиморфны в типе листовых элементов, поэтому мне не нужно особо заботиться о чем-либо Either.

Пример использования: f (N[N[L(Right 20)], N[L(Left "Hi")], L(Left "Hi") , L(Right 20)])-> [Right 20,Left "Hi",Left "Hi",Right 20].

Pyth, 7 6 5 байт

us+]Y

Попробуйте онлайн: демонстрация или тестовый набор

Но, конечно же, есть встроенная функция, которая обрабатывает задачу всего за 2 байта: .n( Test Suite )

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

f=a=>a.map?[for(b of a)for(c of f(b))c]:[a]

Просто потому, что я мог даже избежать использования concat.

Perl, 34 29 байт

Функции.

Если нужно сгладить список вроде my @a = f(@a), 29 байт:

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

Проверьте это на Ideone

Если необходимо сгладить массив как ref my $a = f($a), 34 байта:

sub f{[map{ref()?@{f(@$_)}:$_}@_]}

Проверьте это на Ideone .

Perl 5.22.0+, 27 байт

Благодаря Хоббс .

Если нужно сгладить список вроде my @a = f(@a)27 байтов:

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

Проверьте это на JDoodle

Если необходимо сгладить массив как ref my $a = f($a), 32 байта:

sub f{[map{ref?@{f(@$_)}:$_}@_]}

Проверьте это на JDoodle .

Юлия, 29 байт

f(x,y=vcat(x...))=x==y?x:f(y)

Это рекурсивное разделение на конкатенационные функции до достижения фиксированной точки. пример

julia> f([1,[2,[3,[4,[5,[6]]]]]])
6-element Array{Int64,1}:
 1
 2
 3
 4
 5
 6

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

1>`("(\\.|[^"])+")|[][]
$1
$
]

Попробуйте онлайн! (Первая строка используется только для запуска нескольких тестовых случаев одновременно.)

Retina не имеет понятия массивов, строковых литералов или чисел, поэтому я решил использовать «общий» формат ввода [...,...]массивов стилей и "строк -delimited, где \можно использовать внутри строк для экранирования любого символа (в частности "и \самого себя).

Сама программа просто сопоставляет либо полную строку, либо квадратные скобки, и заменяет их тем, $1что сохраняет строки и удаляет квадратные скобки. Предел 1>пропускает первый матч, чтобы мы не удаляли ведущие[ . Тем не менее, это удаляет трейлинг ], поэтому мы добавляем его обратно на отдельном этапе.

Пайк, 11 байт

.F~]+=])K~]

Попробуй это здесь!

Объяснение:

.F~]+=])    - Deep for loop
  ~]        -    contents of `]` ([] by default)
    +       -  ^+i
     =]     - `]` = ^
        K~] - Output value
        K   - Remove the output from the for loop
         ~] - Return the contents of `]`

Или 7 байт после исправления

M?+]K~]

Попробуй это здесь!

Объяснение:

M?+]    - Deep map
 ?+]    -  `]` = `]`+i
    K~] - Output value
    K   - Remove the output from the for loop
     ~] - Return the contents of `]`

Или даже 2 байта, если печать на стандартный вывод разрешена (это может быть встроено)

M
<newline required>

Попробуй это здесь!

Это глубоко применяет print_newlineфункцию к каждому непоследовательному элементу на входе и рекурсивным элементам последовательности.

Java (v8) 390 276 байт

public static Object[] f(final Object[]a) {
    List<Object>r=new ArrayList<>();boolean t=false;int n=0;
    for(final Object p:a)
        if(t=p instanceof Object[]){for(final Object q:(Object[])p) r.add(q);}
        else r.add(p);
    return(t)?f(r.toArray()):r.toArray();
}  

Просто для полноты и все такое. :) Не могу сказать, что Java-код эффективен.

Python, 57 байт

f=lambda a:sum([list==type(x)and f(x)or[x]for x in a],[])

Попробуйте онлайн: Python 2 , Python 3

Спасибо Кевину Лау за list==type(x)трюк.

Рубин

есть встроенный flattenметод.

Вы можете запустить здесь: http://www.tutorialspoint.com/execute_ruby_online.php

Один 43 байта, но думал поделиться:

f=->a{a.inject([]){|r,e|r+(f[e]rescue[e])}}

Один 45 байт, который более эффективен, чем предыдущий, а другой ответ ruby:

f=->a{a.map{|e|Array===e ?f[e]:[e]}.inject:+}

вот эталон:

require 'benchmark'
n=10^9
arr=[[[20],[[[[[[[[123]]]]]]]],"ads",[[[[[[[4]]]]]]],5,[[[[[[[[[[6]]]]]]]]]],7,8,[[[[[[[[[[9]]]]]]]]]],[[[[[[[[[[0]]]]]]]]]],[[[[[[[[[[[["Hi"]]]]]]]]]]]],[[[[[["Hi"]]]]]],[[[[[20]]]]]]]
Benchmark.bm do |x|
  x.report { f=->a{a.map(&f).inject:+rescue[a]}; f[arr] }
  x.report { f=->a{a.map{|e|e!=[*e]?[e]:f[e]}.inject:+}; f[arr] }
  x.report { f=->a{a.inject([]){|r,e|r+(f[e]rescue[e])}}; f[arr] }
  x.report { f=->a{a.map{|e|Array===e ?f[e]:[e]}.inject:+}; f[arr] }
end

результат:

       user     system      total        real
   0.010000   0.000000   0.010000 (  0.000432)
   0.000000   0.000000   0.000000 (  0.000303)
   0.000000   0.000000   0.000000 (  0.000486)
   0.000000   0.000000   0.000000 (  0.000228)

Perl, 39 34 + 1 (-p флаг) 35 байт

Один лайнер. Вдохновленный Мартином Бюттнером .

#!perl -p
s/("(\\.|[^"])+"|]$|^\[)|[][]/$1/g

Проверьте это на Ideone .

Clojure, 68 байт

(def f #(if(some vector? %)(f(mapcat(fn[z](if(vector? z)z[z]))%))%))

mapcatсначала применяет функцию к каждому элементу, а затем объединяет результаты. Таким образом, каждый раз, когда он совпадает, один «уровень вложенности» теряется. Concat не работает с не последовательностями, поэтому элементы должны быть обернуты в вектор, если они не являются векторными.

Вы можете попробовать это здесь: http://www.tryclj.com

(f [[[20],["Hi"],"Hi",20]])
(f [[["[]"],"[]"]])

ANSI C, 193 байта

#define b break;
#define c case
#define p putch(_);
char f;main(_){switch(_){c 1:putch(91);b c 34:f^=1;p b c 91:f&&p b c 93:f&&p b c 10:c 13:putch(93);return;default:p}_=getch();main(_);}

:-/, какие-либо предложения? Кстати, я попытался найти сетевой источник для компиляции, но WL строго для этого кода для компиляции. В противном случае он будет работать для VS и GCC.

JavaScript 20 байт

a=>(a+[]).split(',')

Массив + массив равен array.toString

C #, 48 байтов

()=>{$"[{i.Replace("[","").Replace("]","")}]";};

Думал, что я также опубликую это, так как никто еще не дал решения C #. Предложения приветствуются!

Ракетка, 63 байта

(define(f l)(apply append(map(λ(x)(if(list? x)(f x)`(,x)))l)))

Java 8 165 символов

import java.util.*;<T>T[]f(T[]a){List<T>l=new ArrayList<>();for(T e:a)if(e instanceof Object[])Collections.addAll(l,f((T[])e));else l.add(e);return(T[])l.toArray();}

Развёрнутый в классе:

public class Q80096 {

    public static <T> T[] flatten(T[] array) {
        List<T> flattenedList = new ArrayList<>();
        for (T element : array)
            if (element instanceof Object[])
                 Collections.addAll(flattenedList, flatten((T[]) element));
            else
                flattenedList.add(element);
        return (T[]) flattenedList.toArray();
    }
}

Этот ответ основан на подходе Джереми Хартона . Я использовал его, изменил его в некоторых местах и ​​создал более похожую на гольф версию.

JavaScript, 17 байт

a=>eval(`[${a}]`)

Наконец, преобразование типов JavaScript может быть полезно! Обратите внимание, что это на самом деле будет выводить массив, но преобразование строки (помещение его в HTML) делает его списком, разделенным запятыми.

Если разделенные запятыми списки допустимы, то допустимо следующее:

7 байт

a=>""+a

ПРИМЕЧАНИЕ: фрагмент по какой-то причине сломан

var subject = 
  a=>eval(`[${a}]`)

<input oninput="try {output.innerHTML = subject(this.value)} catch(e) {output.innerHTML='Invaild Input'}" />
<div id="output"></div>

PHP, 73 байта

<?array_walk_recursive($_GET,function($i)use(&$r){$r[]=$i;});print_r($r);

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

{Reap[Sow@>_]}

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

К счастью, в Attache есть оператор «векторизации», который применяет функцию к атомам списка. В этом случае все, что нам нужно сделать, это настроить жнец с Reapи Sowвсе атомы входа _с@> . Я думаю, что это довольно элегантно.

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

15 байтов: Fixpoint{`'^^_}

16 байтов: Fixpoint!&Concat

17 байтов: {q:=[]q&Push@>_q}

17 байтов: Fixpoint[&Concat]

Эликсир , 74 байта

def d(l)do l|>Stream.flat_map(fn x->if is_list(x)do d(x)else[x]end end)end

Первый ответ Elixir, так что, возможно, можно немного поиграть в гольф.

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

Объяснение:

def d(l)do l|>            # Recursive method taking a list as input:
  Stream.flat_map(fn x->  #  Map over each item `x` of the input-list:
    if is_list(x)do       #   If `x` is a list itself:
      d(x)                #    Do a recursive call with `x`
    else                  #   Else:
      [x]                 #    Simply leave `x` unchanged
    end                   #   End of the if-else statements
  end)                    #  End of the map
end                       # End of the recursive method

Конечно, если встроенные функции были разрешены, это могло бы быть 25 байтов вместо этого:

fn(l)->List.flatten(l)end

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

Желе , 4 байта

;/ÐL

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

объяснение

;/   | Reduce by concatenation
  ÐL | Loop until no further changes

Встроенный Fбудет один байт, если это разрешено.

Wolfram Language (Mathematica) , 13 байт

#~Level~{-1}&

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

Un-golfed: F[x_] := Level[x, {-1}]

выбирает элементы структуры на последнем уровне ее древовидной формы . Я не уверен, что это считается «избегать встроенных» (что будет Flatten).