15-112 Spring 2015 Homework 9
Due Sunday, 29-Mar, at 10pm
Read these instructions first!
-
This hw is partly COLLABORATIVE and partly SOLO. Be certain to understand which is which. Hw9a is collaborative, and hw9b is solo.
-
This hw has two parts: Part A is Collaborative (in teams of up to 3 students total), and Part B is SOLO (working alone). You are going to submit both of these in a single file, hw9.py. This file will contain both collaborative and solo work. Be certain that your solo work is in fact solo!!!! And be sure to list your collaborative partners for Part A by name and andrew id at the top of your file.
-
All solutions must be recursive to receive any points. You may use iteration, too, but you may only use loops where appropriate within recursive functions, such as a loop inside findLargestFile to iterate over the files within a specific folder.
-
No portions of this hw are autograded. Still, you may make up to 5 submissions
in total
(you do not submit hw9a and hw9b separately, so this is 5 total submissions
for the two combined). As usual, only your last one counts.
-
Do not use global variables! Do use test functions! Do use helper functions!
-
Following the hw9 deadline, we will have "CA-moderated code reviews" where
students will meet in small groups and review each others' anonymized code,
both for style and correctness. This is not a grading session, and students will not
be grading each others' code. What's more, the anonymized code will be from
anonymous students in other sections of the course.
Code reviews are a standard practice
in industry, and they are an invaluable tool in helping both the reviewers
and the reviewees improve their understanding of what constitutes good code
and how to more reliably write good code. These meetings will be required,
and will take one-half hour. This activity will be worth 5 points,
which will be awarded based on participation in one such meeting.
Your CA's will contact you soon after the hw9 deadline with more details.
Hw9a: COLLABORATIVE
-
CA-led code reviews [manually graded by participation] [nothing to submit] [5 pts]
(See above for details.)
-
from f13-hw9:
study the recursion notes (this semester's, of course) [in triple-quotes] [manually graded] [10 pts]
-
from f11-hw5:
Reasoning About (Recursive) Code [in triple-quotes] [manually graded] [15 pts; 3 pts each]
-
from f14-hw9:
bubblesort [manually graded] [10 pts]
-
from f11-hw5:
fractalMickeyMouse (and mickeyFace) [manually graded] [10 pts]
Hw9b: SOLO
-
from f11-hw5:
flatten [manually graded] [10 pts]
-
from f11-hw5:
findLargestFile [manually graded] [10 pts]
-
from f13-hw9:
solveABC [manually graded] [30 pts]
Hw9 bonus: SOLO Bonus
-
from f14-hw9:
bonusTwoStackHanoi [manually graded] [2 pts]
-
from f14-hw9:
bonusPythagorasTree [manually graded] [2 pts]
- bonusPegSolitaire [manually graded] [5 pts]
First, read up on peg solitaire
here, and then read this entire writeup carefully. Then, write a peg solitaire solver using backtracking. The boards will be given to the function as a string of periods, O's, and spaces, which represent holes, pegs, and invalid spaces respectively (see examples below). The result should be returned as a list of moves to be made in the form (fromRow, fromCol, toRow, toCol), which indicates which piece to pick up (the from piece) and where it goes (the to piece). Your function must give the answer in a reasonable amount of time, which is defined as 10 seconds.
Note that this problem is actually pretty difficult to do. This is because there are a lot of possible moves one can make at some stages in the puzzle (whereas in nQueens for example there are always only n possible moves). As such, we will grade on a rolling scale as such (examples of each case below).
1pt boards with 10 pegs
1pt boards with 14 pegs
1pt boards with 16 pegs
2pts boards with 32 pegs
Your basic backtracking will eventually get the correct answer for all situations, but it'd probably take many many years to get the solution to the 32 peg board. As such, you will have to be a bit smarter to solve the higher peg boards, and maybe even need more advanced AI techniques to get the 32 peg board.
Here are some boards to play with.
board10 = """\
...
.O.
..OO.O.
.O...O.
..O.O..
O.O
...
"""
board14 = """\
...
OO.
..O.OO.
OO..OO.
.OOO..O
.O.
...
"""
board16 = """\
...
OO.
..OO...
..OO.OO
OOO..OO
OO.
.O.
"""
board32 = """\
OOO
OOO
OOOOOOO
OOO.OOO
OOOOOOO
OOO
OOO
"""