CS 190C, Spring 2008: Problem Set 2

Posted: Friday, January 18, 2008

Due: Thursday, January 24, 2008, 10pm (electronic submission via Blackboard)

Each program should be in a separate file. Name your files problem1.py through problem3.py. This is a good template for your programs for this problem set.

#Aaron Lint
#Problem Set 2, Problem 1
def main():   #This is where your code should go
   print "Hello world."

Problem 1

You have been given the task of writing a small program to search a movie database. The database is provided as a CSV file, Top250Movies.csv, here. in which fields are separated by commas. You should ignore the first line of the file as it simply names each column. Running the program outputs a menu showing options similar to:

Keyword search: 1
Rating search:  2
Statistics:     3
Enter an option: 

The user selects one of the options.

  • Option 1 prompts the user for a word and searches every movie title for that word.
  • Option 2 prompts the user for a minimum rating and a maximum rating, and outputs every movie that has a rating within this range.
  • Option 3 outputs the average rating and the average number of voters for all movies in the database.

For each movie matching the keyword search, the output should be of the form


Hint: Recall that you can read a file line by line using a for loop:

f = open('filename', 'r')
for line in f:
    print 'line =', line

Problem 2

The process of liquid traveling through porous material is known as “percolation”. Project 2 will focus on percolation and this problem will help familiarize you with some of the data structures used. You are given a grid representing a 2D slice of material where a value of 0 indicates empty space (i.e., space where liquid can flow) and 1 indicates where liquid may not flow. The grid will always be square. Write a program that checks whether there exists a column allowing liquid to flow straight down (vertical percolation) through the grid. Note that all you need to determine is whether there exist one column allowing a flow.

Assume the input grid is in a file named “grid.txt”. Your program reads this file and creates the grid using a list of lists structure. Print the grid with '*'s in the column allowing the percolation. You can print '*'s in other location allowing flow, but not leading to percolation. The input file is structured as follows

0 0 0 0 0 1
0 1 0 1 1 0
0 1 0 1 1 1
0 1 0 1 1 1
0 1 0 0 1 1
1 0 0 0 0 1


* * * * * 1
* 1 * 1 1 0
* 1 * 1 1 1
* 1 * 1 1 1
* 1 * 0 1 1
1 0 * 0 0 1

Here are some sample input files. Sample All Ones Big Grid No Percolation Percolation 1 Percolation 2

Note: If you have VPython experience, feel free to use VPython modules to print the final grid.

Problem 3

This problem should be solved using arrays and should perform operations on arrays (do not use lists). The input (from the command line) consists of two strings containing an equal number of characters, say n, and an integer k. You will then explode the strings into arrays using the following process:

s = raw_input()      # read a string from the user
l = list(s)          # explode s into character elements
a = array(l)         # construct an array from the list

The two arrays contain a scrambled message that you are to decode. In order to recover the message, you should rotate the content of first array k places to the right (i.e., a[0] ends up in a[k], a[1] in a[k+1] etc) and the content of the second array rotates k places to the left (i.e., b[0] ends up in b[n-k-1], b[1] ends up in b[n-k-2] etc. Note that when rotating, elements that leave one end of the array should wrap around to the other side. You can use an auxiliary helper array to achieve the rotations (it can be done without one, however).

After rotating, combine the content of the two new arrays in a new array c choosing the next letter from each of a and b, alternating between the two. This operation is also called a “shuffle”: a[0], a[1], a[2] … end up c[0], c[2], c[4],… and b[0], b[1], b[2] … end up in c[1], c[3], c[5], ….. Array c is the final output.

Your program should prompt the user for two strings and the rotation value, k. You should output the decoded message.

To make the final message more readable you may use the following code

print ''.join(C)       # join all characters back into a string and print it

You may use the following samples in testing your code:

        a          |         b         |   k
 dihatc tm         | a ingttak         |   6
 epaioiusprairglsi | itcxildcosueclfai |  10
 epru e            | dept!u            |   5
cs190c/problemset2.txt · Last modified: 2009/01/28 20:33 (external edit)
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki