There are two parts to this assignment. In the first you will write a single class in a module. In the second you will write various small classes and generator in a module.

You should download the program2 project folder and use it to create an Eclipse project. The first module can be tested in a driver I supply; you will create the second module in this project. Eventualy you will submit each module separately in Checkmate.

You should work on this assignment in pairs, with someone in your lab section. Try to find someone who lives near you, with similar programming skills, and work habits/schedule: e.g., talk about whether you prefer to work mornings, nights, or weekends; what kind of commitment you will make to submit program early. If you believe that it is impossible for you to work with someone, because of some special reason(s), you should send me email stating them and asking for special permission to work alone (which I do grant, but not frequently).

Only one student should submit all parts of the the assignment, but both student's names should appear in the comments at the top of each submitted .py file. It should look something like

# Romeo Montague, Lab 1
# Juliet Capulet, Lab 1
# We certify that we worked cooperatively on this programming
#   assignment, according to the rules for pair programming

Print this document and carefully read it, marking any parts that contain important detailed information that you find (for review before you turn in the files). The code you write should be as compact and elegant as possible, using appropriate Python idioms.

Problem Summary:

  x = 0
  for i in irange(1,10): x += 1/10
  print(x) # prints 0.9999999999999999

  x = Rational(0)
  for i in irange(1,10): x += Rational(1,10)
  print(x) # prints 1/1

  print(compute_e(100 ))                 # e ~ 1/0! + 1/1! + 1/2! + ... 1/100!
  print(compute_e(100).approximate(100)) # if you write approximate: extra credit

(which prints... look for the / as the 10th character on the 3rd line)
  42997789077987677528011991222420376346635182807847142751317828133465975238
  70956720660008227544949996496057758175050906671347686438130409774741771022
  426508339/1581800261761765299689817607733333906622304546853925787603270574
  49521355920728670523629599959587319129243555798012243658052856289689600000
  0000000000000000000

  2.718281828459045235360287471352662497757247093699959574966967627724076630
  3535475945713821785251664274

Details

• Define a class named Rational in a module named rational.py

• Write the _gcd (greatest common divisor) algorithm in a class method and call it as needed in the __init__ method. The algorithm for compuing the gcd of two positive integers x and y is:

    while y != 0:
        x, y = y, x%y

  Where the result (gcd of the original x and y) is stored as the final value of x after the loop terminates. Eclipse complains about all class methods, but ignore that error (and the script should still run if you wrote _gcd correctly).

