Instructions for listDiagrams

(produced at 19:09 UTC on 2021-11-01)

This task is part of ps06 which is due at 23:59 EDT on 2021-11-02.

This is an individual task.

You can submit this task using this link.

Put all of your work for this task into the file listDiagrams.py
(which is provided among the starter files)

General Overview

This task involves defining six functions whose purpose is to create lists described by specific memory diagrams.

Let's begin with a sample memory diagram and showing several ways to define a function that creates it. Here's the diagram for a list we'll call list0: A diagram depicting the following memory listing: @0 is a list holding references to objects @1, @2, @1, and @2. Object @1 is a list holding the number 1 and a reference to object @2]. Object @2 is a list holding just the number 2.

We'll consider three different approaches for defining a zero argument function makeList0 that creates and returns the top list in the diagram.

Approach 1 for makeList0: Use variables to name shared sublists

In our makeList0 function, it's OK to define as many local variables as we want to help us, even if they don't appear in the diagram. We can use local variables to name shared sublists and then use these variables to achieve the sharing we desire.

We'll introduce variables shared2, shared1, and top, as shown in the following sequence of statements:

Statements Diagram so far
shared2 = [2] The variable 'shared2', which points to the value @2, which is a list holding the number 2.
shared1 = [1, shared2] The variable 'shared2' as before, along with a variable 'shared1', which points to the value @1, which is a list holding the number one in its first slot and an arrow referencing object @2 (i.e., the same object rerferenced by 'shared2') in its second slot.
top = [shared1, shared2, shared1, shared2] The variables 'shared1' and 'shared2' as before, with an additional variable 'top' which references an object @0 which is a list holding refernces to @1, @2, @1, and @2 in that order.

We can finish by encapsulating the steps for Approach 1 within a zero-argument function makeList0:

def makeList0():
    """
    Returns the top list depicted in the memory diagram for list0.
    Uses Approach 1 to create the appropriate list structure.
    """
    shared2 = [2]                     
    shared1 = [1, shared2]            
    top = [shared1, shared2, shared1, shared2]
    return top

Approach 2 for makeList0: Use a single variable and assignment to list slots

A second approach for creating the list structure shown for list0 is to use a single variable (call it top) to create an initial list with four slots, where all slots but the last one contain bogus placeholder values that will be replaced in subsequent steps. Then we use assignment to list slots to create extra structure and achieve the desired result.

Statements Diagram so far
top = [3, 4, 5, [2]] A variable 'top' which references an object @0 that's a list, holding the numbers 3, 4, and 5 and then in the last slot a reference to a list @2 holding the number 2.
top[0] = [1, top[3]] The same 'top' variable, but now its first slot holds a reference to a list @1 which has two slots holding the number one and a reference to @2.
top[1] = top[3]
top[2] = top[0]
The same 'top' variable, but now the second and third slots have been replaced by references to @2 and @1 respectively.

We can finish by encapsulating the steps for Approach 2 within a zero-argument function makeList0:

def makeList0():
    """
    Returns the top list depicted in the memory diagram for list0.
    Uses Approach 2 to create the appropriate list structure.
    """
    top = [3, 4, 5, [2]]
    top[0] = [1, top[3]]
    top[1] = top[3] 
    top[2] = top[0]
    return top

Approach 3 for makeList0: Use a single variable and .append

A third approach for creating the list structure shown for list0 is to use a single variable (call it top) and use only calls to the list .append method to create the desired diagram using the following steps:

Statements Diagram so far
top = [[1]] A variable 'top' referencing a list @0 with one slot, which references a list @1 with a single slot holding the number 1.
top[0].append([2]) The same variable, now with a second slot in @1 which references @2, a list containing a single slot that holds the number 2.
top.append(top[0][1]) The same variable, except now the object @0 (referenced by the variable 'top') has two slots, and the second references the object @2.
top.append(top[0]) The same variable with a third slot in @0 that references @1 (a second time, since the first slot of @0 also references @1).
top.append(top[1]) The same variable, now with four slots in @0, the last of which references @2.

We can finish by encapsulating the steps for Approach 3 within a zero-argument function makeList0:

def makeList0():
    """
    Returns the top list depicted in the memory diagram for list0.
    Uses Approach 3 to create the appropriate list structure.
    """
    top = [[1]]
    top[0].append([2])
    top.append(top[0][1])
    top.append(top[0])
    top.append(top[1])
    return top

