Notes and code for Week 2 of Informatics at PLC Sydney

week2.py

# -----------------------------------------------------------------------------
#                            Informations 2019 Week 2
# -----------------------------------------------------------------------------
#
# After Week 1 we had the following functions:
#   is_divisible(number, factor)  --> True/False
#   factors(n)                    --> list
#   is_prime(n)                   --> True/False
#
# This week we calculate the HIGHEST COMMON FACTOR of two numbers.
# E.g.
#   hcf(28,70)  --> 14
#   hcf(60,120) --> 60
#   hcf(8,11)   -->  1
#
# For that, we need (at least to begin with) our factors(n) function.
# I am using a new function is_factor instead of the old is_divisible.
# I am also rewriting factors(n) to be more efficient.

def is_factor(f, n):
  return (n % f == 0)

def factors(n):
  result = []
  for f in range(1,n//2):
    if is_factor(f, n):
      result.append(f)
  result.append(n)
  return result

# Now consider the highest common factor of 16 and 40.
#   factors(16) --> [1,2,4,8,16]
#   factors(40) --> [1,2,4,5,8,10,20,40]
#
# The factors in common are [1,2,4,8] and the highest of these is 8.
# The way we will find the HCF is to start with the 16 and ask "is 16 in the
# other list?". The answer is False. Then go to the 8 and ask "is 8 in the other
# list?", and the answer is True. Therefore, the HCF is 8.

# We need a function that tells us whether a given number is present in a list.

def contains(target, xs):
  for x in xs:
    if x == target:
      return True
  return False

def test_contains():
  assert(contains(5, [1,3,5,7,9]) == True)
  assert(contains(5, [2,4,6,8])   == False)
  assert(contains(3, [])          == False)

# We introduce a function hce (highest common element), which takes two sorted
# lists and returns the first common thing it finds when searching backwards
# through the first list. Here is an algorithm description.
#
#   hce(xs, ys)              xs and ys are sorted lists
#     For each x in xs, going backwards
#       If x is in the list ys
#         Return x
#     If we get this far, there is nothing in common, so...
#       ...Return None
#
# To go backwards through a list, we use index notation. The biggest index of
# the list [1,3,7,21] is 3 -- counting starts at zero -- and this is found by
# taking the length of the list (4) and subtracting one.

def hce(xs, ys):
  # Return the highest common element between the two lists, searching backwards in xs.
  index = len(xs) - 1                     # Our starting index
  while index >= 0:                       # Loop while we have a valid index
    x = xs[index]                         # x is the element in xs
    if contains(x, ys):                   # See if x is in ys
      return x                                # Return x if it is
    index = index - 1                     # Decrease the index and repeat the loop
  # If we get this far...
  return None

def test_hce():
  list1 = [1,3,7,21]
  list2 = [1,2,5,10]
  list3 = [1,2,3,5,6,10,15,30]
  list4 = [99, 100]
  assert(hce(list1, list2) == 1)
  assert(hce(list1, list3) == 3)
  assert(hce(list2, list3) == 10)
  assert(hce(list1, list4) == None)

# Now we have enough pieces to implement hcf(a,b).
# We get the factors of a and the factors of b, and get the highest common
# element of the two lists.

def hcf(a,b):
  return hce(factors(a), factors(b))

def test_hcf():
  assert(hcf(21,30) == 3)
  assert(hcf(10,30) == 10)
  assert(hcf(10,21) == 1)
  assert(hcf(21,10) == 1)
  assert(hcf(4200,3528) == 168)

# This function will run all our tests.
# If an assertion is wrong, we get an error.
# If nothing happens, all the tests passed.

def test():
  test_contains()
  test_hce()
  test_hcf()

# So we have written a function that will calculate the HCF of two numbers. Is
# this an efficient way to calculate the HCF? Not really. Next week we will look
# at two more approaches:
#  * the intersection of two sets
#  * Euclid's algorithm
#
# Feel free to do some research on those things before Fri 22 March.
#  * https://www.thoughtco.com/intersection-in-set-theory-3126587
#  * https://brilliant.org/wiki/greatest-common-divisor/
#  * https://www.programiz.com/python-programming/set