Determining board size

[hvds]

Hi Tom, thanks for providing a link to the code.

It isn't clear to me how you are determining the board size for n > 2. Since you are hard-coding it, I guess you need to take the maximum extent reached by any board for the previous n, and add 4 (2 in each direction). But I suspect that only works up to n=4; beyond that you could for example have a new configuration with two 1s in one spot to provide a location for the 2, and three 1s in a completely different spot to provide a location for the 3. I don't see an easy way to put a limit on how far apart those two groupings can be from each other.

Separately from that, it would be worth instrumenting the code to see how much find_symmetries is gaining you at each stage - I suspect after 2 and 3 are placed it will hardly ever find further symmetries, and it's a hugely expensive function, so you could probably gain a good chunk of speed by avoiding it beyond that stage.

[ladouce7]

Yes I agree finding the board size would be difficult, for the lower numbers I have just been making it larger than the previous boards, as you said. For n > 3, it would be more difficult, as for 4 it could be two groups of two 1s that come together, so it has to be larger than the largest board of two multiplied by two, at the maximum. Similarly higher board would need have a finite limit where the ones can be placed. I have just been making them arbitrarily large, which does waste a lot of time. I will also change the findsymmetry function as you suggested, it was very helpful in speeding up n=2 and 3, but would probably be improved. I feel like even with these changes n=5 will take an extremely long time. n=2 took a few seconds, n=3 took a few minutes, and n=4 took a few days.

On Oct 7, 2020 at 10:53 PM, <Hugo van der Sandenmailto:notifications@github.com> wrote:

Hi Tom, thanks for providing a link to the code.

It isn't clear to me how you are determining the board size for n > 2. Since you are hard-coding it, I guess you need to take the maximum extent reached by any board for the previous n, and add 4 (2 in each direction). But I suspect that only works up to n=4; beyond that you could for example have a new configuration with two 1s in one spot to provide a location for the 2, and three 1s in a completely different spot to provide a location for the 3. I don't see an easy way to put a limit on how far apart those two groupings can be from each other.

Separately from that, it would be worth instrumenting the code to see how much find_symmetries is gaining you at each stage - I suspect after 2 and 3 are placed it will hardly ever find further symmetries, and it's a hugely expensive function, so you could probably gain a good chunk of speed by avoiding it beyond that stage.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHubhttps://urldefense.com/v3/__https://github.com/ladouce7/Stepping-Stones/issues/1__;!!HXCxUKc!gOknH5jS8XJXuUN9hHcGO64GYJOetETgw6YTovHlDDYBJeNYpUWZ672cdmqEiDb-$, or unsubscribehttps://urldefense.com/v3/__https://github.com/notifications/unsubscribe-auth/AOHPPPBSXECQN6XRHQ3XP63SJUSTNANCNFSM4SIFM6OQ__;!!HXCxUKc!gOknH5jS8XJXuUN9hHcGO64GYJOetETgw6YTovHlDDYBJeNYpUWZ672cdjyTUTsG$.

[hvds]

for 4 it could be two groups of two 1s that come together

Well no, since only one of those can have the 2, and then the 3 must be adjacent to at least one of those two 1s and the 2. So the third and fourth 1 can only come into play by being close enough to a board state that was also reachable with n = 2 or n = 3 respectively.

I feel like even with these changes n=5 will take an extremely long time. n=2 took a few seconds, n=3 took a few minutes, and n=4 took a few days

With algorithmic improvements and further optimization that should come down a lot - I think 4 should be doable in seconds or minutes.

For n > 4, I think you'd need a rather more complex algorithm: allow for multiple clusters, effectively on separate boards, and at each step consider every way those clusters could be placed with respect to each other that is consistent with previous information - ie not placing so that two numbers > 1 from different clusters are adjacent to each other. That feels hard but possible with two clusters, and a total pain for more than two (but at that point you're dealing with n >= 9).