Latest LQ Deal: Latest LQ Deals
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org New Year Puzzle and fun programming challenge
 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

02-13-2019, 01:15 AM   #121
astrogeek
Moderator

Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_10{.0|.1|.2}
Posts: 4,948
Blog Entries: 11

Rep:

Quote:
 Originally Posted by Beryllos At first I thought one would need to use every possible expression. It turns out that the New Year Puzzle can be solved with a much smaller subset. This is a very interesting discovery. I wonder what the minimal set is.
Thanks for a very nice comparison, and comments.

Indeed, that is the question, "What is the minimal set of expressions which will generate every possible solution?".

I think that the combination of our approaches can ultimately find the answers to that question. I say answers because I suspect there are more than one subset of expressions which will generate all solutions. Which expression generates which solution for which year depends heavily on order of evaluation, more so for some expressions than others.

To find those subsets we must first know what the set of all possible solutions actually is! Yours and dogpatch's code should answer that question as definitively as possible for us. Then, knowing that, my own code should allow us to quickly evaluate different subsets of expressions which generate that known, or agreed, complete solution set. That is more or less the path I am on.

I currently have 183 expressions in my master set and it generates all solutions identically for the range 2000 thru 2999, plus every other smaller range I have spot checked so far. I have not yet used either of your code to try to generate the full ten thousand years as I have done with my own - permuting all expressions for all years will take much longer to run than I have yet done. But as we all seem to be generating such similar results, perhaps it is time to generate a complete master list. Have either of you done so with your code?

Updated: Make that 170 expressions, all included in the latest version v1.0.2 of code now avaliable through my related LQ blog page.

Last edited by astrogeek; 02-13-2019 at 03:53 PM. Reason: Update

1 members found this post helpful.
 02-14-2019, 02:46 AM #122 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_10{.0|.1|.2} Posts: 4,948 Blog Entries: 11 Rep: I have now updated and uploaded the latest version of my code, bundled with the first set of expressions verified to generate exactly the same complete result set generated by the exhaustive RPN code (v3.0.1) of member dogpatch. This has been verified by 100% year by year comparison from 0000 thru 9999. The code archive includes the complete result totals for all ten thousand four digit combinations. This is an exciting milestone to reach, being the first minimal expression set known to generate all currently known solutions. There are 194 expressions in the set, which likely includes some overall redundancy, certainly many overlapping subsets. I have updated the code tarball on my related blog page for those interested. 2 members found this post helpful.
02-14-2019, 08:46 PM   #123
dogpatch
Member

Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 352
Blog Entries: 2

Rep:
Quote:
 Originally Posted by astrogeek I found one expression generated by yours which appears to be mishandled, and unique, however: Code: ```year = 2236 23 = 2^(23/6)```
Good catch, but - weird - have tried to reproduce this, even trying to revert to some old code, but cannot solve 23 for year 2236 with any expression. This bug ought to have falsely elevated my totals for 2236, (and 2326, etc) and overall exhaustive run totals. Well, since i cannot reproduce the anomaly, i will assume it was an unnoticed bug in resolving fractional powers, which has since been corrected.

Quote:
 Originally Posted by Beryllos I made a chart showing how expressions look in these different representations: Attachment 29777
Thank you Beryllos. Will hold on to this comparison chart as a reference tool for expression evaluation techniques.

The leading negation operation continues to vex me, not in producing valid equations, but in converting to an arithmetic expression with adequate but not superflous parentheses. For example,
Code:
`38 = 6--2^(2+3)`
evaluates correctly, but needs parentheses around the -2. Conversely, in this expression
Code:
`81 = ((-1-0)/(-9))^(-2)`
the parentheses around the -9 and -2 are not needed.

As astrogeek has pointed out, these leading negative signs are rarely, if ever, needed, anyway. The above two examples can easily be solved without using leading negative signs, and only show up if the user selects for long (verbose) expressions, (-v when run from the command line). Which leads me to this:

Quote:
 Originally Posted by Beryllos One really big difference in astrogeek's approach is that he didn't fall back on the brute-force "exhaustive" approach, trying all combinations and permutations of operations. At first I thought one would need to use every possible expression. It turns out that the New Year Puzzle can be solved with a much smaller subset. This is a very interesting discovery. I wonder what the minimal set is.
If i were to attempt to generate a minimal set of expressions, would that mean the minimal set to solve for all solvable values? I think that means 46978 total equations for years 0000 through 9999, many of which use the same expression in terms of digits a,b,c,d. So, the total number of expressions would be very much smaller than 46978. Or ought it be the minimal set which generates valid solutions? That number might be much bigger.

