Programming Challenges 4 - 6
Following immediately on from the previous challenges, I had hoped to redeem my rather miserable performance on Challenge 3.
Read on to see how I did with Challenges 4 - 6.
This was a rather fiddly one which took me two goes to solve. Nothing unusually technically challenging and no clever algorithms, just a case of getting all of the details exactly right. Consequently I didn’t really enjoy solving it as much as some of the others. I spent a lot of time checking and double checking numbers of characters, spaces after lines, etc, trying to work out why my first attempt wasn’t accepted by the judge. In the end my bug turned out to be nothing to do with line spacings and was a genuine case that I had missed in my code.
Here is the Source Code, which the judge accepted on my second attempt.
Things got a little more interesting with Problem 5. The stats page shows that this had the highest failure rate of any of the first chapter’s problems, so I was determined to get my solution accepted first go.
Unfortunately this wasn’t to be - my code tripped over on a case I thought I’d tested for. It got stuck in a loop when filling a region with the same colour as the fill colour. In fact I did test for this case but my code only failed in a specific variant of this case and that was the case I hadn’t tested.
This problem lead me to a neat idea which helped me out a lot on the next problem I solved. Part of the input specification said to ignore lines with unrecognised commands. I decided to take advantage of that fact to allow me to put Comments directly into my test data input files. This meant I could label test cases and put a little description to say what they were for, saving me from having to remember which scenarios I had already made test data for. When programming I need to keep as much of my short term memory as possible available for the job in hand, rather than for remember details that could easily be written down, instead.
Here is my finished Source Code, which was accepted on the second attempt.
I loved the concept of this problem - using the computer to create a mini-language to simulate the instructions on a basic CPU. However, I suspected that although it looked like it would be easy to create, it would be a tricky problem to test and I was still looking to get some more problems solved first time.
I went to a lot of trouble to keep things as simple as possible. I aimed to break the problem down into tiny pieces that would be easy to test. For example, in the finished source code you can see the function ParseInstruction(). This is a very simple function but is the sort of thing it is easy to make mistakes in. In fact my first version was more complicated and I didn’t realise I could simplify it until after I finished writing it. At this point I already had the SelfTest() function written, so I could confidently go ahead and change ParseInstruction() and know that if the tests still passed that I wouldn’t have broken it. ParseInstruction() is declared inline, so there is unlikely to be any performance disadvantage from separating it from where it is called.
I also wanted to eliminate as much repetition of code as possible as that would leave fewer places where things could go wrong. For example, where I moved code into another tiny inline routine called ReduceRegisters(). I knew it would be an easy mistake to forget to do the register arithmetic modulo 1000 as instructed, so I wanted to minimise the chances of me missing that.
Finally, there was the issue of how to test the code. It worked on the sample data, but that’s rarely enough for this kind of problem. However, coming up with more test data was tricky. This was where my comments idea from the previous problem came in. I realised that with only a tiny tweak to my program I could get it to ignore any text placed in the input file that wasn’t a number to do with the problem. This meant I could write comments in the input file and have my program ignore them without disturbing the input data. When it came to running on the judge there wouldn’t be any of these comments, so my program would be fine there, too.
I used the following data to test my program:
6
299 492 495 399 492 495 399 283 279 689 078 100 000 000 000 # Correct answer == 16
100 # Correct answer == 1
100 # Correct answer == 1
201 # Set r0 to 1 219 # Set r1 to 9 010 # Goto loc 9 200 # Set r0 to 0 200 # Waste some time 200 # so we know if we’re wrong 200 200 200 100 # Correct answer == 4
259 # Set r5 to 9 359 # Add 9 to r5 458 # Multiply r5 by 8 (s/b 144) 565 # Set r6 to r5 (s/b 144) 656 # Add r6 to r5 (s/b 288) 755 # Square r5 (s/b 82944 => 944) 956 # Set 944 in memory to val of r6 (s/b 144) 876 # Set r7 to val in ram specified by r5 (s/b 944-> value 144) 100
222 # Set r2 to 2 # Test out looping 239 # Set r3 to 9 331 # Add 1 to r3 023 # Branch to address in r2 (==2) unless r3==0 100 # Correct answer == 1985 </code>
You can see how the comments allowed me to write a mini-program that tried out all of the different possible opcodes defined by the problem. It was hard enough to do that with the exact meanings of the numbers written in place, so I think it would have been nearly impossible without that. I used a calculator to work out that the final answer needed to be 1985, before verifying that this was indeed the case. I also used some print statements that I later removed to show the values stored in the registers.
Here is my completed Source Code, which was Accepted first time by the judge.
Here is some bonus extra Source Code which solves Problem 10310 - Dog and Gopher. This code was also accepted first time by the judge. Here is the sample input I created to test this code, using the same comment technique as for the previous problem.
