8

I'm trying to solve this programming riddle and although the solution (see code below) works correctly, it is too slow for succesful submission.

  • Any pointers as how to make this run faster (removal of every n-th element from a list)?
  • Or suggestions for a better algorithm to calculate the same; seems I can't think of anything else than brute-force for now...

Basically, the task at hand is:

 GIVEN: L = [2,3,4,5,6,7,8,9,10,11,........] 1. Take the first remaining item in list L (in the general case 'n'). Move it to the 'lucky number list'. Then drop every 'n-th' item from the list. 2. Repeat 1 TASK: Calculate the n-th number from the 'lucky number list' ( 1 <= n <= 3000)

My original code (it calculated the 3000 first lucky numbers in about a second on my machine - unfortunately too slow):

""" SPOJ Problem Set (classical) 1798. Assistance Required URL: http://www.spoj.pl/problems/ASSIST/ """ sieve = range(3, 33900, 2) luckynumbers = [2] while True: wanted_n = input() if wanted_n == 0: break while len(luckynumbers) < wanted_n: item = sieve[0] luckynumbers.append(item) items_to_delete = set(sieve[::item]) sieve = filter(lambda x: x not in items_to_delete, sieve) print luckynumbers[wanted_n-1]

EDIT: thanks to the terrific contributions of Mark Dickinson, Steve Jessop and gnibbler, I got at the following, which is quite a whole lot faster than my original code (and succesfully got submitted at http://www.spoj.pl with 0.58 seconds!)...

sieve = range(3, 33810, 2) luckynumbers = [2] while len(luckynumbers) < 3000: if len(sieve) < sieve[0]: luckynumbers.extend(sieve) break luckynumbers.append(sieve[0]) del sieve[::sieve[0]] while True: wanted_n = input() if wanted_n == 0: break else: print luckynumbers[wanted_n-1]
Improve this question
15
  • How fast do you need it to be? How much less than a second, on roughly what hardware? Commented Mar 18, 2010 at 22:27
  • Isn't the problem just asking you to generate the nth prime number? Commented Mar 18, 2010 at 22:28
  • @Steve Jessop: I have to calculate several test-cases for n (always < 3000) within 1 second. The script runs in an special test-environment within spoj.pl and I have found no clues about the hardware. When you're going over 1 second you only get a 'time limit exceeded' (without a precise runtime)... Commented Mar 18, 2010 at 22:31
  • @rz: I don't think so: 30985 for example is in the lucky number list (and is divisible by 5). The list does seem to contain a lot of primes though. Commented Mar 18, 2010 at 22:34
  • 1
    These are similar to lucky numbers, but the algorithm is slightly different. Ulam applies his algorithm to the natural numbers; this version starts at 2, not 1. Commented Mar 19, 2010 at 7:04

5 Answers 5

Reset to default
7

This series is called ludic numbers

__delslice__ should be faster than __setslice__+filter

>>> L=[2,3,4,5,6,7,8,9,10,11,12] >>> lucky=[] >>> lucky.append(L[0]) >>> del L[::L[0]] >>> L [3, 5, 7, 9, 11] >>> lucky.append(L[0]) >>> del L[::L[0]] >>> L [5, 7, 11]

So the loop becomes.

while len(luckynumbers) < 3000: item = sieve[0] luckynumbers.append(item) del sieve[::item]

Which runs in less than 0.1 second

Improve this answer
Sign up to request clarification or add additional context in comments.

8 Comments

D'oh! A straightforward del sieve[::item] is much better than my convoluted "set to-be-deleted items to zero and then filter". +1.
Can't believe I did not think of that! Surely shows how the simplest solution in Python is often the best/fastest. Combined with Mark Dickinson's early termination the solution I edited in in my original answer worked fine within the time limit (it scored 0.58 seconds with the test set)!
I'll just check if I can get stubbscroll's or Rex Kerr's suggestions running faster then this (this calculates all 3000 of them in 0.0104 on average on my machine) but otherwise I'll be sure to flag this as accepted answer this weekend!
@ChristopheD, Now the fun challenge is to figure out how to solve the problem 10 times faster still :)
@gnibbler: lol, very true. The fastest python 2.6.2 solution is in @ 0.04 seconds ;-)
|
4

Try using these two lines for the deletion and filtering, instead of what you have; filter(None, ...) runs considerably faster than the filter(lambda ...).

sieve[::item] = [0]*-(-len(sieve)//item) sieve = filter(None, sieve)

Edit: much better to simply use del sieve[::item]; see gnibbler's solution.

You might also be able to find a better termination condition for the while loop: for example, if the first remaining item in the sieve is i then the first i elements of the sieve will become the next i lucky numbers; so if len(luckynumbers) + sieve[0] >= wanted_n you should already have computed the number you need---you just need to figure out where in sieve it is so that you can extract it.

On my machine, the following version of your inner loop runs around 15 times faster than your original for finding the 3000th lucky number:

while len(luckynumbers) + sieve[0] < wanted_n: item = sieve[0] luckynumbers.append(item) sieve[::item] = [0]*-(-len(sieve)//item) sieve = filter(None, sieve) print (luckynumbers + sieve)[wanted_n-1]
Improve this answer

8 Comments

Wow, these two lines run about 10 times as fast as the two in my code above. Very insightful! Let me take a stab at the while loop...
Or maybe for x in xrange(0, len(sieve), item): sieve[x] = 0
Since you're asked to output lucky(n) for several values of n, it would make a lot more sense to compute the array once (up to 3000), rather than to start from scratch for each wanted value. It's then probably not worth worrying much about early termination.
@Steve Jessop: Mark Dickinson's construct is faster, but thanks for the suggestion!
@ChristopheD: I think I maligned Mark's early termination idea unfairly. Adding if len(sieve) < item: luckynumbers.extend(sieve); break after the first line of the loop gives a 3x speed increase on my machine calculating the first 3000. Sorry, Mark.
|
2

An explanation on how to solve this problem can be found here. (The problem I linked to asks for more, but the main step in that problem is the same as the one you're trying to solve.) The site I linked to also contains a sample solution in C++.

The set of numbers can be represented in a binary tree, which supports the following operations:

  • Return the nth element
  • Erase the nth element

These operations can be implemented to run in O(log n) time, where n is the number of nodes in the tree.

To build the tree, you can either make a custom routine that builds the tree from a given array of elements, or implement an insert operation (make sure to keep the tree balanced).

Each node in the tree need the following information:

  • Pointers to the left and right children
  • How many items there are in the left and right subtrees

With such a structure in place, solving the rest of the problem should be fairly straightforward.

I also recommend calculating the answers for all possible input values before reading any input, instead of calculating the answer for each input line.

A Java implementation of the above algorithm gets accepted in 0.68 seconds at the website you linked.

(Sorry for not providing any Python-specific help, but hopefully the algorithm outlined above will be fast enough.)

Improve this answer

1 Comment

@stubbscroll: thanks a lot for this very fine answer! I'll have my go at implementing this weekend (it's late here now) and let you know how it went.
1

You're better off using an array and zeroing out every Nth item using that strategy; after you do this a few times in a row, the updates start getting tricky so you'd want to re-form the array. This should improve the speed by at least a factor of 10. Do you need vastly better than that?

Improve this answer

1 Comment

Interesting suggestion, thanks. I'll give this a try and report back with with the results!
0

Why not just create a new list?

L = [x for (i, x) in enumerate(L) if i % n]
Improve this answer

1 Comment

Hi dan04: I've just rudimentarily tested this but this would be about 200 times slower then the current solution (collected from the answers of gnibbler, Mark Dickinson, Steve Jessop)...

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.