0

I did think quite a lot about this and was able to work out how all the variables and counters are going and how we arrive at the result.

However, is there any logic to support Mark Byer's solution here, or is it just adjusted so that all the counters fall in place?

Please give me a logical explanation for the algorithm

Code

#include <stdio.h>

int main()
{
    int x[3][3] = {1, 2, 3,
                   4, 5, 6,
                   7, 8, 9};
    int n = 3;
    for (int slice = 0; slice < 2 * n - 1; ++slice) {
        printf("Slice %d: ", slice);
        int z = slice < n ? 0 : slice - n + 1;
        for (int j = z; j <= slice - z; ++j) {
            printf("%d ", x[j][slice - j]);
        }
        printf("\n");
    }
    return 0;
}
Community
  • 1
  • 1
saltmangotree
  • 171
  • 4
  • 11

1 Answers1

1

Mark's answer is correct and will work for any n. Maybe Mark should have named his variable diagonal instead of slice.

Look at the way the diagonals' start point and end point are progressing, for n = 3:

       start ->
end   a - b - c
 |    |       |
 \/   h       d
      |       |
      g - f - e

For each diagonal, the start index follows the path: a-b-c-d-e and the end index follows the path: a-h-g-f-e. And to traverse a diagonal we need to travel in a southwestern direction i.e. each next point we visit is one row below and one column leftward. Thus, the diagonals are: a-a, b-h, c-g, d-f, e-e.

For starters, you can just think of ending each diagonal's traversal when we run out of bounds either way (remember, we are increasing the row and decreasing the column, always). Mark's answer captured that too in the loop variables.

We need to also see that the number of diagonals is always n + (n - 1) = 2 * n - 1.

The following table captures the above picture of diagonals:

d#       start    end
----------------------
0       (0, 0)   (0, 0)
1       (0, 1)   (1, 0)
2       (0, 2)   (2, 0)
3       (1, 2)   (2, 1)
4       (2, 2)   (2, 2)

Now, since we can always capture the end once we know the start (i.e. progress in southwestern direction till we run out of bounds), we need to focus on the relationship of d# with start.

If you drew a similar diagram/table for n = 4 perhaps you can see the pattern and capture the first loop's variables in terms of d#.

Kedar Mhaswade
  • 4,535
  • 2
  • 25
  • 34