Lab 3 Part 1: Counting generations

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 allOnes(L) that takes as input a list of numbers L and returns True if all of L's elements are 1 and returns False otherwise. Raw recursion is one good way to do this, though not the only one. Notice that the empty list vacuously satisfies the all-ones criterion, because it has no elements at all! Here are some examples to check:

>>> allOnes( [1,1,1] )

True

>>> allOnes( [] )

True

>>> allOnes( [ 0, 0, 2, 2 ] ) # this should be False!

False # but be careful... if you use sum(L) == len(L), this will be True

>>> allOnes( [ 1, 1, 0 ] )

False

Caution about True/False!

You will 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 1s.
• Second, change runGenerations so that it returns the number of generations needed to evolve the input into all 1s.

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 rwSteps problem from the last homework, or the mylen recursive example written 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 zero) 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

This link continues the lab with the same hw3pr1.py file.