Python mini-challenge: "Lucky" numbers

  • (2 Pages)
  • +
  • 1
  • 2

18 Replies - 3397 Views - Last Post: 10 February 2014 - 07:13 AM Rate Topic: -----

#1 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Python mini-challenge: "Lucky" numbers

Post icon  Posted 07 February 2014 - 11:06 PM

This will not be a hugely difficult challenge for experienced python programmers, but it's a good exercise in working with the language, and the set of "lucky" numbers is interesting to think about.

"Lucky" numbers are numbers which are "lucky" enough to survive the following "sieve" procedure:

Start with the set of the first N positive integers, and select 1 to be the first lucky number.

Repeat the following until no more deletions occur:
select i to be the least number on the list not yet found to be lucky. Counting from the start of the list, remove every ith number.

So for example, running this on the integers from 1 to 100, my first pass selects i = 2 and so strikes out every other number, leaving only the odd numbers. On the second pass, I select i = 3, and strike out every third odd number, getting the following list:

[1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, 33, 37, 39, 43, 45, 49, 51, 55, 57, 61, 63, 67, 69, 73, 75, 79, 81, 85, 87, 91, 93, 97, 99]


On the next pass, i = 7, and every seventh number is deleted from the list, leaving
7 [1, 3, 7, 9, 13, 15, 21, 25, 27, 31, 33, 37, 43, 45, 49, 51, 55, 57, 63, 67, 69, 73, 75, 79, 85, 87, 91, 93, 97, 99]
9 [1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 45, 49, 51, 55, 63, 67, 69, 73, 75, 79, 85, 87, 93, 97, 99]



And we proceed in this vein until we get

[1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, 87, 93, 99]



As I say, this shouldn't be a very difficult piece of code to write, but there are a few places where you can get stuck, so you might have to think about it a little bit.

If you become curious about this sequence, see the entry on wikipedia, and also the entry at OEIS

Implementation tip: I find the enumerate function to be quite useful in this sort of program. It allows me to work with a list's values and its indices inside a list comprehension, rather than a loop, which I find congenial. If you haven't played with this, give it a go. It's often useful for streamlining your code without making it cryptic.

Once you've got it running, you might want to look at the similarities between this set and the primes, which are interesting. This problem should also remind you of the well-known Josephus problem, with which it shares some characteristics.

Have fun!

Is This A Good Question/Topic? 2
  • +

Replies To: Python mini-challenge: "Lucky" numbers

#2 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 105
  • Joined: 27-December 13

Re: Python mini-challenge: "Lucky" numbers

Posted 08 February 2014 - 08:29 AM

I have NEVER used either list comprehension nor the enumerate function. So I gladly accepted your challange.
I have now two working programs generating the correct answer. The first is with only modest use of list comprehension, in the second program, I drive it to the limit (my limit).
The codes are made in Python 3.3.3
Problem is that the second code is really difficult to read and understand while the first code is much more straightforward.
So my question: Is it really good practice to condence the code ? To me it is funny, ok - but is it useful ?

Code 1:
def sieve(lst, t):
    div = lst[t-1][1]
    for item in lst:
        if item[0]%div == 0:
            lst.remove(item)
    lst2 = []
    for item in lst:
        lst2.append(item[1])

    lst3 =[(i, e) for i,e in enumerate((lst2), start=1)]
    
    t += 1
    if len(lst3) > div:
        result = sieve(lst3, t)
        return result
    else:
        return lst2


n =100
lst = [(i,e) for i,e in enumerate(range(1, 100, 2), start=1)]
t = 2
result = sieve(lst, t)

print (result)



Code 2:
def sieve(lst, t):
    div = lst[t-1][1]
    lst2 =[(i, e) for i,e in enumerate(([item[1] for item in [item for item in lst if item[0]%div !=0]]), start=1)]
    t += 1
    if len(lst2) > div:
        result = sieve(lst2, t)
        return result
    else:
        return [item[1] for item in lst]

