15-112 Fall 2014 Homework 7
Due Sunday, 12-Oct, at 10pm

Read these instructions first!

• This entire hw is strictly SOLO, in the same way hw1-part2, hw2, and hw3 were, so you may not even discuss the problems with any other students or anyone except the course staff.


• There is no starter file this week. Submit a single file, hw7.py. Be sure to include your name and andrew id at the top. And be sure to place all the non-autograded problems below the #ignore_rest line!


• You may use 2d lists, sets, and maps, in addition to 1d lists, tuples, strings, graphics, loops, and conditionals, but (as usual) you may not use constructs we have not yet covered (recursion, oop, etc), unless explicitly allowed below.


• This week, you may only make up to 5 submissions max to Autolab. As usual, only your last one counts.


• Note: do not copy-paste the basicAnimation.py file into your hw7.py file. Instead, include the line:
     from basicAnimation import BasicAnimationRunner
  Be sure to include that line below the #ignore_rest line so the autograder does not get confused. And be sure that basicAnimation.py is in the same folder as your hw7.py file when you run it. We'll do the same when we run it.


• This hw is lighter than usual, in part to give you time for Parent's Weekend, but mostly to give you time to start preparing for the upcoming midterm exam. Those of you who need extra work on 2d lists, sets and maps should look here and here for more practice problems. And hopefully everyone will use this extra time to get in some midterm studying.


• Some hints and clarifications are included at the end of this document.

1. isLegalSudoku(board) [25pts] [autograded]
   Do isLegalSudoku from here.


2. friendsOfFriends(d) [20pts] [autograded]
   Do friendsOfFriends from here.


3. playSudoku(initialBoard) [55pts] [manually graded]
   Note: your solution to this problem must use the MVC-style version of our Basic Interactive Graphics that we covered this week, and also must use the isLegalSudoku founction you just wrote.
   
   With this in mind, write the function playSudoku(initialBoard) that takes a 2d list representing a Sudoko board, as described in isLegalSudoku, and lets the user play an interactive, graphical Sudoku game starting from that board. The game must be implemented using our Basic Interactive Graphics code, which you must import (below the #ignore_rest line, of course). The user interface is left to you, and can be either mouse-based, key-based, or some combination, with these requirements:
   
   
   • Your game must work for a 1x1 board, a 4x4 board, or a 9x9 board. We will not test other sizes.
   
   
   • Your game must have a help screen, which is displayed when the user presses either "h" or "?", and all the legal commands (as described below) must be explained on that page. Note that this is actually the same screen and window as your game, just that you should display help info at times, and the game at other times. Hint: it may help to have a variable canvas.data.inHelpScreen that is initially False and set to True when the user presses "h" or "?".
   
   
   • You need a way for the user to place a number in a cell, and to change the number in a cell.
   
   
   • You need to clearly display to the user if a move or a board position is illegal.
   
   
   • You need to display when the board is solved.
   
   
   • You need to provide a simple undo/redo mechanism (that allows for undoing an arbitrary number of steps, all the way back to the initialBoard, and then redoing those steps, if that's what the user wants).
   
   
   • You need to provide a simple timer or counter that somehow continually (say, at least once per second) updates to show how long the user has been trying to solve the given puzzle. This will require using timerFired. It is the only place you need to use timerFired for this problem.


4. Bonus/Optional: play2048() [5 pts] [manually graded]
   Using our basicAnimation framework, write the function play2048(), that plays a fairly close knock-off of the game at this web site. For full credit, include the animations.

---

Here are some hints and clarifications:

• The basic rules of MVC
  When writing playSudoku, remember these basic rules of MVC:
  
  
  • Controllers only modify the model + Controllers never draw!
    So, mousePressed, keyPressed, and timerFired (and any helper functions they call) never draw anything on the canvas. They only modify canvas.data. That's it. The drawing is done by redrawAll, later on. No exceptions!
  
  
  • Views only draw + Views never modify the model!
    So redrawAll (and any helper functions it calls) only draw, and never change anything in canvas.data. Again, no exceptions!
  
  
  The CA's will enforce these rules when grading! And the rules exist very much for your benefit. They are not 15-112 rules. They are The Way to do this (well, to be precise, they are a slightly simplified version of MVC, but still, very much in the spirit of MVC!). This approach will allow you to write more complex animations more quickly and more reliably. It works, at least a whole lot better than the monolithic spaghetti code (yes, that's a technical term!) you've had to write before learning this way.


• makeTestSudokuBoard
  Several of you have asked how to make test functions fit into the 20-line requirement, what with most of those lines being consumed by just creating Sudoku boards. Good question. Here's an idea that could help:

  def makeTestSudokuBoard():
      return [
              [ 5, 3, 0, 0, 7, 0, 0, 0, 0 ],
              [ 6, 0, 0, 1, 9, 5, 0, 0, 0 ],
              [ 0, 9, 8, 0, 0, 0, 0, 6, 0 ],
              [ 8, 0, 0, 0, 6, 0, 0, 0, 3 ],
              [ 4, 0, 0, 8, 0, 3, 0, 0, 1 ],
              [ 7, 0, 0, 0, 2, 0, 0, 0, 6 ],
              [ 0, 6, 0, 0, 0, 0, 2, 8, 0 ],
              [ 0, 0, 0, 4, 1, 9, 0, 0, 5 ],
              [ 0, 0, 0, 0, 8, 0, 0, 7, 9 ]
             ]
  

  If need be, your code could include makeTestSudokuBoard1, makeTestSudokuBoard2, makeTestSudokuBoard3...


• playSudoku(initialBoard) without an app or canvas?
  How can playSudoku only take an initialBoard, and not an app or canvas? Because it is just a one-line function! You'll write another function which does all the work, and that function will take an app, a canvas, and also the initialBoard. Your playSudoku function will include a line similar to this (from the course notes):

  BasicAnimationRunner(myBasicAnimation, width=300, height=300, extraArg="wow!")
  

  Of course, you'll change "myBasicAnimation" to be the other function you write, and you'll change "extraArg" to be the initialBoard.
  
  So why do it this way? Why not just have the user make that call to BasicAnimationRunner? Good question, but also one with a good answer. Because the fact that you used BasicAnimationRunner is an implementation detail. There is no good reason that a user should have to know that you did this. And you certainly could write playSudoku some other way (though not for hw7), perhaps not even using Tkinter at all! So the function playSudoku only specifies Polya 1, and hides the details from the caller. This is generally how high-level functions (such as this) are specified. You are told what to do, but not how to do it. And in such cases, when you are done, the caller should not know or care how you did it. They just say playSudoku and, voila, they get a Sudoku game!


• makeFakeCanvasForTestingPurposes()
  How can we test a helper function that takes a canvas object but then does not draw? Good question! Here's a simple way to do it. Use the function makeFakeCanvasForTestingPurposes, provided here, that creates a fake canvas object. You can then set its canvas.data values appropriately and send that into your function to test it. Check this out:

  # this is the function we want to test
  def thingIsOrange(canvas):
      return (canvas.data.thing == "orange")
  
  # copy-paste this function so you can make a test function
  def makeFakeCanvasForTestingPurposes():
      class Struct(): pass
      fakeCanvas = Struct()
      fakeCanvas.data = Struct()
      return fakeCanvas
  
  # And now we can make a test function
  def testThingIsOrange():
      print "Testing thingIsOrange()...",
      canvas = makeFakeCanvasForTestingPurposes()
      canvas.data.thing = "green"
      assert(thingIsOrange(canvas) == False)
      canvas.data.thing = "orange"
      assert(thingIsOrange(canvas) == True)
      print "Passed!"
  
  # and here we go...
  testThingIsOrange()