CMU 15-112 Spring 2019: Fundamentals of Programming and Computer Science
Homework 10 (Due Sunday March 31, at 5pm)

In the assignment, several questions are labeled Recursion. Unlike in HW9, you CAN use loops and loop-like concepts within your recursive functions (unless otherwise specified). However, every problem labeled Recursion must still use recursion in a meaningful way. Meaningful means that your overall strategy to solving a problem is primarily a recursive one.
When writing recursive code, watch out for destructive functions! Changing mutable values in a function can be useful, but can also make debugging tricky.
Relatedly, if you use default arguments, be careful about how you initialize empty lists and other mutable data types so that you don't create unwanted aliases.

Do you need new collaborator(s) for hw10? Fill out this form and we'll try to pair you up with other students in the class. We'll stop checking for new entries on Friday morning, so fill it out before then!

To start:
1. Create a folder named 'week10'
2. Create a hw10.py file in that folder.
3. When you have completed hw10, submit hw10.py to Autolab. For this hw, you may submit up to 5 times, but only your last submission counts.

Important Note: the autograder we use breaks when it tries to import tkinter. Therefore, all of your tkinter code (for fractalSunViewer() and graphics-related bonus questions) must be included after a comment that reads #ignore_rest. The autograder will only grade code that appears before #ignore_rest. This means that your solutions to all autograded problems must appear before #ignore_rest!
Do not hardcode the test cases in your solutions.

Note: you are not required to generate additional test cases for fractalSunViewer() but you should write test cases for each other problem.

Style [0 pts]
As usual, write your code with good style, and following the 15-112 style guidelines.

TP Mini Lectures! [15 pts]
Term project season is almost upon us! Your TAs have prepared over a dozen hour-long mini lectures on various topics that you may find useful to your term projects. You are required to attend at least one mini lecture, which will be worth 15 points on this assignment. You get to choose which one(s) you want to attend. Attendance will be taken at the sessions, so make absolutely sure you fill out the form and participate in any interactive activities! Standard attendance grading policies apply, and we will not accept regrade requests unless you have an email receipt to show that you filled out the form. Refer to the course schedule for the most up-to-date information and post-lecture materials, but we'll copy the basics here for your convenience:

TP Mini-Lectures: You must attend at least one

Day	Time	Room	Topic	Presenters	Resources
Mon 3/25	4:30PM	DH A302	Databases	Marco
	5:30PM	DH A302	Advanced tkinter	Esther B.
	6:30PM	DH A302	Leap Motion (Gesture tracking)	Jonathan P. and Lisanne
Tues 3/26	4:30PM	GHC 4102	Audio	Jeremy
	5:30PM	GHC 4102	Sockets (Network communication)	Christina
	8:30PM	GHC 4102	Arduino (Microcontrollers)	Sid and Mae
Wed 3/27	6:30PM	SH 125	Data Structures	Jenny and Brent
	7:30PM	SH 125	Game AI	Sarah and Ria
	8:30PM	SH 125	Kinect (Body tracking)	Fletcher and Marco
	8:30PM	DH A302	Graph Theory [1.5hrs]	Emmanuel and Ani
Thurs 3/28	4:30PM	GHC 5222	PyGame	Jonathan P. and Marco
	6:30PM	SH 125	Web Apps	Zuhayer
	7:30PM	SH 125	ML + AI	Kyle
Fri 3/29	4:30PM	GHC 4102	Visual Arts	Jonathan P.
	5:30PM	GHC 4102	OpenCV (Computer Vision)	Fletcher and Kusha
Sun 3/31	1:00PM	WEH 5409	3D Graphics	Chaya

Collaborative problems

Recursion: findLargestFile(path) [15 pts] [autograded]
Without using os.walk, write the recursive function findLargestFile(path), which takes a string path to a folder and returns the full path to the largest file in the folder (and all its subfolders). You can compute the size of a file using os.path.getsize(path). If there are no files, the empty string ("") is returned. You do not need to handle the case where the supplied path is not valid or is not a folder, and you may handle ties however you wish.

Note that file systems can be very large, so in this problem, efficiency is important! Therefore, you may not use listFiles to gather all the files into one place, and you should avoid calling os.path.getsize on a single file more than once.

To help test your code, here are some assertions for use with sampleFiles (available in hw10p2_sampleFiles.zip):

