15-110 Spring 2011 Homework 5
Due Tuesday, 1-Mar, at 10pm

Same basic directions as hw4, so read those carefully (replacing "hw4" with "hw5", where appropriate, of course).

Additional notes:

  1. SOLO Problem-Solving (with Monte Carlo Methods)  [50 pts]
    Background:  in this problem, we will consider the game of Yahtzee.  Actually, we will consider a limited form of Yahtzee, where a turn progresses as such:  first, a player rolls 5 (six-sided) dice.  Then, the player keeps the dice with the most-frequent value (with ties going to the larger value), and re-rolls the others.      For example, if the player first rolls 3,6,4,3,4, then the player would keep the two 4's, and re-roll the other dice.  The player once again keeps the dice with the most-frequent value (which may have changed!), and re-rolls the others (so there are 3 total rolls of the dice -- the first roll of all the dice, followed by two re-rolls of some of the dice).  At this point, if all 5 dice have the same value, the player wins (we say that the dice are a Yahtzee, or 5-of-a-kind).

    Here is another example:
         Start of turn.
         Player rolls 5 dice, and the player's hand is 1,4,5,4,1
         Player keeps the 4's, and re-rolls the other 3 dice.
         Player rolls 2,2,2.
         Now the player's hand is 2,4,2,4,2 (see?).
         Player keeps the 2's (not the 4's), and re-rolls the other 2 dice.
         Player rolls 1,2.
         Now the player's hand is 2,1,2,2,2
         The turn is over, and since not all 5 dice match, the player did not win the round with a Yahtzee.

    Using the appropriate math, or a quick Google search, we can see that the odds of scoring a Yahtzee in this game are about 347897/7558272, or about 4.6%.  In this problem, we will use Monte Carlo methods to confirm this result.

    Actually, we will generalize the game to allow for different numbers of rolls per turn.  So if we set rollsPerTurn to 3, then we are playing traditional Yahtzee, and we expect the odds of a Yahtzee to be about 4.6%.  We can use our simulation to not only confirm this result, but also to investigate the odds of a Yahtzee if we allow other numbers of rolls per turn.

    To aid in this problem, we will first write some useful helper functions, along with their test functions.
    1. SOLO rollDie and testRollDie [5 pts]
      Write the function rollDie (in the file hw5-solo.py).  This function takes no parameters and returns a random integer between 1 and 6, inclusive.  You should use the function random.randint appropriately.

      Then, write the function testRollDie (in the file hw5-solo.py).  This function takes no parameters and tests whether or not the rollDie function works properly.  If rollDie does work properly, this function should do nothing.  But if rollDie does not work properly, this function should raise an AssertionError (this is how all our test functions work).  Now, how can you tell if rollDie works properly?  Well, what would you expect to be true of, say, ten thousand calls to rollDie?  We cannot say that all 6 possible values would occur exactly 1/6th of the time, but we can expect this to be close to true (and even closer as we increase the rolls).  So what is a reasonable range to allow before flagging an error?  This requires some statistics to answer properly, so instead here we'll simply use a range of 10% (which is large enough to handle the expected variance among 10,000 rolls).  So if we expect a value of E, and we observe a value of O, we will consider this correct if (0.90E <= O <= 1.10E). Of course, you have to check each possible expected value from 1 to 6 (though you only need to the roll the 10,000 dice once, and check all 6 counts after that).  Also:  since we are testing correctness, you cannot assume that rollDie will return a value between 1 and 6, or even an integer, so be sure to test for those cases, too!  We will test your testRollDie function not only against your own rollDie function, but against other rollDie functions that we supply (and those will contain numerous errors for your test function to detect).
    2. SOLO isYahtzee and testIsYahtzee [10 pts]
      Write the function isYahtzee (in the file hw5-solo.py).  This function takes one parameter, the hand, which is a list of dice values, and returns True if the hand is a Yahtzee (that is, all the dice values are the same), and False otherwise.   This function must work for hands of arbitrary positive length, and not assume there are 5 dice.  This function should also return False, rather than crash, for any malformed input, including if the hand is not a list, or is an empty list (of length 0), or contains a non-integer, or contains a value outside the range of 1 to 6.

      Then, write the function testIsYahtzee (in the file hw5-solo.py).  This function takes no parameters and tests whether or not the isYahtzee function works properly.   Again, be thorough, as we will test your testIsYahtzee function against numerous error-ful isYahtzee functions we supply.
    3. SOLO dieToKeep and testDieToKeep [10 pts]
      Write the function dieToKeep (in the file hw5-solo.py).  This function takes one parameter, the hand, which is a list of dice values, and returns the value of the most-frequent die, with ties going to the larger value.  So dieToKeep([3,6,4,3,4]) should return 4.  As with isYahtzee, t      his function must work for hands of arbitrary positive length, and not assume there are 5 dice.  This function should return -1, signifying an error, rather than crash, for any malformed input.

      Then, write the function testDieToKeep (in the file hw5-solo.py).  This function takes no parameters and tests whether or not the dieToKeep function works properly.
    4. SOLO gotAYahtzee and testGotAYahtzee [10 pts]
      Write the function gotAYahtzee (in the file hw5-solo.py).  This function takes one parameter, the rolls per turn, and simulates one round of Yahtzee, as described above (so it rolls 5 dice, keeps some and re-rolls, and repeats for the appropriate number of total rolls per turn).  The function returns True if at the end the resulting hand is a Yahtzee and False otherwise.  The function should also return False for malformed input:  in particular, if rollsPerTurn is not an integer or is not positive.  Note:   this function must also use the rollDie(), dieToKeep(), and isYahtzee() helper functions that you already wrote (after all, that's why you wrote them!).

      Then, write the function testGotAYahtzee (in the file hw5-solo.py).  This function takes no parameters and tests whether or not the gotAYahtzee function works properly.  First, it should handle the easy case of checking that gotAYahtzee deals properly with malformed input.  After that, it becomes unclear how to test gotAYahtzee (do you see why?).  It seems that the best test would run this many times, and then compare the results to our expected value (allowing for some variance).  But that is precisely what our next function does, so we will not do that here. Thus, this test function is very weak, but that's ok, since the next test function will subsume this task.  Be sure you understand this!  Also, be sure to include a thoughtful comment in your testGotAYahtzee function explaining that most of its testing is deferred to testYahtzeeOdds (below).
    5. SOLO yahtzeeOdds and testYahtzeeOdds [10 pts]
      Write the function yahtzeeOdds (in the file hw5-solo.py).  This function takes two parameters -- the number of rolls per turn, and the number of total trials to run -- and performs a Monte Carlo simulation of Yahtzee, calling the gotAYahtzee function once for each trial.  The function returns the observed odds, which is the ratio of Yahtzees to the total number of trials (beware integer division!).  If either rollsPerTurn or trials is malformed (either not an integer, or not positive), the function should return -1 to signify an error.

      Then, write the function testYahtzeeOdds (in the file hw5-solo.py).  This function takes no parameters and tests whether or not the yahtzeeOdds function works properly.         First, it should handle the easy case of checking that yahtzeeOdds deals properly with malformed input.  Then things get more challenging, given the variability in expected results of Monte Carlo functions.  Even so, there is plenty we can test.  Proceed as such:
      1. Confirm that calling yahtzeeOdds with any number of rollsPerTurn (say, between 1 and 10) and any number of trials (say, 1, 10, 100, or 1000) always returns a number between 0.0 and 1.0.
      2. Confirm the expected result that the odds of a traditional Yahtzee (with 3 rolls per turn) is about 4.6%.  Use 10,000 trials and require the observed odds to be within 0.01 of the expected odds (0.046).   Note that we could lock down our accuracy closer than 0.01 if we use more trials, which is a good idea, but we'll stick with 10,000 trials to allow your testing (and ours!) to run faster.

        Also note:  since this is probabilistic, there is some very small chance that working code will still fail this test by having the very bad luck to be beyond 0.01 away from the expected odds.  In this case, just re-run your test function a few times, and if it "mostly" works, you are fine.  Our robotic autograder will do the same.  This note applies to the next two test cases, too.
      3. Confirm that as we increase the number of trials, our accuracy increases.  Specifically, confirm that the (absolute value of the) difference between the observed odds and expected odds (4.6%) decreases as the number of trials increases from 1 to 100 to 50,000 (we use large gaps in trials to be confident this pattern emerges).
      4. Finally, confirm that as we increase the number of rollsPerTurn, the odds of a Yahtzee increases.  For that, lock down the trials at 10,000 and check this pattern for each even number of rollsPerTurn from 2 to 12 (2, 4, 6, 8, 10, 12) -- again using gaps (here, skipping the odds) to be confident the pattern emerges.
    6. SOLO Yahtzee Odds for various rollsPerTurn [5 pts]
      In your hw5.doc file, answer the following:  how many rollsPerTurn are required so that the odds of a Yahtzee are greater than 50%?  75%?  90%?   Briefly explain how you used the yahtzeeOdds function to obtain these answers.
  2. SOLO Reasoning About Code (Mystery Functions)  [15 pts; 3 pts each]
    In just a few words of plain English (in your hw5.doc file), state what each of the following functions does in general.  You will receive no credit for describing the line-by-line low-level behavior of the code.   For example:
    def mystery(list):
        count = 0
        for value in list:
            if (value == 0):
                count += 1
        return count
    Correct answer:  "This function returns the number of 0's in the given list."  Or, if you prefer to be succinct, just:  "number of 0's".
    Incorrect answer (no points):  "This function sets count to 0, then sets value to each element in list in turn, and for each value, if it is 0, it adds one to count, and then returns count".  This is all true, but completely misses the high-level behavior of the function, and so would receive zero points.
    1. def mystery1(x):
          # assume x is an integer
          c = str(x)[0]
          return ((c < "0") or (c > "9"))
    2. def mystery2(x,y):
          # assume x and y are non-negative integers
          count = 0
          for target in range(min(x,y), max(x,y)+1):
              product = 1
              for check in range(2,target):
                  product *= (target % check)
              if (product > 0):
                  count += 1
          return count
    3. def mystery3(list):
          # assume list contains integers
          list = [] + list
          while (len(list) > 2):
              list.remove(min(list))
              list.remove(max(list))
          return (list[0] + list[-1])/2         
    4. def mystery4(matrix):
          rows = len(matrix)
          cols = len(matrix[0])
          for row in range(rows):
              for col in range(cols):
                  if (matrix[row][col] != matrix[row][cols-1-col]):
                      return False
          return True
    5. def mystery5(s):
          x = 0
          y = 0
          positions = [[x,y]]
          for c in s:
              if (c == "u"):
                  y += 1
              elif (c == "d"):
                  y -= 1
              elif (c == "r"):
                  x += 1
              elif (c == "l"):
                  x -= 1
              else:
                  return False
              if ([x,y] in positions):
                  return True
              positions += [[x,y]]
          return False
  3. Collaborative Problem-Solving (with File IO)  [15 pts]
      1. K-Letter Word List
        Background:  sometimes it's handy (say, for playing Scrabble or other such games) to have a word list that only contains words of a specific length (eg, 3-letter-words.txt).  Here, we'll write a tool that extracts such word lists from a larger list of words.

        Your task:  Write the function makeKLetterWordListFile (in the file hw5-collab.py).  This function takes two parameters -- the name of a wordList file that is on your desktop (say, "words.txt") and a positive integer k.  The function creates a new file, also on the desktop, with the original file's name prefaced with "k-letter" (where k is the actual value supplied).  So if the word list is "words.txt" and k=3, then the function creates the file "3-letter-words.txt" on the desktop.  In this file, you include each k-letter word, one-per-line, that occurs in the original word list, in the same order as they occur in the original word list.   Your function should return True if this operation succeeds, and False otherwise.  For example, if the original file does not exist, or if k is not an integer or is not positive, then your function should not crash or raise an AssertionError but instead should return False.

        Then, write the function testM        akeKLetterWordListFile.  This function takes no parameters and tests whether or not the makeKLetterWordListFile function works properly.  Note that you may test the makeKLetterWordListFile function using a smaller list of words than "words.txt", but you should create that file in your test function and not just assume it is on the desktop.  Also note that you may assume that "words.txt" is on the desktop.
  4. SOLO Readings in Computational Thinking  [20 pts]
      1. SOLO Chazelle's Pithy Omnibus
        Read “Could Your iPod Be Holding the Greatest Mystery in Modern Science?” by Bernard Chazelle.  In hw5.doc, answer the following questions:
        1. Briefly state Moore's Law.
        2. If we assume (not entirely correctly, but closely enough, at least for the past 40 years) that "twice as many transistors" roughly equates to "twice as fast (at the same price)", then we expect a new $500 computer to be roughly 2x faster every 1.5 years, or 4x faster every 3 years, or 8x faster every 4.5 years, and so on.  Say you have a $500 computer and it is running an incredibly awesome 3d virtual reality program, only it's way too slow to be enjoyable.  No worries.   In how many years would you expect a new $500 computer to run approximately one thousand times faster, and to handle that same 3d virtual reality program with no problem?
        3. In just a few words, what does it mean to be a universal computer?
        4. What is the duality Chazelle refers to?
        5. What does Chazelle mean by this:  "Life's but a self-printing iPod!"?
        6. What is tractability?  State one intractable problem, and one tractable problem.
        7. What does Chazelle mean by a zero-knowledge paradox?
        8. Chazelle says: "Algorithmic thinking is likely to cause the most disruptive paradigm shift in the sciences since quantum mechanics."  Do you agree.  Explain (briefly, but thoughtfully).
  5. Collaborative Bonus/Optional:  Farkle [10 pts]
    In the file hw5-bonus-farkle.py (which is not supplied to you), write the game of Farkle.  Allow for multiple players, including a computer player.  Make your text-based user interface really intuitive, so the game is "walk-up-and-use" (that is, it does not require training, or even reading a help screen, though you may print out some rules and instructions at the start of the game.