W tym wyzwaniu Twoim zadaniem jest stworzenie programu, który przyjmuje zagnieżdżoną tablicę i zwraca jednowymiarową spłaszczoną tablicę. Na przykład [10,20,[30,[40]],50]powinien wyjść [10,20,30,40,50].

Dane wejściowe będą tablicą zagnieżdżoną (np. [10,20,[[[10]]]]). Będzie zawierać tylko liczby całkowite (zarówno ujemne, jak i dodatnie), łańcuchy i tablice. Możesz wziąć dane wejściowe jako argument funkcji, STDIN lub cokolwiek, co pasuje do twojego języka. Możesz założyć, że tablica wejściowa nie będzie pusta.

Wydajność

Dane wyjściowe będą płaską jednowymiarową tablicą z tymi samymi elementami tego samego typu, co w tablicy zagnieżdżonej i w takiej samej kolejności.

Przypadki testowe

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

Poproś o wyjaśnienia za pomocą komentarzy. To jest golf golfowy , więc wygrywa najkrótszy kod w bajtach!

Uwaga: jeśli Twój język zawiera wbudowane narzędzie, NIE możesz go używać.

Podaj także link do strony internetowej, na której można wykonać kod.

K, 3 bajty

,//

To dość powszechny idiom. „Połącz przez konwergencję”.

spróbuj tutaj z ok .

Jak to działa:

Join ( ,) łączy ze sobą atomy lub listy, aby utworzyć listę. Over ( /) pobiera czasownik (w tym przypadku łączyć) i stosuje go między każdym elementem listy, od lewej do prawej. W ten sposób związek ,/spłaszczy wszystkie elementy najwyższego poziomu listy. Symbol /faktycznie ma różne znaczenia w zależności od wartościowości (liczby argumentów) czasownika, z którym jest złożony. Gdy podajemy ,/jako czasownik, ostateczne /działa jako „zbieżne” - wielokrotnie stosuje ,/się do danych wejściowych, dopóki nie przestanie się zmieniać. Niektóre inne języki nazywają taką funkcję „kombinatorem stałych punktów”. Przez wielokrotne łączenie list najniższych poziomów ostatecznie dojdziesz do pojedynczej płaskiej listy i żadna z operacji nie zaburzy kolejności elementów. To wydaje się rozwiązać problem.

JavaScript (ES6), 35 bajtów

Zainspirowany odpowiedzią @ user81655 :

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

Matematyka, 16 14 bajtów

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

Nienazwana funkcja, która pobiera i zwraca listę, np .:

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

Wyjaśnienie

Impreza z syntaktycznym cukrem!

Aby zrozumieć, jak to działa, uwaga, że każdy wyraz w Mathematica jest albo atom (np liczby, ciągi znaków, symboli) lub wyrażenie związek z postaci f[a, b, c, ...], gdzie f, a, b, csame są dowolnymi wyrażeniami. Tutaj fnazywa się głową wyrażenia. Cała reszta to tylko cukier syntaktyczny. Np. {a, b, c}Jest po prostu List[a, b, c].

Zaczynamy od tego, //@która mapuje funkcje na wszystkich poziomach listy. Na przykład:

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

Pamiętaj, że to mapy f atomy, a także wyrażenia złożone. To, czego teraz szukamy, to sposób na pozbycie się głów listy i zachowanie wszystkiego innego.

ApplyFunkcja jest zwykle używany do zasilania elementów listy jako oddzielne argumentów do funkcji, ale jej rzeczywista definicja jest bardziej ogólny i po prostu zastępuje głowę wyrażenia. Np. Apply[g, f[a, b]]Dajeg[a, b] . .

Teraz pojawia się specjalna „głowa”, Sequencektóra po prostu znika. Np. Po {a, Sequence[b, c], d}prostu ocenia {a, b, c, d}. Ideą spłaszczenia listy jest zastąpienie Sequencenagłówków wszystkich wewnętrznych list tak, aby zostały rozpryskiwane na otaczającą je listę. Więc to, co chcemy to do Applygłowy Sequencena listach. Dogodnie, jeśli myApply coś do atomu, po prostu pozostawia atom bez zmian, więc nie musimy w ogóle rozróżniać typów wyrażeń.

Wreszcie, jest jeden mały problem: fjest on również stosowany do najbardziej zewnętrznego poziomu, dzięki czemu usuwa również skrajne List, czego nie chcemy. Najkrótszym sposobem na skontrowanie jest po prostu ponowne zawinięcie wyniku w listę, tak aby otoczenie Sequencemogło bezpiecznie zniknąć.

Zauważ, że nie ma Applyani Sequencekodu. @@jest formą operatora Applyi ##&jest standardową sztuczką golfową, która skraca długą wbudowaną nazwę Sequence. Więc trochę golfa wszystko, otrzymujemy coś takiego:

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

Aby uzyskać więcej informacji na temat tego, jak i dlaczego ##&działa, zobacz sekcję „Sekwencje argumentów” w mojej odpowiedzi na wskazówki Mathematica .

Python 2, 43 bajty

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

Na liście powtarza się na elementach i łączy wyniki. W ciągu lub cyfrze jest umieszczany na liście singletonów.

Niestety, zamawianie w Pythonie 2 typów int < list < stringkanapek listmiędzy innymi, wymaga sprawdzenia dwóch nierówności. Zamiast tego l*0jest sprawdzany na pustej liście [], w przeciwnym razie daje 0lub "".

