Aaron N. Tubbs bio photo

Aaron N. Tubbs

Dragon chaser.

Twitter Facebook Google+ LinkedIn Github

Trying to batch my programming challenges progress up so I don’t bore the non-programmers in the audience. I’ve realized something along the way … even with a spec, and even if we’re not being malicious, the test cases I write (and I do write them, as the sample inputs/outputs are always intentionally deficient) are often far from exhaustive, and often miss failures. Sometimes (like in 10267) I miss something completely, but other times it’s something subtle I didn’t think about. This shouldn’t be any great realization, and indeed it is something I know, but I forget. Never trust the user. The user will try things I can’t think of. Gotta write code that’s better than that. Smarter than that.

Otherwise, I’ve come to appreciate the joy (read: laziness) on programming challenges of never doing bounds checking, and dealing with bounds by just adding dead space around array bounds. It’s not often tempting to write code like this in the real world, but there are some modest efficiency gains in bleeding a little memory for the edge cases.

Throwaway code is fun.

It’s weird using switches so much, instead of polymorphism.

Anyhow, still working through the book in sequence at this point, so I’ve finished the first chapter as of late last night, with results following this paragraph. I’m looking forward to the next chapter, where things should start getting slightly more interesting from a problem standpoint. I hope.

10267 – Graphical Editor

I was interested in this because I like the idea of beating “low” success rate problems. My solution is up; I’m realizing the code I’m writing for each solution is less and less elegant. Oh well. This was also especially interesting since we were talking about a portion of this problem at work last week. Really weird coincidence that it showed up in the next challenge I did.

  1. Runtime error. I fully expected that I was going to blow through my call stack, so this wasn’t a big surprise. I could actually have gotten away with this, if not for later mistakes.
  2. Managed recursion stack myself. Time Limit Exceeded. I made a dumb mistake and didn’t terminate my recursion.
  3. Fixed recursion problem. Wrong answer.
  4. Added some defensive code for guard byte exploits. Wrong answer. I’ve yet to add defensive code that’s solved the problem. I should have learned my lesson by now.
  5. Hah. I never tested my rectangle fill function. It does not work. Should be all set now, right? Wrong answer.
  6. Realized a dumb performance implication of not clamping values. Not a correctness thing, but horribly wasteful. Realized a subtle correctness problem that could come from this and buffer bleeding. Fixed that; no idea if this case was actually exploited. Wrong answer.
  7. Oh. Right. After problem 100 you think I would know better. Same dumb mistake, different problem. Accepted.

Interpreter

I fared better at 10033 Accepted on my first submission, which felt good, as that’s a first for me. On the other hand, if one extends the input slightly to include the entire instruction set (which I did), it’s pretty easy to see if your interpreter is working or not. Here’s my solution.

Check the Check

10196 took two submissions. I got one addition wrong in my code, and the judge found it; I wrote 97 test boards until I found one that demonstrated the issue. Stupid judge, keeping me honest. I am not proud of my solution. I didn’t like this problem, and as a result I didn’t produce a particularly elegant solution.

Australian Voting

10142 was a pain. It’s not because the problem is hard, it’s easy. It’s because this type of input spec is painful to handle in C++ and trivial in, say, Perl. Once I fixed my parsing issues, my solution worked fine.