I write about my solutions to the coding competition problems only for myself. For the problems that stretched my mind a little more. To bring myself a clarity of thought of what i did in the code. To understand my mistakes. Do not read it unless you have really nothing else to do in this awesome universe!
The question : Lakes in Berland. As simple as it could it be. I guess it didn't take me more than 10 minutes to figure out how to solve it. But there awaits the demon. The one everyone talks of. The implementation.
There is a reason why great programmers ask to code your solution. Because just knowing the solution isn't enough! And that is what happened in my case.
It took me quite a good long time, almost a day to get to a working solution! And no, it wasn't anything hard to code. It just reflects my weakness in implementing a solution.
..
While coding the solution, I was noting down all the mistakes that I did, due to which my test cases failed. Here they are in a proper format just to make myself realize my fallacies, and why I need to think a little more before submitting my solution all over again.
MIstake #0 : It took a lot of time to implement the dfs, and the lines of code that I wrote was way more than for the accepted code in C++; always a red signal.
Mistake #2 : I made a very big mistake as my code was allowing the non-starting vertices to be on the border, had to refactor my code to find the connected components!
Mistake #3 : I was using a function parameter to decide whether to change water to land, and I forgot to change its value to 1, so in my answer, water cells that need to get converted didn't get converted
Mistake #4: Now, I was pretty sure that my code worked, and so I submitted it again, and BAM it failed again, and this time for the test case
1 1 0
.
Seeing this, I was like, what the hell. Why didn't I think of this. And then the cure I proposed was a quick if else condition if the test case consisted of single row or single column!
Mistake #5 : The solution I proposed above is a perfect example of why I should not see the failed test case as an exception, but rather a glitch in the code itself.
Why?! Because it failed failed again at another test, and it was this time I saw the fault in my code.
I was basically accessing the first element of one of the arrays every time even when it was quite possible that the array may contain nothing. And the array will definitely contain nothing, when there exist no lakes in the map.
The fix I proposed this time was better, and especially not an exception.
Mistake #6 : This time one test case failed as maximum recursion depth had reached, although the test case was very simple. Since I used recursion, my code was reaching a depth of around 2500, and therefore the runtime error occurred. I reset the recursion depth limit to fix this.
At this point, I noted down 2 things in my mind. One, when using recursion, make sure you know how much depth your recursion can travel based on the constraints, and set the limit accordingly.
And secondly, better use iteration in DFS instead of recursion. I realized it later last night only that it is quite simple to code the iterative version.
And that's how I spent my morning today, coding the iterative version.
..
It was quite a good time solving this question. Quite a good way to make myself realize that just knowing the pseudo code of an algorithm is not enough. Implementation has its own importance!
I am now going to jump over to another problem on HackerEarth, Kingdom of Monkeys. It's quite similar to this one, and hopefully I would code it sooner that this one, without any need to introspect my mistakes.
No comments:
Post a Comment