Programming Challenge No. 9 - Array of Numbers II

[TheQuirk]

A few years ago, I posted several programming challenges. These were basic problems that required very little programming know-how, but did require a little bit of thinking (sometimes a little bit of math, sometimes coming up with an algorithm). They were pretty fun, and I think we all learned a little bit by participating. Is there any interest in a new challenge?

[By the way, would anyone like a recap of the past challenges (e.g. explanations, points that went unnoticed, some theory)?]

This is a follow-up to the spiralling numbers programming challenge (http://www.stop-microsoft.org/bbs/index.php/topic,9590.0.html).

Consider the following infinite array of numbers:

1	2	5	10	...
4	3	6	11	...
9	8	7	12	...
16	15	14	13	...
...	...	...	...	...

(notice how the numbers are placed in shells.)

Part A: Given a pair of indicies (i, j), what number is at the (i, j) position? (For consistency, i denotes the row from the top, and j denotes the column from the left.)
Part B: Given a number k, find the indicies (i, j) such that the number at (i, j) is k.

Source: http://tasks.ceemat.ru/dir/471/1949/ (Russian)

Don't think that the only appropriate reply is a solution! Discuss the problem, post partial solutions, discuss relevant problems, etc.

I cannot offer a real prize, but each person who solves this problem will get to have his name edited into this first post in giant red letters.

[Laukev7]

Part A:

Assuming that array indices start with 0, consider that for array A, A[n][n] - A[n][0] == A[n][n] - A[0][n], since we iterate by 1 from A[n][0] to A[n][n], then to A[0][n]. [n][n].

We can see from the illustration that A[0][n] == (n + 1)^2, which is because it is the final number of a square. This satisfies the base case A[0][0], since (0 + 1)^2 == 1.

We can further determine that A[n][0] = n^2 + 1, since A[n][0] always follows A[0][n]; in this case, A[n][0] is the square of the number of rows rows - 1, which is n. This also satisfies the base case, since 0 ^2 + 1 == 1.

Given this data, we can proceed with the following pseudo-code:


if i < j then
    k := (max(i, jj) + 1) ^ 2;
    k := k - i;
else if i > j then
    k := (max(i, j)^2 + 1;
    k := k + j;
else
    k := (i + 1)^2 - i;

If there are less columns than rows, then we decrement from the bottom left, starting from A{0][n]. If there are more columns than rows, then we increment from the top right, starting from A[n][0]. If the number of rows and columns are equal, then we square the number of rows and substract from it the number of rows to obtain the number in the bottom left corner.

In C we can implement this algorithm as follows:

Code: [Select]

#include "math.h"

{int getIndexFromShellArray(int i, int j, int[] A)
{
    int k;
    if (i < j)
    {
        k = pow(max(i, j) + 1, 2);
        k -= i;
    }

    else if (i < j)
    {
        k = pow(max(i, j)) + 1;
        k += j;
    }

    else
        k = pow(i + 1, 2) - i;

    return A[k];
}

int max(int x, int y)
{
    return (x >= y) ? x : y;
}


[Laukev7]

Part B:

Using the data from part A we can find the indexes with the following algorithm:

function getIndexesFromNumber( integer k ):
where lower_bound = j^2 and upper_bound = j+1^2
    j := 0
    while true
        if upper_bound > k then
            corner = n - floor (upper_bound - lower_bound) / 2)
            if k > corner then
                i := upper_bound - k
               return (i, j)
            else if k < corner then
                j := k - lower_bound
                return (i, j)
            else
                i = j
                return (i, j)
        else if upper_bound = k then
            return (0, j)
        else
            j := j + 1
            i := i + 1
    end

EDIT: Here is the C code:

Code: [Select]

#include "stdio.h"
#include "math.h"

char* getIndexesFromNumber(int k)
{
int i, j;
i = j = 0;
char[50] indexes;

while (1)
{
int upper_bound = pow((j+1), 2);
int lower_bound = pow(j, 2) + 1;

if (upper_bound > k)
{
int corner = upper_bound - (upper_bound - lower_bound) / 2;
if (k > corner)
{
i = higherSquare - k;
sprintf(indexes, "(%d, %d)", i, j);
return indexes;
}


else if (k < corner)
{
j = k - lowerSquare;
sprintf(indexes, "(%d, %d), i, j);
return indexes;
}

else
{
i = j;
sprintf(indexes, "(%d, %d), i, j);
return indexes;
}
}

else if (upper_bound == k)
{
sprintf(indexes, "(%d, %d), 0, j);
return indexes;
}

else
{
++i;
++j;
}
}
}