# Rotate y-axis of a 2D vector

> Reverse rotate a 2D vector by shifting columns up or down.

January 5, 2023 · 7 min read · https://yasint.dev/rotate-y-axis-of-a-2d-vector/
Tags: math, vectors

---

So you want to rotate a vector, huh?

The solution I'm going to describe works well with both **two-dimensional** and **multidimensional** vectors if applied correctly. It is originally based on [John Bentley's Reverse Rotate algorithm](https://www.yasint.dev/vector-rotation) but with a _teeny tiny twist_. So, if you want to understand how this algorithm works, you have to read that article first.

All I did was invert the indices for `left`, `up` and `right`, `down` shift operations to achieve complement sub-vectors $A'$ and $B'$. This makes the algorithm **more efficient and agile** for dynamic programming.

```go
type Direction byte

const (
	up    Direction = iota
	right Direction = iota
	down  Direction = iota
	left  Direction = iota
)

func reverse[T any](x *[]T, i, j int) {
	for i < j {
		(*x)[i], (*x)[j] = (*x)[j], (*x)[i]
		i++
		j--
	}
}

func reverseRotate[T any](x *[]T, delta int, direction Direction) {
    if delta == len(*x) {
		return
	}
	switch direction {
	case left, up:
		reverse(x, 0, delta-1)
		reverse(x, delta, len(*x)-1)
	case right, down:
		reverse(x, len(*x)-delta, len(*x)-1)
		reverse(x, 0, len(*x)-delta-1)
	}
	reverse(x, 0, len(*x)-1)
}
```

Note that I have utilized generics in both functions to accept different types. `[T any]` allows multiple types as the argument (you may change this to any concrete type you desire). Additionally, we use an enumeration called `Direction` to improve the clarity of the code.

## Shift up

Suppose you want to shift up all the 2D vector columns by `1`.

![Shift up operation on 2D vector](./up-shift.png)

```go
a := [][]int{
	{2, 3, 4, 5},
	{9, 8, 7, 6},
	{5, 4, 2, 3},
	{8, 7, 3, 4},
}
reverseRotate(&a, 1, up)

// =>
// [9 8 7 6]
// [5 4 2 3]
// [8 7 3 4]
// [2 3 4 5]
```
## Shift down

Suppose you want to shift down all the 2D vector columns by `1`.

![Shift down operation on 2D vector](./down-shift.png)

```go
a := [][]int{
	{2, 3, 4, 5},
	{9, 8, 7, 6},
	{5, 4, 2, 3},
	{8, 7, 3, 4},
}
reverseRotate(&a, 1, down)

// =>
// [8 7 3 4]
// [2 3 4 5]
// [9 8 7 6]
// [5 4 2 3]
```

## Y-axis column rotation

If you want to rotate specific columns with __variable__ shifts. We need a bit more than `reverseRotate`. In such a case, the problem is a bit hard because when we think of it as columns, each element index is located in a different array. I devised a 3-step solution, which works for me right now (I want to keep it super simple).

> **Not the Optimal Way** — You're advised to think through and use it because it's not the optimal way to do it. Libraries like `NumPy` have clever optimizations for functions such as [transpose, rot90, flip, etc](https://github.com/numpy/numpy/blob/v1.24.0/numpy/lib/function_base.py). But in our problem, we intend to rotate each column. If you find a more efficient solution, let me know as well, haha.

For example, let's say we have a `3 x 3` matrix.

![3x3 matrix example](./matrix-3x3.png)

Here, the challenge is to shift columns `2` and `3` up by 1 and 2 consecutively instead of rotating the entire facet. Let's take a more complex input to understand how we can do it.

Suppose you have a `6 x 6` matrix.

![6x6 matrix example](./matrix-6x6.png)

And then, each column of the matrix has to be shifted up a variable amount of `n`.

![6x6 matrix with variable shifts](./matrix-6x6-shifts.png)

We could do this in three easy steps. First, copying the target column to a temporary vector, then rotating it using `reverseRotate`, and finally reassigning the values for the source vector. However, this takes $O(n^2)$ time and uses $O(m)$ space to hold the temporary vector while iterating each column.

![Three steps to rotate columns](./three-steps.png)

Here's the code for it: -

```go
func rotate2D[T any](x *[][]T, deltas []int, dir Direction) error {

	// the length of the changes must be exact.
	// if it's 6x6 then: deltas = {?, ?, ?, ?, ?, ?}
	if len(deltas) != len(*x) {
		return errors.New("columns are not equal")
	}

	// if every element in the deltas array is equal
	// then no point of rotating each column one by one.
	if EveryElementEquals(&deltas, &deltas[0]) {
		reverseRotate(x, len(deltas), dir)
		return nil
	}

	// try to reduce the column shifts.
	ReduceShifts(x, &deltas, dir)

	for ci, cn := range deltas {

		// if there's no rotations to be done
		// then, simply skip this column.
		if cn <= 0 {
			continue
		}

		// Extract the column elements.
		var col []T
		for _, row := range *x {
			col = append(col, row[ci])
		}

		// rotate the temporary column.
		reverseRotate(&col, cn, dir)

		// reassign the elements to correct
		// indices after shifting.
		for si, s := range col {
			(*x)[si][ci] = s
		}

	}

	return nil

}

func ReduceShifts[T any](x *[][]T, deltas *[]int, dir Direction) {

	// find the minimum delta value
	min := FindMinDelta(deltas)
	if min <= 0 {
		return
	}

	// do a minimum rotation
	reverseRotate(x, min, dir)

	// reduce the shifts by min value
	for i := range *deltas {
		if (*deltas)[i] == min {
			(*deltas)[i] = 0
		} else {
			(*deltas)[i] = (*deltas)[i] - min
		}
	}

}

func EveryElementEquals(a *[]int, x *int) bool {
	for i := 1; i < len(*a); i++ {
		if (*a)[i] != *x {
			return false
		}
	}
	return true
}

func FindMinDelta(x *[]int) int {
	smallest := (*x)[0]
	for _, num := range (*x)[1:] {
		if num < smallest {
			smallest = num
		}
	}
	return smallest
}
```

Also, note that `ReduceShifts` is a small optimization I've implemented for the algorithm. For example, if we receive the delta array `[ 4,5,6,6,4,3 ]`, we can find the minimum `delta` and rotate the entire facet $n$ times. Here, the minimum is $3$. So we rotate the whole facet $3$ times. Once rotated, we can reduce the shifts of each delta by the minimum rotations we did, and we are left with new changes `[1, 2, 3, 3, 1, 0]`. Effectively reducing several iterations of the algorithm[^1].

[^1]: Note that this algorithm can be optimized even more! Suppose we get a delta array like `[ 1, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 ]` for a `12x12` matrix to _upshift_. In this case, rotating the entire facet 8 times up and _downshifting_ the first column will be cheaper. We could use a pre-computation to determine the **frequency distribution** of the changes (including the _inverted_ axis) and devise an optimal way to solve this. I'll keep digging for a better dynamic programming approach for this problem. If you find something, let me know. I'd like to know :)

How to use this function, so? Simple!

```go
m6x6 := [][]int{
	{0, 0, 0, 0, 0, 0},
	{1, 1, 1, 1, 1, 1},
	{2, 2, 2, 2, 2, 2},
	{3, 3, 3, 3, 3, 3},
	{4, 4, 4, 4, 4, 4},
	{5, 5, 5, 5, 5, 5},
}

deltas := []int{4, 5, 6, 6, 4, 3}

err := rotate2D(&m6x6, deltas, up)
if err != nil {
	panic(err)
}

// =>
// 4   5   0   0   4   3
// 5   0   1   1   5   4
// 0   1   2   2   0   5
// 1   2   3   3   1   0
// 2   3   4   4   2   1
// 3   4   5   5   3   2
```

## Bonus: shift left and right

If you want to shift in the `x-axis`, then you have to iterate through each sub-vector of the `2D` vector to achieve the outcome. For example, you could do the following: -

```go
a := [][]int{
	{2, 3, 4, 5},
	{9, 8, 7, 6},
	{5, 4, 2, 3},
	{8, 7, 3, 4},
}
for _, x := range a {
	reverseRotate(&x, 1, left)
    // reverseRotate(&x, 1, right)
}

// =>
// [3 4 5 2]
// [8 7 6 9]
// [4 2 3 5]
// [7 3 4 8]
```

Left and right shifts yields a running time of $O(n^2)$ with $O(1)$ space in-place shifting. But why run sequentially, when you can parallelize?I'll show you how to do this **efficiently** without hogging up our precious CPU in an upcoming article. **Reverse Rotate** algorithm is an absolute gem.

That's it folks!