CPTR 124 Fundamentals of Programming

In this lab you will write some functions that work with Python lists.

  1. Teams

    You may work with a partner for this lab. You and your partner should begin thinking about the problems and begin writing the code before lab time.

  2. Set up

    Download the Python source file listprocessing.py. This file contains skeletal code for the functions that you are to implement. The file has a function named main containing some very simple test code. You can augment this simple test code with your own more exhaustive tests.

  3. Implement the functions

    Implement the five functions found in listprocessing.py. The functions all process Python lists. Some of the functions impose some restrictions about the list's content; for example, some expect the list they process to contain only integers. The behavior of any of these functions is undefined if the list passed to it does not comply with the function's expectations. (Undefined behavior means you do not need to worry about what happens.)

    Python's standard library provides a number of functions that deal with lists, but for this assignment you are limited to the len function. You also may use the list.append method within the functions that construct lists. (It is okay to use the range function, as it does not return a list.)

    The specifications for the functions are listed here:

    • load_int_list(filename)

      This function reads a collection of integers stored in a text file with the name specified by the string parameter filename. The integers in the file are separated by spaces and newlines. This means there may be more than one number on each line. You may find the split and strip string methods useful for extracting the numbers from the file. Do not forget to convert the string representation of the numbers into their proper integer form.

      This function stores the numbers in a list in the same order they appear in the file. The function then returns the list of integers.

    • missing(checklist, mainlist)

      This function returns a list containing all the elements of list checklist that are not found in list mainlist. The elements in the returned list should appear in the same relative order as they appeared in the checklist list. If mainlist contains all the elements in checklist, the function returns the empty list. This function does not modify the lists passed to it.

      For example, if s1 is the list [10, 20, 30, 4, 2, 67, 22, 8, 31, 11] and s2 is the list [10, 100, 398, 20, 16, 30, 2, 6, 22, 8, 310, 177], the call missing(s1, s2) would produce the list [4, 67, 31, 11].

      The returned list will have duplicate elements if the checklist list contains duplicates.

      You may not use list comprehension in this function.

    • missing2(checklist, mainlist)

      This function is identical to missing, except you must implement it with just a single return statement using list comprehension.

    • rotate(seq, dist)

      This function physically rearranges the elements of list seq, shifting all the elements towards the back by a distance of integer value dist. As an element "falls off" the rear, the function places it at the front in the space vacated when it shifted the first element backwards.

      For example, if s is originally [1, 2, 3, 4, 5, 6], the call rotate(s, 2) rearranges s to contain [5, 6, 1, 2, 3, 4].

      Notice that if dist is equal to the size of the list, after the rotation all the elements rotate to their original locations.

      If dist is negative, the function shifts the elements forward dist spots instead of backwards. As an element "falls off" the front the function places it on the rear in the space vacated when it shifted the last element forwards.

      For example, if s is originally [1, 2, 3, 4, 5, 6], the call rotate(s, -2) rearranges s to contain [3, 4, 5, 6, 1, 2]. The rotation is easier to understand if you visualize the list as a circular structure as shown in the following figure:

      Diagram of a list rotation

      The figure shows the original list on the left and the list rotated by –2 on the right.

      This function necessarily can affect the contents of the list. The function should use no extra space except for a few local scalar variables. The function should not return anything to the caller.

    • pairwise_sum(seq, n)

      This function returns a list of 2-tuples (a, b) where a and b both are elements of list seq, a + b = n, and a ≤  b. The result should contain no duplicate 2-tuples. The order of the 2-tupes within the result is unspecified. The function returns the empty list if seq is empty, and the function's behavior is undefined if seq contains at least one non-number. This function does not modify the list passed to it.

      For example, if list lst is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24], the call pairwise_sum(lst, 12) would produce the list [(0, 12), (1, 11), (2, 10), (3, 9), (4, 8), (5, 7), (6, 6)].

    The specification that a function does not disturb the list means that the function should leave contents of the list unchanged; the function may not reassign, rearrange, add, remove, or otherwise change the elements of the list. The specification that a function uses no extra space except for a few local scalar variables means that you may not define any local lists or other potentially large data structures to facilitate the function's processing. You cannot, for example, make a copy of a list. We say that the function processes the list "in place" without copying its contents into another, temporary list. Be aware that this means you cannot slice a list, as slicing a list makes a new list containing the contents of the slice.

    None of the functions specified above should call the print or input functions. You are welcome to add printing statements during development for debugging purposes, but you should remove or comment out these printing statements when you are ready to submit your program for testing.

  4. Check out

    Your finished listprocessing.py file will be evaluated for correctness and compliance. Before showing me your code, be sure that it complies with the following requirements:

    1. Your name and your partner's name should appear in the in a comment at the top of the source code. Failure to provide such a comment results in an immediate failed test.
    2. Ensure that your completed functions in the listprocessing.py module execute without any problems with the original main function. If your functions generate run-time exceptions with the original main function, they will not work with my test program either. If your code exhibits any errors, it counts as a failed test. The simple test code provided is very minimal and is designed merely to verify that your functions meet some minimal standards; it does not begin to demonstrate the correctness of your code's logic. You should write your own test code to verify your functions' correctness.

    You may provide to me your listprocessing.py file for testing up to three times before its due date. The final test determines the score based on the number of functions that pass all their tests. The grade for completed assignments will be 5 + n, where n is the number of functions that pass all of their tests.

    If you provide your functions for their first test after their due date, your score for the assignment is determined by the first test. After the final check you should submit your listprocessing.py Python source file to http://eclass.e.southern.edu.