Monday, July 30, 2012

NCSpiral? - Initial notes

I wrote this in some spare time yesterday (i.e most of yesterday). As reference, consider an Excel spreadsheet that looks like this:



Also bear in mind that much of the code in these notes is actually wrong and/or won't do the right thing.

--

Ulam's Spiral is better looked at as a bunch of concentric squares for mathematical purposes.

Imagine that the origin point, 1, is at (x,y) where both x and y are (initially) 0. Each concentric square greater than 0 begins at (x+1, y) and ends at (x

+1, y-1). Additionally, x and y are re-initialized at the end of a square. Thus, if square 1 begins at (1, 0), then it will end at 1, -1).

Based on the representation in Excel, the squares should (and indeed do) begin and end thus:

x = 0, y = 0
Begin = (x+1, y)
End = (x+1, y-1)
s(n) = square name
for n++ : End (s(n-1)) = (x,y)

Format: square name = (Begin) (End)

s1 = (1,0) (1,-1)
s2 = (2,-1) (2, -2)
s3 = (3, -2) (3, -3)
s4 = (4, -3) (4, -4)
s5 = (5, -4) (5, -5)
s6 = (6, -5) (6, -6)

As you go out from the origin at 1, each square has progressively more slots. Let's number each concentric square starting with square 1, which contains only

the number 1. Square 2 contains up to 9. And so on like this:

square name (up to x) = amount of numbers

s1 (up to 9) = 8
s2 (up to 25) = 16
s3 (up to 49) = 24
s4 (up to 81) = 32
s5 (up to 121) = 40
s6 (up to 170) = 48

And so on.

This shows that each concentric square increases in "capacity" by 8 as you move outwards from the origin.

Indeed, using Excel to represent this makes sense, as you have a clear visual image that:

s1 = 3x3
s2 = 5x5
s3 = 7x7
s4 = 9x9
s5 = 11x11
s6 = 13x13

The area of each square is as follows:

s1 = 9
s2 = 25
s3 = 49
s4 = 81
s5 = 121
s6 = 169

But the numbers are around the "perimeter." However, note that the perimeter of a square is 2L+2W (or simply s*4 where s = side) which in each instance here

gives a higher value than the amount of numbers actually present. This is because the "corners" are occupied. Notice it is a difference of 4 for each:

square name (perimeter) = actual amount of numbers in each

s1 (12) = 8
s2 (20) = 16
s3 (28) = 24
s4 (36) = 32
s5 (44) = 40
s6 (52) = 48

This also shows how, incidentally, the perimeter of each square also increases by 8 each time. Thus, we have to imagine that square 0 (which contains only

the number 1) has a perimeter of 4, meaning each side has length 1. Never mind that this implies it holds 0 numbers. 

So, the formula we have thus far is:

s(x) = length of one side of square x
p(x) = perimeter of square x
n(x) = amount of numbers in square x

s0 = 1
s1 = 3
s2 = 5
s3 = 7
s4 = 9
s5 = 11
s6 = 13

p(x) = s(x) * 4
n(x) = p(x) - 4

>> n(x) = (s(x) * 4) - 4

The amount of numbers in one square of the spiral is equal to the value of 4 times the length of each side of the square minus 4.

--

Consider the Excel spreadsheet once again.

For our purposes here, it is best to imagine the  origin (1) to be cell BP100.  According to the formula,  this means that each new square should start at B

(+letter)(+1). See above - I explain that each square begins at (x+1, y) and ends at (x+1, y-1) where for each new square, the "End" values of x and y become

the new initial values for x and y.

In Excel terms, do we really need an ending value? If you start drawing a square with a line thickness of one cell, there's only one possible way to do it if

you want to increase in thickness by one cell each time - you increment the STARTING value.

See, imagine you are physically drawing a square. Your start point is wherever you put your pencil down. You are finished drawing the square once your pencil

returns to that point, aren't you? And wouldn't it be more efficient to start drawing a new, slightly bigger square around the first one starting from a

point, say, diagonal from the corner of the square? (hint - of course it is, especially for computers).

square name = (start)

s1 = (BQ100)
s2 = (BR101)
s3 = (BS102)
s4 = (BT103)
s5 = (BU104)
S6 = (BV105)
s7 = (BW106)

and so on and so forth...

