Competitive/Collaborative Programming Class

Array Tricks

• Normal way to pass 3x3 filter over a 2D array. This just works. It can be converted to 5x5 by canging initial and final values. Note that two loops are used making a non-trivial amount of overhead.

  for (i=-1; 2>i; i++)
   { // for i
     for (j=-1; 2>j; j++)
      { // for j
      // if used to ignore non-positive data
      if (0 < ary[x+i][y+j])
       { // add it up
          total = total + ary[x+i][y+j];
       } // add it up
      } // for j
   } // for i
  
  

• Here is a neat way to process a 3x3 window across a 2D array using a single loop. i and j shift from loop control vaiables to x and y offset arrays.

  int i[7] {-1, -1, -1, 0, 0, 1, 1, 1};
  int j[7] {-1, 0, 1, -1, 1, -1, 0, 1};
  
  /* assume we are processing ary[x][y] */
  
  for (k=0; 8>k; k++)
   { // for k
      // if used to ignore non-positive data
      if (0 < ary[x+i[k]][y+j[k]])
       { // add it up
          total = total + ary[x+i[k]][y+j[k]];
       } // add it up
   } // for k
  

• Here is a way to implement spiraling through a 2D array Imagine an array that was 11 x 11 (0..10 are the indicies) and that you are 5,5 (the exact center).
  The 4 points closest to (5,5) are (5,4), (5,6), (4,5) and (6,5) (left, right, down and up)
  The 4 next closest points are (4,4), (4,6), (6,6) and (6,4) -- the diagonal points are a little further away
  

                    F E D E F    
                G D C A 9 A C D G 
                D B 8 7 6 7 8 B D  
              F C 8 5 4 3 4 5 8 C F
              E A 7 4 2 1 2 4 7 A E
              D 9 6 3 1 0 1 3 6 9 D
              E A 7 4 2 1 2 4 7 A E
              F C 8 5 4 3 4 5 8 C F
                D B 8 7 6 7 8 B D
                G D C A 9 A C D G
                    F E D E F 
  
  id  dist   dist    points
  -- ------- -----   ----------------------------------------------------------
  0  sqrt(0) 0     = 0,0
  1  sqrt(1) 1     = 1,0   0,1  -1,0   0,-1
  2  sqrt(2) 1.414 = 1,1  -1,1  -1,-1  1,-1
  3  sqrt(4) 2     = 2,0   0,2  -2,0   0,-2
  4  sqrt(5) 2.236 = 2,1   1,2  -1,2  -2,1  -2,-1 -1,-2  1,-2  2,-1   
  5  sqrt(8) 2.828 = 2,2  -2,2  -2,-2  2,-2
  6  sqrt(9) 3     = 3,0   0,3  -3,0  -3,-3
  7 sqrt(10) 3.162 = 3,1   1,3  -1,3  -3,1  -3,-1 -1,-3  1,-3  3,-1
  8 sqrt(13) 3.606 = 3,2   2,3  -2,3  -3,2  -3,-2 -2,-3  2,-3  3,-2
  9 sqrt(16) 4     = 4,0   0,4  -4,0  -4,-4
  A sqrt(17) 4.123 = 4,1   1,4  -1,4  -4,1  -4,-1 -1,-4  1,-4  4,-1
  B sqrt(18) 4.243 = 3,3  -3,3  -3,-3  3,-3
  C sqrt(20) 4.472 = 4,2   2,4  -2,4  -4,2   -4,-2 -2,-4  2,-4  4,-2
  D sqrt(25) 5     = 5,0   4,3   3,4   0,5   -3,4  -4,3  -5,0  -4,-3 -3,-4  0,-5  3,-4  4,-3
  E sqrt(26) 5.099 = 5,1   1,5  -1,5  -5,1   -5,-1 -1,-5  1,-5  5,-1
  F sqrt(29) 5.385 = 5,2   2,5  -2,5  -5,2   -5,-2 -2,-5  2,-5  5,-2
  G sqrt(32) 5.657 = 4,4  -4,4  -4,-4  4,-4
  

  As you can see, a spiral is a real pain in the you know what to implement. If you tried to do this programatically, the calculations would kill you. With offset arrays:

  x[]={ 0, 1, 0,-1, 0, 1,-1,-1, 1, 2, 0,-2, 0, 2, 1,-1,-2,-2,-1, 1, 2 ...
  y[]={ 0, 0, 1, 0,-1, 1, 1,-1,-1, 0, 2, 0,-2, 1, 2, 2, 1,-1,-2,-2,-1 ...
  
  for (k=0; 17>k; k++)
   { // loop for each spot of the spiral
      process ary[i+x[k][j+y[k]]
   } // loop for each spot of the spiral
  As you can see, a single loop is used that never does a single distance computation. By counting matches, the loop could short circuit early. Imagine trying to code a spiral search manually...