the merge sort code shown only works on arrays are a length of a power of 2. Adding another condition for len(L) == 1 in mergeSort that returns a single element array and a 2 element array will take care of the general case. Otherwise you'll get stuck in an endless recursion loop since it can't handle the base case of a 3 element array.
NOTE ON THE EXERCISES: the provided solution to exercise 1 in tiling-exercise1.py produces both False Positives and False Negatives. The most obvious False Positive is the case where 3 tiles form an L that blocks off a corner tile (which clearly cannot then be connected to two other tiles). You can test this with tileFourMissingYard(2, [(1,0),(0,1),(1,1),(3,3)]), which returns True instead of False (since (0,0) will be isolated). As for False Negatives, there are cases where neither of their stated cases are met but you can still successfully tile the board. Try tileFourMissingYard(2, [(0,0),(0,1),(1,2),(2,2)]), which is fairly easy to tile by eye but the function will return False. To be clear, as far as I can tell their function works for the given assumptions, but the exercise instructions don't say to implement those two assumptions, just to generally "Write a procedure that will determine if you can tile the courtyard or not." I'm a little frustrated that I spent hours drawing variations on graph paper trying to find a pattern to the general case, only to finally check the provided solution and find it to be wrong, but I do feel a little better about not figuring it out, lol. Just to be clear, I love the videos and the course! I'm learning a ton and having fun. So, thanks MIT and Professor Devadas! Just a little salty tonight and wanted to share what I figured out :P Keep on coding! :)
the merge sort code shown only works on arrays are a length of a power of 2. Adding another condition for len(L) == 1 in mergeSort that returns a single element array and a 2 element array will take care of the general case. Otherwise you'll get stuck in an endless recursion loop since it can't handle the base case of a 3 element array.
NOTE ON THE EXERCISES: the provided solution to exercise 1 in tiling-exercise1.py produces both False Positives and False Negatives. The most obvious False Positive is the case where 3 tiles form an L that blocks off a corner tile (which clearly cannot then be connected to two other tiles). You can test this with tileFourMissingYard(2, [(1,0),(0,1),(1,1),(3,3)]), which returns True instead of False (since (0,0) will be isolated). As for False Negatives, there are cases where neither of their stated cases are met but you can still successfully tile the board. Try tileFourMissingYard(2, [(0,0),(0,1),(1,2),(2,2)]), which is fairly easy to tile by eye but the function will return False.
To be clear, as far as I can tell their function works for the given assumptions, but the exercise instructions don't say to implement those two assumptions, just to generally "Write a procedure that will determine if you can tile the courtyard or not." I'm a little frustrated that I spent hours drawing variations on graph paper trying to find a pattern to the general case, only to finally check the provided solution and find it to be wrong, but I do feel a little better about not figuring it out, lol.
Just to be clear, I love the videos and the course! I'm learning a ton and having fun. So, thanks MIT and Professor Devadas! Just a little salty tonight and wanted to share what I figured out :P
Keep on coding! :)
Thank you so much.