Problem number 1 – Solutions to the spiral matrix problem published in the October 2007 DACS.DOC
by Charles Bovaird
Wow! This problem generated a host of responses and different approaches to solving it. Five DACS members submitted programs that arrived at the correct solution. The methods ranged from simple to complex dependent upon the solvers experience. All the solutions can be viewed as a programming-model or math-model for solving the problem.
The answer to this problem is a single integer of large value (669171001). The challenge is open to all readers of this article to submit solutions along with their programming solution to mathsig@dacs.org. Students, instructors or other non-DACS members are invited to respond.
OBSERVATION: Each persons capability as a problem solver is dependent upon one's past training, experience, and willingness to apply their experiences to problems at hand.
PROBLEM RESTATED AND EXPANDED
The original problem was illustrated as a 5 x 5 matrix. Following is the same problem expanded to a 13 x 13 matrix.
157 158 159 160 161 162 163 164 165 166 167 168 169
156 111 112 113 114 115 116 117 118 119 120 121 122
155 110 73 74 75 76 77 78 79 80 81 82 123
154 109 72 43 44 45 46 47 48 49 50 83 124
153 108 71 42 21 22 23 24 25 26 51 84 125
152 107 70 41 20 7 8 9 10 27 52 85 126
151 106 69 40 19 6 1 2 11 28 53 86 127
150 105 68 39 18 5 4 3 12 29 54 87 128
149 104 67 38 17 16 15 14 13 30 55 88 129
148 103 66 37 36 35 34 33 32 31 56 89 130
147 102 65 64 63 62 61 60 59 58 57 90 131
146 101 100 99 98 97 96 95 94 93 92 91 132
145 144 143 142 141 140 139 138 137 136 135 134 133
Observations:
- Note the center value “1” and the spiral pattern as the values increase by one.
- The center cell (value = 1) is surrounded by ever increasing size squares with odd number count sides (3, 5, 7, etc.)
- The top left diagonal contains cell values equal to the square of the number of cells to a side (9, 25, 49, etc.) of each square.
- The values in the three remaining corners of each square are an offset from the values in observation.
PROGRAMMING METHODS
Three different approaches (types) were used to attack the problem.
- Write a program to model the behavior of the numbers in the spiral matrix and accumulate the results until you reach your objective value 1001 (the value in the top right corner of the five hundredth square).
- Manually (or write a program) to expand the spiral matrix to the required size (the brute force method).
- Produce an algebraic statement that will be used in a program to compute the desired result by inputting 1001 or 500 as appropriate to which algebraic model is selected.
Results validation A program solution will produce correct results for any size matrix up to the five hundredth square. The correct solution for the 500 square matrix is 669171001.
PROGRAMMING METHODS—detail
A type (1) method—Written in ROBOTbasic language by John Gallichotte.
The program “SpiralMatrix.Bas” was written in RobotBASIC.
John’s approach—
Starting with the number 1 and moving to the right in a clockwise direction, a 5-by-5 spiral matrix is formed as follows:
- Create a program that will produce the diagonal sum for the 501 by 501 spiral matrix as well as other such matrices.
- What would be the program to determine all the diagonal sums for the spiral matrices from 1 to 501?
Analysis: It is noted that each turn of the spiral ends with a number that is odd. After the starting term “1” each turn of the spiral only adds four values to the diagonals sum. The last element in each matrix is determined by squaring the number of elements along an edge.
One element added to the sum is the square of the elements along an edge, the remaining three are easily determined.
A program to calculate the sum for each spiral requires only a single loop. The loop limit is stated as being 500. The sum is initialized to 1 before entering the loop. The four elements to be summed within the loop are calculated. A print subprogram is written to display the results for 500 loops.
//----------------------------------------------------------------------------------------
MainProgram:
Y = 45 // constants
Ord = 1
Dsum = 1
spirals = 500
GoSub OutputHeader //
For W = 1 to spirals // Next six lines calculates the sum of the diagonals
line = Y + (W ) * 20
Ord = Ord + 2
Dsum = Dsum+((Ord*Ord)-Ord+1)+(Ord*Ord)+((Ord-2)*(Ord-2)+Ord-1)+((Ord-1)*(Ord-1)+1)
GoSub Print // sub-program not included
Next // end loop
XYstring 10, 575, "Execution complete"
End
//----------------------------------------------------------------------------------------
The following individuals submitted type (1) programming models using the looping approach:
NAME |
PROGRAMMING LANGUAGES / METHODS |
Gallichotte, John |
RobotBASIC |
Lansdale, John |
C#, Java, C, HTML, PHP |
Bovaird, Charles |
APL |
Westfall, Lew |
C |
No one submitted type (2) programming models (brute force method).
The following individuals submitted type (3) programming models (Algebra).
These will be addressed in a future article in DACS.DOC.
NAME |
PROGRAMMING LANGUAGES / METHODS |
Wilkinson, David |
Algebra, C |
Bovaird, Charles |
Matrix Algebra (polynomials), APL |
Charles Bovaird
January 14, 2008 |