Your Task: Define Functions to Create the List Structures in Six Memory Diagrams

In the file listDiagrams.py, you will flesh out the definitions of six functions that create and return a list. Each function must take zero arguments and return the top list for the structure depicted in the associated memory diagram.

In all of your functions, it is OK to use as many local variables as you want to name parts of the memory diagram, even though the memory digrams themselves do not show any variables. See the three versions of makeList0 above for examples of using local variables in this way.

In all of the functions, it is possible to use only a single local variable (like top in Approaches 2 and 3 for makeList0). If you want to give yourself a challenge, write your solutions using at most only local variable. (We do not have an easy way to test this in Potluck, so it is not officially an ``extra'' goal.)

makeList1

The function makeList1 takes zero arguments and returns a list with the following structure: An object @0 is a list with three slots, containing a reference to @1, the number 3, and a reference to @2. The object @1 is a list holding the numbers 1 and 2, while @2 is another, separate list holding the numbers 1 and 2.

makeList2

The function makeList2 takes zero arguments and returns a list with the following structure: An object @0 which is a list holding two references to an object @1, with the number 3 between them. @1 is a list holding the numbers 1 and 2.

makeList3

The function makeList3 takes zero arguments and returns a list with the following structure: An object @0 which is a 3-slot list, holding references to objects @1, @2, and @3. @1 is a list holding the number 1 followed by a reference to @2. @2 is a list holding a reference to @3 followed by the number 2. @3 is a list holding just the number 3.

makeList4

The function makeList4 takes zero arguments and returns a list with the following structure: An object @0 which is a list with four slots, which hold references to objects @1, @2, @3, and @4. @1 is a list which holds the numbers 4 and 5. @2 is a list which holds refernces to @1 and @3 (in that order). @3 is a list which holds references to @1 and @4. @4 is a second list which holds the numbers 4 and 5, just like @1 did.

makeList5

The function makeList5 takes zero arguments and returns a list with the following structure: An object @0 which is a list with two slots, holding a reference to the string 'parent', and a reference to an object @1. @1 is a list with two slots holding a reference to objects @2 and @3. @2 is a list with two slots holding a reference to the string 'child' and then a reference to object @0. @3 is a list with two slots holding a reference to the string 'child2' and a reference to @0.

Note that this diagram contains some string values; "parent", "child1", and "child2" are strings stored in list slots, not variable names (variables are shown without quotes, have an associated box, and do not have arrows pointing to them).

makeList6

(Defining this function is an extra goal.) The function makeList6 takes zero arguments and returns a list with the following structure: An object @0 which is a list with 3 slots, holding a reference to an object @1, the number 6, and a second reference to @1. @1 is a list with 4 slots, holding the number 7, a reference to @0, the number 8, and a reference to @1 (itself).

Testing your Functions

You cannot tell just from the printed output of your functions whether they have the correct structure. For example, both list1 and list2 have the printed representation:

[[1, 2], 3, [1, 2]]

The list1 diagram from above, depicting an object @0 which is a list with 3 slots, containing a reference to object @1, the number 3, and a reference to object @2. Objects @1 and @2 are clones of each other, each is a list holding the numbers 1 and 2. The diagram for list 2 above, which shows an object @0 that is a list with three slots, holding a reference to object @1, the number 3, and a second reference to @1. @1 is a list holding the numbers 1 and 2.

The Python is operator (covered in Lec 11) is useful for determining which sublists are shared an which are not. For example, executing the statements

list1 = makeList1()
list2 = makeList2()
print('list1[0] is list1[2] =>', list1[0] is list1[2])
print('list2[0] is list2[2] =>', list2[0] is list2[2])

prints

list1[0] is list1[2] => False
list2[0] is list2[2] => True

By using suitable tests involving is (in conjunction with some other tests), it is possible to determine if the lists returned by the six makeListn functions have the correct structure.

In the file listDiagrams.py, for each of the six makeListn functions, there is a zero-argument testn function that has been defined for you that performs appropriate tests using optimism to verify that that the makeListn function returns a list with the correct structure. For example, if you execute test4() and it displays a sequence of (red) checkmarks, you have high confidence that your definition of makeList4 is correct.

There is also a test() function, that, when called, invokes the six testing functions test1() throughtest6(). It's a good idea to calltest()` after you define all six functions to test them all.

Examples

Examples for each function

