tortoise and hare algorithm<\/a> for finding cycle detection. Just moments ago, I read the following in the (awful) comment on wikipedia:<\/p>\n# now the position of tortoise which is the distance between\r\n# hare and tortoise is divisible by the length of the cycle.<\/pre>\nSo, 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.”<\/p>\n
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.<\/p>\n
Instead of trying to keep things in your head<\/strong> — 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<\/strong>. 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.<\/strong><\/p>\n* 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/posts\/673"}],"collection":[{"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/comments?post=673"}],"version-history":[{"count":5,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/posts\/673\/revisions"}],"predecessor-version":[{"id":678,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/posts\/673\/revisions\/678"}],"wp:attachment":[{"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/media?parent=673"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/categories?post=673"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/wcarss.ca\/log\/wp-json\/wp\/v2\/tags?post=673"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}