Talk:Lake

Counting lakes

Re: lake-counting. An explicit formula seems reasonably doable, doesn't it? Adding 8 cells to a lake allows you to lengthen a pair of sides. Let's call the shape with one pair of sides having minimal length (and the other thus maximal) the basic shape. Then, you get a slightly longer basic shape, and from that you can modify the figure by shortening the long side/lengthening the short one to get all the other "straight-side" shapes. That's pretty trivial, and then, it's a matter of figuring out what you can do with the corners given those shapes. I'd guess that the number of corner-changing actions you can do is a function of the length of the shorter side and probably independent of the length of the longer one, which makes it easier. Of course, you might think that with my confident conjecturing and a decent amount of data to check theory against, I'd just go ahead and try to do this myself, but maybe later... Elithrion 03:04, 5 February 2009 (UTC)

I tried basically exactly what you said, but it became insane very quickly. The number of interactions between which corners you can and can't "bend in" seems to be much too complicated to get a hold on. Also, one problem with just considering the "convex" lakes and distorting them is that you can never get "loopy" lakes (which can only exist for large n). By "loopy" I mean like if you were to put a 2D sausage around a spiral and use its border as a lake. Feel free to try though, you've got some data to compare your results with now at least. Nathaniel 03:24, 5 February 2009 (UTC)

Oh, hmm... yeah, I see what you mean. At least about "loopy" - not seeing the problems with corners as easily. Well, I'm sure I'll semi-consciously puzzle over the matter for a while longer (a new plan that centres around just possible configurations of pieces is already beginning to emerge and will probably soon be beginning to be shot down), and see how that goes. Elithrion 04:05, 5 February 2009 (UTC)

Okay, I have succeeded... in rephrasing the problem in a way that makes its nature clearer and my confidence in ever seeing a solution much much lower. What we're trying to count is the number of SAWs with three rules: they reach the origin at the last step, each step must be orthogonal to the one before, there is a total of [cells]/2 steps. I'm not even sure if this is easier than the boxed SAWs problem we have... on hold. On the bright side, some easy upper bounds are available! The most basic one is obviously just 2^k (k = [number of steps of the walk] = 4*n = [number of cells]/2)... and I'm a little alarmed by the amount of difficulty I'm having improving on that. Well, it can't be more than (3/4)*(2^k), since if you walk at random, 1/4 of the time you'll end up immediately making a loop (e.g. walking down and then right after by chance walking up and then left). This doesn't hold for k=4, of course. Similar reductions could be made for larger loops, but this would still leave us orders of magnitude off. So, I've got no other good ideas for now. Elithrion 05:54, 5 February 2009 (UTC)

Oh, umm, woops. Obvious reductions by a factor of k for arbitrary starting point, by 4 for rotations and by 2 for reflections (for large k). So, 3/k*2^(k-5), perhaps? Although the results from that seem much too low, but that may be because my "for large k" assumption is highly relevant. Or I may have messed up! Also, apparently it's a "self-avoiding polygon" (SAP). Elithrion 06:31, 5 February 2009 (UTC)

Never mind, once I remembered k=4n, the results became as way-too-high as they should be. It's a bit late. Elithrion 07:38, 5 February 2009 (UTC)

Yeah, that restatement you gave is exactly how my program computes it, actually (I basically re-used my code from the maximal SAW program with slight modifications). The "simplifications" that my program uses to make it compute faster are: a) All lakes have to have a "right, up, right, down, right" section somewhere (except for the pond), so my program just assumes you start there (this seems to be essentially the simplification you're doing as well), and 2) If you're currently more than 2*n-(stepNumber) steps either horizontally or vertically away from the origin, then you can't get back so you might as well just abandon the current lake now. That second simplification might be difficult to turn into a numerical thing, but who knows. Nathaniel 12:22, 5 February 2009 (UTC)