Challenge #4: Flattening, 7 Aug 2006
Document Actions
A real world problem!
Say we have data called a "mixed sequence", which is a sequence (list, tuple, etc) which may contain regular values or other mixed sequences. One might look like
[1, (2, 3), 4, 5, [6, 7, 8, (9, 10), 11], 12]
or, in a more expanded view:
[1,
(2, 3),
4,
5,
[6, 7, 8, (9, 10), 11],
12]
For our purposes, the structure is meaningless. Write a function to take a mixed sequence and return a list of all the values in that sequence, preferably in order. For example:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
One might call this "flattening the list". Keep efficiency in mind.
This will almost certainly not be a one-line solution; can it be a one-liner if we do not nest more than one level?
[1, (2, 3), 4, 5, [6, 7, 8, (9, 10), 11], 12]
or, in a more expanded view:
[1,
(2, 3),
4,
5,
[6, 7, 8, (9, 10), 11],
12]
For our purposes, the structure is meaningless. Write a function to take a mixed sequence and return a list of all the values in that sequence, preferably in order. For example:
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
One might call this "flattening the list". Keep efficiency in mind.
This will almost certainly not be a one-line solution; can it be a one-liner if we do not nest more than one level?
Re: Challenge #4: Flattening, 7 Aug 2006
Posted by
kclarks
at
2006-08-15 16:06
I played with this for a little while, but couldn't think of anythign creative. All I came up with was:
def flatten(input):
flat = []
for item in input:
if type(item) == type(1):
flat.append(item)
else:
flat.extend(flatten(item))
return flat
def flatten(input):
flat = []
for item in input:
if type(item) == type(1):
flat.append(item)
else:
flat.extend(flatten(item))
return flat
Re: Re: Challenge #4: Flattening, 7 Aug 2006
Posted by
kclarks
at
2006-08-15 16:08
Ooops, sorry... posted my reply in the wrong place.
Re: Re: Challenge #4: Flattening, 7 Aug 2006
Posted by
kclarks
at
2006-08-15 16:09
Arg... and it ruined all my indenting. That's what I get for not coming up with a one-liner :(
http://mountainbunker.org/~cbearden/PythonChallenge/challenge04.py.txt
Couple of interesting things I noticed. There is no standard Pythonic test for "is this object a sequence?". I wanted to leave open the possibility of the list to be flattened containing sequence types other than tuples and lists, in case there were ones I didn't know about. I don't generally like solutions where you have to explicitly test against two or more conditions, if there's a way to generalize.
But amazingly, there doesn't appear to be wide agreement on what sequences really *are*. After all, a string is considered a sequence of single characters in many contexts, but I assume for purposes of this challenge that we don't want to flatten [1, (2, 'foo'), 'b'] to ['1', '2', 'f', 'o', 'o', 'b']!