Specifically, i am confident that i can solve for the exact same 46978 values without ever employing leading negative signs. But eliminating those from the list might eliminate some interesting expressions, especially where the user selects for complex or lengthy equations.

Or - are you only interested in the minimal set for year 2019?

Meanwhile, i'd still like to try getting my parenthesizing logic fixed up, especially for terms with leading negation. Will try to work on that between now and my next posting here, probably studying both Beryllos' and astrogeek's code in doing so.

1 members found this post helpful.
02-14-2019, 08:51 PM   #124
dogpatch
Member

Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 352
Blog Entries: 2

Rep:
Quote:
 Originally Posted by astrogeek There are 194 expressions in the set, which likely includes some overall redundancy, certainly many overlapping subsets.
Oh.

Just 194? And that includes redundancy? Who'd a thunk it?

1 members found this post helpful.
02-15-2019, 01:50 AM   #125
Beryllos
Member

Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 480

Original Poster
Rep:
Quote:
 Originally Posted by dogpatch ... If i were to attempt to generate a minimal set of expressions, would that mean the minimal set to solve for all solvable values? I think that means 46978 total equations for years 0000 through 9999, many of which use the same expression in terms of digits a,b,c,d. So, the total number of expressions would be very much smaller than 46978.
Yes, that is the minimal set that I am thinking about.

Quote:
 ... Or ought it be the minimal set which generates valid solutions? That number might be much bigger.
Not a lot bigger. I am in the process of sorting out the expressions. Without leading negative signs, there are 683 unique expressions. A lot of those are redundant in the sense that they are algebraically equivalent and obtain the same values. Here are two examples of redundant sets:
Code:
```a-(b+c)-d
a-(b+c+d)
a-b-(c+d)
a-b-c-d```
Code:
```(a+b)*cd
ab*(c+d)```
If we just pick one from each set of equivalent expressions, about half of the 683 expressions are eliminated. I'm still working on this and I'll have more to report soon.

Edit: I forgot to say, at some point I'll add leading negative signs and see if that opens up any new solutions.

Further edit: I had some wrong numbers, now corrected.

Last edited by Beryllos; 02-15-2019 at 08:42 AM. Reason: corrected some wrong numbers

1 members found this post helpful.
 02-15-2019, 12:32 PM #126 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 480 Original Poster Rep: In case anyone wants to use my expression lists, I'm posting 3 files here. Between them they include all valid expressions having no leading negative signs. The first file contains 336 expressions which I have determined (aided by software) to be algebraically unique: expressions-algebraically-unique-preliminary.txt. The second file contains 29 expressions which I have not been able to sort as either unique or redundant: expressions-uncertain-whether-algebraically-unique.txt. The third file, which you can safely ignore, contains 318 expressions that are equivalent to expressions in the other files: expressions-rejected-as-not-algebraically-unique.txt. The file contents are not sorted in any sensible order. Well, actually the order is software-determined. Briefly, this is how I designed the program to help me to find redundant/equivalent expressions: Begin by generating a numerical signature for each expression, based on its results for all 24 permutations of the year 2357. All results are taken without regard to integer or range status. All errors (divide by zero, overflow, or invalid power) are set to the invalid fraction 0/0. The 24 fractions are put in a python list, the list is sorted first by numerator and then sub-sorted by denominator. The sorted list is taken as the signature for that expression. The expressions are then sorted by signature. Expressions sharing the same signature are considered probable matches and printed by groups to a text file. Visual inspection confirmed that all expressions in each group were algebraically equivalent. (I couldn't figure out how to determine symbolic algebraic equivalence by software.) From each set of equivalent expressions, I picked the one I liked the best and moved it to the "unique" file using a text editor. All the expressions in the "uncertain" file shared the same signature of all zeroes, indicating that there were no valid numerical results for any permutation of digits. From that set, I was able to identify some equivalencies and moved 10 redundant expressions to the "rejected" file, but none were moved to the unique file. So that's what I have for now, and I'll be moving on to other fine points of the New Year puzzle. 2 members found this post helpful.
 02-15-2019, 02:13 PM #127 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_10{.0|.1|.2} Posts: 4,948 Blog Entries: 11 Rep: Thanks, that will be interesting to sift through! I have reduced my list somewhat, but do not have it refined enough to post yet. I found four outright duplicates in my file (easy to find with uniq -c) which reduces it to 190 expressions, plus I have found small subset which seem to overlap others such that removing them does not change any of the totals, only the exact expressions used for some of the solutions. I have not yet worked out way to automate or accelerate the process of minimizing the list, so doing it all by eyeball and best guess at the moment. I have automated comparison of your (v6) yearly totals against the set produced by dogpatch's and my code. Yours with python3 on my old hardware is roughly 1500 times slower (granted, it is doing a lot more too!), which is why I initially compared with dogpatch's code. At this time I am in the 5000+ year range (beginning with year zero) and have found not a single different total from yours, so well on the way to having a yearly total set which all three methods agree on. I have also been exploring some avenues which caught my attention for various reasons while working out my expression set - one in particular which has produced some very interesting and unexpected results is "How many ways to produce 81?". Answer: 81. If we suppress absolute value on results and ask for only exact solutions, answer: 81. Good thing we are not mystics! 1 members found this post helpful.