Now then. The question here is one of how best to represent this programatically...and, indeed, using what language. VB? C? C++? VC?

Since I am more familiar with C/C++, let's try to represent it with that. By "it," I mean the function that would be best implemented to put numbers into the

boxes.

C and C++ do not have any way to represent shapes - at least, not as "shapes" on a "plane." What they do have, though, is the ability to create a

multidimensional array. This is essentially no different from a matrix. It is represented textually as a grid of numbers, and you can pick x and y co-

ordinates of each number in the array very simply.

To create a multidimensional array, we simply initialize it thus:

int SpiralArray [7][7];

This creates exactly what it looks like - an array called SpiralArray with 7 rows and 7 columns. In terms of our prime spiral, this will go up to the number

49.

There is one thing conceptually different about a multidimensional array when compared to a series of concentric squares, however - a multidimensional array

is a bunch of rows and columns (which in any other program might as well be called a table) whilst a series of concentric squares is, well, a bunch of

squares containing and being contained by each other.

Conceptually, it's a bit less meta to think of rows and columns...

So! Once the array is initialized, we can call it with any number of operators and do a bunch of stuff with whatever is in the array. Problem is, there is

nothing in the array yet.

There are two options to fill SpiralArray. One is manually, which will take a while. The other is programatically, which will take a while to WRITE, but is

MUCH more highly scalable.

Let's do it manually first, because it's actually really simple.

int SpiralArray [7][7] =
{
    {37, 36, 35, 34, 33, 32, 31},    //row 0
    {38, 17, 16, 15, 14, 13, 30 },    //row 1
    {39, 18, 5, 4, 3, 12, 29},    //row 2
    {40, 19, 6, 1, 2, 11, 28},    //row 3
    {41, 20, 7, 8, 9, 10, 27},    //row 4
    {42, 21, 22, 23, 24, 25, 26},    //row 5
    {43, 44, 45, 46, 47, 48, 49}    //row 6
};

Look at that very closely...it's the prime spiral, isn't it? Well, start at 1 in the middle, and spiral out. Looks like it to me!

Okay, so that was easy. It took a few minutes of typing, but now we have the array. We can do stuff with it, like print it or find out what's in a certain

location within it, or whatever people do with arrays.

But this is neither scalable nor efficient. Actually, it's borderline ridiculous. Having 49 numbers is one thing. That's up to s3 in our example above. (Note

that s1, s2, and s3 combined actually hold 48, but remember we decided s0 was the square with 1, so s0 through s3 = 49 numbers.)

Using this array we typed out, however, we can determine relationships between the numbers, since of course there ARE relationships and it IS predictable.

We should start with the number 1 to determine the numbers' relationships programatically. 1 is at the fourth spot in the third row, or in C++ terms:

int middle = SpiralArray[3][4];
cout >> middle;

That should print the number 1 to the console window.

Notice the straightforward syntax - NameOfArray[row][column] - which will get the value in the specified location (but only AFTER the array is set up!)

Now to figure out a relationship...

First, let's represent row and column as x and y, respectively. To best represent this, I'll have to re-write the way we initialize the array.

const int Rows = 7;
const int Columns = 7;

int SpiralArray [Rows][Columns]=
{
    {37, 36, 35, 34, 33, 32, 31},    //row 0
    {38, 17, 16, 15, 14, 13, 30 },    //row 1
    {39, 18, 5, 4, 3, 12, 29},    //row 2
    {40, 19, 6, 1, 2, 11, 28},    //row 3
    {41, 20, 7, 8, 9, 10, 27},    //row 4
    {42, 21, 22, 23, 24, 25, 26},    //row 5
    {43, 44, 45, 46, 47, 48, 49}    //row 6
};


for (int x= 0; x< Rows; x++)
    for (int y= 0; y< Columns; y++)
        cout << SpiralArray[x][y];

But wait, all that does is print the array. I thought we wanted to try filling it programatically.

So, let's try this instead. Remember that x is the row and y is the column.


const int Rows = 7;
const int Columns = 7;
int x = 3;
int y = 4;
int n = 1;

