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:

  1. Note the center value “1” and the spiral pattern as the values increase by one.
  2. The center cell (value = 1) is surrounded by ever increasing size squares with odd number count sides (3, 5, 7, etc.)
  3. 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.
  4. 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.

  1. 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).
  2. Manually (or write a program) to expand the spiral matrix to the required size (the brute force method).
  3. 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:

  1. Create a program that will produce the diagonal sum for the 501 by 501 spiral matrix as well as other such matrices.
  2. 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



DacsGear!
Mugs and more, visit CafePress to order
 
 
© Danbury Area Computer Society, Inc. All Rights Reserved.
Web Site Terms & Conditions of Use