• __init__ has two parameters, the numerator then denominator of the rational number being constructed (use default values of 0 and 1 respectively, so just as int() is 0, Rational() is 0/1 (this is how it will print with __str__ method described below). This method sholuld raise AssertionError(s) if either parameter is not an int or if the denominator is 0.

  Objects in the Rational class are immutable: the methods you will write should never bind any instance variables (except __init__, which initializes them) but exclusively returns newly constructed Rational objects. I suggest using the instance variables num and denom.

  The following data invariants should be implemented in __init__ for representing rational numbers; you can use these invariants to help simplify the code in methods.

  1. Zero is always represented by 0/1
  2. The denominator is always positive; rational numbers are negative or positive based on the sign of their numerator
  3. The numerator and denominator are stored in the lowest possible terms: they have no factors in common (use gcd to establish this data invariant).

  For example, print(Rational(6,-8)) prints -3/4 (see __str__ below): the numerator is negative and the numerator and denominator have no common factors.

• __repr__ returns a string, which when passed to eval returns a newly constructed rational with the same value (==) to the object __repr__ was called on.

• __str__ returns a string, with the (signed) numerator and the denominator (always positive) separated by a slash(/); see examples of of printing a Rational above.

• Write all the underscore methods needed to ensure the prefix +/- work correctly.

• Write all the underscore methods needed to ensure that the add, subtract, multiply, and divide (/) operators produce the correct answers when their operands are any combination of Rational and int values. Hint: When mixing types, convert the int to an equivalent Rational and then perform the operation: e.g., 5 converts to Rational(5,1) If Python tries to apply an arithmetic operator to a Rational and any other type of value (besides Rational or int) raise the standard TypeError with the standard messsage about unsupported operand types: see what 1+'a' produces.

• Write the underscore method that allows us to raise a Rational to any int power (positive or negative): e.g., print(Rational(1,2)**10) prints 1/1024 and print(Rational(2,1)**-2) prints 1/4.

• Write all the underscore methods needed to ensure that we can compare two Rationals with the six standard relational operators. If Python tries to compare a Rational with any other type of value raise the standard TypeError with the standard messsage about unorderable types.

• Python automatically provides meanings for +=, -=, *=, /=, and **=; ensure they are correct or rewrite the needed underscore methods.

• Ensure that the abs function works on rationals and that the boolean intepretation of a rational is 0/1 is False and any non-zero value is True.

• Extra credit:
  • Write a method name approximate that returns a string showing the decimal approximation of the Rational to the specified number of decimal places. So, Rational(1,123).approximate(10) returns '.0081300813'. Hint: deal with the sign of the result, the integer part, and the decimal part (by computing the next digit after the decimal point by multiplying by 10 -I know, a bit cryptic, but it is extra credit).
  • Write the __setattr__ method so that after the num and denom instances variables are set in __init__ trying to change them will raise the NameError exception with an appropriate message about which instance variable was attempted to be changed.
  • Write a class method named best_approximation whose argument an int. Return a rational number closest to the one this method is called on, subject to the requirement that its numerator and denominator contain no more digits than the integer argument. For example Rational(314159,100000).best_approximation(2) returns 22/7 (the best approximation of π using 2 digit numbers).

  The Rational class I am asking you to write duplicates the functionality of the Fraction class currently available in Python. You may not use the Fraction class, nor the Decimal class in any of your code

  Testing

  I provided a short driver that allows you to enter one-line Python statements; it includes a function to compute π by truncating an infinite series. Note that exceptions are raised, they are printed by the driver but the Command: prompt sometimes appears misplaced.

  You can use this driver or write code at the bottom of your rational.py module to test the Rational class (as you are writing its methods). Try to incrementally test the methods you write, not write all mthods in the class then test it. Here is a short example of the driver running.

    Command: x = Rational(1,2)
    Command: y = Rational(1,3)
    Command: print(x+y)
    5/6
    Command: print(-x)
    -1/2
    Command: print(x+2*y)
    7/6
    Command: print(x > y)
    True
    Command: print(compute_e(10))
    9864101/3628800
    Command: print(x < 1)
      Traceback (most recent call last):
      ....trace details
      TypeError: unorderable types: C() < int()
  

Problem Summary:

Details

• Define a class named Bag in a module named bag.py

• __init__ has one parameter, an iterable of values that initalize the bag. Writing Bag(['d','a','b','d','c','b','d']) construct a bag with one 'a', two 'b', one 'c', and three 'd'

• __repr__ returns a string, which when passed to eval returns a newly constructed rational with the same value (==) to the object __repr__ was called on. For example, for the Bag in the discussion of __init__ the __repr__ method would print its result as Bag(['a', 'c', 'b', 'b', 'd', 'd', 'd']). Bags like sets are not sorted, so these 7 values can appear in any order.

• __str__ returns a string that more compactly shows a bag. For example, for the Bag in the discussion of __init__ the __str__ method would print its result as Bag(a[1], c[1], b[2], d[3]). Bags like sets are not sorted, so these 7 values can appear in any order.

• __len__ returns the total number of values in the Bag. For example, for the Bag in the discussion of __init__ the __len__ method would return 7.
• __contains__ returns whether or not its argument is in the Bag.

• count returns the number of times its argument is in the Bag: 0 if the argument is not in the Bag.

• add adds its argument to the Bag: if that value is already in the Bag, its count is incremented by 1; if it is not, it is added to the Bag with a count of 1.

• remove removes its argument from the Bag: if that value is already in the Bag, its count is decremented by 1 (and if the count reduces to 0 it is removed from the dict; if it is not in the Bag, throw a ValueError exception, with an appropriate message that includes the value that could not be removed.

• __iter__ that returns an object on which next can be called to produce every value in the Bag: all len of them. For example, for the Bag in the discussion of __init__, the following code

    for i in x:
        print(i,end='')

  would print

    acbbddd

  Bags like sets are not sorted, so these 7 values can appear in any order.

  Ensure that the iterator produces values in the Bag at the time the iterator starts executing; so mutating the Bag during iteration will not affect what valuess it produces.

  Hint: I defined a simple class generator to do this job.

Testing

You can use this driver or write code at the bottom of your bag.py module to test the Bag class (as you are writing its methods). Try to incrementally test the methods you write, not write all methods in the class at once and then try to test them all; verify your progress as you write your code.

Problem Summary:

• sequence takes any number of iterables as parameters: it produces all the values in the first iterable, followed by all in the second, ... , all values in the last iterable. For example

    for i in sequence('abcd','ef','ghij'):
        print(i,end='')

  produces the values 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', and 'j'.

• transform takes any iterable and any function whose domain includes all the iterated values: it produces transformed (by the function) values. For example

    for i in transform('abCdeFg',upper):
        print(i,end='')

  produces the values 'A', 'B', 'C', 'D', 'E', 'F', and 'G'.

• count takes any iterable and any predicate function (returning bool values): it produces a running count of how many values up to the one just iterated over, satisfied the predicate. For example

    for i in count('aBcDEfGhijK', lambda x : 'A'<=x<='Z'): # is upper-case
      print(i,end=' ')

  produces the values 0, 1, 1, 2, 3, 3, 4, 4, 4, 4, and 5.

• chunk_sum takes any iterable and an int n: it produces a the sum of the first n values, the sum of the second n values, etc. If there aren't n more values in the iterable, chunk_sum cannot produce the next result. For exmample

    for i in chunk_sum(irange(1,20),5):
      print(i,end=' ')

  produces the values 15 (1-5), 40 (6-10), 65 (11-15), 90 (16-20). Hint: use a while loop with explicit calls to iter and next.

• Extra credit:
  • Write a method name flatten that returns every value nested in any iterable data type (except for string: return strings as themselves, not their individual characters. For exmample

      for i in flatten([1,2,[3,4,(5,6,7,{'abc':1,'xyz':2}),8,9],10]):
        print(i,end=' ')

    Prints as: 1 2 3 4 5 6 7 xyz abc 8 9 10

    Note that this iterator does not control the order that sets or keys of dicts are iterated through (we could if we used sorted), although iteration through lists and tuples is always sequential. Hint: use iteration and recursion.

  Testing

  I provided a short driver that allows you to test your code. You can use this driver or write code at the bottom of your generator.py module to test these generators.