assert(findLargestFile("sampleFiles/folderA") == "sampleFiles/folderA/folderC/giftwrap.txt") assert(findLargestFile("sampleFiles/folderB") == "sampleFiles/folderB/folderH/driving.txt") assert(findLargestFile("sampleFiles/folderB/folderF") == "")

Hint: You will almost certainly want to use a wrapper function or an optional parameter to make the problem easier to solve. This will make it easier to pass file size information back along with file names...

Recursion: createKnightsTour(n) [25 pts] [autograded]
Write the function createKnightsTour(n) that returns a 2D list representing a valid knight's tour on an n-by-n chessboard, or None if no solution exists. Recall that you have already solved isKnightsTour(board) in HW5. This is convenient because you can use it to test createKnightsTour(n)! First, let's review what constitutes a knight's tour:
A knight's tour in chess is a sequence of legal knight moves such that the knight visits every square of a chessboard exactly once. We can represent a (possible) knight's tour as an n-by-n list of the integers from 1 to n² listing the positions in order that the knight occupied on the tour. If it is a legal knight's tour, then all the numbers from 1 to n² will be included and each move from k to (k+1) will be a legal knight's move.

Here are a few examples of successful knight's tours:

#The only n=1 board: board0 = [[1]] #A few different n=5 boards: board1 = [ [ 1, 20, 9, 14, 3 ], [ 10, 15, 2, 19, 24 ], [ 21, 8, 25, 4, 13 ], [ 16, 11, 6, 23, 18 ], [ 7, 22, 17, 12, 5 ], ] board2 = [ [ 1, 18, 23, 12, 7 ], [ 24, 13, 8, 17, 22 ], [ 19, 2, 25, 6, 11 ], [ 14, 9, 4, 21, 16 ], [ 3, 20, 15, 10, 5 ], ] #Our isKnightsTour function from HW5 should return True for each assert(isKnightsTour(board0)==True) assert(isKnightsTour(board1)==True) assert(isKnightsTour(board2)==True)

