Insights by Danielle Fong

Konstantin Lopyrev writes (on the TopCoder forums):

“Everyone always discusses algorithms and such on this forum. However, there is one trait that is perhaps equally important as knowledge of algorithms – good problem solving strategy. By that I mean not jumping into solutions too quickly, thinking through everything before writing any code and such. Can anyone share what they’ve figured out that helps them? I’ve noticed that I have several flaws when I solve problems in general. I am too quick to start writing code. Also, I don’t think through my algorithms thoroughly. Also, there are many other things. Does anyone have similar flaws that they’ve already passed. If you have, please share your strategies for getting better at problem solving in general. Anything would be helpful, since I have the TCHS tournament coming up and I want to go home with some sort of prize.”

I wrote back, on May 10th ’07:

One thing I want to start doing is to make estimates of the implementation time of parts of my solution, how difficult each will be to code correctly/debug, and how sure I am that my method will work in the first place.

I’ve gotten very good at making estimates of time and space constraints. Now they are second nature. But knowing how best to solve a problem practically is still another area which I need to improve.

For example, for the last hard problem on TopCoder (circa May 9th, sorry, you’ll have to register to see it). I broke the problem down. Six steps toward victory! Five of those steps were really quite simple, though a few bugs crept in. The sixth was brutal — I could solve the problem by implementing a complicated comparison function object which recursively called itself on sorted sets of children. It was really crazy. To get it all working properly took nearly eight hours after the match.

Each bug, if not isolated, tends to increase debugging time by something like the square of the number of interacting components: the rate at which the number of dependencies would grow. Perhaps it would be simpler to either independently verify each component (by having pre-written tested functions or methods), or to organize the program, inasmuch as possible, as a linear pipeline or other simple acyclic graph. In fact, one might take a few seconds just to sketch the program idea out — how strongly coupled is it? What can I be sure of? How much of a pain will it be to debug? Can I make it less so? If not, can I anticipate debugging requirements and build in information gathering tools?

Furthermore, I was lured by that fact that, conceptually, ‘most’ of the problem could be coded simply. This blinded me to the fact that the code that was doing all of the work was almost completely unsupported by the auxiliary framework I had envisioned, and that the whole thing was a tightly entangled mess. Maybe the other coders can handle it. But I think it’s mostly because they know ways to keep things from failing — keep bugs isolated and visible enough to squash.

What I really needed to do was find a data structure or recurrence that was simple enough to verify piecemeal. I cannot be trusted to write bugless code. In fact, I should guard against it by breaking things down. This has the added benefit of making more clear what I need to do. I would need to remember less. Increasing my effective working memory has an impressively super-linear effect on my problem solving ability, how fast I can learn things, and also how much fun I’m having. I’ve come to realize this only recently, while studying for PhD qualifiers using index cards, scrap paper, two levels of books, one rough, one ‘canonical’, a wiki system of notes and a flashcard engine we made for it.

The last thing — and I think this is really more rudimentary, but I’ve yet to learn my lesson, know exactly what your variables are. In all of my experience this is the worst problem I have. Again and again I find myself with a few minutes to spare before the end of the coding phase (for readers unfamiliar with TopCoder, to get any points you need to have a solution that is (almost) exactly correct, submitted before the 1:15hr deadline). There is some minor error which I’ve detected. The tests give one more in some cases, one less in others, maybe it fails on an edge case. The tinkerer in me asks ‘hey! what happens if I turn this knob? Cross that t? Increment that i?’. So, I try it. Does it ever work? No. Not one damned time.

It’s voodoo programming, sure, and I make fun of it when I see others do it, but there’s just something — as that clock is ticking down, for some reason it feels like the competition is not about making sense of problems but just trying loads of things really really fast. And when I’ve defined an ‘r’ or an ‘x’ or a ‘q’ as some kind nifty function, where I only know the ‘approximate’ relationship with what I’m doing (up to a least significant bit, or maybe it’s part of the state of my program’s implicit automata that I used to speed up coding), when I’ve done this and the program nearly works except for this minor case or that minor case, it takes me nearly forever to disentangle what something is from what it is supposed to be. Even though I feel like I’m so close, when the pressure is on I just can’t handle it. It’s just way too complicated to do in my head when I keep having to watch the clock.

——

One advantage of TopCoder is that you’ll be constantly stretching your abilities. You’ll be solving many more problems than you otherwise might, and because of the time pressure you’ll learn faster, and it will stick better. I came across apropos comments by Philip Greenspun

1. A person won’t become proficient at something until he or she has done it many times. In other words., if you want someone to be really good at building a software system, he or she will have to have built 10 or more systems of that type.
2. A person won’t retain proficiency at a task unless he or she has at one time learned to perform that task very rapidly. Learning research demonstrates that the skills of people who become accurate but not fast deteriorate much sooner than the skills of people who become both accurate and fast.

and

Whatever the training task, the pace must be ruthlessly brisk. The learner should be expected to build at the same pace as an experienced developer. The difference between the learner and the wizard is that you expect the learner to make a lot of mistakes. The system as built may be awkward or not handle error cases properly. That’s okay. Training research shows that if you get speed now you can get quality later. But if you don’t get speed you will never get quality in the long run. We practice this technique in 6.916, Software Engineering for Web Applications, our course at MIT. Each student builds five database-backed Web applications during the 13-week semester. The first few that they build, during the course of the problem sets, are not necessarily elegant or optimal, but by the end of the semester they’ve become remarkably proficient, especially when you consider that each student is taking three or four other classes.

This rings remarkably true. Periods where I’ve needed to learn a skill in a short period of time have inevitably resulted in me learning them well. TopCoder is a terrific example. So was the high school math I needed to catch up on when I found myself in the university math department at 12. Cramming seems to have gotten a bad rap. I learn best intensely.

It’s not overarching. One of the most striking counterexamples is my friend Joel. When I met him in first year, he had already read code complete, and was working on his own games. He painstakingly engineered every assignment to be bug free. Extensible. Readable. Coherent. Most of us rationalised such behavior as making sense only because later assignments built upon the previous.

Joel lost the floppy he kept his work on. Most of us would have been upset. He was unphased. He did all his engineering for practice, and was happy to be able to do it again.

On TopCoder, he isn’t always the fastest. But he is the only competitor I know with a perfect accuracy rating. I don’t believe this skill was developed under time pressure. But I do believe that it entailed long hours, and sincere commitment to build something well. That is quite rare.

——

It’s been a while since I’ve done any of these contests: things keep getting in the way. Making rent, and taking care of other basic necessities has impeded my time for fun. Hopefully my skill wouldn’t have deteriorated in the interim. I actually have hope that I’ve unlearned more of the bad habits than my good. :-)

Further Reading

Misof’s description of the solution to the “RussianCheckers” TopCoder problem highlights a crucial part of the problem solving process: understanding how to reliably, quickly, and accurately implement a particular solution. The problem statement gives all the information one needs to solve the problem, but the task of implementation is so hard that only two competitors manage. Petr, the winner of the match, has a solution that’s a paragon of readability.