Competitive/Collaborative Programming Class

ICPC Computer Programming Contest Prep

Problem Solving in Computer Science

Spring 2024 -- CSC 2700 Section 01 (1218 Patrick Taylor, 6:30 PM - 8:20 PM)



Array Techniques

Guard

Quite often it becomes useful to load data into a 2D array. Sometimes things can go swrong and you can put things in the wromg place. Other times you simply want/need a border to make processing simple.

One thing you can do is to put guard cells around. You can add a row at front and at the bottom as well as a column at the beginning and end of each row.

0000000000000000000000000000
0445554325267989546336y68970
0435595923452475457957527690
0445554325267989546336y68970
0435595923452475457957527690
0445554325267989546336y68970
0435595923452475457957527690
0445554325267989546336y68970
0435595923452475457957527690
0000000000000000000000000000

I typically place a value in the guard are that will not naturally occur in the data (in this case 0 [-1 is often a good choice also]). At any point you can search the guard areas for any non-guard value (this tells you that you made a subscripting error).

If you are summing up points in a 3x3 filter and use 0 as the guard value, then you can always sum up 9 values without checking for edges (faster). You will need to know how many guard points you use if a division by cell count is needed.

Return to Top of Page


3x3 Filter

This is the normal way to pass 3x3 filter over a 2D array. This just works. It can be converted to 5x5 by changing 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 variables to x and y offset array indices.

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

Return to Top of Page


Spiral Search

Here is a way to implement spiraling through a 2D array Imagine an array that was 11 x 11 (0..10 are the indices) 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...