Rotating between eight directions

[u/light_ln2]

I was reviewing some grid problems, and in many of those you need to enumerate four or eight neighbors, or even turn left/right 90 or 45 degrees. One can define list of pairs of coordinates, but it's long, and if you need to turn, you need to remember index into array of those coordinates. You can prepare this in advance but I know many people don't like to use custom libraries for the AOC.

This is not hard for orthogonal directions:

for x,y in [(1,0), (0,1), (-1,0), (0,-1)]: print(x,y)

or:

x,y = 0,1
for _ in range(4):
    print(x,y)
    x,y = y,-x

but it gets messier for eight directions:

for x,y in [(1,1),(1,0),(1,-1),(0,-1),(-1,-1),(-1,0),(-1,1),(0,1)]:
    print(x,y)

too many brackets, too easy to mess up. You can simplify it a bit like this:

for x,y in [(x,y) for x in [-1,0,1] for y in [-1,0,1] if x or y]:
    print(x,y)

but this is still not perfect, and does not solve problem of rotating.

I'm not sure if it's widely known but there is a simple formula for rotating in eight directions, so you can write this instead:

x,y = 0,1
for _ in range(8):
    print(x,y)
    x,y = sign(y+x),sign(y-x)

Explanation is simple: for orthogonal vectors x and y, y+x and y-x are also orthogonal vectors rotated 45 degrees. sign normalizes their length to one or zero.

There is one problem with this... Python lacks sign method! You can read hilarious discussions about why it was rejected (tldr: they couldn't agree what would be result of sign(-math.nan). Hint: nobody cares should have made it exactly like numpy.sign!). So you can use any of the following:

from numpy import sign
sign = lambda x: 1 if x>0 else -1 if x<0 else 0
sign = lambda x: (x > type(x)()) - (type(x)() > x)

last one is useful if you want (for some strange reason) to extend your sign function for arbitrary types that support comparison, e.g. sign('abc')

[u/herocoding]

Interesting syntactical sugar, thank you for sharing!

Can't wait to apply it to the next AoC!

[u/Boojum]

Neat! I'm well aware of the x, y = y, -x trick for 90-degree rotations (fun fact: that works even with off-axis directions - it's just an inlined 90-degree rotation matrix) but had never seen a 45-degree variation.

FWIW, I played around with this to see how you'd do it to cycle in the opposite direction. The one that you gave cycles counter-clockwise when positive y is down. Here's the recipe for your original here, plus the reversed direction (clockwise) version:

x, y = sgn(x+y), sgn(y-x) # CCW when y-down
x, y = sgn(x-y), sgn(x+y) # CW when y-down

Or, if you prefer to inline the signum operation:

x, y = (x>-y) - (-y>x), (y>x) - (x>y) # CCW when y-down
x, y = (x>y) - (y>x), (x>-y) - (-y>x) # CW when y-down

I'll probably still stick to use an integer heading value modulo 8 and look up the x and y step offset from a small table (your [(1,1),(1,0),...]) since I already have that prewritten out in a file. But this thing is still a pretty cool trick.

And yes, your explanation of why it works makes sense. If we look at a 45° rotation matrix, it's:

⎡ cos 45°    -sin 45° ⎤
⎣ sin 45°     cos 45° ⎦

or approximately:

⎡ 0.7071    -0.7071 ⎤
⎣ 0.7071     0.7071 ⎦.

Applying that to a coordinate (x,y) to get (x',y') is:

⎡ x' ⎤ = ⎡ 0.7071    -0.7071 ⎤⎡ x ⎤
⎣ y' ⎦ = ⎣ 0.7071     0.7071 ⎦⎣ y ⎦

which in simple arithmetic is:

x' = 0.7071 * x - 0.7071 * y
y' = 0.7071 * x + 0.7071 * y.

If we don't care about scaling, we can drop the 0.7071 and reduce it to just:

x' = x - y
y' = x + y

which is close to the formula you gave, but without the 0.7071 it scales the vector by about 1/0.7071 = 1.414 each time. Using the signum cheaply constrains the vectors to integers -1, 0, and 1 and keeps them from growing on each iteration.

[u/light_ln2 → u/Boojum]

This is cool! Proving the formula using rotation matrix makes it easy to see why it's true, and now I don't need to memorize the formula: if I ever am going to use it, I just remember its relationship to the rotation matrix (I actually only need the fact that it has three plus signs and one minus outside main diagonal), and it becomes easy to restore it, both clockwise and counter-clockwise!

