At the moment, the runGenerations function has evolved its input lists in a number of ways, but it so far has not evolved them for any purpose or to achieve any particular result. In the game of Lights-On, the goal is to evolve the list so that all of its values are “on”. Throughout the rest of the lab, we will use 1 to indicate that a cell is “on” and 0 to indicate that it is “off”. In this portion of the lab, we will experiment with several strategies for evolving a list into a same-length list of all 1s. From now on, our initial lists will consist only of 0s and 1s.

Detecting when we’ve reached our goal

In your hw3pr1.py file write a function named isAllOnes(aList) that takes as input a list of numbers aList and returns True if all of aList’s elements are 1 and returns False otherwise. Raw recursion is one good way to do this, though not the only one, e.g., a list comprehension.Notice that the empty list vacuously satisfies the all-ones criterion, because it has no elements at all! Here are some examples to check:

>>> isAllOnes([1, 1, 1])
True
>>> isAllOnes([])
True
>>> isAllOnes([0, 0, 2, 2])     # this should be False!
False    # but be careful... if you use sum(aList) == len(aList),
         # this will be True
>>> isAllOnes([1, 1, 0])
False

Hint: if you use recursion, a natural base case would be to handle the empty list []. Note that isAllOnes([]) is True!

Caution about True/False!

Especially if you use recursion, you may want to use the line

return True

somewhere in your code, as well as the line

return False

Be sure to return (and not print) these values!

Also, watch out that you’re returning the values True and False. You DON’T want to return the strings “True” and “False”!

Improving the function runGenerations

Now that you have a function for testing if a list is all ones, improve your runGenerations function in two ways:

• First, add a base case to the recursion, so that runGenerations stops when the input list is all 1’s. (Note that the original function runGenerations never stops.)
• Second, change runGenerations so that it returns the number of generations needed to evolve the input into all 1s.

Leave your setNewElement as you left it in the prior exercise, where it returned a randomly generated 0 or 1.

Suggestions

• Leave the print and pause lines before the check to see if the all-ones base case has been reached. That way they will run whether it’s the base case or the recursive case that runs afterward.
• In order to return the number of generations required to evolve the list into all ones, consider the randomWalkSteps problem from the last homework, or the myLen recursive example discussed in class. The idea is to add 1 for each evolve step. That 1 needs to be added to the number of steps needed to evolve the new list into all-ones.

Trying it out

First,you might want to reduce or remove the half-second pause produced by the line time.sleep(0.5). A value of a twentieth of a second (or even zero if you are a speed-reader) might be better for these trials. Then, try your new runGenerations function on input lists with varying numbers of 0s. You should use the random element chooser that you wrote at the end of the previous part of the lab as your setNewElement function. Here are two examples:

>>> runGenerations([0, 0, 0, 0, 1])
[0, 0, 0, 0, 1]
[1, 0, 1, 1, 1]
[1, 1, 0, 0, 0]
[1, 0, 1, 0, 1]
[1, 0, 0, 0, 1]
[1, 1, 1, 1, 0]
[0, 1, 1, 0, 0]
[1, 1, 0, 1, 0]
[0, 0, 1, 1, 0]
[0, 1, 1, 1, 1]
[1, 1, 1, 0, 0]
[1, 1, 0, 1, 0]
[1, 1, 1, 1, 1]
12
>>> runGenerations([0, 1, 0, 1, 1])
[0, 1, 0, 1, 1]
[0, 0, 0, 1, 0]
[0, 1, 0, 1, 1]
[1, 1, 0, 1, 1]
[1, 1, 1, 1, 1]
4

It’s worth mentioning that it can take much longer for a 5-element list to randomly come up all-1s. Another test we ran took 93 steps… As a thought experiment, how many steps would be expected — over many trials— for a 5-element list to randomly generate all 1s? Please add a short comment answering this question at this point in your code.

Call your instructor or TA and

?Get checked 1?

[Try runGenerations([0, 1, 0, 1, 1]) and make sure it stops with all ones and reports the correct number of lines.]

[Click here for the third part of the lab. Continue the lab with the same hw3pr1.py file.

 

---