I spent the bulk of my time yesterday solving problems on SQLzoo.net and leetcode.com. I built a program that converts Roman Numerals to integers & also one that converts integers to Roman Numerals. I watched the third lecture of 6.006 (Algorithms and Data Structures), where we talked about Heaps, Max & Min Heaps, Max-Heapify and HeapSort. I think the professor is trying to build up to introducing algorithms that can sort certain data structures in time faster than O(nlogn). Heapsort doesn’t quite accomplish this, however it is getting us closer to that goal. I spent some more time trying to do lab1 for 6.009, but came across a logical bug in my code that was stumping me so decided to walk away from the problem for a bit. Fortunately, that decision turned out to be prudent as today I solved it!
As the picture above demonstrates, I was unable to pass the test_blur test cases, and the reason why is because I had improperly implemented the correlate method.
Here is the properly implemented algorithm. My logical error lied in the first line of the inner most nested for loop (this line ‘for kerny in range(len(kernel[kernx])’). I had originally been trying to retrieve the pixel (x-1+kerny, y-1+kernx), but after scrutinizing this code for the better part of 2 hours today, realized that this case would only work on 3×3 kernel. To generalize, I had to retrieve the pixels for x and y that were in the range (x-len(kernel)//2 +kerny, y-len(kernel)//2+kernx), as this number is the distance from the center to the edge of the kernels. It turned out that for 3×3 kernels this number was always 1. I conceptualized this method on 3×3 kernels, but didn’t realize that this number needed to be generalized for higher dimension kernels as well. This took a good deal of reasoning and time for me to solve; I was almost convinced at one point that it was the test cases that were broken, and not my code. You can probably imagine my feelings of vindication when I ran this test to see the following message:
Success! Once I had the correlate method working properly, the rest was pretty straightforward. All that’s left for me to implement is the test_edges method, which I would have done today had I not run out of time (it is a Friday night after all, and I am allowed to have some fun, right?!)
My copy of The Self Taught Programmer” also came in the mail today and I began reading it. Skipped through the first 15 chapters or so since it’s just basic Python syntax rules. The sections on reading and writing to files are nicely prepared though, with a thorough introduction to the with function used to write or read files, and also a discussion on how to handle CSV files. I began reading up on regular expressions and printed ‘The Zen of Python’ poem, a pretty logical starting point for regular expressions. Still trying to wrap my head around this a bit more, so I decided to not spend much more time delving deeper into regular expressions.
Side note: in this book, they talk about the FizzBuzz program and how its a solid interview question to filter out candidates. Umm, is this real? I made this program on my third day of learning python; it seemed trivially easy. This makes me either doubt the industry or the author of this book; and I don’t doubt the industry.
That’s all for today!
