New Years Puzzle, Fractional Math and More...
Posted 02-08-2019 at 02:10 AM by astrogeek
Updated 02-22-2019 at 04:43 PM by astrogeek (Reorganizing categories)
Updated 02-22-2019 at 04:43 PM by astrogeek (Reorganizing categories)
Updated 2/17: New code now available, minimal expression set, see below...
The continuing saga fo the New Years Puzzle and Programming Challenge.
Member Beryllos who originally opened the thread discovered that some solutions were missed (and possibly other invalid solutions included) as a result of math errors intrinsic to floating point math. They very correctly identified integer math, math using only integer fractions, as the necessary solution. In the face of some reluctance on the part of other participants (including myself!), Beryllos patiently explained the problem and the solution, the truth of the matter winning in the end as it always must!
They have now posted their current version of code, and a few notable test cases which produce more complete results using fractional math, than code which uses floating point math. Applause all around!
I have continued to flail away at my own program and have posted an updated version of the code below. I have changed, and hopefully much improved my original code for this puzzle, from the ground up, and have now added evaluation of expressions using fractional math!
My initial interest in the puzzle was not so much "how many" solutions the program could generate, but how I could explore the generating expressions themselves, and their relations to each other and to the digits for which they were being evaluated. So I had in mind an approach that was more user interactive (it is a puzzle after all!), as opposed to an exhaustive expression generator.
To that end I have removed the expressions themselves from the code completely, and turned the program into an expression parser and evaluator. A human user must supply the expressions, either from the command line or from a file, and the program performs year digit permutations and substitution into those expressions, generating various measures of their effectiveness.
The code now accepts each expression in symbolic form, and parses it into an abstract syntax tree, or AST which is then evaluated to produce the final result. This also assures that correct precedence and associativity of parenthesis and operators is maintained in evaluating expressions, making it easier to validate the result and to detect human errors entering into expressions! The program provides a simple way to validate the AST itself by generating simple graphviz dot language output if desired, which can be turned into images like these...
It also provides a textual representation generated by the walking algorithm.
Expressions are always supplied in symbolic form, with lower case a,b,c and d standing in for the digits of the year, like these...
From a programming perspective, having the parser already in place using floating point math greatly simplified addiiton of the fractional math evaluation code too! Other than putting together the fractional handlers, I simply had to add a function to walk the tree using the fractional functions instead of the floating point functions - meaning the program can do either, selectable at runtime. This makes it easy for the user to explore and see the difference each method makes!
The AST nodes and values or terms used to evaluate the expressions are each simple structs returned by the various handlers. They have in common that they are created frequently, used quickly then forgotten. To simplify their management we create a small static array of each struct type with an associated index, then assign pointers and initialize them sequentially on demand. When the index reaches the end of the array it is pointed back to the beginning, so that we use the elements in round-robin fashion and never have to concern ourselves with disposing of them - they are simply reinitialized when needed.
I have also added the ability to specify a range of years to be evaluated, and several different output data formats which make it easy to summarize the data, or to drill down to see the expressions as they are evaluated, even those which fail.
I included a file of about 150 expressions which together produce a fairly complete set of results for most years, as measured by comparison with the programs which produce exhaustive result sets.
It is also fast, able to evaluate all of those expressions and generate totals for all 10,000 four digit years in about 37 seconds on my old 32 bit laptop, with which I am well pleased!
There are always improvements that can be made, and that is certainly true of this little program! But those interested should find it at least readable and functional, and I hope those following this little puzzle will find it useful - maybe even fun to play with.
I have named the file with a .txt filename extension for upload - simply rename it to years.tar.gz and untar it.
Update 2/17: Updated code now serving... years_minimal_v1.0.2.tar.gz.txt
This archive includes most recent code, with all known errors fixed, plus the first verified complete expressions set. This archive also includes a minimal set of expressions which produces all totals for all years, derived from "complete" expression set by identifying all which produced no change in totals when removed. There are now 176 expressions in the set, see comments at top of that file.
There is a simple README included to get you started, additional information and simple build instructions included in comments at top of the years.c file. And of course a --help feature.
Enjoy!
PS - From the data generated during tests we get this graph of the distribution of total results by number of years (the data are in the tarball, updated for complete_v1.0.2, includes all known solutions):
Note that there are no years with 100 or all 101 solutions, nor with 2, 3, 5, 6, 7, 8, 10 or 12 solutions, produced by the current set of expressions - fertile ground!
The continuing saga fo the New Years Puzzle and Programming Challenge.
Member Beryllos who originally opened the thread discovered that some solutions were missed (and possibly other invalid solutions included) as a result of math errors intrinsic to floating point math. They very correctly identified integer math, math using only integer fractions, as the necessary solution. In the face of some reluctance on the part of other participants (including myself!), Beryllos patiently explained the problem and the solution, the truth of the matter winning in the end as it always must!
They have now posted their current version of code, and a few notable test cases which produce more complete results using fractional math, than code which uses floating point math. Applause all around!
I have continued to flail away at my own program and have posted an updated version of the code below. I have changed, and hopefully much improved my original code for this puzzle, from the ground up, and have now added evaluation of expressions using fractional math!
My initial interest in the puzzle was not so much "how many" solutions the program could generate, but how I could explore the generating expressions themselves, and their relations to each other and to the digits for which they were being evaluated. So I had in mind an approach that was more user interactive (it is a puzzle after all!), as opposed to an exhaustive expression generator.
To that end I have removed the expressions themselves from the code completely, and turned the program into an expression parser and evaluator. A human user must supply the expressions, either from the command line or from a file, and the program performs year digit permutations and substitution into those expressions, generating various measures of their effectiveness.
The code now accepts each expression in symbolic form, and parses it into an abstract syntax tree, or AST which is then evaluated to produce the final result. This also assures that correct precedence and associativity of parenthesis and operators is maintained in evaluating expressions, making it easier to validate the result and to detect human errors entering into expressions! The program provides a simple way to validate the AST itself by generating simple graphviz dot language output if desired, which can be turned into images like these...
It also provides a textual representation generated by the walking algorithm.
Expressions are always supplied in symbolic form, with lower case a,b,c and d standing in for the digits of the year, like these...
Code:
a^(b/c)-d ((a+b)/c)^d (a*c)-(d/b) a^c/b^d ab+(c*d)
The AST nodes and values or terms used to evaluate the expressions are each simple structs returned by the various handlers. They have in common that they are created frequently, used quickly then forgotten. To simplify their management we create a small static array of each struct type with an associated index, then assign pointers and initialize them sequentially on demand. When the index reaches the end of the array it is pointed back to the beginning, so that we use the elements in round-robin fashion and never have to concern ourselves with disposing of them - they are simply reinitialized when needed.
I have also added the ability to specify a range of years to be evaluated, and several different output data formats which make it easy to summarize the data, or to drill down to see the expressions as they are evaluated, even those which fail.
I included a file of about 150 expressions which together produce a fairly complete set of results for most years, as measured by comparison with the programs which produce exhaustive result sets.
It is also fast, able to evaluate all of those expressions and generate totals for all 10,000 four digit years in about 37 seconds on my old 32 bit laptop, with which I am well pleased!
There are always improvements that can be made, and that is certainly true of this little program! But those interested should find it at least readable and functional, and I hope those following this little puzzle will find it useful - maybe even fun to play with.
I have named the file with a .txt filename extension for upload - simply rename it to years.tar.gz and untar it.
Update 2/17: Updated code now serving... years_minimal_v1.0.2.tar.gz.txt
This archive includes most recent code, with all known errors fixed, plus the first verified complete expressions set. This archive also includes a minimal set of expressions which produces all totals for all years, derived from "complete" expression set by identifying all which produced no change in totals when removed. There are now 176 expressions in the set, see comments at top of that file.
There is a simple README included to get you started, additional information and simple build instructions included in comments at top of the years.c file. And of course a --help feature.
Enjoy!
PS - From the data generated during tests we get this graph of the distribution of total results by number of years (the data are in the tarball, updated for complete_v1.0.2, includes all known solutions):
Note that there are no years with 100 or all 101 solutions, nor with 2, 3, 5, 6, 7, 8, 10 or 12 solutions, produced by the current set of expressions - fertile ground!
Total Comments 0
