Lab Exercise 11

Lists for Experiments and Games

CS 1510 - 11/10/2015
Due by 11:11 AM on 11/11/Wednesday

   lab11 -- Lists for Experiments and Fun. 
                                            *** random.randint(lower, higher) bucket lists and TIC TAC TOE game ***	
   Due by submit before Wednesday, Nov 11, 11:11 AM

Introduction

This week is again all about lists. You will use them to run an experiment, and you will use them to implement the basic tools for a simple game. Of course, we also get more practice with loops and functions and strings and ....

You will submit a responses.txt file this week. Download this template file and use it to record any answers or predictions asked for in the exercises.

Task 1: Testing the Randomness of Python's random.randint()

We will learn and use two functions from Python's random module to generate random numbers for simulations, games and a few other tasks this semester. Computers can't generate truly random numbers, because they depend on programs and inputs that are not completely random. But we can write programs that generate streams of numbers that look and behave like they are random.

How might we judge the randomness of a random number generator? One measure is the distribution of the numbers. We should expect that Python's randint(lower, upper) function generates all the numbers between lower and upper over time, and that each number is equally likely. We would also expect that numbers in the 60s would be as likely as numbers in the 90s or the 20s.

Let's write code to evaluate the distribution of the numbers produced by randint().

Step 1.

Download this partially-completed program.

Step 2.

Write a function named generate_random_list(list_size) that produces a list of size list_size consisting of random numbers in the range MIN_VALUE .. MAX_VALUE, where those are specified as constants in our program.

       >>> generate_random_list(10)
       [45, 79, 9, 86, 98, 89, 26, 82, 49, 13]

       >>> generate_random_list(16)
       [59, 77, 22, 58, 25, 46, 36, 2, 7, 72, 26, 36, 23, 15, 83, 53]

Step 3.

Write a function named generate_empty_buckets(n) that produces a list consisting of n empty lists.

       >>> generate_empty_buckets(10)
       [[], [], [], [], [], [], [], [], [], []]

Step 4.

Write a short program that:

• Generates a random list of size 20.


• Generates a list of ten empty buckets.


• Loops through the list of random numbers and puts each number in a bucket according to its first digit. For example, 82 would go in bucket[8] and 16 would go in bucket[1]. We will treat single-digit numbers as if they have a 0 as their first digit.


• Loops through the resulting buckets to see what the smallest, largest, and average bucket sizes are.

  See example IDLE interactions and output. One run had 30 and four runs had 20 for the list size. randomIntegers.txt...



• Prints the smallest and largest bucket sizes, as well as the expected average.

For example:

       expected bucket size = 100000
       smallest bucket size = 99659
       largest  bucket size = 100489

After you have your code working, change LIST_SIZE to one million. Re-run the experiment at least three times. Record the results in your responses file.

Step 5.

Modify your program to do exactly the same thing, except this time putting each number in a bucket according to its last digit. For example, 82 would now go in bucket[2], 16 would go in bucket[6], and 4 would go in bucket[4].

Run the experiment at least three times with lists of one million random integers. Record the results in your responses file.

Task 2: Building Infrastructure for a Simple Game

Lists of lists can be used to represent the boards for many simple games. Suppose that two people are playing the common children's game Tic-Tac-Toe. The players might be making marks on a grid, like this:

       |   | X
    -----------
     O |   | X
    -----------
       |   | O

    [ [' ', ' ', 'x'],
      ['o', ' ', 'x'],
      [' ', ' ', 'o'] ]

To create a program that lets two people play Tic-Tac-Toe, we will need a number of functions that operate on such lists. Let's do it.

Download or copy and paste this Python file named tic_tac_toe.py. Show an example of output demonstrating your functions for each step below in your responses file.

For the following steps, assume these assignments:

    board_1 = [ [' ', ' ', 'x'],  \
                ['o', ' ', 'x'],  \
                [' ', ' ', 'o'] ]

    board_2 = [ [' ', ' ', 'x'],  \
                ['o', 'o', 'x'],  \
                [' ', ' ', 'x'] ]

    board_3 = [ ['o', ' ', 'x'],  \
                ['x', 'o', 'x'],  \
                [' ', ' ', 'o'] ]

Step 1.

Write a function named display(board) that prints the rows of a board. For example:

       >>> display( board_1 )
       [' ', ' ', 'x']
       ['o', ' ', 'x']
       [' ', ' ', 'o']

       >>> display( board_2 )
       [' ', ' ', 'x']
       ['o', 'o', 'x']
       [' ', ' ', 'x']

       >>> display( board_3 )
       ['o', ' ', 'x']
       ['x', 'o', 'x']
       [' ', ' ', 'o']

Bonus. Provide a prettier, more human-friendly output -- but only after you do Steps 2-5 first!

Step 2.

Write a function named is_occupied(board, row, col) that returns False if board[row][col] is a space, and True otherwise. For example:

       >>> is_occupied(board_1, 0, 1)
       False

       >>> is_occupied(board_2, 2, 2)
       True

Step 3.

Write a function named make_move(token, board, row, col) that places the given token at board[row][col], but only if that position is available. We will use this function for the change it makes to the board. Have it change the board by adding the X or O to its new state after the move, or return false if the position was already occupied. For example:

       >>> make_move('x', board_1, 1, 1)
       >>> display( board_1 )
       [' ', ' ', 'x']
       ['o', 'x', 'x']
       [' ', ' ', 'o']

       >>> make_move('o', board_1, 2, 0)    # original board_1 again to start
       >>> display( board_1 )               
       [' ', ' ', 'x']
       ['o', ' ', 'x']
       ['o', ' ', 'o']

       >>> make_move('x', board_1, 2, 2)
       False

Step 4.

Write a function named is_win_for(token, board) that takes as arguments a player token ('x' or 'o') and a game board. It returns true if there is a row, column, or diagonal with three of that token. For example:

       >>> is_win_for( 'x', board_1 )
       False
       >>> is_win_for( 'x', board_2 )
       True
       >>> is_win_for( 'o', board_2 )
       False
       >>> is_win_for( 'x', board_3 )
       False
       >>> is_win_for( 'o', board_3 )
       True

Step 5.

Write a function named make_board() that creates a brand new game of TIC TAC TOE.
Example demo of the function:

>>> b = make_board()
>>> 
>>> display(b)
[' ', ' ', ' ']
[' ', ' ', ' ']
[' ', ' ', ' ']

---

Step 6 - Optional, not required, we will do this in class. .

Think about this and start developing it, if you wish. It is OPTIONAL, it is not required.
Write a function named play_game() that lets players 'x' and 'o' alternate making moves on a game board. As soon as one player wins, the program should announce the winner and terminate. If the board becomes full with neither player winning, the program should announce a tie game or stalemate and terminate.

Finishing Up

Make sure that your program files are complete and saved. Save your responses.txt file.

Submit your files for grading on the electronic submission system, at lab11 -- Lists for Experiments and Fun.

• random_test.py
• tic_tac_toe.py
• responses.txt

Due by 11:11 AM on 11/11/Wednesday

As always, make sure you see the verification screen that says The files listed above were uploaded.

If you need any help, let me or Logan know.