rokicki / apmath

Code to generate good solutions for large arrays

This directory contains a program to generate good solutions based on Jarek Wroblewski's ideas and some computer search. There is one program, 171recon5.cpp, and 28 data files, two for each size of 139 through 578 that were used in Al Zimmermann's Programming Contest AP Math from 2021.

To build the program, a command line such as this works:

g++ -march=native -g -std=c++17 -O3 -o 171recon5 171recon5.cpp

You can drop the -mark=native if your platform doesn't support it. Clang works equally well.

The program, when provided with the appropriate arguments and data file, generates an almost infinite set of good solutions. All of these solutions will have the same number of points set, but other than that they will differ fairly extensively (although they are all based on the 275x3x3/171 modular solution by Jarek). The generation will be very fast, likely limited by I/O once it begins (only a few seconds). The generation are randomly selected although not fully unbiased.

The output format is concise and different form Al's format. The output format describes a raster scan of the solution, encoding the differences between adjacent selected points. The coordinate system is of a square. If the hexagon is n on a side (say 11), then the square is 2n-1 (here 21) in width. The y multiplier mult is 2w or 4n-2 (42 in this case), and the base value (for the 0,0 square) is at (w-1)(mult+1) (or 860). So to read the coordinates as a set of x/y values in the square, given the values in a matrix, use code much like this (assuming v holds the input values and n is the size of the hexagon):

w = 2 * n - 1 ;
mult = 2 * w ;
base = (mult + 1) * (w - 1) ;
for (int i=1; i<(int)v.size(); i++)
   v[i] += v[i-1] ;
for (auto z: v) {
   x = (z - base) % mult ;
   y = (z - base) / mult ;
   // ... do something with x and y here
}

As an example, you can work out the following solution for n=6.

 230 3 1 18 1 2 1 19 6 18 3 1 15 6 2 1 13 1 6 16 3 21 2 1 4 16 6 16 3 1 19 3 1

For this example, n=6, w=11, mult=22, base=230. So the first point is (0,0). Then, add 3, and the next is (3,0), then (4,0). Then we add 18, which wraps around and goes to (1,0). And so on.

You have 28 data files. The data files are named scansolsm-n-1-o.log where n is the size of the hexagon and o is a special parameter describing the labeling. To run the program, give the numeric parameters followed by the data file name on the command line, as in

./171recon5 578 1 132 scansolsm-578-1-132.log

This will write to standard output good solutions, one per line. The number of numbers on each line is the number of points set in that solution, and it will be identical for every solution generated by a particular data file.