Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In this challenge, your task is to create a program which takes in a nested array and returns a single-dimensional flattened array. For Example [10,20,[30,[40]],50] should output [10,20,30,40,50].


Input

The input will be a nested array (eg. [10,20,[[[10]]]]). It will contain only Integers (both negative and positive), Strings and Arrays. You can take the input as function argument, STDIN or whatever suits your language. You can assume that the input array won't have an empty array.


Output

The output will be a flatted single-dimensional array with the same elements of same type as in the nested array and in the SAME order.


Test Cases

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


Feel free to ask for any clarification by using comments. This is , so the shortest code in bytes wins!

Note: If your language contains a built-in for this, then you must NOT use it.


Edit

Please also include a link to a website where your code can be executed.

share|improve this question
3  
Some languages treat strings as arrays, is [["Hi"],[[10]]] -> ["H","i",10] ok? – Nᴮᶻ May 18 at 5:30
3  
@Mego I was surprised too to find out that there was an unflatten question but no flatten question on PPCG. – Sting 2 days ago
2  
What if your language only supports subarrays of the same size? (E.g. Java?) What if the type of each element must be the same? (E.g. Java, C++ etc.?) Also, please add e.g. ["[",[["[",],'[',"['['"]] as a test case. – flawr 2 days ago
3  
@flawr That test case only makes sense for languages that support bot ' and " as delimiters. (But I agree that a test case involving [, ], " and \ inside a string would be useful.) – Martin Büttner 2 days ago
2  
The test cases also exclude languages which do not support these kinds of arrays with multiple types, or with another notation for array literals. – flawr 2 days ago

21 Answers 21

JavaScript (ES6), 35 bytes

Inspired by @user81655's answer:

f=a=>a.map?[].concat(...a.map(f)):a
share|improve this answer
2  
Very clever! +1 for [ab]using JS's weird way of handling missing keys! – Cyoce 2 days ago
    
I can beat that. – Bald Bantha yesterday
    
@BaldBantha: We're looking forward for your answer :-) – Bergi yesterday
2  
Crap NVM My 33 byte solution fails on one of the test cases. NOOOO – Bald Bantha yesterday
    
@Bergi here it is anyway: i=x=>x.join().split(','); – Bald Bantha yesterday

K, 3 bytes

,//

This is a fairly common idiom. "Join over converge".

try it here with oK.

How it works:

Join (,) fuses together atoms or lists to produce a list. Over (/) takes a verb (in this case join) and applies it between each element of a list, left to right. Thus, the compound ,/ will flatten all the top level elements of the list. The symbol / actually has different meanings depending on the valence (number of arguments) of the verb with which it is compounded. When we provide ,/ as the verb, the final / acts as "converge"- it repeatedly applies ,/ to the input until it stops changing. Some other languages call a feature like this a "fixed point combinator". By repeatedly fusing bottom level lists, you will eventually arrive at a single flat list, and none of the operations will perturb the order of elements. This seems to solve the problem.

share|improve this answer
1  
All right, thanks for the explanation! Have your well-earned +1. – Kevin Lau - not Kenny May 18 at 5:52
    
    
I came up with the same algorithm (but not in this language). +1 for picking the right language to implement it in! – Cyoce May 18 at 5:56
    
@Cyoce If your language has equivalents to the three operators used here, it's an extremely natural solution. By all means post your variation. – JohnE 2 days ago
    
@JohnE Long story, I'm deriving a language from algorithms I come up with, so the language isn't finished (and thus implemented) yet. – Cyoce 2 days ago

Mathematica, 16 14 bytes

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

An unnamed function which takes and returns a list, e.g.:

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

Explanation

Syntactic sugar party!

To understand how this works, note that every expression in Mathematica is either an atom (e.g. numbers, strings, symbols) or a compound expression of the form f[a, b, c, ...], where f, a, b, c are themselves arbitrary expressions. Here, f is called the head of the expression. Everything else on top of that is just syntactic sugar. E.g. {a, b, c} is just List[a, b, c].