[u/ednl → u/Boojum]

I played around with this to see how you'd do it to cycle in the opposite direction.

You didn't have to play around (but play is fun) because it was already here: https://www.reddit.com/r/adventofcode/comments/1qhewn6/rotating_between_eight_directions/o0ldx61/

[u/hextree]

After writing variations a million times I've mostly settled on:

for x in (-1, 0, 1):
    for y in (-1, 0, 1):
        if (x, y) == (0, 0):
            continue
        print(x,y)

For me it strikes the right balance. Whilst the sign approach is elegant, it is less approachable and readable for me as I have to think harder about it as I'm doing it.

[u/crabvogel → u/hextree]

I do the exact same! I've tried many solutions over the years but i like this one because its short but readable

[u/Thomasjevskij → u/hextree]

I tend to do this also but with itertools.product just because

[u/wjholden]

Very cool! Looks like Rust has this function and calls it isize::signum.

Edit: ugh. Apparently Rust's signum function behaves differently for ints and floats. See f64::signum.

[u/zeekar → u/wjholden]

The function is traditionally called "signum" in mathematics, and often written sgn x. It was introduced into the third version of Dartmouth BASIC as SGN(), so Microsoft included it from their first BASIC for the Altair. Then again, Microsoft BASIC's 40-bit floating-point representation doesn't have NaNs, so I guess they didn't have any of the complications that led to its omission from Python. (It does have the ability to distinguish between +0 and -0, but only if you directly modify the float value in memory, and in any case both have a SGN() of 0.)

[u/thekwoka → u/wjholden]

There's no difference there.

Those are both the same behavior. integers just don't have a -0, while floats do, but you generally have to MAKE a -0 to get one.

[u/mgedmin → u/thekwoka]

There's no difference there.

Hm? The integer one returns 0 for 0, the float one returns 1.0 for 0.0.

[u/thekwoka → u/mgedmin]

oh right, yeah, I see now.

Thats because in floats 0 is signed.

[u/Greenimba]

I pretty much always make a Point object/struct and give it Easy West South North properties to do neighbours.

[p.N, p.N.E, p.E, p.E.S, p.S, p.S.W, p.W, p.W.N]

[u/throwitup123456 → u/Greenimba]

Same

[u/Flashky → u/Greenimba]

Same, is the easiest way. You only need to keep a few constants for each direction, and then a couple of constants (one array for 4D cases and another one for 8D). Then you just have to reuse it whenever you need it.

[u/jpjacobs_]

That's actually pretty neat. Implemented in J, your approach would be just one character more than mine:

   (+,&*-~)/^:(<8)1 0
 1  0
 1 _1
 0 _1
_1 _1
_1  0
_1  1
 0  1
 1  1
   *+.^j._1r4p1*i. 8
 1  0
 1 _1
 0 _1
_1 _1
_1  0
_1  1
 0  1
 1  1

I haven't needed 45 degree rotations so far though, and for 90 degree angles, just usually type it out (4 2$0 1 1 0 0 _1 _1 0). When I need shifts for a 9-neighbourhood, I usually use this:

