Today, I started out wanting to implement Langton's Ant in javascript, just to have something to play with. Implementing things like this is always interesting, because there are typically a lot of ways to write the program that are kind of annoying and painful; for example, in this case, you could encode the 2D grid the ant lives on as an array, but arrays in javascript have finite size, and so you'd have to watch closely to make sure the ant doesn't run off the edge of the array and then resize it... ugh.
Instead, I thought I'd just keep a list of locations that the ant has visited. Then, you can calculate the color of the ant's current location by checking how many times the ant's been there before. However, since the ant's rules are written from the perspective of which way the ant is facing ("turn left" or "turn right"), deciding whether the ant moves up, down, left, or right depends on the last two moves and also the color of the square. This is only mildly annoying to code, but I'm very lazy, so I kept trying to cut down the complexity.
Next, I thought I'd keep a list of move directions, like "uldrurdrd...". This would make calculating the next step easier. Interestingly, with this representation, you don't need to keep a list of positions at all -- all of the information about which squares the ant has visited is encoded in the sequence of moves! To know the color of the current square, count the number of times it has been visited before, which is equal to the number of prefixes of the move sequences where (number of up moves minus number of down moves) and (number of right moves minus number of left moves) are the same as these properties of the whole string. I wrote a (probably buggy) program based on this idea (see end of post).
This got me thinking, though, about the overall problem of the highway conjecture. In this representation, the highway appears as a repeating sequence of (up, down, left, right) moves. This is kind of nice, because it makes it easier to see when the ant has hit the highway; this sequence is kind of like an attractor, or something.
We now have, instead of an ant on a grid, a system for generating the next letter in a sequence. Given a list of letters, the next letter is determined by:
- The last letter
- The parity of the number of substrings with the same properties (u - d) and (r - l) as the overall letter sequence
This system could be generalized in a variety of ways. Using e.g. modulo 3 or 4 instead of parity would add more colors, and it's interesting to me that we could use properties other than (u - d) and (r - l) -- for example, ratios or more complex expressions.
I'm not sure, but I feel like this is incremental progress toward solving the conjecture, which makes the whole thing feel worthwhile :) If I can make more progress, you'll hear about it in a future post.
A final note: Langton's Ant is reversible, so theorems that hold into the future also hold into the past. For example, not only will the ant get arbitrarily far away from its starting point (see wikipedia), it also came from arbitrarily far away if you assume it's been running forever. If the highway conjecture is correct, ants not only eventually build highways, they came from highways, unwinding them from the infinite distance until they got to their starting point! That's kind of neat.
⁂
The program:
function move(ms) {
possible = ({u:"lr", d:"rl", l:"du", r:"ud", "":"ud"})[ms.slice(-1)];
x = ms.split("r").length - ms.split("l").length;
y = ms.split("u").length - ms.split("d").length;
console.debug(x+", "+y);
color = 0;
ms.split("").forEach(function (c) {
x = x - (c=="r"?1:c=="l"?-1:0);
y = y - (c=="u"?1:c=="d"?-1:0);
if (x == 0 && y == 0) color = -color+1; // wrong here to include last character? Does this just invert?
});
return ms + possible.charAt(color);
}
No comments:
Post a Comment