Have just uploaded my latest LQ 2019 Challenge program to http://cyberjerry.info/calc/fx/LQpuzzle.php. Notice it is no longer in my 'tmp' temporary folder. Am calling it version 6.0.000. Versions 4 and 5 never left my home 'puter, but are messy experiments in generating expression lists and in early trials with decimal points. More commented-out code than executable, so never uploaded.
With this upload, have confirmed similar performance improvements on the server; the exhaustive run takes less than 6 seconds! Same totals as in my previous post. Still hope to improve my expression lists for decimal point values, both a better 'concise' list, and perhaps a mimimum expression list. |
1 Attachment(s)
Have continued to play around with expressions involving decimal points, which have provided much greater complexity and some new instances of algebraic equivalence. For example, these two expressions
Code:
ab/(c/d) In considering these two less obviously equivalent expressions Code:
(a+b)*.c+d But there are other more interesting cases. For example, the whole-number expression Code:
a^-b-cd Code:
.a^-b-cd The above and other complexities, and the scope of new possibilities explain how decimal points ended up making my program run 20 times slower. By way of review, my original program generated equations on the fly in the form of Reverse Polish Notation strings. When a dynamically generated RPN string yielded an acceptable value, it was converted to an algrebraic expression and then stored/displayed. So now my latest program follows astrogeek's lead in using pre-generated expressions, and goes one step further in also using corresponding pre-generated RPN strings to valuate efficiently and speedily. No dynamic expression generation necessary, no on-the-fly conversions necessary between RPN and algebraic expressions, and a minimum of validation logic. Fast. This was possible, of course, only after producing adequate lists of expressions. My latest 'concise' list using decimal points contains 1426 expressions, down from 1941, since i've tried to reduce most unneeded leading negative signs and unneeded decimal points where possible. Have also produced a new minimum expression list. Previously underestimated how the increased scope of decimal point equations would affect the minimum number of expressions needed. Using the exact same techniques used to derive 193 expressions for the original Challenge, i could derive no fewer than 485 expressions to yield the full 54534 solutions. (Am not sure, but 54534 solutions and 485 minimum expessions may both be improvable numbers.) The 'concise' list of 1426 expressions is by no means definitive. My previous list of 1941 was a sort of 'garden run' selection, starting with a long list, then programmatically culling where two or more expressions yielded exactly the same solutions. My goal was a relatively brief list to achieve all 53534 solutions, and in which a non-exhaustive but nice variety of equations might be selected according to user preference. My current list consists of a few more refinements, selecting against unnecessary, superflous, or ugly complexity where possible, and also 'cherry-picking' a few favorite expressions for specifically desirable equations for 2019 and a few other select years. For example, i hand-picked Code:
.a^(b-c)+d Code:
14 = .2^(0-1)+9 Ended up putting all lists together in one .h include file. Two arrays of strings, one for algebraic expressions, the other for corresponding RPN strings. Both arrays start with 485 minimum expressions followed by 941 more. The exhaustive run processes only the first 485 (for speed), single year runs process all 1426 (for variety); a simple matter of two different limits in the 'for' loop. Limited to 485 expressions, the exhaustive run on the fast server now processes all 715 4-digit numbers w/ 10000 permutations, generating 54534 solutions in less than 2 seconds. The .h file containing the lists is attached:Attachment 30584 This include file, along with the C program code and current fractional-exponential math routines, are also available as before at http://cyberjerry.info/calc/fx/LQpuzzle.php. What remains someday is to document my methodology for generating the lists, both for LQ and for my own future reference. Right now i will just say that my list-generating methodology was, i think, quite similar to Beryllos', albeit spastic and haphazard, with many dead-ends and detours, much less methodological than his approach. |
Have posted my chaotic history of generating expression lists at my LQ blog:
Building expressions lists - 1 Building expressions lists - 2 |
Wrapping Up the Thread
It has been a year since I started this thread, and half a year since the last reply. We have solved the New Year Puzzle and covered much more besides. I'm going to mark it as SOLVED.
I thank all of the participants, and especially astrogeek and dogpatch, who checked out my programs, introduced me to new ways to look at the problem, developed and shared their own programs, and made it a most enjoyable collaboration. Wishing all a Happy New Year! |
Thanks again for the enjoyable diversion Beryllos!
I left my part of it unfinished and it remains on my to-do list, but the machine I had temporarily dedicated to the tasks had to be repurposed and has not returned to the queue... The solution set for this year is rather small, any new puzzles (I ask with some trepidation)? ;) |
Thanks to both
|
All times are GMT -5. The time now is 08:48 AM. |