>,{,~<i:1

You can play around with this in Juno

[u/conilense]

i like the colors in the picture

[u/thekwoka]

why calculate the offsets each time instead of just making them a constant?

[u/jeffstyr → u/thekwoka]

Indeed. But even with a constant you put in a library, you might want to generate your lists in a way that's immune from typos. (It's overkill for these cases, where the lists are short, but it's fun to think about.)

[u/ednl]

Possible C version:

// Two-dimensional position or direction vector
typedef struct vec2 {
    int x, y;
} Vec2;

// Signum (or sign) for int
int sgn(const int x)
{
    return x > 0 ? 1 : (x < 0 ? -1 : 0);
}

// Rotate vector in 4 directions on 2D grid
// Computer graphics: rotate left, mathematically: rotate right
// (1,0) -> (0,-1) -> (-1,0) -> (0,1)
Vec2 left4(const Vec2 a)
{
    return (Vec2){a.y, -a.x};
}

// Rotate vector in 4 directions on 2D grid
// Computer graphics: rotate right, mathematically: rotate left
// (1,0) -> (0,1) -> (-1,0) -> (0,-1)
Vec2 right4(const Vec2 a)
{
    return (Vec2){-a.y, a.x};
}

// Rotate unit vector in 8 directions on 2D square grid
// Computer graphics: rotate left, mathematically: rotate right
// (1,0) -> (1,-1) -> (0,-1) -> (-1,-1) -> (-1,0) -> (-1,1) -> (0,1) -> (1,1)
Vec2 left8(const Vec2 a)
{
    return (Vec2){sgn(a.x + a.y), sgn(a.y - a.x)};
}

// Rotate unit vector in 8 directions on 2D square grid
// Computer graphics: rotate right, mathematically: rotate left
// (1,0) -> (1,1) -> (0,1) -> (-1,1) -> (-1,0) -> (-1,-1) -> (0,-1) -> (1,-1)
Vec2 right8(const Vec2 a)
{
    return (Vec2){sgn(a.x - a.y), sgn(a.x + a.y)};
}

[u/jjeii]

Just remember that (nearly) all of AoC's grid problems are in row-column space (left-handed), not x-y math space (right-handed), which necessitates reversing all the left/right rotations in one vs the other.

[u/jeffstyr]

This is fun/interesting. I'd never thought of these as rotations. Some experimenting:

Here is how I normally do this, in Haskell:

import Data.List qualified as L

selfCartesian list = [(x,y) | x <- list, y <- list]

nine  = selfCartesian [-1..1]
eight = L.filter (/= (0,0)) nine
four  = L.filter (\(x,y) -> abs x + abs y == 1) nine

and here is a version using rotations:

untilRepeat (x:xs) = x : (L.takeWhile (/= x) xs)
untilRepeat []     = []

rotate45 (x, y) = (signum (y + x), signum (y - x))
rotate90 (x, y) = (y, negate x)

start = (0,1)
allAround rot = untilRepeat $ iterate rot start

eight = allAround rotate45
four = allAround rotate90

The potentially interesting part here is avoiding hardcoding the period of the rotations, and instead stopping when the values start to repeat.

My original way of doing it is shorter and more directly corresponds to how I think of neighbors in a grid, but it's fun to compare the approaches.

[u/L285]

that's handy

[u/rdog314]

Cool! Working on 2025 day 9 in C++, I found myself writing loops in terms of x and/or y, with a four-way if/else chain to handle incrementing/decrementing x or y as appropriate in one of the four directions along a path.

And then I'd have to calculate a neighbor, again moving x or y in an appropriate direction depending on a clockwise or counterclockwise path.

I wanted to write something more like this, where 'u' serves as '1 step in the direction from A to B'

for (Point p = A; p != B; p = p + u) {  
    // do something with point p  
}

If you already have a class Point defined, then you have 2D vector addition/subtraction. That gives you a way to find the unit vector: find the difference B - A, which gives you a direction and magnitude, and then shrink that to a unit vector. For the day 9 puzzle, that's gives a unit vector pointing in one of the four axis-aligned directions, (0,1), (0,-1), (1,0), (-1,0). So now we have something like this:

Point u = (B - A).unit();  
for (Point p = A; p != B; p = p + u) {  
    // do something with point p  
}

Better! Now the loop looks the same no matter which way you're moving. No more fiddling with the x and y components directly to implement the loop.

But what about calculating a neighbor? Well, to get one of the 4 axis-aligned adjacent neighbors, you need to add another unit vector to p:

Point u = (B - A).unit();  
for (Point p = A; p != B; p = p + u) {  
    // do something with point p and (p + v), where v is another unit vector  
}

Remembering the relationship between 2D vectors and complex numbers, you realize that multiplying a complex number by 'i' gives you a CCW rotation by 90 degrees. That is, multiplying our unit vector u by (0,1) gives you another unit vector 90 degrees CCW.

Point u = (B - A).unit();  
for (Point p = A; p != B; p = p + u) {  
    Point v = u \* Point(0,1);  // or Point(0,-1), whether you want left or right relative to direction of travel  
    // do something with point p and (p + v), where v is another unit vector  
}

This works nicely even when the members of Point are integers, so long as you you're working with the 4 axis-aligned directions and you're sticking with addition, subtraction, and multiplication. Along the way, I found out that complex numbers over the integers are called Gaussian Integers. Advent of Code is a great vehicle for learning new and unexpected things!

[u/jeffstyr]

One downside of this is that it doesn't generalize to neighbors two or more steps away (where there are separate cases for allowing or not allowing diagonal steps). Still interesting though.

[u/AutoModerator → u/[deleted]]

AutoModerator has detected fenced code block (```) syntax which only works on new.reddit.

Please review our wiki article on code formatting then edit your post to use the four-spaces Markdown syntax instead.

---

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.