Progressive loop through pairs of increasing integers

Question

Suppose one wanted to search for pairs of integers x and y a that satisfy some equation, such as (off the top of my head) 7 x^2 + x y - 3 y^2 = 5

(I know there are quite efficient methods for finding integer solutions to quadratics like that; but this is irrelevant for the purpose of the present question.)

The obvious approach is to use a simple double loop "for x = -max to max; for y = -max to max { blah}" But to allow the search to be stopped and resumed, a more convenient approach, picturing the possible integers of x and y as a square lattice of points in the plane, is to work round a "square spiral" outward from the origin, starting and stopping at (say) the top right corner.

So basically, I am asking for a simple and sound "pseudo-code" for the loops to start and stop this process at points (m, m) and (n, n) respectively.

For extra kudos, if the reader is inclined, I suggest also providing the loops if one of x can be assumed non-negative, or if both can be assumed non-negative. This is probably somewhat easier, especially the second.

I could whump this up myself without much difficulty, but am interested in seeing neat ideas of others.

This would make quite a good "constructive" interview challenge for those dreaded interviewers who like to torture candidates with white boards ;-)

If you already have a solution to this, then this is not an "actual problem that you face" (see the FAQ). If you'd like a critique of your solution, a better forum would be http://codereview.stackexchange.com. — Oliver Charlesworth, Jun 23 '12 at 20:43
@OliCharlesworth [It's ok to ask questions you already know an answer to](http://meta.stackexchange.com/questions/2706/posting-and-answering-questions-you-have-already-found-the-answer-to). There's even a [badge](http://stackoverflow.com/badges/14/self-learner) that rewards answering your own questions. — JJJ, Jun 23 '12 at 20:56
@Juhana: True. But this seems to be a "let's compare solutions!" scenario, which is not really appropriate. At any rate, it's easy to find duplicates of this question (i.e. iterating over a 2D array in spiral fashion), e.g. http://stackoverflow.com/questions/945265/2d-array-in-spiral-order or http://stackoverflow.com/questions/8979214/iterate-over-2d-array-in-an-expanding-circular-spiral. — Oliver Charlesworth, Jun 23 '12 at 20:57
@Juhana: I was expecting that kind of comment to be on an actual self-answer, not a question that isn't even a question. There is a difference between our self-answer format, and what Oli is talking about. — BoltClock, Jun 23 '12 at 21:11

score 0 · Answer 1 · answered Jun 23 '12 at 20:51

def enumerateIntegerPairs(fromRadius, toRadius):
    for radius in range(fromRadius, toRadius + 1):
        if radius == 0: yield (0, 0)
        for x in range(-radius, radius): yield (x, radius)
        for y in range(-radius, radius): yield (radius, -y)
        for x in range(-radius, radius): yield (-x, -radius)
        for y in range(-radius, radius): yield (-radius, y)

score 0 · Answer 2 · answered Jun 23 '12 at 21:22

Here is a straightforward implementation (also on ideone):

void turn(int *dr, int *dc) {
    int tmp = *dc;
    *dc = -*dr;
    *dr = tmp;
}
int main(void) {
    int N = 3;
    int r = 0, c = 0;
    int sz = 0;
    int dr = 1, dc = 0, cnt = 0;
    while (r != N+1 && c != N+1) {
        printf("%d %d\n", r, c);
        if (cnt == sz) {
            turn(&dr, &dc);
            cnt = 0;
            if (dr == 0 && dc == -1) {
                r++;
                c++;
                sz += 2;
            }
        }
        cnt++;
        r += dr;
        c += dc;
    }
    return 0;
}

The key in the implementation is the turn function, that performs the right turn given a pair of {delta-Row, delta-Col}. The rest is straightforward arithmetic.

Progressive loop through pairs of increasing integers

2 Answers2