int SpiralArray [Rows][Columns];

    do {

SpiralArray[x][y] = n; // 1

y++;
n++;

SpiralArray[x][y] = n; // 2

x--;
n++;

SpiralArray[x][y] = n; // 3

y--;
n++;

SpiralArray[x][y] = n; // 4

y--;
n++;

SpiralArray[x][y] = n; // 5

x++;
n++;

SpiralArray[x][y] = n; // 6

x++;
n++;

SpiralArray[x][y] = n; // 7

y++;
n++;

SpiralArray[x][y] = n; // 8

y++;
n++;

SpiralArray[x][y] = n; // 9

       }

while (x < Rows, y < Columns);


for (x = 3; x< Rows; x++) {
    for (y = 4; y< Columns; y++){
        cout << SpiralArray[x][y];
}
}

There we go! We just made...well, one square of the spiral, anyway. Make this code snippet into a full (albeit tiny) program, and if should give us this:

0 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 5 4 3 0 0
0 0 6 1 2 0 0
0 0 7 8 9 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Looks promising, doesn't it? Well here's the thing. We can't simply implement that same function for each square, because each square contains progressively

more and more numbers.
That is, we're going to need to step forward, back, up, or down for more than just one row or column each time. In fact, the amount by which the steps would

need to increase is predictable.

This code snippet makes s0 and s1, which contain 1 and 8 numbers respectively. This is the only case in which the quantity of numbers differs by a number

other than 8.

The best way to go about this, actually, is to define helper functions for each step (a "step" is wherever we insert numbers into the array).

Also, we're going to switch rows and columns to y and x, respectively. If you think about a co-ordinate plane, this makes more sense.

We'll start with the transition from 1 to 2, which is a left-to-right movement, so we'll call it "StepRight".

void StepRight (int& column, int& value)
{
    column++;
    value++;
}

And to actually implement this, we'll have to call it thus:

StepForward(x,n);
SpiralArray[y][x] = n;

But we'll also be needing some other functions. For now, that's four in total:

StepRight= for left-to-right movement (x++)
StepLeft= for right-to-left movement (x--)
StepUp = for down-to-up movement (y++)
StepDown = for up-to-down movement (y--)

Because after all, a spiral of squares essentially moves in four increments of 90 degrees each.

Of course, the spiral WILL still come back to itself...we'll get to that.

So now, we can write the code like this:

const int Rows = 7;
const int Columns = 7;
int x = 4;
int y = 3;
int n = 1;

int SpiralArray [Rows][Columns];

    while (SpiralArray[y][x] != 0)
{

SpiralArray[y][x] = n; // 1

StepRight(x,n);
SpiralArray[y][x] = n; // 2

StepUp(y,n);
SpiralArray[y][x] = n; // 3

StepLeft(x,n);
SpiralArray[y][x] = n; // 4

StepLeft(x,n);
SpiralArray[y][x] = n; // 5

StepDown(y,n);
SpiralArray[y][x] = n; // 6

StepDown(y,n);
SpiralArray[y][x] = n; // 7

StepRight(x,n);
SpiralArray[y][x] = n; // 8

StepRight(x,n);
SpiralArray[y][x] = n; // 9

}

This should return the exact same thing we got before.

But that's still just s1. How do we fill s2, which has 16 numbers in it?

It doesn't make much sense to just keep writing Step* functions out. So, we use recursivity.

Making each square involves a certain amount of right, up, left, down, and right movement IN THAT ORDER. Looking back at the Excel spreadsheet, you notice

that each new square begins exactly one step to the right of where the previous one ended. This is a helpful consistency for sure.

s1 = Right 1, Up 2, Left 2, Down 2, Right 2

Because a square has corners, and we don't want to over-step them, the most it will ever step on a side is the length of the side minus one.

s2 = Right 1, Up 3, Left 4, Down 4, Right 4

Or in relative terms:

s(x) = Right 1, Up (side length - 2), Left (side length - 1), Down (side length - 1), Right (side length - 1)

Does that work? Let's just see.

s3 = Right 1, Up 5, Left 6, Down 6, Right 6

Hey! Yeah, it does work. Look back at the array we generated. The one with the 0s in it? Yeah - count around in a spiral and you'll see this formula does

indeed work.

But, how do we implement recursion like that?

One way is using "for" loops like this below. Let's pretend we are starting at 1, so the first StepRight() gets us to where 2 should be. Assume everything

else is already initialized as it is above.

