Tests done on sk_17p2a

http://pagesperso-orange.fr/gpenet/SK17TEST/test.htm

These test results are published with as main targets

 

Giving an idea of the run time to come

Registering some key test for later regressive tests check

Giving some key data to see where is the room for improvement

 

Validation tests

 

The validation tests are done on the file of known 17 having the 665 distribution.

 

Test of the valid path

 

The first test, was to check the path leading to the solution. Only the step and the chunk containing the solution are run, only the XY containing the solution is expanded.

 

This is a quick test (some millisecond per entry) that can be used as regressive test to check that nothing wrong occurred.

 

The test is stopped if the expected 17 is not found for a given entry.

 

The test took an average 58 ms per entry. This includes the band expansion and the UAs generation.  The only limitation toward the final process is in the GUAs generation. Having only one band 3 attached, less sockets are in use.

 

One interesting stat to catch is the ratio of XY passing the first filters. Here 1.5% of the XY have to go to the brute force. This is with the primary set of UAs. As the process is limited to the valid XY, no UA is added later. Below are the results in conditions closer to the search to do.

 

 

Test of valid17 in “standard conditions”

 

Here, the program is called in standard conditions, with as unique band 3 the band of the entry.

The program produces all XY as in the future run, but with only one band 3, more XY can be cleared.

 

The final result is slightly optimistic as ”band 1+2”  result, but pessimistic as “per solution grid” result, having only one band 3 against an average 9 bands 3 in the final run.

 

But as for high index the average number of bands 3 is close to one, This test gives a good idea of the expected result per solution grid for these band 1.

 

The last 116 band 1 (index 300 to 415) produce only  1.85 million bands 1+2 (out of 610 millions) and the ratio is 1.22 band 3 for one pair band 1+2.

 

For this lot, we could expect an average run time around 10 seconds per bands 1+2.(see test results done on my laptop)  which is about 9 month of work for one core.

 

Here below are stats (per entry) for the last 826 entries

 

62 809                                                      1 chunks processed entries gochunk

3 207 102 755                                         2 XY count

5 678 780                0.18%                      3 XY passing UA filter

1 581 053                0.05%                      4 XY brute force

1 141 572                0.04%                      5 valid brute force

186 897                   0.01%                      8 valid b12 after build active

 

 

In this test the average count of  XY  reflects and average high index (as the file is sorted on the min lexical value of the entry, the link to the index is unclear)

The ratio of XY passing the UA filter is now 0.18% against 1.5% in the first test. This is the effect of UAs added during the  1 581 053 average calls to the brute force. 4 millions of them show a multiple solution for the XY and deliver a new UA.

The smaller are added to the primary table.

 

 

Evaluation tests

 

The second group of tests is to see what happens in various parts of the solution grids catalog.

 

I took some first index 0,10,100,200,400. The number of XY grows with the index and the average number of bands 3 falls.

 

For each band 1, I took the first 10 bands 2. processing band 400, I could not reach 10 bands with the limit settled for the band 2 search. (only 5 bands in the enumeration test). This means also that the run time for this lot is not representative of the band processing. With an index over 305, we have a catalog generator penalty of some minutes per band 1.

 

The average count of bands 3 in more or less in line with the enumeration average, but the distribution is not steady. With only 10 bands, we have significant deviations

 

 

Index             av b3  av ref

0                    29       18.59

10                  22.1    17.26

100                2.1      7.54

200                1.9      2.85

300                1         1.32

400                1         1

 

In this table, the first column is the index, the second the average number of bands3 found, in the last column the average given by the enumeration test (all bands 2 for the band 1).

 

 

                      XY                           UA filter      valid b12

0                    285 104                  0.354%        0.081%

10                  23 217 551             0.395%        0.067%

100                483 896 961          0.065%        0.007%

200                1 280 205 954       0.093%        0.011%

300                3 440 913 347       0.104%        0.004%

 

 

This second table shows the count of XY, then XY passing the first filter, then puzzle passing all test for at least one attached band.

 

First of all, as in the test on known, the percentage of XY passing the fist filter is relatively high. Lower value appear in following tests. My guess is that a lower value linked to a bigger number of XY can be explained by the fact that more additional UAs are produced 

 

The last column gives a good indication of the overall filters efficiency. With index 10, we have in average 4 bands 3 per valid Bands 1+2; this ration falls sharply below 2 for higher index. We have one band 3 per valid bands 1+2 with index 300;400

 

Run time

 

The sequence per band 1 is the following (average  run time per band 2 test done on my laptop)

 

 

Index             time (second)

 0                   0.17

 10                 1.67

 100               2.14

 200               10.5

 300               10.71

 

The time grows up quickly, but we have to keep in mind that 55% of the pairs band1;band2 have an index <= 100 and that 77% of the bands 3 are collected in this group

 

It could be that another step organization would perform better with high index. For example, 2 common cells in X (5 clues) ; 3 common cells in Y (6 clues).

The priority will be to run more tests for the phase 2 (band3 handling), then to start the process for the bands with the low index;

 

 

End of run statistics

 

Next page gives explanations on statistics delivered at the end of each run

These stats, written on “cout” are just here to help in the design of the code.

I kept them to have the possibility to analyze oddities in the search.