15-112
Fall-14

Home

Syllabus

Schedule

Piazza

Autolab

Gallery

15-112 Fall 2014 Homework 3a
Due Sunday, 14-Sep, at 10pm

Read these instructions first!
  1. largestPrimeSubnumber(n) [autograded]
    Assuming n is a non-negative int, we will say that a "subnumber" (a coined term) of a number n is a number k made up of consecutive digits in n. Thus, the subnumbers of 485 are: 4, 8, 5, 48, 85, and 485. With this in mind, write the function largestPrimeSubnumber(n) that takes a non-negative int n and returns the largest subnumber of n that is also prime. If no such number exists, return None.
    Hint: you will want to use 2 loops. One for the start digit of the subnumber, and an inner loop for the end digit.

  2. nthLikelyLychrelNumber(n) [autograded]
    First, read this page (and perhaps the links it refers to) about Lychrel numbers. One difficulty: you need to know when you can stop the reverse-then-add loop and declare the number to be a Lychrel number. To keep this easy, you should stop if ever you have looped 50 times and still not found a palindromic number. Because we cannot guarantee this works in all cases, we will call the numbers we find this way "likely Lychrel numbers" (a coined term). With this in mind, write the function nthLikelyLychrelNumber(n), that takes a non-negative int n and returns the nth likely Lychrel number (counting from 0, of course). Note that with a max of 50 passes, our sample solution generated all the terms on this page, and even perhaps some that are not on that page! Also note that you are being graded this week on top-down design. Our sample solution to this problem used 7 well-chosen functions (including kthDigit and digitCount). You do not need to use exactly 7 functions in your solution, but that should give you an idea of roughly what we are looking for in your design.

  3. drawTiledFlags(margin, rows, cols, flagWidth, flagHeight)
    Write the function drawTiledFlags that takes the parameters (margin, rows, cols, flagWidth, flagHeight) and draws a rows-by-cols grid of flags of the given dimension, with the given margin around the whole grid, and with the window sized to just fit around the grid with the given margin. The flags should alternate in a checkerboard pattern between the flag of the European Union (with circles drawn in place of stars) and the flag of the Bahamas, with the EU flag in the left-top corner. You do not have to exactly color match, but the blue in the Bahamas flag must be obviously lighter than the blue in the EU flag. Also, your black triangle in the Bahamas flag does not have to match proportions exactly, just reasonably closely. The same goes for the circles in the EU flag, just be reasonably close.
    For example, this call:
       drawTiledFlags(margin=10, rows=3, cols=5, flagWidth=100, flagHeight=60)
    produces this result:


  4. drawBlankSheetMusic(title, winWidth, winHeight, lineHeight, lineMargin, measuresPerLine)
    Write the function drawBlankSheetMusic that takes the parameters (title, winWidth, winHeight, lineHeight, lineMargin, measuresPerLine) and draws as many lines of blank sheet music that can fit in the given sized window. The title is given as a string, which should be drawn in 20-point Arial bold font, horizontally centered 25 pixels below the top of the window. The top of the first line should be at 50 pixels from the window top. Each row, or line, is actually called a "staff line". It is made up of 5 separate horizontal lines (see picture below for details). As an aside: you do not need to read music to do this exercise, but most of you probably know that these lines correspond to the notes E-G-B-D-F, from bottom to top. In any case, the vertical distance from the top line to the bottom line in one row is the given lineHeight. The vertical distance between the bottom line of one row and the top line of the next row is the lineMargin. This is also the horizontal distance between the edges of each row and the left and right edges of the window. Finally, each row is split up by vertical lines into measures, according to the given measuresPerLine.
    For example, this call:
       drawBlankSheetMusic(title="Blank sheet music", winWidth=800, winHeight=200,lineHeight=50, lineMargin=20, measuresPerLine=5)
    produces this result:

15-112 Fall 2014 Homework 3b
Due Tuesday, 16-Sep, at 7:30pm (note the odd day and time)
No extensions or late days!

