Python Function Challenge #2

Board Discussion Number 4

Page 1 of 1

12 Replies - 3478 Views - Last Post: 07 January 2011 - 06:56 AM Rate Topic: ***** 1 Votes

#1 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 758
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Python Function Challenge #2

Post icon  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  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • 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

Was This Post Helpful? 2
  • +
  • -

#3 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 758
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Python Function Challenge #2

Posted 04 January 2011 - 09:03 PM

:whistling:
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

Was This Post Helpful? 0
  • +
  • -

#4 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5746
  • View blog
  • Posts: 12,553
  • 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

Was This Post Helpful? 1
  • +
  • -

#5 duffman18  Icon User is offline

  • D.I.C Head

Reputation: 14
  • View blog
  • 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

Was This Post Helpful? 1
  • +
  • -

#6 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5746
  • View blog
  • Posts: 12,553
  • 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
Reason for edit:: Added additional spoiler tag

Was This Post Helpful? 2
  • +
  • -

#7 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 758
  • View blog
  • Posts: 2,010
  • 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

Was This Post Helpful? 0
  • +
  • -

#8 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 758
  • View blog
  • Posts: 2,010
  • 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?
Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5746
  • View blog
  • Posts: 12,553
  • Joined: 16-October 07

Re: Python Function Challenge #2

Posted 06 January 2011 - 08:18 AM

View Postatraub, 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. :P

View Postatraub, 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

Was This Post Helpful? 1
  • +
  • -

#10 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 758
  • View blog
  • Posts: 2,010
  • 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

Was This Post Helpful? 0
  • +
  • -

#11 Nallo  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 163
  • View blog
  • Posts: 255
  • 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 :innocent:
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

Was This Post Helpful? 0
  • +
  • -

#12 dorknexus  Icon User is offline

  • or something bad...real bad.
  • member icon

Reputation: 1255
  • View blog
  • Posts: 4,618
  • 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

Was This Post Helpful? 0
  • +
  • -

#13 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 758
  • View blog
  • Posts: 2,010
  • Joined: 23-December 08

Re: Python Function Challenge #2

Posted 07 January 2011 - 06:56 AM

Perhaps someone should make a ruby function challenge?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1