Write the function randomCircleFun that takes a canvas, and a left, top, width, and height of a rectangular area of that canvas, and fills that area with randomly-generated circles so that the image looks very much like a reasonable variation of this image (ignoring the water mark):
Note that the image uses alpha transparency, and of course with Tkinter you cannot, so don’t worry about that. But you should use roughly the same size circles and the same color scheme. Hint: you will have to import random and then you can use the function random.random() to get a float between 0.0 and 1.0, or random.randint(lo,hi) to get a random integer between lo and hi.
A palindromic prime number is a number that is both prime and a palindrome – the same forwards as backwards. The first several palindromic primes are: 2, 3, 5, 7, 11, 101, 131, 151, 181, 191, 313,… With this in mind, write the function nthPalindromicPrime(n) for non-negative int n.
Write the function nthSmithNumber that takes a non-negative int n and returns the nth Smith number, where a Smith number is a composite (non-prime) the sum of whose digits are the sum of the digits of its prime factors (excluding 1). Note that if a prime number divides the Smith number multiple times, its digit sum is counted that many times. For example, 4 equals 2**2, so the prime factor 2 is counted twice, thus making 4 a Smith Number. The first few Smith numbers are 4, 22, 27, 58, 85, 94, 121, ... You may read more about Smith numbers here.
Aside: as we will cover more carefully later in the course, a function may take another function as an argument. For example, consider this code:
def h(n):
return n+5
def f(g, x):
return 2*g(x)
print f(h,3) # prints 16
Here, we define a function f whose first argument is another function. On the last line, we call f providing the function h, which is bound in f to the parameter g. Hence, calls to g in f are really calls to h. Play around with the sample code to get the hang of this idea. Then, read the next preliminary topic...
In mathematics, one way to numerically (as opposed to algebraically) find a zero of a function f(x) is to use what amounts to binary search. To start, we need to know two values, x0 and x1, with x0<x1, where f(x0) and f(x1) have different signs (so one is positive and the other is negative). Hence, by the Intermediate Value Theorem, we know there is some value x in the range [x0,x1] such that f(x)=0. It is that value of x that we are seeking. How? First, try the value xmid, which is the midpoint between x0 and x1. If f(xmid) is exactly 0, we are done! Otherwise, we can divide our range in half as such: if f(xmid) and f(x0) are the same sign, use the range [xmid, x1]. Otherwise, f(xmid) and f(x1) must share the same sign, so use the range [x0, xmid]. We repeat this in a loop until x0 and x1 are within some suitably small epsilon.
With this in mind, write the function findZeroWithBisection that takes a function f, a float x0, a float x1, and a float epsilon, and returns an approximate value x in [x0,x1] where f(x) is approximately zero. Your function should stop when x0 and x1 are within epsilon, and at that time should return the midpoint of that range. Note that if it is not true that exactly one of f(x0) and f(x1) is negative, your function should return the Python value None, signifying that the bisection method cannot be used on the given range.
Let's see this in action! First, we'll use it to approximate the square root of 2 without the ** operator:
print "use bisection to approximate sqrt(2):"
def f1(x): return x*x - 2 # root at x=sqrt(2)
x = findZeroWithBisection(f1, 0, 2, 0.000000001)
print " x =", x # prints x = 1.41421356192
print " check: x**2 =", (x*x) # prints check: x**2 = 1.99999999871 (really close!)
Next, let's use it to approximate phi (the golden ratio), without using the closed-form solution ((1 + sqrt(5))/2), instead using the interesting property of phi that adding one to it is the same as squaring it. That is, ((phi + 1) == phi**2). How do use that? Simple, convert it into an equation equal to 0: phi**2 - (phi + 1) == 0. Now we're set! (Of course, we could just use the Quadratic Formula here, but it's more interesting to use bisection, now that we have it!).
print "use bisection to approximate phi (the golden ratio):"
def f2(x): return x**2 - (x + 1) # root at x=phi
x = findZeroWithBisection(f2, 0, 2, 0.000000001)
print " x =", x # prints x = 1.61803398887
phi = (1 + 5**0.5)/2 # the actual value (to within Python's floating point accuracy)
print " check: x/phi =", (x/phi) # prints check: check: x/phi = 1.00000000007 (nice!)
The previous two examples are nice, but simpler techniques than bisection would have worked as well. So let's solve a problem that would be hard to solve without bisection (or some other numeric approximation algorithm). Specifically, find a number x such that x5 == 2x:
print "use bisection to approximate x where x**5 == 2**x"
def f3(x): return x**5 - 2**x # f(1)<0, f(2)>0
x = findZeroWithBisection(f3, 1, 2, 0.000000001)
print " x =", x # prints x = 1.17727855081
print " check: x**5 - 2**x =", (x**5 - 2**x) # prints check: x**5 - 2**x = 3.63570817896e-09 (great!)
Hopefully this bisection excursion helps you appreciate the awesome computational power that about 10 lines of Python can have!
Background: A right-left route cipher is a fairly simple way to encrypt a message. It takes two values, some plaintext and a number of rows, and it first constructs a grid with that number of rows and the minimum number of columns required, writing the message in successive columns. For example, if the message is WEATTACKATDAWN, with 4 rows, the grid would be:
W T A W
E A T N
A C D
T K A
We will assume the message only contains uppercase letters. We'll fill in the missing grid entries with lowercase letters starting from z and going in reverse (wrapping around if necessary), so we have:
W T A W
E A T N
A C D z
T K A y
Next, we encrypt the text by reading alternating rows first to the right ("WTAW"), then to the left ("NTAE"), then back to the right ("ACDz"), and back to the left ("yAKT"), until we finish all rows. We precede these values with the number of rows itself in the string. So the encrypted value for the message WEATTACKATDAWN with 4 rows is "4WTAWNTAEACDzyAKT".
With this in mind, write the function encodeRightLeftRouteCipher that takes an all-uppercase message and a positive integer number of rows, and returns the encoding as just described.
Write the function decodeRightLeftRouteCipher, which takes an encoding from the previous problem and runs it in reverse, returning the plaintext that generated the encoding. For example, decodeRightLeftRouteCipher("4WTAWNTAEACDzyAKT") returns "WEATTACKATDAWN".
On last semester’s schedule, you can find some code I wrote to give everyone a Thanksgiving message. For small points, figure out how it works, and explain in plain English how it works. To actually generate the encoded version of the message that’s in the Python code online, I wrote a second program, not included there, that took my real message and converted it to that form. Actually, I also used the output of a Linux program called “banner”, and you may do the same. Your task is to write that second program, the one that takes a plaintext English message and converts it into one encoded like the one in the program. Place your solution to the bonus problem at the very top of your submission, and include the free-response English text in a comment there, too. Enjoy!