02-15-2019, 07:25 PM   #129
astrogeek
Moderator

Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_10{.0|.1|.2}
Posts: 4,948
Blog Entries: 11

Rep:
Quote:
Thanks for the update, I have downloaded and will have a look.

As for your expressions being OK, I think they are! My final run of Beryllos v6, 9000 - 9999, just completed and I find zero differences between your v3.0.1, my own v1.0.2 using the "complete" expression set, so all three approaches are in agreement on what constitutes a complete set of solutions for all 10,000 four digit years! I can supply the individual results if interested, but they look exactly like the tenkyears_complete file in my last uploaded archive, but in 100 year batches for yours, and 1000 year batches for Beryllos. For my own uses, that is now the standard for checking result totals.

Thank you for your kind comments, especially about my C code, very much appreciated! My style has always been a little different than most, and I have not coded much C in recent years, so such a comment coming from someone who actually knows what they are doing is high praise indeed! It has been fun!

And agreed on thanks to Beryllos for starting this thread and teaching us all the true path to fractional enlightenment! And thank you for your own great efforts, without which our "tripod" of results would not be so stable!

I am now considering my own math code essentially frozen, although I may add a few more output filtering functions to help with sifting. My focus now is on producing a true minimal set of expressions which will produce the same solution set as above.

I am considering inserting all the results into a relational database and doing the search and correlation work with queries. I think that would not require a great effort and would certainly cast the search and correlation into a standard mould, SQL, rather than endlessly generating and filtering results.

Would that be useful to either of you?

Last edited by astrogeek; 02-15-2019 at 07:31 PM.

1 members found this post helpful.
 02-17-2019, 11:20 PM #130 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_10{.0|.1|.2} Posts: 4,948 Blog Entries: 11 Rep: A brief update - I have now uploaded the v1.0.2 code set (unchanged), bundled with a minimal set of expressions which still produces the same totals for all years as the previous complete set. The minimal set was produced by removing all expressions from the complete set which produced no change in any total upon removal. The removed expressions are commented at top of the minimal_v1.0.2.txt file, leaving a total of 176 active expressions, all of which are necessary to produce the complete totals. I doubt this is the only such set that could be identified, but it is the one which results from my previous complete set, ordered, as the initial set. A different ordering or different initial set would likely produce a different minimal set. I have done some simple comparisons against Beryllos' posted algebraically unique expressions set, but have not noted any special correlations worth commenting on at this time. 1 members found this post helpful.
 02-23-2019, 02:43 PM #131 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 480 Original Poster Rep: I have a few developments to report, which I'll break into three or four posts. I confirmed that my program gives the same yearly totals, for all years 0000-9999, as those of astrogeek and dogpatch. This is reassuring and it suggests we are not missing any results. To test expression sets, I worked out a relatively simple method in bash to generate the set of 4-digit years excluding permutations (called "combinations with replacement"). The script below shows how I used that method with astrogeek's program: Code: ```for y1 in \$(seq 0 9) do for y2 in \$(seq \$y1 9) do for y3 in \$(seq \$y2 9) do for y4 in \$(seq \$y3 9) do ./years -f expressions.txt -F -n \$y1\$y2\$y3\$y4 done done done done | cut -d' ' -f5 | awk '{s+=\$1} END {print s}'``` In actual practice, I put all that together on one line. The cut and awk commands at the end extract the yearly totals and add them up, producing the following output for a complete set of expressions: Code: `46978` I know that astrogeek's program can calculate the grand total over a range of years: Code: ```./years -f expressions.txt -F -r 9999 -g -n 0000 ... 720970``` but it turns out that eliminating the permutations speeds things up a lot. That should be surprising. I would have thought my script wouldn't be so fast because it has to load the executable program 715 times (once for each year tested), but apparently that system overhead is not much of a penalty. Anyway, in a simple timing comparison, the script in the first example ran in 3.354s, and the single command in the second example ran in 46.686s, which is roughly proportional to the number of years calculated (715 vs. 10000). Thank you, astrogeek, for a very fast and flexible program! I have enjoyed using it. 1 members found this post helpful.
 02-23-2019, 04:01 PM #132 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 480 Original Poster Rep: I thought for a long time about how to introduce leading negative signs into my program, and I was hitting a wall there, but I recently had a great insight: A leading negative sign on a digit, or on any term, is the same as prepending the operation 0-. So, for example, the following two expressions are the same: Code: ```9-(-4) 9-(0-4)``` If we are dealing with a larger expression, just put 0- in front of the whole thing, with parentheses as needed: Code: ```(a+b)^(-(c-d)) (a+b)^(0-(c-d))``` This is very good because the latter expressions can be calculated in a way very similar to the calculations we have been doing all along. In fact, my evaluate_recursively function can calculate these with no modifications at all. All I have to do is feed it the modified expression. I wrote an expression modifier function that takes the original expression code and builds it up with optional negative signs everywhere that they can be fit, which is 7 places. Here is an illustration: Code: ```a-b*(c-d) 0+((0+a)-(0-((0+b)*(0-((0+c)-(0-d)))))) ^ ^ ^ ^ ^ ^ ^ 7 extra signs``` Bear in mind that in my program, the expressions do not originate in that format, nor are they used in that format. Internally the above expression would be represented as 3 lists separately containing digits, operations, and order of operations. Then, in the tradition of brute forcing, I added a loop to go through all 128 combinations of + and - signs. It works, but it sure is slow! Results: In this way I am testing each expression and looking for any new results over all 4-digit years. I am about 1/3 of the way through my list of expressions, and so far I haven't picked up any new results. Last edited by Beryllos; 02-23-2019 at 04:05 PM. 1 members found this post helpful.
