# Python Function Challenge #2

Page 1 of 1

## 12 Replies - 2872 Views - Last Post: 07 January 2011 - 06:56 AMRate Topic: 1 Votes //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=208315&amp;s=cfbb2c6e32df21f406bedc05e26cdd97&md5check=' + ipb.vars['secure_hash'], cur_rating: 5, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 atraub

• Pythoneer

Reputation: 734
• Posts: 1,890
• Joined: 23-December 08

# Python Function Challenge #2

Posted 04 January 2011 - 02:39 PM

POPULAR

A new year and a new challenge, but this one may force you to think outside the box a bit. Today's challenge is: flattening functions.

Let's say you have a list that is made up of items, some of which are lists. Each of those lists may be made up of items or more lists and so on...

For this challenge, your job is to take a list or tuple as an input and convert it to a flat list or tuple (meaning that all the non-data structure values are present, but all the data structures are removed).

In designing your functions, some of you may want to focus solely on speed, others on creativity, and some of you may want to find a balance of the two... all of these approaches are great. Let's see how many different approaches the Python board can come up with!

Example input:
>>> x = [1,[2,[3,[4,5,6,[7]],9]],[10,11],12]
>>> flatten(x)
>>> print(x)
[1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12]

Can anyone flatten this list?
x = [1,[2,[3,[4,5,6,[7]],9]],(10,11),12]

OPTIONAL:
If you're feeling particularly hardcore, let's assume that the initial value is a list or tuple, but it can also contain a dictionary. For dictionaries, order the values based on the keys (0-9, A-Z, a-z case sensitive). They keys should not exist in our final result, only their associated flattened values.

This post has been edited by atraub: 06 January 2011 - 08:01 AM
Reason for edit:: removed tuple input

Is This A Good Question/Topic? 6

## Replies To: Python Function Challenge #2

### #2 Nallo

Reputation: 159
• Posts: 241
• Joined: 19-July 09

## Re: Python Function Challenge #2

Posted 04 January 2011 - 04:04 PM

Harhar, atraub finally found a problem for which recursion feels natural.

I will oblige, here is my version. Don't beat me if it is ugly or buggy ... its late at night here:
Spoiler

This post has been edited by Nallo: 04 January 2011 - 04:07 PM

### #3 atraub

• Pythoneer

Reputation: 734
• Posts: 1,890
• Joined: 23-December 08

## Re: Python Function Challenge #2

Posted 04 January 2011 - 09:03 PM

Hahaha are you suggesting I allowed the recursive potential of this problem influence my decision to make it my second challenge? That's just crazy talk...

This post has been edited by atraub: 04 January 2011 - 09:16 PM

### #4 baavgai

• Dreaming Coder

Reputation: 4949
• Posts: 11,356
• Joined: 16-October 07

## Re: Python Function Challenge #2

Posted 05 January 2011 - 09:16 AM

The requirement to do this in place is kind of annoying; but fun.

Also, no recursion for you!
Spoiler

Could be bloody awful performance wise, but I liked the bubbly sort nature of it.

This is the same logic as above, but probably slightly faster:
Spoiler

### #5 duffman18

Reputation: 13
• Posts: 54
• Joined: 20-October 10

## Re: Python Function Challenge #2

Posted 05 January 2011 - 10:55 PM

I am still kind of a noob in python so my code might be the quickest or best way to do something, but it works. There is probably a way better way to check if the object is a list, but I couldn't get any other way to work. Anyways here is my crack at it, I went for minimalistic.

Spoiler

### #6 baavgai

• Dreaming Coder

Reputation: 4949
• Posts: 11,356
• Joined: 16-October 07

## Re: Python Function Challenge #2

Posted 06 January 2011 - 05:54 AM

Hmm... looks like I'm not the only one who didn't like the in place requirement. It is indeed awkward.

For those playing along at home, you can get around it with this kind of pattern:
Spoiler

Thus freed from the in place constraint, I'll offer another non recursive version. I rather like this one.
Spoiler

This post has been edited by atraub: 06 January 2011 - 07:19 AM

### #7 atraub

• Pythoneer

Reputation: 734
• Posts: 1,890
• Joined: 23-December 08

## Re: Python Function Challenge #2

Posted 06 January 2011 - 07:10 AM

The in-place requirement was purposely put in to force greater creativity and to nourish problem solving skills.

This post has been edited by atraub: 06 January 2011 - 07:35 AM

### #8 atraub

• Pythoneer

Reputation: 734
• Posts: 1,890
• Joined: 23-December 08

## Re: Python Function Challenge #2

Posted 06 January 2011 - 07:58 AM

Uh oh! It seems no one has managed to write a program that actually fulfills the requirement of being able to work with tuples! Of course, tuples ARE immutable, so flattening a tuple may prove impossible, but surely it's possible to flatten a list with a tuple in it.

Can anyone flatten this list?
x = [1,[2,[3,[4,5,6,[7]],9]],(10,11),12]

Who will rise to this challenge?

### #9 baavgai

• Dreaming Coder

Reputation: 4949
• Posts: 11,356
• Joined: 16-October 07

## Re: Python Function Challenge #2

Posted 06 January 2011 - 08:18 AM

atraub, on 06 January 2011 - 08:10 AM, said:

The in-place requirement was purposely put in to force greater creativity and to nourish problem solving skills.

Lol, sorry. It's mostly causing people to ignore it, I'm afraid.

atraub, on 06 January 2011 - 08:58 AM, said:

It seems no one has managed to write a program that actually fulfills the requirement of being able to work with tuples!

I thought Nallo's approach of checking for expected attributes did a pretty good job. It's certainly a more general solution, allowing for custom types to be processed.

Here's a list/tuple specific one. Just added a couple lines to the above:
Spoiler

### #10 atraub

• Pythoneer

Reputation: 734
• Posts: 1,890
• Joined: 23-December 08

## Re: Python Function Challenge #2

Posted 06 January 2011 - 08:30 AM

Doh! I overlooked Nallo's! +1 style points to Nallo! Because of that little recursion poke he gave me, I got distracted and completely overlooked his code. Dang Nallo, that's a lot better than anything I came up with!

This post has been edited by atraub: 06 January 2011 - 08:32 AM
Reason for edit:: EXPANSION

### #11 Nallo

Reputation: 159
• Posts: 241
• Joined: 19-July 09

## Re: Python Function Challenge #2

Posted 06 January 2011 - 09:41 AM

Oh, thanks.

But I completely overlooked the in place requirement
Guess I have to rewrite it after all when I find time for it.

Well if the top level structure is a list I could easyly fake in place operation:

Spoiler

Edit: oops, didnt look at baavgais posts. He described the fake an in place operation already.

This post has been edited by Nallo: 06 January 2011 - 11:07 AM

### #12 dorknexus

Reputation: 1189
• Posts: 4,590
• Joined: 02-May 04

## Re: Python Function Challenge #2

Posted 07 January 2011 - 12:21 AM

I was trying to do method injection in Python because I'm used to open classes in Ruby but came to the conclusion that it's whacky and convoluted and I don't know enough Python to be patient with it. In other words it reminded me of why i dislike Python in the first place.

But, in Ruby it would be trivial, even ignoring the existing flatten method for collections.

So there!

This post has been edited by Dark_Nexus: 07 January 2011 - 12:21 AM

### #13 atraub

• Pythoneer

Reputation: 734
• Posts: 1,890
• Joined: 23-December 08

## Re: Python Function Challenge #2

Posted 07 January 2011 - 06:56 AM

Perhaps someone should make a ruby function challenge?

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }