pro-tip:

don’t try to keep it all in your head.

I’m reading about the tortoise and hare algorithm for finding cycle detection. Just moments ago, I read the following in the (awful) comment on wikipedia:

# now the position of tortoise which is the distance between
# hare and tortoise is divisible by the length of the cycle.

So, the position of the tortoise is x, and the position of the hare is 2x, and x is divisible by L, the length of the cycle. I’m surprised that x is necessarily divisible by L, so I figured it’s time to do a thought experiment. So I sat here and thought “okay so let’s imagine a graph with a cycle in it — maybe 2 nodes going in, and 3 nodes cycling back and forth”. Next, I thought “Now let’s consider the tortoise at the point of entry into the cycle — he’s moved 2 steps, so the hare would have moved 4… so the hare would be” and I started trying to picture the point the hare would be at. Meanwhile, I’m thinking “maybe I should try fewer vertices? Or more…”, and “Maybe I should go step by step and keep track of each of their progress through the sequence.”

If that sounds confusing, good. Because it is. Keeping a ton of stuff in your head like that is silly, and error-prone, and vulnerable to distraction. Just by thinking “I should write a short blog post about this”, I lost some of the state I’d built up. Actually writing the blog has obliterated any progress I’d made.

Instead of trying to keep things in your head — whether you do it out of laziness, or because you want to prove you can do it*, or because it just doesn’t occur to you to do otherwise — just write things down. Open a text editor and plop things in there, or my personal recommendation: grab a pencil and some paper and write/draw it out. The physical world can do the job of remembering where and what everything is, and you just have to figure out the transformations. Much easier. Much smarter.

* I fall into this trap whenever I use Khan Academy’s tests. I start off on something easy enough that it makes sense to keep in my head. Then it gets a little harder, for a long time, and eventually I’m struggling to multiply 5 digit numbers in my head for no reason other than a misguided sense of pride. I’ll usually give up around then, too, which shows that it’s not a smart path.

Leave a Reply

Your email address will not be published. Required fields are marked *