n =100
lst = [(i,e) for i,e in enumerate(range(1, 100, 2), start=1)]
t = 2
result = sieve(lst, t)
print (result)


Was This Post Helpful? 1
  • +
  • -

#3 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Python mini-challenge: "Lucky" numbers

Posted 08 February 2014 - 10:57 AM

The second one looks a lot more like what I'd like to see. The logic of the first version is - to me - obscured in a lot of scaffolding. I think this is something that happens over time as you write more python, though. If you're coming from a language like Java, you're used to seeing a lot of language devoted to the structure, and it makes sense to see it, but as you write more in python you'll probably gravitate towards stuff more like the second version.

Thanks for having a go at this one - I hope you enjoyed writing it.

Quote

So my question: Is it really good practice to condence the code


In my opinion, clarity is paramount. Unfortunately, two people might differ on what they consider "clear" depending on what they're used to seeing.
You could probably refactor this to make it easier to read. I'm not sure that I like the recursion. I used a while loop, which looked more straightforward to me. The inner loop, of course, was a list comp, but somewhat simpler than yours. I'll post mine in a day or so, but for now, try rewriting the comprehension to collect the values and filter using the indices. So for each pair (index, val) that you get from the enumeration, you just want the val, and only if the index passes the filter. This will probably reduce the complexity in a couple of places.
Was This Post Helpful? 0
  • +
  • -

#4 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 105
  • Joined: 27-December 13

Re: Python mini-challenge: "Lucky" numbers

Posted 08 February 2014 - 04:00 PM

Fantastic - you are right - AND you make me a better Python coder.
I did clean up my long complicated list comp/enumetate line and it still works !!

I also did the same with a while-loop - 8 lines all-in-all >> same result.

I will not publish the while-loop solution at this time - don't want to spoil the fun for others.

Actually I don't know Java or any other programing languages - Python is my first. I started with Python in May last year, from scratch and with only a few books.
Once again: Thank you for taking your time to help newcomers such as me.
Was This Post Helpful? 0
  • +
  • -

#5 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Python mini-challenge: "Lucky" numbers

Posted 08 February 2014 - 07:10 PM

View PostDK3250, on 08 February 2014 - 06:00 PM, said:

I did clean up my long complicated list comp/enumetate line and it still works !!
...
Once again: Thank you for taking your time to help newcomers such as me.

Cool. It's pretty cool when that happens, isn't it? Suddenly, everything looks a little clearer.
Glad I could help!
Was This Post Helpful? 0
  • +
  • -

#6 Mekire  Icon User is online

  • D.I.C Head

Reputation: 117
  • View blog
  • Posts: 215
  • Joined: 11-January 13

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 02:21 AM

My current attempt. I think selection of the next current number can probably be improved:
(Edit: Found the improvement in this approach, though it remains a naive solution.)
Spoiler

-Mek

Edit:
The time complexity of this seems to be terrible. Trying to figure out a way to do it by hashing indexes.

Edit2:
Latest performs much better but calculation time still blows up. Does 100,000 in about a second, but 1,000,000 takes too long to bother:
Spoiler


Edit3:
Massive improvement (0.12s for 100,000 and 13s for 1,000,000):
Spoiler
Edit4(cleaned the above a bit)

This post has been edited by Mekire: 09 February 2014 - 04:44 PM

Was This Post Helpful? 1
  • +
  • -

#7 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 105
  • Joined: 27-December 13

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 09:21 AM

>>

Wrong posting removed by DK3250

This post has been edited by DK3250: 09 February 2014 - 09:20 AM

Was This Post Helpful? 0
  • +
  • -

#8 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 105
  • Joined: 27-December 13

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 09:39 AM

>> Mekire. I think list comprehension and use of enumerate was the primary goal in this challenge...

I've made two solutions, one uses recursion, the other a while-loop. Both uses list comprehension and enumerate's as much as I can push into the code.

