Programming Challenges 1 - 3
I downloaded a copy of Skiena and Revilla’s book Programming Challenges from here. I wasn’t hugely taken by the book as it is mostly about coding in C, rather than C++ which I prefer, so I’ve only really skim-read it. However, I did take the time to solve some of the challenges after the first chapter, which was a far more valuable learning experience.
I decided that as the first few challenges looked fairly straightforward that I would make it my goal to solve each one 100% correctly on the first go. Unlike the Ancient Messages challenge where comprehensive test data was supplied, this time each challenge only came with one or two examples. This means that coming up with a good way to test the program is essential if one wants to pass the judge’s tests first time. In a programming competition failure to pass tests means a time or score penalty. But I’m more concerned with real life where a programming error could mean death, financial loss, or worse, the wrong coloured background on a dialog box!
So, how did I do?
This problem didn’t take me long to solve. It helps that I remembered solving a very similar Project Euler problem not so long ago. Of particular value was remembering one of the main “gotcha’s” of this problem - the fact that although the problem specification requests solutions for values between 0 and 1,000,000 the code needs to handle much larger values of n. The other “gotcha” is that without storing known results, the program will fail to finish within the specified time limit.
You can see in my solution where I store all values of the solution where n is less than a million, but re-calculate them where needed whenever n goes larger than a million.
You can also see that I have written a function called SelfTest() that only gets called when the program is run on my PC, and not when it is submitted to the Online Judge. Every time the program runs this function checks that all of the different components of the program are producing the expected values.
I’ve found functions like this to be incredibly valuable for writing good quality software. Although I would always want to test my software, having the tests as actual compiled code that gets run every time means that any problem I may subsequently introduce into the code gets picked up almost immediately.
Here is my finished Source Code which was Accepted by the judge on the first attempt.
I didn’t fare quite so well with this one though I felt a little cheated when I discovered the cause of my initial submission’s failure. A single blank line after the last test case. The instructions are quite specific in asking for a blank line between test cases, so it was a fair cop. This certainly made me far more alert when it came to reading the instructions for the next couple of problems I solved.
In this puzzle I didn’t include SelfTest code as it was easier to simply store complete test cases in separate test input files. However, I did make more use of assertions in the code to check that expected conditions were always true. This helped me to trap one or two bugs early on in development and prevent them from coming back by adding futher assertions to ensure that the bug remained fixed.
Here is my finished Source Code for the Minesweeper problem, which was Accepted by the judge on the second attempt.
I struggled with Problem 3 for a shameful amount of time, making some classic mistakes.
My first mistake was attempting to solve this problem using floating point numbers. I think I allowed this representation of the data to overcomplicate the problem. In my final solution I simply multiply the dollar amounts by 100 to convert them into cents. It should make a difference but it felt easier to get my head around.
My main mistake was to indulge in what is known as Voodoo Programming. That is, I leapt to my keyboard bashing away to solve a problem without really fully understanding the problem. This lead to me going around in circles and “trying things out” without a clear goal.
Eventually I got this on my fourth attempt, after taking a step back and working some examples out on paper, using a simple algorithm to share the money out, rather than the complicated fast solution I had thought I could get to work. Once again the SelfTest() code proved vital in getting code that would work and stay working through several changes.
Here is my Source Code.