The results above can be generated by calling createKnightsTour(n), but your function might not (and doesn't need to) match it exactly, as long as the tour is valid. The knight must always start in the top-left corner (i.e. result[0][0]==1). This will reduce the number of possibilities we have to check.

Important note: Your function only needs to run on board sizes up to n=6 (i.e. 36 squares in the grid). The number of possible move sequences becomes ridiculously large as n increases. Unless you do something clever (see the bonus!) your program might take hours to finish on n=8.
Also note that some board sizes have no valid solutions. For example, createKnightsTour(2) should return None.

We highly recommend (but will not require) that you apply your @print2DListResult decorator to createKnightsTour so that whenever a complete and valid knight's tour is returned, it is printed out in a readable format (otherwise the decorator does not print anything). Printing 2D lists normally can get quite messy, so this will help you debug! If you try this and your code is printing out tons of partial results, a wrapper for createKnightsTour(n) can ensure that you only print the result of the outermost recursive function call.

Here is an image from Wikipedia's article on knights in chess which demonstrates the possible moves for two knights.

If you are unfamiliar with how a knight moves in chess, you can envision the possible moves as a 3-by-2 L-shape, where the start and destination are are at opposite ends of the letter.

Hint: You may use your isKnightsTour(board) solution from HW5 to help you write test cases for createKnightsTour! If you do that, copy your function AND your isKnightsTour tests so that you can be sure it's working properly (and so that you meet the style requirement of having tests for major functions). Note that if you haven't solved isKnightsTour, that's ok as long as you still create test functions. If you would like help writing or fixing your isKnightsTour function, TAs can help you with this in office hours!

(03/27/19) New hint!: You may find that your createKnightsTour function works, but it's still too slow for Autolab on n=6 boards. Here's a hint that can speed up your function's ability to find a solution quickly. For each piece, the order in which you attempt each move can make a difference. Revisit the wikipedia article and watch the gifs to see if you notice (especially in the first few moves) any tendancy of the knight to travel around the board in a certain way. Then consider that some squares are very difficult to get to, while some are rather easy. Specifically, the corner squares can only be reached from two other squares, and a knight in any corner also has just two possible places it can go next. Edge squares also have a fewer number of squares leading to them, and a fewer number of possible moves from those points. The middle squares can be reached from 8 different locations though, and have plenty of options for subsequent moves! Given the choice, would you rather try to move around the edges of the board first, or fill the center squares first? Can we accomplish that by attempting moves in a certain order? If your function works but is slow (about two minutes for n=6), consider these points before making major changes to your algorithm!

(03/28/19) Even newer hints!: If you feel like your backtracking logic is good but your code is still slow, read on! As mentioned in class, the order in which you attempt the moves does matter quite a bit! Consider the previous figure and the eight possible ways the black knight can move. You should attempt these moves in a circular order, i.e. pick and attempt a direction (like [-1,-2]), and if the move is either invalid or the subsequent recursive case returns none, try the next clockwise move (from [-1,-2], the next would be [-2,-1]). Keep exploring moves in a clockwise fashion and you'll probably find a complete and valid board faster, if one exists for that board size. You might even complete the 8-by-8 case!

Solo problems

@print2DListResult [10 pts] [manually graded]
Usually when we try to print 2D lists, they can end up being difficult for us to read. Let's fix that by creating the decorator @print2DListResult. When applied to a function that returns a single 2D list, the function will print out the list in a more "human-readable" way. If the function returns anything that is not a 2D list (or returns nothing), the decorator does not print anything. The decorator should not change the returned value of the function (i.e. when we apply this decorator later in the homework, it should not interfere with your test cases.)
While you don't have to match the exact spacing, see the example below for guidance. We'll be manually grading your decorator with a few of our own functions, but here's one for you.
@print2DListResult def makeExample2DList(n): myList=[] for row in range(n): myList.append([col*row for col in range(n)]) return myList lst = makeExample2DList(8) '''This code creates a 2D list. If we removed the decorator, it wouldn't print anything, but WITH the decorator, it prints the following lines: [ 0 0 0 0 0 0 0 0 ] [ 0 1 2 3 4 5 6 7 ] [ 0 2 4 6 8 10 12 14 ] [ 0 3 6 9 12 15 18 21 ] [ 0 4 8 12 16 20 24 28 ] [ 0 5 10 15 20 25 30 35 ] [ 0 6 12 18 24 30 36 42 ] [ 0 7 14 21 28 35 42 49 ] Nice! Now let's see what would happen if we print(lst) like normal''' print(lst) '''Big yike! This is what we're avoiding with the decorator: [[0, 0, 0, 0, 0, 0, 0, 0], [0, 1, 2, 3, 4, 5, 6, 7], [0, 2, 4, 6, 8, 10, 12, 14], [0, 3, 6, 9, 12, 15, 18, 21], [0, 4, 8, 12, 16, 20, 24, 28], [0, 5, 10, 15, 20, 25, 30, 35], [0, 6, 12, 18, 24, 30, 36, 42], [0, 7, 14, 21, 28, 35, 42, 49]]'''
Note: You may assume that the 2D lists we are interested in are rectangular (non-ragged) and do not contain elements with more than 4 characters, i.e. you don't have to worry about perfect spacing if the list contains large elements like "Kimchee the Axolotl" or 12345.00001. You also don't need to worry about 3D or larger lists, or any elements that are sets, dictionaries, etc. Don't sweat making it perfect; we just want something that prints 2D lists of letters and numbers in a more readable format.
You also do not need to write test cases for this decorator, but make sure to test it manually!

myJoin(L, sep) [10pts] [autograded]
Using reduce, map, and lambda, write the single-expression function myJoin(L, sep) that takes a non-empty list L and a string sep, and without calling sep.join(L), works roughly the same as that -- returning a single string with the values in L separated by the sep. So:
myJoin(['a','b','c'], '-') returns 'a-b-c'
Unlike sep.join(L), your function must work even if L contains non-strings. So:
myJoin([1, 2, 3], '@@') returns '1@@2@@3'
Remember that you may not call join, and your solution must be only one python expression.

Recursion: drawFractalSun(data, canvas, xc, yc, r, level) [25 pts] [manually graded]
Write an animation which displays a majestic fractal sun centered at the (xc, yc) position, with the given radius r, and at the specified recursion level. To draw a fractal sun, start with a circle in the middle of the screen; that circle should send out eight equally-spaced rays (each twice the length of the circle's radius), then repeat the sun fractal at the end of the ray with a quarter of the original radius, one recursion level down. Here's an example of a fractal sun at varied recursion levels:

Note that the colors of the suns change based on the recursion depth in our example. You can either use our color scheme or invent your own! The only requirements are as follows: a) the suns at the same recursion depth must be the same color, b) suns at different recursion depths must be different colors, and c) the colors must look good no matter what the maximum recursion depth is. Hint: you'll probably want to use data in some way to determine which color to draw with at each depth.