The code(s) are shown here for inspiration and discussion:

def sieve(lst, t):
    div = lst[t][1]
    lst2 =[(i, e) for i,e in enumerate(([item[1] for item in lst if item[0]%div !=0]), start=1)]
    if len(lst2) > div:
        return sieve(lst2, t+1)
    else:
        return [item[1] for item in lst]
n =100
lst = [(i,e) for i,e in enumerate(range(1, n, 2), start=1)]
t = 1
print (sieve(lst, t))



n = 100
lst = [(i,e) for i,e in enumerate(range(1, n, 2), start=1)]
t = 1
div = lst[t][1]
while len(lst) > div:
    lst = [(i, e) for i,e in enumerate(([item[1] for item in lst if item[0]%div !=0]), start=1)]
    t += 1
    div = lst[t][1]
print ([item[1] for item in lst])



If you want to run the code with big numbers, remember to change the print statement to
<result => or similar.
Was This Post Helpful? 0
  • +
  • -

#9 Mekire  Icon User is online

  • D.I.C Head

Reputation: 117
  • View blog
  • Posts: 215
  • Joined: 11-January 13

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 09:52 AM

View PostDK3250, on 09 February 2014 - 04:39 PM, said:

>> Mekire. I think list comprehension and use of enumerate was the primary goal in this challenge...
The only thing I care about is whether the solution scales. My first solution used both a list comp and enumerate. It was also terrible.

Time your code with input of 100,000 or more.

Spoiler
I get results like this for yours
3.331848339

And mine:
Spoiler
Result:
0.141049516678


The only thing that matters is scalability.
-Mek

This post has been edited by Mekire: 09 February 2014 - 09:53 AM

Was This Post Helpful? 0
  • +
  • -

#10 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 10:02 AM

Okay now, let's keep this fun. The point was to explore an interesting number set and see what we can learn from the exercise.
Was This Post Helpful? 0
  • +
  • -

#11 Mekire  Icon User is online

  • D.I.C Head

Reputation: 117
  • View blog
  • Posts: 215
  • Joined: 11-January 13

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 10:09 AM

View Postjon.kiparsky, on 09 February 2014 - 05:02 PM, said:

Okay now, let's keep this fun.
I didn't mean that to come off as belittling his solution. Just that generally what we are interested in is scalability of algorithms like this. I'm also sure mine is still far from optimal. The fact that I have to recreate the entire list every loop is quite annoying.

-Mek
Was This Post Helpful? 0
  • +
  • -

#12 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 10:27 AM

View PostMekire, on 09 February 2014 - 12:09 PM, said:

I didn't mean that to come off as belittling his solution.


Just want to make sure we keep this collegial. :)/>


View PostMekire, on 09 February 2014 - 11:52 AM, said:

The only thing that matters is scalability.
-Mek


Quote

Just that generally what we are interested in is scalability of algorithms like this. .


I want to push at this a little. I definitely agree that scalability is a hugely important part of algorithm design. In fact, it's the third interesting feature of an algorithm (after "does it terminate?" and "is it correct"?) when considered purely from the perspective of computation.

However, I don't think that this is the only perspective that we can take. One obvious perspective is the student's view. If a student writes a suboptimal implementation and learns a useful way of thinking about problems in the process, that's a good thing and it matters that they write that suboptimal implementation as well as they can do. Classic example would be a naive recursive Fibonacci generator, which is informative partly for its flaws, but also because it is such a clear expression of what recursion is and what it can do.
Another perspective, even more interesting, is the mathematical perspective. Surely in this case the properties of the set of lucky numbers are interesting to us - otherwise, we're just writing code to show off how cool we are, without any purpose that actually matters. We can leave that to the Haskell kids. Obviously, finding better algorithms is progress towards that - but often the more naive algorithms are much better at expressing the underlying math than the faster ones. For example, if you want to teach someone about matrix multiplication, you don't show them Strassen's algorithm first. You show them the O(n^3) algorithm, because that's the one with the important insights in it. So I don't agree that the only interesting algorithms are the ones that scale. That's only true if what you most want is to generate the longest possible list of lucky numbers, but that might not be your goal.