Rubinowy, 43 42 34 bajtów

Rozwiązanie rekurencyjne. Teraz z obsługą wyjątków! (równie dobrze może pochwalić @akostadinov za inspirację zmiany)

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

Link IDEOne

JavaScript (ES6), 41 bytes

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 bytes

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

Explanation:

{ # 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 $_
      }
    )
  }
}

Test:

#! /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 bytes

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

Haskell has neither nested lists with different depths of the sublists nor mixed types for the list elements. For nesting I define a custom data type D which is either a leaf L that holds some element or a node N which is a list of Ds. For the mixed elements I use the predefined data type Either which combines two types into one, here Either String Integer. The new type D and the flatten function f are fully polymorphic in the type of the leaf elements, so I don't have to take extra care of anything regarding Either.

Usage example: 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 bytes

us+]Y

Try it online: Demonstration or Test Suite

But of course, there is also a build-in function, that handles the task in just 2 bytes: .n (Test Suite)

JavaScript (Firefox 30-57), 43 bytes

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

Just because I could even avoid using concat.

Perl, 34 29 bytes

Functions.

If needs to flatten to list like my @a = f(@a), 29 bytes:

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

Test it on Ideone

If needs to flatten to array ref like my $a = f($a), 34 bytes:

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

Test it on Ideone.

Perl 5.22.0+, 27 bytes

Thanks to hobbs.

If needs to flatten to list like my @a = f(@a), 27 bytes:

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

Test it on JDoodle

If needs to flatten to array ref like my $a = f($a), 32 bytes:

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

Test it on JDoodle.

Julia, 29 bytes

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

This is recursive splatting into a concatenate function until a reaching a fix point. Example

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

Retina, 30 bytes

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

Try it online! (The first line is only used to run multiple test cases at once.)

Retina has no concept of arrays, string literals or numbers, so I decided to go with a "common" input format of [...,...] style arrays and "-delimited strings, where \ can be used inside the strings to escape any character (in particular " and \ itself).

The program itself simply matches either a full string or a square bracket, and replaces them with $1 which keeps strings and removes square brackets. The limit 1> skips the first match so that we don't remove the leading [. However, this does remove the trailing ], so we add it back in in a separate stage.

Pyke, 11 bytes

.F~]+=])K~]

Try it here!

Explanation:

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

Or 7 bytes after a bugfix

M?+]K~]

Try it here!

Explanation:

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

Or even 2 bytes if printing to stdout is allowed (This might come under built-ins)

M
<newline required>

Try it here!

This deeply applies the print_newline function to every non-sequence item in the input and recurses for sequence items.

Java (v8) 390 276 bytes

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

Just for completeness and all that. :) Can't say Java's code-efficient.

Python, 57 bytes

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

Try it online: Python 2, Python 3

Thanks to Kevin Lau for the list==type(x) trick.

Ruby

there is builtin flatten method.

You can run here: http://www.tutorialspoint.com/execute_ruby_online.php

One 43 bytes, but thought to share:

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

One 45 bytes that is more efficient than the previous and the other ruby answer:

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

here's benchmark:

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

result:

       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 flag) 35 bytes

Oneliner. Inspired by Martin Büttner.

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

Test it on Ideone.

Clojure, 68 bytes

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

mapcat first applies function to each element and then concats results. So every time it concats one 'nesting level' is lost. Concat does not work on not sequences so elements have to be wrapped into vector if they're not vector.

You can try it here: http://www.tryclj.com

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

ANSI C, 193 bytes

#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(_);}

:-/, any suggestions? Btw, I did try to find an online source to compile this but the WL is strict for this code to compile. It will work for VS and gcc otherwise.

JavaScript 20 bytes

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

The array + array is equal to array.toString

C#, 48 bytes

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

Thought I'd post it also since nobody has given a C# solution yet. Suggestions welcome!

Racket, 63 bytes

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

Java 8 165 chars

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

Ungolfed into a class:

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

This answer is based on Jeremy Harton's approach. I used it changed it in some places and created a more golf-like version.

JavaScript, 17 Bytes

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

Finally, JavaScript's type conversions can be put to some good use! Please note that this will actually output an array, but string conversion (putting it into HTML) causes it to become a comma separated list.

If comma separated lists are acceptable output, then the following is valid:

7 Bytes

a=>""+a

NOTE: Snippet is broken for some reason

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 Bytes

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

Attache, 14 bytes

{Reap[Sow@>_]}

Try it online!

Fortunately, Attache has a "vectorization" operator, which applies a function at the atoms of a list. In this case, all we need to do is to set up a reaper with Reap and Sow all atoms of the input _ with @>. I think it's quite elegant.

Alternatives

15 bytes: Fixpoint{`'^^_}

16 bytes: Fixpoint!&Concat

17 bytes: {q:=[]q&Push@>_q}

17 bytes: Fixpoint[&Concat]

Elixir, 74 bytes

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

First Elixir answer, so can probably be golfed a bit.

Try it online.

Explanation:

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

Of course, if builtins were allowed, this could have been 25 bytes instead:

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

Try it online.

Jelly, 4 bytes

;/ÐL

Try it online!

Explanation

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

Built-in F would be one byte if allowed.

Wolfram Language (Mathematica), 13 bytes

#~Level~{-1}&

Try it online!

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

picks out the elements of the structure at the last level of its tree form. I'm not sure this counts as "avoiding the builtin" (which would be Flatten).