grambulate-rust

An implementation of grambulation in Rust, as initially explained on Reddit and more precisely defined for Code Golf.

Speed

The approach described below may seem confusing, but it avoids any loops that change with the inputs; the only loops in my code iterate only over the 4 types of Diagonal.

This allows very low execution time regardless of input; results from a rough test on my computer:

value_a	value_b	time per iteration, average of 100'000'000
1	2	529ns
10	25	395ns
100000	2500000	601ns
100000000000000	2500000000000000	364ns

These were just the first numbers I chose and this is in no way a proper test, but it'll do for an impression.

Implementation

If the MathJax doesn't render, try viewing the README on GitHub.

To grambulate two numbers $a$ and $b$ to a solution $c$, we must find the coordinates $c'$ of the solution, for which we must first determine the coordinates of $a$ and $b$ ($a'$ and $b'$) on the spiral.

To do so, we can calculate the 'rings' $r_a$ and $r_b$ the numbers are in with the formula $$r(x)=\left\lfloor{\frac{\left\lceil{\sqrt{x}}\right\rceil}{2}}\right\rfloor$$ Then, the formula $$v_d(r)=4r^2-(5-d)\cdot{}r+1$$ can be used to to calculate the four values on the four main diagonals for ring $x$, where $d$ specifies which diagonal to use. To do this, we specify the number on a given diagonal in ring 1 as $d$:

Diagonal	$d$
top-right	3
top-left	5
bottom-left	7
bottom-right	9

This gives us 4 values near our desired value (either $a$ or $b$). If we find the value closest to but larger than or equal to our target value, we can calculate the difference and apply it as either an x or y offset, giving us the coordinates of our desired value.

Now that we have both pairs of coordinates, we can calculate the connecting vector $\vec{v}$ and apply to it to $b'$ to find $c'$.

Once we know $c'$, we know that the ring is the larger of the absolute x and y values.

We now determine which diagonal we need to calculate, retrieve the value using the above formula and subtract the difference of the relevant coordinate.

Example

Let $a=5$ and $b=11$.

We can use the ring formula to determine $r_a=1$ and $r_b=2$.

Starting with $a$, we can calculate the 4 diagonal values on ring $r_a$:
$v_3=3$
$v_5=5$
$v_7=7$
$v_9=9$

The closest of these values that is $\le{}a$ is $v_5=5$. The coordinates of that value are $v_5'=(-1\cdot{}r_a~|+1\cdot{}r_a) = (-1~|~1)$. As $v_5=a$, we don't need any further offsets.

Moving on to $b$:
$v_3=13$
$v_5=17$
$v_7=21$
$v_9=25$

The closest of these values that is $\le{}b$ is $v_3=13$. The coordinates of that value are $v_3'=(+1\cdot{}r_b~|+1\cdot{}r_b)=(2~|~2)$. As $v_3\neq{}b$, we still need to do more.

As we determined the closest value ahead of $b$ to be the top-right diagonal, we need to decrease the y coordinate of $v_3'$ by $v_3-b=13-11=2$. That leaves us with:

$$\vec{c'}=\vec{v_3'}-\begin{pmatrix}0\\2\end{pmatrix}=\begin{pmatrix}2-0\\2-2\end{pmatrix}=\begin{pmatrix}2\\0\end{pmatrix}$$

Now we know:

$$a'=(-1~|~1)\hspace{2cm}b'=(2~|~0)$$

The connecting vector is

$$\vec{v}=\vec{b'}-\vec{a'}=\begin{pmatrix}2-(-1)\\0-1\end{pmatrix}=\begin{pmatrix}3\\-1\end{pmatrix}$$

Applying this to $b'$ gives us the position vector of $c'$.

$$\vec{c'}=\vec{b'}+\vec{v}=\begin{pmatrix}2+3\\0+(-1)\end{pmatrix}=\begin{pmatrix}5\\-1\end{pmatrix}$$

As the value is not directly on a diagonal ($|x|\neq{}|y|$), we can use the following table to determine the diagonal ahead of our target value:

condition	diagonal
$|x|< y$	top-left
$x>|y|$	top-right
$x<-|y|$	bottom-left
$-|x|>y$	bottom-right

We need the top-left diagonal. We also know that our value is on ring $r_c=\max(|5|, |-1|)=5$. The value of the top-left diagonal at ring 5 is, using the formula above, $v_3(5)=91$. By definition, $c$ is smaller than that value. As the straight in front of the top-left diagonal is vertical and upwards, we need to subtract the difference between the y-value of 91 and the y-value of $c'$ from 91 and we should find $c$. $$c=91-((y_{91})-(y_{c'}))=91-((+1\cdot{}5)-(-1))=91-6=85$$

That's it! $5~\lozenge{}~11=85$.