Read these instructions first!
  1. doPigStrategyAnalysis()
    This problem relates to the Pig game you wrote in hw2. This paper describes various strategies for playing Pig. It claims that "hold at 20" is a pretty good strategy, if not the optimal strategy. Your task here is to write some Python code that empirically demonstrates that "hold at 20" is a better strategy than "move randomly" (which may be restated as "hold when a coin flips to heads"). Note that this problem will be manually graded, so place your code below the #ignore_rest line. There should be a function called doPigStrategyAnalysis which, when run, actually does the analysis (presumably pitting the two strategies against each other lots of times, and counting how many times each one wins), and prints the results in some meaningful fashion (so we ignore the function's return value; in this case, what matters is what it prints out). We are not expecting sophisticated statistical analysis here, just a compelling empirical demonstration of the fact we are investigating.

  2. drawGraph(winWidth, winHeight, fn, xmax, xstep, ymax, ystep)
    Background: before writing this function, review the following example, which was also covered in this week's recitation. This code draws a graph of y=100sin(x). Be sure to thoroughly understand how it works: 
    # Example drawing a simple graph of y = 100sin(x)
# This is "simple" in that it does not scale, so one pixel
# corresponds to one point on the graph, and it hardcodes
# the function being graphed, and it does not have hash marks, etc.

# Also, you might wish to split this code up into some
# well-chosen helper functions, especially if you were planning
# to add some functionality to it, as you will in just a moment...

import math
from Tkinter import *

def drawSimpleSineGraph():
    # set up the window
    root = Tk()
    (winWidth, winHeight) = (600, 400)
    canvas = Canvas(root, width=winWidth, height=winHeight)
    canvas.pack()
    (cx, cy) = (winWidth/2, winHeight/2)
    # draw x and y axes
    canvas.create_line(0, cy, winWidth, cy)
    canvas.create_line(cx, 0, cx, winHeight)
    # plot points
    oldScreenX = oldScreenY = None
    for screenx in xrange(winWidth):
        x = screenx - cx
        y = 100 * math.sin(math.radians(x))
        screeny = cy - y
        if (oldScreenX != None):
            canvas.create_line(oldScreenX, oldScreenY, screenx, screeny, fill="blue")
        (oldScreenX, oldScreenY) = (screenx,screeny)
    # and display the window
    root.mainloop()

drawSimpleSineGraph()

    With this in mind, write the function drawGraph that extends the simple example above in some useful ways. In particular, drawGraph takes the parameters (winWidth, winHeight, fn, xmax, xstep, ymax, ystep), and then:
    • It creates a window of the given dimensions.
    • And it graphs the given function (which is a normal Python function, which you may assume takes one variable, a float, and returns a float result).
    • The graph needs to be scaled, so that the center of the graph is still (0,0), but the rightmost point of the x axis is at (xmax,0), and the xmin value is -xmax, so the leftmost point of the x axis is at (-xmax, 0). Similarly, ymax describes the extent of the y axis. To do this, you will want to compute a scaling factor for each dimension. For this, consider that the distance from xmin to xmax in the actual graph corresponds to the number of horizontal pixels in your window.
    • The graph needs to have hash marks along the axes, as indicated by the given xstep and ystep values. The hash marks need to be labeled, with the x axis labels just below the hash marks, and the y axis labels just to the left of the hashmarks. Note: for hashmarks, you do not have to worry about the "boundary conditions", in that you may or may not include the last hashmark in each direction (this may make the math just a bit easier in some cases).
    • The graph needs a title, centered in a bold 40-point Arial font. The title should be obtained by fn.__name__ (Python adds this field automatically to every function defined using "def").

    For example, this call:
    def cosineInDegrees(degrees):
    return math.cos(math.radians(degrees))

drawGraph(winWidth=600,winHeight=300,
          fn=cosineInDegrees,
          xmax=+720, xstep=90,
          ymax=+3, ystep=1)

    produces this result:


    Also, using the exact same unmodified drawGraph function, this call:
    def strangeFunction(x):
    if (int(round(x)) % 2 == 0):
        return x+5*math.cos(x)**3
    else:
        return 10*math.sin(x/2)

drawGraph(winWidth=600,winHeight=300,
          fn=strangeFunction,
          xmax=+20, xstep=4,
          ymax=+15, ystep=3)

    produces this result:

  3. Bonus/Optional: drawRadialTesselation(winWidth, winHeight) [3 pts]
    Write the function drawRadialTesselation that takes the dimensions of a window, and displays a window of those dimensions filled completely with the following tesselation (with all other details left for you to decide):

    (Image from http://www.uwgb.edu/dutchs/Graphics-Other/tilings/spiral3a.gif)