Compsci 101, Fall 2012, Lab 3

There are three parts to this lab. Each part is meant to provide practice with looping and lists, but the contexts are different.

Introduction: Monte Carlo Simulations


A room of computers working at the National Advisory Committee for Aeronautics, 1949. Courtesy of Wikipedia.		 "Monte Carlo" simulations are a very powerful technique for calculating values which cannot be calculated exactly. They have been used since the dawn of computing, when scientists on the Manhattan Project were working to design an atomic bomb. Back then, a "computer" was a woman whose job was to do math problems all day long. The nuclear physicists would construct various scenarios of uranium reactions, and then hand these problems off to a room full of computers, similar to a modern data center. Each individual problem didn't explain much about fission, but taking hundreds of scenarios in aggregate allowed the physicists to design the bomb.

In this lab you'll answer some questions about list comprehensions and then use them in some Monte Carlo simulations.

Part 1: Vocabulary: List Comprehensions

A Python list comprehension allows you to create a list from another list/sequence. For example the list comprehensions below generate the output shown. Note that a list comprehension is a list defined by a for-loop inside square brackets, and that the loop iterates over some list, creating a new list in the process. In the examples below, the output of each print statement is shown in italics. 

print [x*2 for x in range(0,10)]
[0,2,4,6,8,10,12,14,16,18]



print [s[0] for s in ['apple', 'termite', 'elephant']]
['a','t','e']



print [n % 2 == 0 for n in [2,4,6,1,3,5,8]]
[True,True,True,False,False,False,True]


print [n for n in [2,4,6,1,3,5,8] if n % 2 == 0]
[2,4,6,8]
Without using a computer, (so by thinking) show what each line below prints. Write your answers on the turn in sheet for lab. 
  1. print [x**2 for x in range(1,10,2)]

  2. print [s[1] for s in ["big", "brown", "bare", "stem", "pea"]]

  3. print ['po'*i for i in range(0,5)]

  4. print [i*i for i in range(1,10) if i % 2 == 0]

  5. print sum([1 for p in [1,2,3,4,5,6,7,8]])

  6. print sum([1 for x in "ostentatiously" if "aeiou".find(x) > -1])

    Generate List Comprehensions

  7. Using a list comprehension write one expression using the function sum that returns the sum of all the odd integers in a list of integers named nums -- so for [1,3,2,4,5] your expression should evaluate to 9 --- fill in the parentheses: sum(...).

  8. Using a list comprehension and the list functions sum and len write an expression that returns the average length of all the strings in a list of strings named strs. So you'll call two list functions: one with strs as an argument and one with a list comprehension using strs as an argument: combining in one expression sum(...) and len(...). For example, the average length of the strings in the list below is (3+3+4+5)/4 = 15/4 = 3.75 
      strs = ["cat", "dog", "bear", "tiger"]

Part 2: APT and loop practice

You'll work on loops and strategies to solve one APT: ScoreIt which is part of the apt-2 group of APTs, so you can snarf them for testing.

  1. What value should maxPoints return for the call maxPoints([2,2,4,5,4]) and why?
  2. The number of occurrences of 1 in a list toss is given by the expression toss.count(1) --- what expression gives the number of 2's that occur in the list toss?

  3. The code below sets variable best correctly to be the best score for a list toss if the only values in the list are 2 or 4. Explain in words why the second if CANNOT be an elif --- provide an example that would fail to set best correctly for a list of only 2's and 4's if an elif statement is used (explain your reasoning). best = 0 if 2*toss.count(2) > best: best = 2 * toss.count(2) if 4*toss.count(4) > best: best = 4 * toss.count(4)
  4. If the values used above, 2 and 4, are replaced by a variable roll then a loop could be used as shown. Explain in words how this loop replaces six if statements similar to the two shown above so that the code below results in best having the best score for the list toss best = 0 for roll in [1,2,3,4,5,6]: if roll*toss.count(roll) > best: best = roll*toss.count(roll) return best
  5. Explain in words why the single line below using a list-comprehension will return the correct result for this APT (replacing the loop with if statement above). return max([roll*toss.count(roll) for roll in [1,2,3,4,5,6]])

Part 3: DiceRolling and Tossing Coins

For this problem you'll be asked to think about the code in DiceRolling.py,and OneDWalker.py which you can snarf as lab3.

  1. In DiceRolling.py the function get_diceroll returns the sum of two dice rolls, it's reproduced below. If the last statement is changed to return a+a what will the bar-graph that's generated look like? Draw a graph you think is reasonable and provide a justification on the handin page.

    def get_diceroll(): ''' Returns a random roll of two 'fair' die ''' a = random.randint(1,_DIESIDES) b = random.randint(1,_DIESIDES) return a+b

  2. In DiceRolling.py the function print_stats takes a list of dice-rolls and analyzes the list --- the list is created by calling the function generate_rolls to return a list of rolls, e.g., in the program shown 100,000 roles are created and stored in a list. As an alternative, the function could take an int parameter named numRolls indicating the number of dice rolls to generate. Instead of looping over the list, the loop would be: counters = [0]*(2*_DIESIDES+1) for i in range(0,numRolls): roll = get_diceroll() counters[roll] = counters[roll] + 1 # code here the same On the handin page describe why this approach could be preferred to generating a list of all the dice rolls.

  3. What changes are needed (all of them) so that three dice are rolled instead of two, i.e., so that the total rolled on each dice roll is between 3 and 18 (for three six-sided dice).

These questions are about the code in OneDWalker.

  1. Run the program five times and write the numbers that are printed (after the 11) on the handin pages

  2. If you change steps in the trials function to 6 describe how the results printed are different and why they are different.

  3. Describe in words why the test while sum(locs) != 2*n+1 in the loop in walk works.

  4. Describe two ways of determining how many steps are needed (average) to visit all locations when the walk goes from -500 to 500. One method is simple but might take a while, the other method involves predicting a time based on trends from runs that do not take so long.