CODEWITHSUNDEEP
pythonpython-3.x
Emm
Emm

Reputation: 2507

Algorithm is too slow; do I have higher odds of winning the lotto i pick the same 4 numbers

Here is the problem statement.

There is a lottery where 4 random numbers are picked everyday. I want to find out whether I have better odds of winning the lottery (let's say over 1 000 000 trials).

I have added the solution I have written to solve this problem, but it is very slow, running. Anything over 3000 trials is very very slow.

I have added comments to my code to show my reasoning

ADD: I need help finding the bottleneck

ADD2: Code is complete, sorry, had renamed a few variables

#lottery is 4 numbers
#lottery runs 365 days a year
#i pick the same number every day, what are my odds of winning/how many times will i win
#what are my odds of winning picking 4 random numbers
import random

my_pick = [4,4,4,7]
lotto_nums = list(range(0,9))
iterations = 3000

#function to pick 4 numbers at random
def rand_func ():
  rand_pick = [random.choice(lotto_nums) for _ in range(4)]
  return rand_pick

#pick 4 random numbers X amount of times
random_pick = [rand_func() for _ in range(iterations)]

#pick 4 random numbers for the lottery itself
def lotto ():
  lotto_pick = [random.choice(lotto_nums) for _ in range(4)]
  return lotto_pick

#check how many times I picked the correct lotto numbers v how many times i randomly generated numbers that would have won me the lottery
def lotto_picks ():
  lotto_yr =[]
  for _ in range(iterations):
    lotto_yr.append(lotto())
    my_count = 0
    random_count = 0
    for lotto_one in lotto_yr:
      if my_pick == lotto_one:
        my_count = my_count +1
      elif random_pick == lotto_one:
        random_count = random_count +1
  print('I have {} % chance of winning if pick the same numbers versus {} % if i picked random numbers. The lotto ran {} times'.format(((my_count/iterations)*100), ((random_count/iterations)*100), iterations))

lotto_picks()

Upvotes: 0

Views: 258

Answers (2)

valegians
valegians

Reputation: 940

Your problem is with the nested for loop. Your initial running time for your first for loop is of the order O(n) (aka linear). For each initial iteration (let's say i) your nested loop runs i times.

for i in range(iterations):

    for lotto_one in i:

This means that in total your nested loop will be run 4501500 times (sum of numbers from 1 to 3000). Add your initial outer loop iterations to it (3000) and you get 4 504 500 "real" iterations total. Which gives you something like O(n^1.9) running time, almost ^2 running time. That's your bottleneck.

Upvotes: 1

Fernando Irarrázaval G
Fernando Irarrázaval G

Reputation: 913

The reason of why your code is slow is because in each iteration you are calculating all simulations all over again. In reality you need to check if you won the lottery only once per simulation. So lotto_picks() should probably look something like this:

def lotto_picks ():
  lotto_yr = []

  my_count = 0
  random_count = 0
  for _ in range(iterations):
    new_numbers = lotto()
    lotto_yr.append(new_numbers) # You can still save them for later analysis

    if my_pick == new_numbers:
      my_count = my_count +1

    if random_pick == new_numbers: # Changed from elif to if
      random_count = random_count +1

  print('I have {} % chance of winning if pick the same numbers versus {} % if i picked random numbers. The lotto ran {} times'.format(((my_count/iterations)*100), ((random_count/iterations)*100), iterations))

This will make your program run in linear time O(n), and before your code was running at a quadratic time complexity O(n^2).

Upvotes: 2

Related Questions