You should write your code under the #ignore_rest line with the basic animation framework and the fractal starter code, such that calling run(500, 500) produces an image like the one shown above (perhaps with different colors). Your code must use drawFractalSun(data, canvas, xc, yc, r, level) to actually draw the fractal. Pressing the arrow keys should change the level of the recursion depth appropriately. Please have your animation start at recursion level 1!

Note: your program may become slow at recursion depth 5 and beyond. Your program should still theoretically work at these larger depths, but we'll only test for depths 0 to 4.

Bonus problems

Fast createKnightsTour(8) [2 pts] [autograded]
We will test your createKnightsTour(n) function with n=8. If your program is fast and does not time out, these bonus points are yours! By "fast" we mean that createKnightsTour(8) should return a valid solution in under 10 seconds. You don't need to write a separate createKnightsTour(n) function for this problem, but you will almost certainly have to incorporate some new logic to achieve these speeds. You may not use any external resources except for the single Wikipedia page on knights' tours linked in the homework problem.

To simplify grading, the following bonus fractal animations should run after drawFractalSun (one at a time, of course!) and all animation code should be placed after the #ignore_rest line.
runStellaFractalViewer() [3 pts] [manually graded]
Note: This problem is pretty much runTeddyFractalViewer from last semester's HW.
Write a function drawStellaFace(canvas, xc, yc, r) that draws a circular-shaped face of Prof. Rivers' dog Stella, without ears. This function takes as input a canvas to draw on, the (xc, yc) coordinates of the center of the face, and the radius r of the face. You don't need to do anything overly complex as long as it looks (sort of) like Stella. Does it have eyes, a nose and/or mouth, and approximately the right colors? If yes, you're probably good.

Hint: to draw the mouth, you might consider the function create_arc(...) of Tkinter with the optional parameters style and extent. For more information about this function read the documentation here.

Now, using your previous function drawStellaFace, write a function drawFractalStella(canvas, xc, yc, r, level) that recursively draws a character with the face you previously defined, and a recursively downsized version of that same face as ears. Your function will take as parameter a canvas to draw on, the (xc, yc) coordinates of the center of the face, the radius r of the face, and an integer level representing the maximum depth of recursion. The radius of each ear is exactly half the radius of the face. We don't have any examples of a Fractal Stella, but here's a picture of Real Stella and an example of a desaturated Fractal Teddy with maximum recursion level (depth) of 6. (Just... umm... imagine it's a Stella instead of a Teddy.)

Also, write the function runStellaFractalViewer() that behaves similarly to the run function for drawFractalSun, except you'll be drawing Stellas and their ears instead of suns.
Super Special Prize: If you make a great Fractal Stella, we might use it in the course notes next semester. Secure your legacy!

runKimcheeFractalViewer [3 pts] [manually graded]
Note: This problem is an extension on the Pythagoras Tree practice problem. CHECK THIS LINK
Prof. Taylor's axolotl Kimchee doesn't want to be left out. Read carefully, because she wants something a little different. Below the #ignore_rest line, write a function drawKimcheeFace(canvas, xc, yc, faceWidth, faceHeight) that draws an oval-shaped face of Kimchee, without gill feathers. This function takes as input a canvas to draw on, the (xc, yc) coordinates of the center of the face, and the dimensions of the face (faceWidth and faceHeight). You don't need to do anything overly complex as long as it looks (sort of) like an axolotl. Does it have eyes, a big mouth, and approximately the right colors? If yes, you're probably good. Here's a picture of her, and you can always google for more pictures of axolotls if you need inspiration:

Now for the gills. First, read about the Pythagoras Tree here. With this in mind, write the function drawGills() that creates a majestic, symmetrical set of gills for Kimchee that incorporates Pythagoras Trees in some way. You can choose how exactly they ought to look, as long as they are majestic and are drawn recursively.

Finally, write the function runKimcheeFractalViewer() that behaves similarly to the run function for drawFractalSun, except you'll be drawing Kimchee's gills. Make sure they don't obscure her adorable face.
Another Super Special Prize: If you make a great Fractal Kimchee, we might use it in the course notes next semester. Kimchee will also appreciate you.

CMU 15-112 Spring 2019: Fundamentals of Programming and Computer Science Homework 10 (Due Sunday March 31, at 5pm)

CMU 15-112 Spring 2019: Fundamentals of Programming and Computer Science
Homework 10 (Due Sunday March 31, at 5pm)