We start with //@ which maps a functions over all levels of a list. For instance:

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

Note that this maps f over atoms as well as compound expressions. What we're now looking for is a way to get rid of the list heads and keep everything else.

The Apply function is normally used to feed the elements of a list as separate arguments to a function, but its actual definition is more general and simply replaces the head of an expression. E.g. Apply[g, f[a, b]] gives g[a, b].

Now there's a special "head" called Sequence that simply vanishes. E.g. {a, Sequence[b, c], d} just evaluates to {a, b, c, d}. The idea for flattening the list is to replace the heads of all inner lists with Sequence so that they get splatted into their surrounding list. So what we want is to Apply the head Sequence to the lists. Conveniently if we Apply something to an atom, it just leaves the atom unchanged, so we don't have to distinguish between types of expressions at all.

Finally, there's one small issue: f is also applied to the outermost level, so that it also removes the outermost List, which we don't want. The shortest way to counter that is simply to wrap the result in a list again, such that the surrounding Sequence can safely vanish.

Note that there's neither Apply nor Sequence in the code. @@ is an operator form of Apply and ##& is a standard golfing trick to shorten the long built-in name Sequence. So ungolfing everything a bit, we get something like:

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

For more details on how and why the ##& works, see the section on "Sequences of arguments" in my answer for the Mathematica tips.

share|improve this answer
    
First time I've seen //@. Very useful to know about! – DavidC 2 days ago
    
//@ captures a neat pattern. Reminds me a bit of some of the recursive combinators in Joy. Do you have a link to a good reference to any related functions in Mathematica? I'm very interested in ways of factoring explicit recursion out of programs. – JohnE 2 days ago
1  
@JohnE Well, here's the docs. You could also look at things like Map, MapAt, Apply, as well as Replace and related functions. In general though there's a lot of function which take an optional levelspec parameter (see my original 16-byte solution), which lets you apply the function at multiple/all levels at once. – Martin Büttner 2 days ago

Python 2, 43 bytes

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

On a list, recurses on the elements and concatenates the results. On a string or number, encases in a singleton list.

Unfortunately, Python 2's ordering for types int < list < string sandwiches list between the others, requiring two inequalities to check. So, instead, l*0 is checked against the empty list [], otherwise giving 0 or "".

share|improve this answer

Ruby, 43 42 34 bytes

Recursive solution. Now with exception handling! (might as well credit @akostadinov for inspiring the change though)

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

IDEOne link

share|improve this answer
    
kudos for shortness, awesome – akostadinov 2 days ago
    
I didn't know you could use rescue like that – Cyoce 2 days ago
    
@Cyoce I think it's because Ruby technically doesn't have a try block, so you use begin instead to differentiate the parts you want to be catching for and the parts that you don't. So since you're catching for the entire rest of the block before it, you technically don't need it? The rest is just trimmed whitespace, since Ruby interprets the line as ...inject(:+) rescue [a] – Kevin Lau - not Kenny 2 days ago
    
@KevinLau-notKenny, no, rescue on same line is different, just rescuing that line. e.g. a = raise("haha") rescue 1 would assign 1 to a. It' – akostadinov yesterday

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>

share|improve this answer

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)

share|improve this answer
    
Just 3 away from the current winner! +1 – Sting 2 days ago
    
@Sting: Golfed away another byte. Forgot that Pyth append the last character G implicitly, if I don't write it. – Jakube 2 days ago
    
Congratulations! – Sting 2 days ago

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].

share|improve this answer

JavaScript (Firefox 30+), 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.

share|improve this answer
    
Isn't it ECMAScript 6 not Firefox 30+? – Solomon Ucko yesterday
    
@SolomonUcko No, [for(of)] is only available in Firefox 30+. It was proposed for ES7 but later dropped. – Neil yesterday
    