int length = 3;
int pos = 0;
int GoUp = length - 2;
int GoLeft = length - 1;
int GoDown = length -1;
int GoRight = length -1;

for (length = 3; length < 14; length+=2)
        {

StepRight(x,n);

for (pos=0; pos < GoUp; pos++) // going up
    {

StepUp(y,n);
SpiralArray[y][x] = n;

    }

for (pos=0; pos < GoLeft; pos++) // going left
    {

StepLeft(x,n);
SpiralArray[y][x] = n;

    }

for (pos=0; pos < GoDown; pos++) // going down
    {

StepDown(y,n);
SpiralArray[y][x] = n;

    }

for (pos=0; pos < GoRight; pos++) // going right
    {

StepRight(x,n);
SpiralArray[y][x] = n;

    }
        }

This sure does look like it ought to draw a spiral...

But wait. Where does 1 go?

1 is strange. It's not really a square. If we are imagining this as a coordinate plane, 1 is more like a dot (or more accurately, a point).

When we decided that our biggest square would have a length of 7, we used (4,4) as our value of (y, x) - that is, row 4, column 4.

Notice anything about that? The numbers, specifically. That's right - 4 and 4 add up to 8, which is 7+1.

In more literal terms, the x and y (column and row) coordinates of 1 are always equal, and their values are half of the even number one greater than the

maxiumum side length.

This is no coincidence. It also happens to be the amount of numbers in the first square after 1, which is a coincidence and irrelevant to this program.

The length of each square is an odd number, and odd numbers have "middles." The "middle" is a number where there are an equal amount of numbers on each side.

Determining the middle of a number is simple. Also, it just so happens that the middle of the length of a side of a square here will be the column (or x

value) in which we will place 1.

We can do this thus:

int Rows, Columns, y, x, maxlength;
int n = 1;

cout << "Enter the maximum length of the biggest square..."
cin >> maxlength;

x = (maxlength + 1) / 2;
y = x;

Rows = maxlength;
Columns = maxlength;

int SpiralArray [Rows][Columns];

Let's say that instead of 7, you want to go up to s6, which is 13 numbers long. Where do we put 1? Well, at (7,7), right? So you put in 13 and it calculates

x to be (13+1) / 2, which is 7. Then, it sets y to the same thing. So when we start off the program, we do

SpiralArray[y][x] = n;

which puts n (1) at (7,7), or in row 7 column 7.

Consider this:

Max side length : 1 is at (y, x)

3 : (2,2)
5 : (3,3)
7 : (4,4)
9 : (5,5)
11 : (6,6)
13 : (7,7)
15 : (8,8)
17 : (9,9)
19 : (10,10)

The maximum side length, if you hadn't noticed, also dictates the dimensions of the array. It makes more sense to demonstrate with a smaller array/spiral, so

let's say you want the max square length to be only 3:

5 4 3
6 1 2
7 8 9

Oh, look, there's 1 at row 2 column 2. Extrapolate to a max side length of 5:

17 16 15 14 13
18 5 4 3 12
19 6 1 2 11
20 7 8 9 10
21 22 23 24 25

Okay, the formatting is off, but you can easily tell that 1 is indeed at row 3 column 3.

It might not make logical sense, at first, to think that 10 is the "middle" of 19. Well, yes, it is:

1 2 3 4 5 6 7 8 9 >>10<< 11 12 13 14 15 16 17 18 19

Count the numbers on each side of 10. There are 9. 9 on each side. No, we do not start at 0. When do you ever start counting at 0? No one does that. You

don't start with nothing and suddenly have something. If you're trying to get somewhere quantifiable, you need to start somewhere quantifiable, or you're

basing your pursuit on nothing, which is going to get us nowhere.

Plus, if you start at 0, then even numbers have middles, and that would throw this whole program off, so don't do it.

We need to slow down for a moment here. What do we even HAVE thus far?

- a bunch of prerequisites and definitions
- an understanding of how multi-dimensional arrays work
- a way to create an array with as many rows and columns as you need (or want)
- a fairly good way to loop the spiraling function
- oh, and we also have functions to step up, left, down, and right as needed based on the length of the side

Numbers work in interesting ways. The fact that there is a relationship at all between the length of the side of the square and the amount we need to step in

any direction is remarkable.

We are well on our way to generating Ulam's Spiral in a C++ program!

No comments:

Post a Comment