Note that although these examples show what the results look like as Python values, they don't show the aliasing structure (or lack thereof) that's happening.

In []:
makeList1()
Out[]:
[[1, 2], 3, [1, 2]]
In []:
makeList2()
Out[]:
[[1, 2], 3, [1, 2]]
In []:
makeList3()
Out[]:
[[1, [[3], 2]], [[3], 2], [3]]
In []:
makeList4()
Out[]:
[[4, 5], [[4, 5], [[4, 5], [4, 5]]], [[4, 5], [4, 5]], [4, 5]]
In []:
makeList5()
Out[]:
['parent', [['child1', <Recursion on list with id=4607169472>], ['child2', <Recursion on list with id=4607169472>]]]
In []:
makeList6()
Out[]:
[[7, <Recursion on list with id=4607169152>, 8, <Recursion on list with id=4607169232>], 6, [7, <Recursion on list with id=4607169152>, 8, <Recursion on list with id=4607169232>]]

In the output above, where it says "<Recursion on list with id=...>", this is an indication that the item in that slot is actually an arrow pointing to another part of the same structure. "Recursion" is something that we'll learn about in a few weeks, but essentially it refers to a situation where one thing contains something similar (or even exactly the same) inside of itself, like how trees contain branches which contain leaves, and at each level the structures are similar. It is related to the word "recur" meaning "to occur again," and to the concept of fractals.

Rubric

 
unknown Style Requirements
How your code is written.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown All functions are documented
Each function you define must include a non-empty documentation string as the very first thing in the function.
 
unknown Procedure Requirements
What code you use to solve the problem.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown Define makeList1
Use def to define makeList1
 
unknown Use a return statement
Within the definition of makeList1, use return _ in at least once place.
 
unknown Define makeList2
Use def to define makeList2
 
unknown Use a return statement
Within the definition of makeList2, use return _ in at least once place.
 
unknown Define makeList3
Use def to define makeList3
 
unknown Use a return statement
Within the definition of makeList3, use return _ in at least once place.
 
unknown Define makeList4
Use def to define makeList4
 
unknown Use a return statement
Within the definition of makeList4, use return _ in at least once place.
 
unknown Define makeList5
Use def to define makeList5
 
unknown Use a return statement
Within the definition of makeList5, use return _ in at least once place.
 
unknown Extra goals
Complete all extra goals in addition to the core goals for a perfect score.
 
unknown Define makeList6
Use def to define makeList6
 
unknown Use a return statement
Within the definition of makeList6, use return _ in at least once place.
 
unknown Product Requirements
Your code's result values.
 
unknown Core goals
Complete all core goals for core credit. Get partial credit for completing at least half, and more partial credit for completing at least 90%.
 
unknown makeList1 result looks the same
The result of makeList1 must at least compare equal to the solution result, even if it has a different in-memory structure.
 
unknown The value must have the correct memory structure
The memory structure of the value produced by your code must match that of the value produced by the solution code, including which parts are aliases of each other.
 
unknown makeList2 result looks the same
The result of makeList2 must at least compare equal to the solution result, even if it has a different in-memory structure.
 
unknown The value must have the correct memory structure
The memory structure of the value produced by your code must match that of the value produced by the solution code, including which parts are aliases of each other.
 
unknown makeList3 result looks the same
The result of makeList3 must at least compare equal to the solution result, even if it has a different in-memory structure.
 
unknown The value must have the correct memory structure
The memory structure of the value produced by your code must match that of the value produced by the solution code, including which parts are aliases of each other.
 
unknown makeList4 result looks the same
The result of makeList4 must at least compare equal to the solution result, even if it has a different in-memory structure.
 
unknown The value must have the correct memory structure
The memory structure of the value produced by your code must match that of the value produced by the solution code, including which parts are aliases of each other.
 
unknown makeList5 result looks the same
The result of makeList5 must at least compare equal to the solution result, even if it has a different in-memory structure.
 
unknown The value must have the correct memory structure
The memory structure of the value produced by your code must match that of the value produced by the solution code, including which parts are aliases of each other.
 
unknown Extra goals
Complete all extra goals in addition to the core goals for a perfect score.
 
unknown makeList6 returns the correct result
The result returned when your makeList6 function is run must match the solution result.
 
unknown The value must have the correct memory structure
The memory structure of the value produced by your code must match that of the value produced by the solution code, including which parts are aliases of each other.