thanks for explaining! Mostly, i just thought it was for(__ in __) – Solomon Ucko yesterday
    
@SolomonUcko [for(in)] was an alternative experimental syntax which gave you the keys of the object. – Neil yesterday

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 - $[[["[]"], "[]"],]
share|improve this answer

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.

share|improve this answer
2  
Hello, and welcome to PPCG! This question is code-golf, so please try to minimize your code. Thanks! – NoOneIsHere 2 days ago
    
Do you have any specific suggestions? I have minimized it, Java is just a heavy language. – Jeremy Harton 2 days ago
2  
Remove all the unnecessary spaces, tabs, and newlines. Change oaf to o, and change flatten to f. – NoOneIsHere 2 days ago
1  
You don't need the finals, the whole thing can be a lambda, you don't need public static... – David Conrad yesterday
    
you could save couple characters if you use generics instead object – user902383 yesterday

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.

share|improve this answer
    
Just 4 away from K! +1 – Sting 2 days ago

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
share|improve this answer

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.

share|improve this answer
    
I haven't tested it, but think ?@{f@$_}: should work instead of ?@{f(@$_)}:, saving two bytes. – msh210 2 days ago
1  
@msh210 No, it’s not working. The compiler doesn’t khow that f is a function because f not yet declared. sub f{}sub f{... f@$_ ...} working. – Denis Ibaev yesterday
    
1. ref doesn't need the parens to work, saving 2 bytes. 2. As far as I can see, sub f{map{ref?f(@$_):$_}@_} is within the rules and saves another 5. f takes an array (nonref) as a list, so it can return the same. – hobbs yesterday
    
@hobbs 1. If no parentheses with ref then the compiler assumes that ? is starting ?PATTERN? operation like ref(?PATTERN?). So the compiler searches second ? and throws error. – Denis Ibaev yesterday
    
@DenisIbaev ah. ?PATTERN? was removed in 5.22.0 (m?PATTERN? still works) and I'm testing on a recent version. So you can gain those two bytes by specifying 5.22+. – hobbs yesterday

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.

share|improve this answer
2  
type(x)==list is shorter than isinstance(x,list). – Kevin Lau - not Kenny May 18 at 5:37
1  
“It will contain only Integers (both negative and positive), Strings and Arrays.” How about [`x`>'['and...? (That works in Python 2 only.) – Lynn 2 days ago

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.

share|improve this answer

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)
share|improve this answer
1  
Hello, and welcome to PPCG! Unfortunately, your answer is not valid, because of this rule: Note: If your language contains a built-in for this, then you must NOT use it. – NoOneIsHere 2 days ago
    
@NoOneIsHere, thanks, didn't know that – akostadinov 2 days ago
1  
How does my new update stack against time-wise against yours? Also, just like my new answer, you can remove the spaces around rescue – Kevin Lau - not Kenny 2 days ago
    
@KevinLau-notKenny updated, thanks! rescue looks to be rather slow btw, like try/catch in java – akostadinov 2 days ago
1  
Update your bytecount, too – Kevin Lau - not Kenny 2 days ago

Perl, 39 34 + 1 (-p flag) 35 bytes

Oneliner. Inspired by Martin Büttner.

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

Test it on Ideone.

share|improve this answer

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 [[["[]"],"[]"]])
share|improve this answer
    
Nice first code-golf. +1 :) – Sting 18 hours ago

Racket, 63 bytes

(define(f l)(apply append(map(λ(x)(if(list? x)(f x)`(,x)))l)))
share|improve this answer

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.

var subject = 
  a=>eval(`[${a}]`)
<input oninput="try {output.innerHTML = subject(this.value)} catch(e) {output.innerHTML='Invaild Input'}" />
<div id="output"></div>

share|improve this answer
2  
This doesn't seem to work when run in the console for input ["["]... I tried running (a=>eval([${a}]))(["["]) and got a SyntaxError – jrich 2 days ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.