Class Notes: 1d Lists: Worked Examples

1. The Locker Problem
2. Anagrams
3. The Sieve of Eratosthenes
4. The Prime Counting Function

The Locker Problem

  video

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))

Select Visualize Run

Anagrams

  video

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()

Select Visualize Run

The Sieve of Eratosthenes

  video

# 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))

Select Visualize Run

The Prime Counting Function

  video

# 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()

Select Visualize Run