LinuxQuestions.org
Welcome to the most active Linux Forum on the web.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
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


Reply
  Search this Thread
Old 05-11-2019, 11:21 AM   #181
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 418
Blog Entries: 4

Rep: Reputation: 182Reputation: 182

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.
Old 05-17-2019, 03:53 PM   #182
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 418
Blog Entries: 4

Rep: Reputation: 182Reputation: 182
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.
Old 06-19-2019, 02:57 PM   #183
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 418
Blog Entries: 4

Rep: Reputation: 182Reputation: 182
Have posted my chaotic history of generating expression lists at my LQ blog:
Building expressions lists - 1
Building expressions lists - 2
 
Old 01-02-2020, 10:16 PM   #184
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 525

Original Poster
Rep: Reputation: 317Reputation: 317Reputation: 317Reputation: 317
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.
Old 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: Reputation: 3369Reputation: 3369Reputation: 3369Reputation: 3369Reputation: 3369Reputation: 3369Reputation: 3369Reputation: 3369Reputation: 3369Reputation: 3369Reputation: 3369
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.
Old 01-08-2020, 12:12 PM   #186
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 418
Blog Entries: 4

Rep: Reputation: 182Reputation: 182
Thanks to both
 
2 members found this post helpful.
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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



Similar Threads
Thread Thread Starter Forum Replies Last Post
LXer: Minilens Fun Open Source Puzzle Platform Game LXer Syndicated Linux News 0 10-27-2017 11:54 AM
LXer: SpaceChem, One of the Best Indie Puzzle Game Released this Year for Linux LXer Syndicated Linux News 0 06-19-2011 03:50 PM
Puzzle Challenge: Collecting lots of files from many people? General General 6 06-25-2010 06:35 AM
<fun> The Windows Crash </fun> Simon Bridge General 6 08-26-2007 07:46 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

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

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Open Source Consulting | Domain Registration