Welcome to the most active Linux Forum on the web.
 LinuxQuestions.org [SOLVED] New Year Puzzle and fun programming challenge
 User Name Remember Me? Password
 Programming This forum is for all programming questions. The question does not have to be directly related to Linux and any language is fair game.

Notices

 05-11-2019, 11:21 AM #181 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 418 Blog Entries: 4 Rep: 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. 2 members found this post helpful.
 05-17-2019, 03:53 PM #182 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 418 Blog Entries: 4 Rep: 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) a.b/(.c/d)``` are obviously equivalent. In this case, the introduction of decimal points added no new solutions, nor does it affect the ordering of the digits or any other significant variableness. So, in compiling both a minimum list of expressions, and a more inclusive 'concise' list, my list compilation logic would prefer the former, simpler expression, and discard the second. In considering these two less obviously equivalent expressions Code: ```(a+b)*.c+d a+(.b+.c)*d``` it's more of a toss-up, perhaps the former selected as being somewhat briefer, or perhaps both retained in the 'concise' list for purposes of variableness in the ordering of digits. But there are other more interesting cases. For example, the whole-number expression Code: `a^-b-cd` is practically useless for the 2019 Challenge. It cannot yield a positive integer, and the only way it can yield a negative integer is if 'a' were '1', or either a or b were zero, in which case b's leading negative sign turns out to be meaningless. But by introducing a single decimal point Code: `.a^-b-cd` it becomes a quite useful expression. Replacing '.a' with '.1', '.2' or '.5' ('.0' is disallowed) and 'b' with a non-zero digit, this expression can provide a nice variety of positive integer values, quite possibly some of them new solutions. (As a matter of fact, this very expression is needed in the exhaustive run for at least 23 of the 53534 solutions.) 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` just so that it would give the prettily ordered equation Code: `14 = .2^(0-1)+9` for the home year 2019, even though it was not strictly needed. 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:exp.dot.lists.h.txt 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. 1 members found this post helpful.
 06-19-2019, 02:57 PM #183 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 418 Blog Entries: 4 Rep: Have posted my chaotic history of generating expression lists at my LQ blog: Building expressions lists - 1 Building expressions lists - 2
 01-02-2020, 10:16 PM #184 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 525 Original Poster Rep: 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! 2 members found this post helpful.
 01-06-2020, 01:44 PM #185 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_12{.0|.1} Posts: 5,420 Blog Entries: 11 Rep: 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)? 2 members found this post helpful.
 01-08-2020, 12:12 PM #186 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 418 Blog Entries: 4 Rep: Thanks to both 2 members found this post helpful.

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is Off HTML code is Off Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post LXer Syndicated Linux News 0 10-27-2017 11:54 AM LXer Syndicated Linux News 0 06-19-2011 03:50 PM General General 6 06-25-2010 06:35 AM Simon Bridge General 6 08-26-2007 07:46 PM

LinuxQuestions.org

All times are GMT -5. The time now is 02:47 AM.

 Contact Us - Advertising Info - Rules - Privacy - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -