15-112 Spring 2014 Homework 2
Due Monday, 27-Jan, at 10pm

Read these instructions first!
  1. Manually-Graded Portion
     
    1. F13 Quiz2  [20 pts]
      Do the problems from f13 quiz2 (the first version, and you may skip the bonus).  Though you can be brief in your supporting work, be sure to show at least some work (or you will not receive credit!).
      Submit the solutions to these problems in a triple-quoted string at the top of hw2.py (it is already there for you).
       
    2. Graphics [40 pts]
       For these problems, you will create functions that draw images using Tkinter graphics (using the simple graphics primitives we covered this week, drawing rectangles and ovals and polygons, and not by drawing images such as jpg's or gif's).  When you run the provided hw file, it will display a window with some buttons, one button for each graphics function you will write.  When you click a button, the respective function is called twice, once for a larger image on the left, and again for a smaller image on the right.  Even though the two images may differ in some ways, as described below, they are generated by the same function -- so your function must include conditionals based on the image width to make this work.  For this purpose, you may assume that a "large" image has a width greater than 200 pixels.  Each function will take 5 parameters: canvas, x0, y0, x1, and y1.  The function should draw into the canvas, filling the rectangle from (x0,y0) to (x1,y1) with the image as described below.  Note that we will grade this mainly visually, and so you do not have to provide a "pixel-perfect" match of the given image, but you do have to be fairly close.  For example, in our drawCircle image, our border width is 4, and you could use anything from 3 to 5 and receive full credit.

      Note:  be sure not to "hard-code" your graphics.  For example, you may not assume anything about the location or dimensions of the rectangular region.  Your code must not only work for the regions in the file we provided, but for regions of any other size or location.  Our graders will in fact run your code on regions in different locations and different sizes.  The one exception:  you may hardcode a different behavior for large (width>200) versus small (width<=200) images.
       
      1. drawCircle(canvas, x0, y0, x1, y1)
        [Note: the solution for this function is provided for you as an example. See the hw2.py file for details.]
        Write the function drawCircle that takes 5 values – a canvas, a left, top, right, and bottom – describing a rectangular region of the canvas, and fills this region with a drawing of a circle.  For large areas (>200 pixels wide), the circle should be blue.  For smaller areas, it should be pistachio.  In either case, it should have a slightly thick black border.  Here is a screenshot to help (click on the image to see a larger version):

         
      2. drawCircleGradient(canvas, x0, y0, x1, y1)
        Write the function drawCircleGradient that takes 5 values – a canvas, a left, top, right, and bottom – describing a rectangular region of the canvas, and fills this region with a drawing of a circle gradient.  For smaller areas, it should have 5 rings.  For larger areas, it should have 50 rings.  The outermost ring should be all green (with no red or blue), and the innermost ring should be all red (with no green or blue).  Each ring in between should linearly interpolate the amount of green and red (so, for example, the ring in the middle would have about half green and half red and still no blue).  Here is a screenshot to help (click on the image to see a larger version):

         
      3. drawLinePattern(canvas, x0, y0, x1, y1)
        Write the function drawLinePattern that takes 5 values – a canvas, a left, top, right, and bottom – describing a rectangular region of the canvas, and fills this region with a drawing of the line pattern in the picture below.  The drawing is the same for larger and smaller areas.  To do this, you will want to write a helper function that draws one of the two "V" patterns in the picture.  This helper function will be called twice -- once to draw the blue V pattern, then again to draw the upside-down red V pattern.  You might want this helper function to take the 3 points defining the V, along with the color to use.  That helper function will then work as follows:  first, it will draw the lines that form the outer shell of the V.  Then, it will connect 20 points on one of those lines to 20 points on the other one.  Look carefully at the picture to understand how to choose these 20 points.  Big hint:  if a line runs from (x0, y0) to (x1, y1), then the width is (x1-x0) and the x value of the point one-third of the way would be at x=x0+width/3.  In any case, here is a screenshot to help (click on the image to see a larger version):

         
      4. drawCrazyCubes(canvas, x0, y0, x1, y1)
        Write the function drawCrazyCubes that takes 5 values – a canvas, a left, top, right, and bottom – describing a rectangular region of the canvas, and fills this region with a drawing of the "crazy cube" pattern in the picture below.  The drawing is the same for larger and smaller areas.  To do this, first note that the cubes are arranged in a grid, so you will want to use nested for loops there.  Also, you should choose a grid width to fit 10 cubes exactly across, which then may leave some extra space vertically, since you should only draw cubes if they will fit entirely in the image.  As for the "cubes", notice that each red-green-blue piece really is a single hexagon.  Interesting.  So this is really a grid of red-green-blue hexagons layered over a yellow background.  So you should write a helper function to draw a hexagon given its center and radius.  Then, after drawing the yellow background, you should call that helper function repeatedly, once for each hexagon.  As for the helper function, it may have to use a little trig to find the hexagon vertices that are not on the horizontal, then you would draw 3 different polygons with those points.  And that's all there is to it!  Here is a screenshot to help (click on the image to see a larger version):

         
      5. Optional/Bonus:  drawHexagonsBonus(canvas, x0, y0, x1, y1) [3 pts]
        This is bonus and entirely optional.  Write the function drawHexagonsBonus that takes 5 values – a canvas, a left, top, right, and bottom – describing a rectangular region of the canvas, and fills this region with the following drawing (click on the image to see a larger version):

       

  2. Autograded Portion:  Problem-Solving (Writing functions) [40 pts]:  The 112 Game!
    Note:  Carefully read this entire writeup first!  This way, you will have a clear idea of how all the functions described here fit together into a cohesive design!

    Background:  in this section, we will implement a version of the world-famous and endlessly amusing 112 game.  Here is how the game works.  Start with a board with N positions, something like a 1xN tic-tac-toe board, with all positions empty.  There are two players who alternate turns.  On each turn, the current player must place either a 1 or a 2 in any unoccupied position.  If the move results in the number 112 among any three contiguous positions, then the player who just moved wins the game.  If the board is full, without any 112's, then it is a tie.  So, for example, here is a short game on a board of size 5:
     
    Start with an empty board  -  -  -  -  -
    Player 1, at position 4, places a 2  -  -  -  2  -
    Player 2, at position 1, places a 2  2  -  -  2  -
    Player 1, at position 3, places a 1  2  -  1  2  -
    Player 2, at position 2, places a 1
    And Player 2 wins!!!    		  2  1  1  2  -

    Now, while it would be interesting to write an interactive game (either text-based in the console or with graphics) that people could play, here we will instead slightly adapt the problem so that a computer autograder can easily autograde it.  So instead of playing a game interactively, we will write a function called play112 that takes a specification of a game and simply returns the outcome of that game.  A game specification has to include the size of the board, which we will restrict to being an integer between 1 and 9 inclusive, and then a series of moves, which will be two values -- the position (an integer from 1 to boardSize, where 1 is the leftmost position) and the value to place there (either a 1 or a 2).  The natural representation in Python for this would be a list.  So the game above would be represented by this list:
       [5, 4, 2, 1, 2, 3, 1, 2, 1]
    This list indicates that the board is of size 5, then specifies each move -- at position 4 place a 2, at position 1 place a 2, and so on.  The list does not include the player numbers, because we know these alternate, starting from player 1.  Using a list this way is natural, only we have not yet covered lists.  We need to find a different, less natural, less ideal, but workable way to represent these values using the types that we currently know.  We do not even have strings yet.  But we do have integers.  So we can represent that same list of digits (and notice they are all single digits, and then all are non-zero) as a single integer value:
        542123121
    Again, this may not be ideal, but it definitely works (one thing: for larger boards, this will result in a long integer, with the L suffix; this is not a problem, but just be aware of it).

    Now that we can specify a game, we also need a way to store the board as the game progresses.  Again, we are limited to integers, so we will store the entire board as a single integer.  We need to store 1's and 2's where they were played, but we also need to store empty values.  It may seem like 0 is a good idea for these, only that can lead to some oddness due to leading 0's not being displayed.  For example, if 0's were the empty spaces, then the board above would be represented like the values in the third column of this table:

    Start with an empty board  -  -  -  -  -       0
    Player 1, at position 4, places a 2  -  -  -  2  -      20
    Player 2, at position 1, places a 2  2  -  -  2  -   20020
    Player 1, at position 3, places a 1  2  -  1  2  -   20120
    Player 2, at position 2, places a 1
    And Player 2 wins!!!    		  2  1  1  2  -   21120

    See how the board is initially 0, even though it represents 5 blank spaces?  This works, because 0 is the same as 00000, but it's not necessarily intuitive.  It 's also worth noting that we are only talking about intuitive for the programmer (that is, you!).  Users would never know how you chose to represent the board internally in your program.  Even so, good decisions here will lead to clearer, easier to understand, easier to debug code.  In any case, for these reasons, instead of 0, we will use 8 to represent a blank space.  Thus, here are the integer representations of the boards in the example game:

    Start with an empty board  -  -  -  -  -   88888
    Player 1, at position 4, places a 2  -  -  -  2  -   88828
    Player 2, at position 1, places a 2  2  -  -  2  -   28828
    Player 1, at position 3, places a 1  2  -  1  2  -   28128
    Player 2, at position 2, places a 1
    And Player 2 wins!!!    		  2  1  1  2  -   21128

    Now that we have a game specification, and a way to store a board, what should play112(542123121) return?  Any call to play112 will return a single string (ok, we'll bend our limitation about strings just so we can more easily autograde) composed of two parts:  the board as it existed at the end of the game, and then the result of the game.  And so:
         play112(542123121) returns:  "21128: Player 2 wins!"
    Compare this result to the table above to confirm that 21128 represents the last board of the game, and also that Player 2 in fact won.

    Ok, so now we are ready for a formal problem description.  Here it is:  write the function play112(gameSpec).  It takes a gameSpec as defined above, and it returns a string composed of the final board, a colon (:), a space, and then the outcome of the game.  Note that your code must match this spec exactly, character-for-character (no extra spaces, no incorrect upper or lower cases, etc).   Here are the possible outcomes of the game:

    Player 1 wins! Player 1 played a move that generated 112, and won!
    Player 2 wins! Player 2 played a move that generated 112, and won!
    Player 1: move must be 1 or 2! Player 1 played a piece other than a 1 or 2, and lost.
    Player 2: move must be 1 or 2! Player 2 played a piece other than a 1 or 2, and lost.
    Player 1: occupied! Player 1 played a piece into an occupied position, and lost.
    Player 2: occupied! Player 2 played a piece into an occupied position, and lost.
    Player 1: offboard! Player 1 played a piece into a position not on the board, and lost.
    Player 2: offboard! Player 2 played a piece into a position not on the board, and lost.
    Tie! Neither player has won or lost, and the board is full.
    Unfinished! None of the preceding cases applies.

    Note that the game stops immediately after a win or loss, even if the game specification contains more moves.

    Here is a test function for you:

    def testPlay112():
        print "Testing play112()...",
        assert(play112( 5 ) == "88888: Unfinished!")
        assert(play112( 521 ) == "81888: Unfinished!")
        assert(play112( 52112 ) == "21888: Unfinished!")
        assert(play112( 5211231 ) == "21188: Unfinished!")
        assert(play112( 521123142 ) == "21128: Player 2 wins!")
        assert(play112( 521123151 ) == "21181: Unfinished!")
        assert(play112( 52112315142 ) == "21121: Player 1 wins!")
        assert(play112( 523 ) == "88888: Player 1: move must be 1 or 2!")
        assert(play112( 51223 ) == "28888: Player 2: move must be 1 or 2!")
        assert(play112( 51211 ) == "28888: Player 2: occupied!")
        assert(play112( 5122221 ) == "22888: Player 1: occupied!")
        assert(play112( 51261 ) == "28888: Player 2: offboard!")
        assert(play112( 51122324152 ) == "12212: Tie!")
        print "Passed!"

    Study the test function carefully.  Manually confirm every single line of it, so that you understand why each given call to play112 produces the expected result.

    So now what?  At this stage of the course, this is a daunting task, perhaps too daunting without some more guidance.  But it gives you your first real taste of what we are trying to teach you.  This course is not about how a mod operator or a for loop works.  Instead, this course is meant to teach you how to solve problems.  And that requires higher-level design, abstraction, problem-solving, and so on.  In particular, given a problem such as this, we will use a top-down design approach.  So we will try to break this problem down into smaller parts, and to break those down into even smaller parts, until we get to problems small enough that we can fairly easily write and test them.

    For this problem, we will provide the entire design for you, and you must use this design.  The autograder will expect you to write every function specified here, in just the way it is specified.  Of course, in the future,  you will need to do this sort of design yourself.

    At the lowest level, we will need some functions that do some basic manipulations of our board:
     

    At the next-higher level, we need some functions that use the lower-level functions you just wrote to perform the individual steps of game play:
     

    And that finally leads to the top-level function that uses all the preceding functions to actually play the game:
     

    And that's it!  Good luck!
     

  3. Bonus/Optional Graphics
    Read this carefully!  The following problems are bonus/optional.  They are graphical, and you should be certain to place them (and any helper functions they require) below the #ignore_rest line in your hw2.py submission.  Unlike the autograded problems, the bonus graphics problems will be graded only in person on Tuesday or Wednesday night at office hours.  To get your bonus graphics grade, go to office hours where you should download your submitted code (and it must be just as submitted, with no modifications), run it and show the CA the result.  The CA will grade your bonus at that time, mainly visually but also by looking at the code as needed.

    1. Bonus/Optional:  Radial and Spiral Tilings [2.5 pts each, up to 5 pts]
      Write a function that draws this picture and/or this picture from this page on Radial and Spiral Tilings. 

carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem   -   carpe diem