Because the output of your program will first be preprocessed by an automatic comparison program before being examined by a human being: please follow formatting instructions/examples very carefully. The results your program produces will need to look exactly like the target! Do not embellish with extra titles, blanks, tabs, decimals after integers, or other text. No extras such as "run complete" or "CS212 output" or even an extra space. The formats must be identical. I will take off points for this. (This is realistic. Most companies run test suites on their products and breaking the test suites is not looked upon kindly in industry and often the output of one program can be the input to another.) The testing facility of the submit script will help you get this annoying detail right. I hope to make it easy to get it right. Thanks for your patience.

IMPORTANT: be sure the first line in your python file is: 

#!/usr/bin/env python3

The Problems

The assignment is to write a set of small executable Python files to get practice with simple Python programming and submitting to test tool. The output of these tools will be easy in that the results are text and comparable to a fixed set of output using the unix sdiff tool. You can get some help on reading the comparison by looking at sdiff in the unix handout for the class.

The only module you may use is the sys module.

1) Combinations by remembering previous results

Write a program called fib.py that will read a number one per line from stdin. Some of the example I/O routines in the whiteboards for the classes might be useful to pick an approach to reading. Remember that read functions return strings that must be converted to ints before you use them as ints. Remember most read functions have a trailing newline that might need to be stripped off.

Write a function fib(n) that takes an integer known to be 1 or greater and returns the Fibonacci number of that number. For example: fib(1) is 1, fib(2) is 1, fib(3) is 2, fib(7) is 13, fib(73) is 806515533049393. Use the simple recursive formula and a dictionary to store any previously computed answer so it doesn't have to be recomputed. If it sees the same argument again it just looks it up! Of course it could be easily computed in a loop, but that is not the point of this exercise. Be sure fib has a Python documentation string.

Write a main function that when called goes into a loop getting an int from stdin and computing the fib of that number. If the number read in is less than 1 it stops looping and the dictionary is just printed.

Call main as the last line in the program. Name this program "fib.py".

The fib.py program has been provided. Change it so that it computes the combinations (like for pascal's triangle) by using this recursion: 

Comb(n, k )  = 1                               if k=0 or k = n
             = Comb(n-1, k-1) + Comb(n-1, k)   otherwise

dictionaries can only be indexed by immutable things like constants or tuples. You can make a tuple out of n and k and store the value of the combination in the dictionary under the tuple. Something like: 

dict[ (n, k) ] = value of Comb(n, k)

Follow the pattern in the given program fib.py but rename it comb2.py. It must now read in an n and a k on each line until it reads 0 0.

Pay attention to the formating of the output. It should use the format method on strings to create the exact spacing given.

2) Compute Probabilities

In the game of Risk you march your armies around a map of the world and try and take over the world.

To attack from one country to another you roll die to determine how many armies you lose in the battle. The number of dice you roll depends the number of armies in the attacking and defending countries. Here is the original rule book description: Part 1, Part 2. The only change for this problem is the attacker can use up to 4 die and the defender up to 3.

Write a program called riskdice.py that takes no input.

Write a function attackLoss(avec, dvec) that takes two lists of die rolls as input. These are the attack rolls and defender rolls in unsorted order. It then computes the number of attacker's armies lost and returns that. To do this will have to sort the rolls and compare them. One way quick way might involve the Python zip function and a for statement. The function should have a Python documentation string.

You should now write a main program that tries all combinations of rolls of 4 die for the attacker and 3 die for the defender and creates an unsorted list of the rolls for the attacker called avec and one for the defender. Feeding this into the attackLoss function it counts how many rolls lead to 0, 1, 2, and 3 lost armies. Your output should look like this: 

Attacker Loss Table A:4 D:3 for 6 sided die
Loss Probability
   0 70293/279936 25.1%
   1 73599/279936 26.3%
   2 68873/279936 24.6%
   3 67171/279936 24.0%
It shows the number of armies lost and the probability of the loss as a fraction and as a percentage. The format MUST match exactly so use the format() method on strings to format the output line to look like this. Remember format is critical. 6 to the 7th power is 279936.

HINT: Easiest route for this problem may just be to do 7 nested for statements and that is OK. But you can also be more ingenious with how you create all 279936 possible rolls. This program does not do anything random. It is a brute force try of all possible rolls. We will do a more complex version next assignment.

You have an example solution for riskdice.py. Study how the program works. Also carefully study how the program count.py works by using a function called nextcnt(numsides, c) to create new rolls of dice. You can see how it is returning a Boolean value that indicates when the last set of rolls has been generated. You must remove the 7 nested loops and must have two nested loops using nextcnt(numsides, c): one for the attack rolls stored in avec and one for the defense rolls stored in dvec. Print the table for 4 attack dice and 4 defense dice and 5 sided dice. The new program is called riskdice2.py. 

Attacker Loss Table A:4 D:4 for 5 sided die
Loss Probability
   0 27610/390625 7.1%
   1 54400/390625 13.9%
   2 71960/390625 18.4%
   3 89920/390625 23.0%
   4 146735/390625 37.6%

3) Word Counts

Write a program called wordcount.py. It will keep a dictionary of the unique words that came in on stdin. It will print then in sorted order along with number of times each word occurred. For the opening likes of this famous book: All uppercase should be converted to lowercase and common punctuation removed.

All punctuation will be removed as described in the text below. You should NOT use translate to do this.

Use the provided code wordcount.py to create a program wordcount2.py. It will remove from the input text all characters that are not a lowercase letter, blank, newline, or apostrophe. It will do this by using a for to extract all the characters from the text and add them to a new text if they are one of the acceptable letters. This new text will be broken up by split for words as in the original program. It must NOT use the translate command.

If this is the input: 

O, she doth teach the torches to burn bright!
It seems she hangs upon the cheek of night
Like a rich jewel in an Ethiope's ear;
Beauty too rich for use, for earth too dear!
So shows a snowy dove trooping with crows,
As yonder lady o'er her fellows shows.
The measure done, I'll watch her place of stand,
And, touching hers, make blessed my rude hand.
Did my heart love till now? forswear it, sight!
For I ne'er saw true beauty till this night.

It should write out the words in alphabetical order with counts just like this: 

There 69 unique "words" in the input
a 2
an 1
and 1
as 1
beauty 2
blessed 1
bright 1
burn 1
cheek 1
crows 1
dear 1
did 1
done 1
doth 1
dove 1
ear 1
earth 1
ethiope's 1
fellows 1
for 3
forswear 1
hand 1
hangs 1
heart 1
her 2
hers 1
i 1
i'll 1
in 1
it 2
jewel 1
lady 1
like 1
love 1
make 1
measure 1
my 2
ne'er 1
night 2
now 1
o 1
o'er 1
of 2
place 1
rich 2
rude 1
saw 1
seems 1
she 2
shows 2
sight 1
snowy 1
so 1
stand 1
teach 1
the 3
this 1
till 2
to 1
too 2
torches 1
touching 1
trooping 1
true 1
upon 1
use 1
watch 1
with 1
yonder 1

Submission

Homework will be submitted as an uncompressed tar file that contains no subdirectories. The tar file is submitted to the class submission page. You can submit as many times as you like. The LAST file you submit BEFORE the deadline will be the one graded. Absolutely, no late papers. For all submissions you will receive email at your uidaho address showing how your file performed on the pre-grade tests. The grading program will use more extensive tests, so thoroughly test your program with inputs of your own. Your code should compile and run with runtime errors such as seg faults. If it doesn't it is considered nearly ungradable.

If you have tests you really think are important or just cool please send them to me and I will consider adding them to the test suite.