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)

Not too difficult, I think. A slightly broader version that should include it is that of the the k steps, exactly k/4 must be up, k/4 down, k/4 left, k/4 right. In fact, it returns to the origin iff that statement is true, which could be good. Now what to do with it... perhaps replace the 2^k starting point with (k/2 C k/4)^2 (C being one notation for binomial)? I'm hoping I did that correctly. The idea is that you have k/2 steps in each of the orthogonal directions, and you must assign exactly half to each of the opposite directions along those, then multiply the assignments together for the total number of combinations. So, we get ((k/2)!)^2/((k/4)!)^4. The result seems to be at least two orders of magnitude smaller than using 2^k, which is nice. So I suppose my new attempt at an upper bound is 3/(k*2^5)*((k/2)!)^2/((k/4)!)^4. This gives me the sequence 0.1, 0.42, 3.12, 28.7, 297.6, 3335.06, 39437.35, 4.85*10^5, 4.85*10^6, 8*10^7. Yeah, still not good at all, and the only new tweak that comes to mind is adding in extra information on loops. Like, where I have 3/4 right now, I should have some function of k that takes into account that you aren't looping back to hit itself, which is a little complicated but plausibly doable (and if executed perfectly enough might fully account for the self-avoidance). Elithrion 17:20, 5 February 2009 (UTC)

Okay, I don't exactly have an answer, but I think I have enough of an approach to it to write it down. Let's throw away the 3/4 first, so that leaves us with 1/(k*2^3)*((k/2)!)^2/((k/4)!)^4 walks that start and end at the origin, and that are different under rotation/reflection/translation. Now, the last important condition is self-avoidance. This can be rephrased for this case as "they don't contain any of the walks with a lower number of steps", since those include all possible loops that can be made. That's basically the approach, following is a possibly not well-reasoned attempt to implement it. So, let's say there are S_k walks with k steps, then this line of reasoning leads to something like S_k = 1/k*2^3*((k/2)!)^2/((k/4)!)^4 - sum(S_i*(((k-i)/2)!)^2/(((k-i)/4)!)^4),i=1..k). Or something like that. Anyway, basically, taking all the previous walks, attaching little bits of to them (well, k-i length bits, where i is the length of the previous walk) and removing those walks from consideration. One problem is that the k-i length bits can themselves form more loops, which could lead to a lot of double-counting. Maybe more recursion could solve the issue. To be continued some time, probably. Elithrion 03:35, 6 February 2009 (UTC)

This really should be moved to the forums probably, or at least summarized and continued there ;). More friendly on my eyes, and also other people are more likely to join in if/when they find the site after I advertise it (after it's more done-ish). Nathaniel 03:44, 6 February 2009 (UTC)

Fair enough. I even did my best to add a bit of organisation/legibility to my ramblings there. On the other hand, typing easily readable formulae is made no easier (well, barring making images and linking them or something). Elithrion 04:49, 6 February 2009 (UTC)

I say that we start with the top left corner of a lake and follow it clockwise. A right turn signifies a 1, and a left turn signifies a 0. The 32-cell lake could be 1011010110110101 or 1010110110101101. Now convert to decimal. The 32-cell lake could be lake 46517 or lake 44461. Why this works is because a number can only make one lake, even though a lake can have more than one number. -wwei23 12:18PM 6/25/2017 NY time

The new 40-cell lake

Does this count? It is made of dominoes and you can trace a path that goes through all the dominoes, so therefore it is a closed loop. Right?

░▓▓░░░░▓▓░
▓░░▓░░▓░░▓
▓░░▓░░▓░░▓
░▓▓░▓▓░▓▓░
░░░▓░░▓░░░
░░░▓░░▓░░░
░▓▓░▓▓░▓▓░
▓░░▓░░▓░░▓
▓░░▓░░▓░░▓
░▓▓░░░░▓▓░

-wwei23 12:26PM 6/25/2017 NY time

Probably not since it isn't completely open on the inside, although you could possibly count it as some form of degenerate lake. - AwesoMan3000 (talk) 16:55, 25 June 2017 (UTC)