So as a real counter-example for your claim, I suggest that if you came up with an algorithm that could find the nth lucky number directly (ie, without calculating the intermediate steps) that would matter greatly, no matter what its time complexity, because at the moment no such algorithm exists and it would show a much deeper understanding of the problem domain than a simple optimization. Optimization is interesting on its own hook, but it's not the only thing, or even necessarily the primary thing that we care about. From the mathematical perspective optimisation is interesting precisely to the extent that it provides insight into the problem domain - which I think might happen in the case of your approach, so I'm looking forward to seeing what more you come up with.

Quote

I'm also sure mine is still far from optimal. The fact that I have to recreate the entire list every loop is quite annoying


Yeah, that's a complaint I often have with python. I'm wondering if there's a more functional approach that might do this more beautifully. I don't know what that looks like, and I have to go run sound for a while, but I'll be back to think about that presently.

This post has been edited by jon.kiparsky: 09 February 2014 - 10:28 AM

Was This Post Helpful? 2
  • +
  • -

#13 DK3250  Icon User is offline

  • D.I.C Head

Reputation: 27
  • View blog
  • Posts: 105
  • Joined: 27-December 13

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 11:57 AM

Speed of execution vs. speed of development.

I am familiar with one programming language only, Python. I am totally autodidact, started May last year. I don’t use programming in my professional life.
I’ve also sniffed into C++, but have left it aside for later (if ever).
In my view those two languages differ a lot. Development (making code) is much quicker in Python than it is in C++; C++ on the other hand (often) executes faster.
So, if you are making programs for single or limited use, Python will get you to your goal much faster that C++. And if it is really for limited use, who cares about differences in execution time on the level of seconds – or even minutes. You probably saved 100 times this in shorter development time.
If, on the other hand, your program is to be distributed and run thousands of times, - then, of cause, speed of execution is important and you might choose C++ or some other – not Python.
Now, we are on a Python forum. Without neglecting the value of execution speed, the Python forum is not where I expect to find blistering fast number-crunching code. Python is rather about quick development, easy readable code, structure (PEP 8), etc. Speed of execution is secondary.
When a challenge is given scoping list comprehension and enumerate’s – this should be the primary focus.
Scalability is fine, but if scalability is the primary focus then Python maybe is the wrong language… ?

This post has been edited by macosxnerd101: 09 February 2014 - 03:58 PM
Reason for edit:: Removed [size] and [font] tags to improve readability

Was This Post Helpful? 0
  • +
  • -

#14 Mekire  Icon User is online

  • D.I.C Head

Reputation: 117
  • View blog
  • Posts: 215
  • Joined: 11-January 13

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 03:55 PM

The subject of time complexity is a major one in computer science. If you haven't been introduced to it before then it is definitely worth studying; it can unfortunately be a little bit daunting. It has nothing to do with language choice however.

As Jon said, yes, there is much to learn from this exercise other than building the most efficient method of generating numbers. Time complexity is something you should concern yourself with though, Python programmer or not.

I strongly suggest looking into coding basic sorting algorithms to become accustomed to the concepts of linear time, polynomial time, logarithmic time, etc.

-Mek

This post has been edited by Mekire: 09 February 2014 - 03:56 PM

Was This Post Helpful? 2
  • +
  • -

#15 jon.kiparsky  Icon User is offline

  • Pancakes!
  • member icon


Reputation: 7996
  • View blog
  • Posts: 13,694
  • Joined: 19-March 11

Re: Python mini-challenge: "Lucky" numbers

Posted 09 February 2014 - 04:18 PM

Yes - time complexity is very important. It's just not the only important thing.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2