LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 October 2 2012

Joe
Member

[Exercise] Flatten nested sequences

In this exercise you have the freedom to chose the type of sequence you want to work with (arrays, lists, vectors, ...) according to the language you're using.

Let's define a "nested sequence" as a sequence where each element can be either:

  • a value.

  • a nested sequence

The goal of this exercise is to write a function that will take a nested sequence as input and returns the corresponding "flat" list. For instance:

a = (5, (3, 2), ((5, (3, 2), 4), (2, 1)), 2)

f(a) -> (5, 3, 2, 5, 3, 2, 4, 2, 1, 2)

Notes
  • You should be able to deal with deep nestings. Consider that there is no depth limit.

  • If your language implements this function, clearly don't use it

  • Bonus points: Don't use a for loop.

Offline

#2 October 2 2012

Ra8
Member

Re: [Exercise] Flatten nested sequences

In Javascript, return by reference

function flatten(arr,i,newA)
{
     if(arr.length==i)
          return -1;
     if(typeof(arr[i])=="object")
     {
          if(flatten(arr[i],0,newA)==-1)
               return flatten(arr,i+1,newA);
     }
     else
     {
          newA.push(arr[i]);
          return flatten(arr,i+1,newA);
     }
}
t=[1,[1,2],[2,3]];
g=[];
flatten(t,0,g);

Offline

#3 October 2 2012

mesa177
Member

Re: [Exercise] Flatten nested sequences

Matlab:

29uwy8z.png

PS; Yes, it's easier for me to include this run on Octaviz than to explain my final one-liner. It's a simple manipulation of matrices, namely transpose (the ' symbol), column assorting (the (:) symbols), and horizontal concatenation of arrays (the horzcat function). If the code is still not clear, then I'll go through it more thoroughly.

[Edit] Well the one liner isn't that clear, so the code goes like this:

flat_x=[]; for (i = 1:size(x'(:)',2)) flat_x = horzcat(flat_x,((x'(:))'{i}'(:))'); end

Where x is any cell matrix.

So, if x is given as:

x = {1,[2,4,5];3,[6,13;2,6]}

then the result would be:

flat_x = [1,2,4,5,3,6,13,2,6]

Note 1: Flattening nested sequences is an inherent property of Matlab, and that's why I decided to step it up and flatten nested matrices instead.

Note 2: This Matlab one-liner code has a very nice real-life application if you think of it. Consider an RGB image; when imported into Matlab/Octaviz, the image is saved as a cell matrix of the binary matrices R, G, and B which compose the image (think of the RGB image as a 3D matrix where R is 1D, G is another 1D, and B is the final 1D). If the binary entries on these matrices were to be transmitted via a channel (let's say emulated in Simulink), then the entries on the matrices would have to be flattened before transmission. I like this exercise :)
[/Edit]

Last edited by mesa177 (October 2 2012)

Offline

#4 October 3 2012

Joe
Member

Re: [Exercise] Flatten nested sequences

Working on Python tuples (it can be very easily adapted to other types of sequences), this code takes advantage of the newly introduced yield from syntax.

def flatten_gen(s):
    if len(s) > 0:
        elt=s[0]
        if isinstance(elt, tuple):
            yield from flatten_gen(elt)
        else:
            yield elt
        yield from flatten_gen(s[1:])

def flatten(s):
    return tuple(flatten_gen(s))

>>> a = (5, (1, 2, (2, 3), (( 5, 4), 3)), (2, 3), (1, (), (2, 5)))
>>> print(flatten(a))
(5, 1, 2, 2, 3, 5, 4, 3, 2, 3, 1, 2, 5)

Offline

#5 October 3 2012

rolf
Member

Re: [Exercise] Flatten nested sequences

In PHP; Nothing fancy, just a recursive function with a foreach loop.
I like how readable the code is :)

<?php

$flat_list = $tree = array();

$tree = array(
   "one",
   array(
      "two",
      "three",
      array(
         "four"
      ),
      "five"
   ),
   "six",
   "seven",
   array(
      "eight"
   )
);

function descend($into) {
   global $flat_list;
   if (is_array($into)) {
      foreach($into as $item) {
         descend($item);
      }
   } else {
      $flat_list[] = $into;
   }
}

descend($tree);

print_r($tree);
echo "\r\n";
print_r($flat_list);

?>

See it in action:
http://codepad.org/awXfJqCl

Edit: I had to replace all tabs with spaces in the code for it to display properly. Something is very wrong with the code box.

Last edited by rolf (October 3 2012)

Offline

#6 October 5 2012

Joe
Member

Re: [Exercise] Flatten nested sequences

Haskell's equivalent (to a certain extent) to Python's yield from is called concatMap.

data NestedList a =
    Elem a | List [NestedList a]
 
flatten :: NestedList Int -> [Int]
flatten (Elem x) = [x]
flatten (List x) = concatMap flatten x

Offline

Board footer