- The Locker Problem
def lockerProblem(lockers):
isOpen = [ False ] * (lockers+1)
students = lockers
for student in range(1,students+1):
for locker in range(student, lockers+1, student):
isOpen[locker] = not isOpen[locker]
openLockers = [ ]
for locker in range(1, lockers+1):
if isOpen[locker]:
openLockers.append(locker)
return openLockers
print(lockerProblem(2000))
- Anagrams
def letterCounts(s):
counts = [0] * 26
for ch in s.upper():
if ((ch >= "A") and (ch <= "Z")):
counts[ord(ch) - ord("A")] += 1
return counts
def isAnagram(s1, s2):
# First approach: same #'s of each letter
return (letterCounts(s1) == letterCounts(s2))
def isAnagram(s1, s2):
# Second approach: sorted strings must match!
return sorted(list(s1.upper())) == sorted(list(s2.upper()))
def testIsAnagram():
print("Testing isAnagram()...", end="")
assert(isAnagram("", "") == True)
assert(isAnagram("abCdabCd", "abcdabcd") == True)
assert(isAnagram("abcdaBcD", "AAbbcddc") == True)
assert(isAnagram("abcdaabcd", "aabbcddcb") == False)
print("Passed!")
testIsAnagram()
- The Sieve of Eratosthenes
# Sieve of Eratosthenes
# This function returns a list of prime numbers
# up to n (inclusive), using the Sieve of Eratosthenes.
# See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
def sieve(n):
isPrime = [ True ] * (n+1) # assume all are prime to start
isPrime[0] = isPrime[1] = False # except 0 and 1, of course
primes = [ ]
for prime in range(n+1):
if (isPrime[prime] == True):
# we found a prime, so add it to our result
primes.append(prime)
# and mark all its multiples as not prime
for multiple in range(2*prime, n+1, prime):
isPrime[multiple] = False
return primes
print(sieve(100))
- The Prime Counting Function
# Sieve of Eratosthenes
# More complete example, showing one reason why we might
# care to use the sieve rather than the simple isPrime function
# we already learned how to write.
# We'll be computing the prime counting function, pi(n):
# See http://en.wikipedia.org/wiki/Prime-counting_function
# We'll do it two different ways: once using the simple isPrime
# function, and again using the sieve. We'll time each way
# and see how it goes.
####################################################
###################
## sieve(n)
###################
# This function returns a list of prime numbers
# up to n (inclusive), using the Sieve of Eratosthenes.
# See http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
def sieve(n):
isPrime = [ True ] * (n+1) # assume all are prime to start
isPrime[0] = isPrime[1] = False # except 0 and 1, of course
primes = [ ]
for prime in range(n+1):
if (isPrime[prime] == True):
# we found a prime, so add it to our result
primes.append(prime)
# and mark all its multiples as not prime
for multiple in range(2*prime, n+1, prime):
isPrime[multiple] = False
return primes
# Here we will use the sieve to compute the prime
# counting function. The sieve will return a list
# of all the primes up to n, so the prime counting
# function merely returns the length of this list!
def piUsingSieve(n):
return len(sieve(n))
###################
## piUsingisPrime(n)
###################
# Here we will use the isPrime function to compute
# the prime counting function.
def piUsingIsPrime(n):
primeCount = 0
for counter in range(n+1):
if (isPrime(counter)):
primeCount += 1
return primeCount
def isPrime(n):
if (n < 2): return False
if (n == 2): return True
if (n % 2 == 0): return False
for factor in range(3, 1+int(round(n**0.5)), 2):
if (n % factor == 0):
return False
return True
####################################################
###################
## test code
###################
# Before running the timing code below, let's run
# some test code to verify that the functions above
# seemingly work. Test values are from:
# http://en.wikipedia.org/wiki/Prime-counting_function
def testCorrectness():
print("First testing functions for correctness...", end="")
assert(piUsingSieve(10) == 4)
assert(piUsingIsPrime(10) == 4)
assert(piUsingSieve(100) == 25)
assert(piUsingIsPrime(100) == 25)
assert(piUsingSieve(1000) == 168)
assert(piUsingIsPrime(1000) == 168)
print("Passed!")
testCorrectness()
####################################################
###################
## timing code
###################
# Finally we can time each version for a large value of n
# and compare their runtimes
import time
def testTiming():
n = 1000 # Use 1000 for Brython, 1000*1000 for Python
print("***************")
print("Timing piUsingIsPrime(" + str(n) + "):")
startTime = time.time()
result1 = piUsingIsPrime(n)
endTime = time.time()
time1 = endTime - startTime
print(" result = " + str(result1))
print(" time = " + str(time1) + " sec")
print("***************")
print("Timing piUsingSieve(" + str(n) + "):")
startTime = time.time()
result2 = piUsingSieve(n)
endTime = time.time()
time2 = endTime - startTime
print(" result = " + str(result2))
print(" time = " + str(time2) + " sec")
print("***************")
print("Comparison:")
print(" Same result: " + str(result1 == result2))
print(" (time of isPrime) / (time of sieve) = " + str(time1 / time2))
print("And this only gets worse, and quickly, for larger values of n.")
testTiming()