The Numbers Game – part 3

Following on from the two previous posts, the third version of this program is now finished and available in an online version here

This version is different again, as it needs to run in a web server, and my production web server has a time out of 30 seconds. As my best version so far takes about 2m30s to calculate all possible combinations, this one needed to be a bit clever.

The user interface is a single webpage within the Glover Family Net framework, which consists of a header, a footer, a left menu and a right menu. Within this framework is a simple HTML page with the basic text, headings, buttons and the like. There are several chunks of PHP that that generate the tables of numbers to be selected, the target numbers, and the list of selected numbers. Each item in the table of ‘buttons’ is actually just a table detail (<TD>), and any interaction with these buttons to mark numbers as selected, changing them from enable to disabled etc is handled by Javascript routines . All logic regarding validation of the number of numbers selected, and the choice of the target amount is handled within this Javascript.

The “Start Again” button backs out any updates to leave a clean slate to, well, start again on. An extra button has been added, to give two ways of processing the results. The first is stopping when 10 matches have been found, which is usually quite quickly, and the second is using the full 30 seconds to process as many matches as is possible. Only 20 matches are shown but a count of matches is displayed, if you want to see more download the windows version.

Finally the “Solve” button is just a button with an onclick Javascript function, which uses an AJAX routine (Asynchronous Javascript And XML – but I don’t use the XML part!). The Solve button uses  a URL to call the PHP  Solver module, passing the chosen numbers, target and solve method as parameters. This PHP solver module runs in the background on the web server at WebhostingNZ, and the AJAX routine tests occasionally for completion of the routine and the return of the results. The results are placed in the results area of the original web page which remains on the screen for the whole time.

The PHP solver is a rewrite of the Python version, with some features of the Pascal version included. PHP has some extra restrictions and capabilities, which have meant some changes, mostly around making it all happen within 30 seconds.

Firstly, the table of 720 permutations of 6 digits is shuffled and  hard-coded into the program, not generated each time as in previous version.

Similarly, the 1024 combinations of 5 signs from the 4 available is also shuffled and hard-coded, but reduced to 991 combinations, removing ‘/ / / / /’, ‘ – – – – – ‘ and all combinations consisting of just divide and minus signs which would never produce a match for a target. I also remove ‘////+’ as removing this reduces the array to 991 in size. The number 991 is a prime number, and chosen on purpose.

And lastly, the Reverse Polish Notation stacks of the combinations of Number and Operator positions are also hard coded.

Reducing the operators array by the 32 unneeded combinations, plus the one very unlikely to be any use, reduces the total number of combinations to 29,957, 840 from 30.9 million.

Rather than three nested loops which processes all RPN stacks for each operator combination and each operator combinations for each number, the latest version uses a more flexible method. In order to hit a better variety of numbers, operator and RPN stacks, the program is now a single loop, where each array is parsed individually along side the other arrays. When the end of an array is reached, it starts parsing that array again, while the other two arrays continue as normal. Eventually all three arrays will get back in synchronization (think of 3 meshed gears rotating until they come back to their starting point), at this point the 42 element RPN stack is shuffled again, and the loop continues until the 30 seconds time expires. As each array is a different length, parsing through them all at the same time means we will see 4,994,640 combinations, each shuffle of the RPN stack will produce a new set of 4,994,640 combinations . There are nearly 30 million combinations to process altogether, but we cannot do all of these in 30 seconds.  While there is some risk of missing some possible matches, enough will be found to solve the huge majority of possible puzzles, and less will be missed than just doing a small part of the number array in a fixed sequence.

The number 4,994,640 comes from the product of the common prime factors for the length of each array. The prime factors of 991 are 991, of 720 are 2,2,2,2,3,3,5 and of 42 are 2,3,7, making the total 2x2x2x2x3x3x5x7x991 which is 4,994,640 (or 720 x 991 x 7). The factors 2 and 3 in the RPN stacks factors are already covered by the factors of 720, so are not used.

Previous versions presented the results as “Infix” formulas, e.g. (((((100+6) * 3) * 75) -50) / 25) = 952, in order to make the results more easily read, this version presents them as a series of statements, e.g. 100+6=106 106×3=318 318×75=23850 23850-50=23800 23800/25=952. Results are deduplicated, and sorted shortest string to longest string, giving the simplest answers first.

The results are presented either as a single line giving the closest match when no match is found, or the first 10 matches when matches are found, or up to 20 matches if the 30 second option is chosen. A 30 second time limit means that when no match is found, the full 30 seconds is used up, when a 10 matches are found, it may take a few fractions of a second, a few seconds, or the full 30 seconds to find the matches, depending on the difficulty of the number set and the target. A count of matches, attempts to match and the time taken are shown on the results.

POP and PUSH (or APPEND) as used in the Python code simplified the conversion a little, and removing the nested processing of the arrays simplified the code significantly. There is still some optimisation to go, and in 30 seconds between 6 million and 8 million combinations can be attempted to find or not find a match.