Here I have my lame implementation of a grid search pattern sequence generator. I hate it because it avoids repeating only by remembering and checking that it hasn't yielded a cell's coordinate before. I feel like there should be an elegant iteration that is guaranteed to hit every cell in the search grid exactly once, emanating from the origin, without resorting to this memory and performance hit. Cells should be visited in a roughly closest-to-origin-first order. So the magnitude of the vector should generally be increasing.
I figure such an algorithm/sequence exists and has a name, but I don't know it. Do you? It seems like it will be useful in local searches in Constraint Satisfaction Problems over integers.
function *spiralWalk(dimensions : number) : Generator<number[]> {
function *spiralWalk_(dimensions : number, digits : number) : Generator<number[]> {
if (dimensions === 0) {
yield [ ];
} else {
for (let digit = 0; digit < digits; digit++) {
for (let subwalk of spiralWalk_(dimensions - 1, digits)) {
let sym = digit % 2 === 0 ? digit / 2 : -Math.floor(digit / 2)
yield [ sym, ...subwalk ];
}
}
}
}
// This `seen_it_before` mechanism is the performance killer to be removed
let seen_it_before : { [key : string] : boolean } = {};
for (let digits = 2; true; digits++) {
for (let candidate of spiralWalk_(dimensions, digits)) {
let key = candidate.toString();
if (!seen_it_before[key]) {
seen_it_before[key] = true;
yield candidate;
}
}
}
}
for (let x of spiralWalk(4).take(100)) {
console.log(x);
}
For N dimensions, I'm exhausting all the combinations in Base-2. Then I go to Base-3 and exhaustively list those. Then Base-4, .... Always sticking with the same number of "digits" or dimensions in my variably-based number representation. Each time we go to the next Base up, we will see a lot of repeats in the combinations of distinct symbols, and that must be avoided, so I remember them and skip them if I've seen them before.
The line let sym = digit % 2 === 0 ? digit / 2 : -Math.floor(digit / 2)
simply remaps the distinct "symbols" abstraction to the sequence 0, 1, -1, 2, -2, 3, -3, ...
to be more useful as offsets centered around 0.
spiralWalk(2)
gives this sequence:
[0, 0]
[0, 1]
[1, 0]
[1, 1]
[0, -1]
[1, -1]
[-1, 0]
[-1, 1]
[-1, -1]
[0, 2]
[1, 2]
[-1, 2]
[2, 0]
[2, 1]
[2, -1]
[2, 2]
[0, -2]
[1, -2]
[-1, -2]
[2, -2]
[-2, 0]
[-2, 1]
[-2, -1]
[-2, 2]
[-2, -2]
[0, 3]
[1, 3]
[-1, 3]
Here's an improvement that doesn't have that lookup. For any number of digits after 2
make sure at least one of the digits is the top digit, or else it would have been seen before.
function *spiralWalk(dimensions : number) : Generator<number[]> {
function *spiralWalk_(dimensions : number, digits : number) : Generator<number[]> {
if (dimensions === 0) {
yield [ ];
} else {
for (let digit = 0; digit < digits; digit++) {
for (let subwalk of spiralWalk_(dimensions - 1, digits)) {
yield [ digit, ...subwalk ];
}
}
}
}
for (let digits = 2; true; digits++) {
for (let candidate of spiralWalk_(dimensions, digits)) {
if (digits < 2 || candidate.some(d => d === digits - 1)) {
yield candidate.map(digit => digit % 2 === 0 ? -digit / 2 : Math.ceil(digit / 2));
}
}
}
}
for (let x of spiralWalk(4).take(100)) {
console.log(x);
}