02-24-2019, 01:44 AM   #133
astrogeek
Moderator

Registered: Oct 2008
Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_10{.0|.1|.2}
Posts: 4,948
Blog Entries: 11

Rep:
Quote:
 Originally Posted by Beryllos I have a few developments to report, which I'll break into three or four posts. I confirmed that my program gives the same yearly totals, for all years 0000-9999, as those of astrogeek and dogpatch. This is reassuring and it suggests we are not missing any results.
Thanks for your own confirmation of the totals. It is very reassuring that all three code methods produce the same result set, and that now all three authors of that code have independently expressed satisfaction with that result.

With a mutually agreed complete solution set, I have moved focus from the code to analysis of the results, and like you am also trying to find any avenue that might yield a few new results, or any additional insights into the behavior of the expressions and the digits. That effort has been very fruitful indeed, this past week!

Like yourself, I have found that I must organize it all across more than one post! To avoid posting a wall of text in the thread, I have been working on a set of related pages in my LQ blog, but have not completed those yet... hopefully within the next day or two.

Quote:
 Originally Posted by Beryllos it turns out that eliminating the permutations speeds things up a lot. That should be surprising. I would have thought my script wouldn't be so fast because it has to load the executable program 715 times (once for each year tested), but apparently that system overhead is not much of a penalty. Anyway, in a simple timing comparison, the script in the first example ran in 3.354s, and the single command in the second example ran in 46.686s, which is roughly proportional to the number of years calculated (715 vs. 10000).
I am very surprised at that difference! The original program only worked on single years, so it did not matter which permutation it started with, it simply worked through all unique permutations of the four digits it was given - every year is just a permutation of one of those 715 unique combinations anyway. When I added range handling I considered limiting to the combinations again, but it still seemed somewhat at cross purposes with what I saw as the intended use.

Wrapping it in a script to feed it the combinations as you have done is an excellent way to extend it to meet your own use case! Bravo! And seeing that speed difference I may reconsider incorporating that as a general option in future!

As it happens, I have modified it to make use of the combinations in a different way altogether, which will be the subject of one or two of those upcoming blog posts!

I am delighted that you are getting some use out of my little program, and appreciate your comments!

Last edited by astrogeek; 02-24-2019 at 02:20 AM.

1 members found this post helpful.
 02-24-2019, 09:57 AM #134 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 480 Original Poster Rep: Breaking news: My brute-force (exhaustive) search has found two new results so far: Code: ```year 2278: 58 = 8*(7+2^(-2)) = a*(b+c^(-d)) year 2288: 62 = 8*(8-2^(-2)) = a*(b-c^(-d))``` and it is so far about 60% through the list of all valid expressions (396 out of 683). Last edited by Beryllos; 02-24-2019 at 09:58 AM. 2 members found this post helpful.
 02-24-2019, 10:51 AM #135 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 12,241 Rep: nice.

 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 10:59 AM.

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