One of my Christmas presents was the fabulous book: Getting Started with D3 by Mike Dewar.
I recommend reading it, if you haven't already! But anyway, after I had read it, I was looking for some data I could visualize. The book suggested the New York transit dataset, but I didn't want to have to clean it just to play with d3. So after a bit of thinking and doing distractive things, I remembered having read about Ulam spirals quite a while back.
The Idea
The decision was made, what was missing was the data. I wanted to refresh my knowledge about Ulam spirals,
so I loaded up Wikipedia and copied the spirals onto a whiteboard.
I gave myself the task of finding an algorithm that would generate just number spirals, given a dimension and [x, y] coordinates to return a value.
I also gave this task to my father @qmacro, so we would compete on finding an algorithm.
The source of both finished algorithms is here:
and I ran them through JSPerf here.
Finding an algorithm
My approach was, I would say, a bit clumsy. It took quite a while, until I actually got anywhere, but when I finally did something it was an analytical approach.
My idea was to just stare at the spiral for a long time until something
magically flew to my mind. And, as opposed to the expectations you may have to the outcome of this, I suddenly had an idea.
During the staring time I made some interesting observations, as can be seen in the next section.
Observations
Here is a sample 4x4 & 5x5 matrix so you can follow along:
___________________ ________________________
|16 | 15 | 14 | 13| |17 | 16 | 15 | 14 | 13|
|-----------------| |----------------------|
|5 | 4 | 3 | 12| |18 | 5 | 4 | 3 | 12|
|-----------------| |----------------------|
|6 | 1 | 2 | 11| |19 | 6 | 1 | 2 | 11|
|-----------------| |----------------------|
|7 | 8 | 9 | 10| |20 | 7 | 8 | 9 | 10|
------------------- |----------------------|
|21 | 22 | 23 | 24 | 25|
------------------------
- Number spirals are just some matrices that follow a certain pattern.
- The dimension squared is the highest value of the matrix.
- The location of the dimension squared is dependent on parity: If odd, in the bottom right, if even, in the top left, corner of the matrix.
- You can work out the numbers on the outer rim of the matrix with simple formulas.
- If you compare the two matrices, how are they different? The 5x5 matrix has one "frame" more than the 4x4 matrix.
You could imagine it just being stuck on one of the sides, if you need higher dimensions. Again the side on which the last frame was "stuck" is determined by the parity of the dimension.
(In this case onto the left-bottom side)
So from these observations you could draw some conclusions, which I did!
Conclusions
Based on the previous observations I had the thought that one could just "drop a frame" if the desired number doesn't lie within the area of that frame.
So I wrote a function that worked out if "dropping a frame" was possible.
It takes coords of the location of the number you would like to have, and the dimension of the matrix.
function check_if_drop_frame(coords, d){
if (d % 2 === 0){
if (coords[0] != d && coords[1] != 1){
return true;
} else {
return false;
}
} else if (d % 2 === 1) {
if (coords[0] != 1 && coords[1] != d){
return true;
} else {
return false;
}
}
}
In simple terms, the function checks the parity of the dimension and then checks if the coords
[x, y] lie within the last frame.
The idea is just to make the matrix smaller so, the original coords lie on the outermost frames, from which we know from the observations that they are easy values to work out.
But in order to do so, we can't simply decrement the number of dimensions and leave the coords the same, we have to translate them.
function translate(coords, d_old){
if (d_old % 2 === 0){
coords[1] -= 1;
} else if (d_old % 2 === 1) {
coords[0] -= 1;
}
return coords;
}
This function again checks the parity and from that is knows which coord it needs to decrement, either x or y. So putting those two thing together we just drop frames/dimension as long as that is possible:
while (check_if_drop_frame(coords, d)){
coords = translate(coords, d);
d -= 1;
}
Once that loop has finished, it is guaranteed that the coords describe a number on one of the outermost frames.
From there one only needs to find formulas to work out the value. Luckily I have already done that for you, they are a bit messy but they work. Wrapped in a function they look roughly like this:
function work_out_value(coords, d){
var val = -1;
var x = coords[0],
y = coords[1];
if (d % 2 === 0){
if (coords[1] === 1){
val = Math.pow(d, 2) - (coords[0] - 1)
} else if (coords[1] === d){
val = Math.pow(d, 2) - 2 * (d - 1) - (d - 2) + (x - 1) - 1
} else if (coords[0] === 1){
val = Math.pow(d, 2) - 3 * (d - 1) - (d - 2) + (y - 2)
} else if (coords[0] === d){
val = Math.pow(d, 2) - d - (y - 2)
}
} else if (d % 2 === 1){
if (coords[1] === 1){
val = Math.pow(d, 2) - 2 * (d - 1) - (x - 1)
} else if (coords[1] === d){
val = Math.pow(d, 2) - (d - 1) + (x - 1)
} else if (coords[0] === 1){
val = Math.pow(d, 2) - 2 * (d - 1) + (y - 1)
} else if (coords[0] === d){
val = Math.pow(d, 2) - 3 * (d - 1) - (y - 1)
}
}
return val;
}
Basically, the function works out which is the outermost frame and then takes the dimension squared, whose position we can foresee, and works backward towards to desired coords.
With a bit of boundary checking you can see the complete source here.
Hooking it up with d3!
After I had figured out all of this it was night time, and I wasn't really bothered with good code style at that time of day, but since I wasn't satisfied yet I hooked it up with d3, and made my own ulam spiral.
This demo generates a 2d array and then loops though each element and checks if it is a prime.
If it is it sets the fill-color to red, else just leaves it gray.
Then it just gets d3 to draw the matrix.