[SOLVED] New Year Puzzle and fun programming challenge

ProgrammingThis forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices

Welcome to LinuxQuestions.org, a friendly and active Linux Community.

You are currently viewing LQ as a guest. By joining our community you will have the ability to post topics, receive our newsletter, use the advanced search, subscribe to threads and access many other special features. Registration is quick, simple and absolutely free. Join our community today!

Note that registered members see fewer ads, and ContentLink is completely disabled once you log in.

If you have any problems with the registration process or your account login, please contact us. If you need to reset your password, click here.

Having a problem logging in? Please visit this page to clear all LQ-related cookies.

Introduction to Linux - A Hands on Guide

This guide was created as an overview of the Linux Operating System, geared toward new users as an exploration tour and getting started guide, with exercises at the end of each chapter.
For more advanced trainees it can be a desktop reference, and a collection of the base knowledge needed to proceed with system and network administration. This book contains many real life examples derived from the author's experience as a Linux system and network administrator, trainer and consultant. They hope these examples will help you to get a better understanding of the Linux system and that you feel encouraged to try out things on your own.

Click Here to receive this Complete Guide absolutely free.

I suspect the absolute value is responsible for at least some or most of that difference.

I would be very interested in comparing all three minimal sets to see just how different they actually are. If your two sets turn out to be equivalent, and if the differences with mine can all be accounted for by the absolute value operation, that would be a very interesting and meaningful result indeed!

... It's interesting that your method handles both irrational and imaginary numbers...

To be perfectly accurate, it only handles imginary and real rational numbers. I think it would still require floating point math to handle irrational numbers (such as pi or trig functions).

... and, Yes, i believe you are correct in saying that only muliplication, division and power operations could work two or much such terms back to a real number. May have to noodle about this a bit more.

Last edited by dogpatch; 03-27-2019 at 05:43 PM.
Reason: add 2nd paragraph

To be perfectly accurate, it only handles imaginary and real rational numbers. I think it would still require floating point math to handle irrational numbers (such as pi or trig functions).

Ah, well, I was thinking of certain fractional powers which are irrational, like 2^(1/2), which is sqrt(2). You are right that pi cannot be represented as (a/b)^(c/d) with integers a,b,c,d.

Ah, well, I was thinking of certain fractional powers which are irrational, like 2^(1/2), which is sqrt(2). You are right that pi cannot be represented as (a/b)^(c/d) with integers a,b,c,d.

Of course. I was forgetting that fractional powers are also irrational numbers.

The two numbers following the expression is the fractional key used for rating and sorting. The denominator of this fraction is the lowest number of expressions sharing the same solution. Naturally, all expressions in this list have a denominator of one, since all are required by at least one solution. The numerator is the number of times the expression is thus used (in this case, the number of times the expression is required). The third number is the total number of times the expression could be used in an exhaustive run. The fourth number is simply the sort order, or index.

The above 'NP-Complete' link talked about an 'Amazing Computer' approach when facing a challenge like this. So i began thinking that my native computer ought to be more fully involved. That is, my frontal lobe assisted by my visual cortex.

So i worked the minimum equation matrix via brute force programming to where i had 135 expressions providing 46469 solutions. That left me with 511 unsolved values which i found could be solved with 273 expressions. That is a matrix, i thought, that my visual cortex can comprehend. So i wrote a php script to portray the 511x273 bitmap as an html table. Added javascript to enable me to cherry-pick one expression at a time, and see how that affected the rest of the matrix.

It was almost like playing Concentration on my 'puter. Had some fun trying first this combination, then another. but always ended up having to select many expressions that could only add one value to the solution set. Result: needed 58 expressions to solve the 511. 135 + 58 = 193!

Started over with 154 expressions to solve 46822, leaving 158 unsolved. Reconfigured my html table, played the game some more, easier now, because the matrix smaller. Result: 39 new expressions. 154 + 39 = 193!

Now have several lists of 193 expressions, each one slightly different. Which is to say that i seem to be stuck on 193 as the mimimum number of expressions to solve all 46980 values. And stuck i will remain. Depending upon what Beryllos comes up with, i think astrogeek wins.

Continuing to slowly develop general math routines using fractional-exponential integer structures, and have started to include decimal values, a little bit like Cobol implied-decimal integer math. Only a bit like Cobol. Am using the exact same fractional-exponential structure as before; a number containing a decimal point simply has a power of 10 as its denominator. So, for example, 15.27 is stored as (1527/100)^(1/1)

Anyway, the natural place for me to start testing decimal point integer math was the 2019 Challenge. My math routines should handle a wide variety of valid decimal point numbers, but for the 2019 Challenge test, I restricted myself with these new rules:

- Allow (but not require) a single decimal point in any of the numeric values.
- A single leading zero is allowed (but not required) preceding the decimal point.
- At least one non-zero digit has to follow it, with no trailing zeroes.

So, both "0.2" and ".19" would be allowed, but not "2." nor "2.0". Some acceptable equations for year 2019 are:

Notice that these represent new solved values over the original rules. In fact, employing the above decimal point rules increases the solved values to 59 for year 2019, and the exhaustive run to 54481 total equations (7501 additional). Not only that, but am now getting all 101 solutions for 28 of the 715 4-digit numbers, 648 of the 10000 permutations. Am not sure whether these are stable numbers. Probably one of you could improve on them.

Unfortunately, this has also increased my 2019 Challenge run times by a factor of about 20 times slower, and, I suppose, would add a great complexity to the generating of valid expressions, and a new minimum expression list (which I've not yet attempted). So, before you hurl curses at me, let me add that I am not formally introducing this idea as a new challenge, but mostly just reporting on my progress re. algebraic expression evaluation and the use of fractional-exponential integer math, which began for me with this thread.

I have dived deep into finding true minimal cover sets with a few interesting results, but have been interrupted by life and have not wanted to spam the thread with my ill-considered and incomplete results. I hope to return to the fun soon.

Interesting however, that my (incomplete) attempts to apply the cover set approach to finding any smaller set for the total solutions showed nothing hopeful below 193 expressions. Also, I made a set of expressions derived from my set of 178 which produces all results without the absolute value rule applied - it has 193 expressions in it. I will not try to guess at this point how meaningful that result may be - but we all seem to be hitting the very same wall!

Applying my cover set queries to individual combinations has been successful in finding smaller sets than found by the previous approximate method for about half those tested. I had improved the methed to produce a first hit much more quickly, getting the 2019 result down to about 4 seconds from about a minute. However, about the time I was interrupted I had completely filled a hard drive with approximately 2 billion partial sets evaluated in 4 hours without a single completed minimal set for one ordinary looking combination (I think it was 2049, but not certain at the moment). So the NP-complete nature of the problem does assert itself! This too is an interesting and useful result.

I have to admit a continuing interest in development of fractional math routines beyond the newyear puzzle, so will follow your lead if/when that time comes around!

astrogeek and dogpatch, inspired by your recent posts, I have gotten back to work on this, and finally stumbled across a reliable method for identifying most of the expressions in the minimal set.

I wrote (offline) a detailed description of the method, but it's too long, so I'm going to give the highlights in this post, and attach the full text here: beryllos-LQ-2019-04-24.txt

(1) Generate a list of all possible expressions. Extra negative signs are not a problem. In my programs, the full list contains 2374 expressions.

(2) For each result, that is, each whole number 0-100 in each year 0000-9999, list all expressions that can yield that result. I'll call these "solution sets."

(3) Eliminate empty sets and duplicate sets.

(4) Now we start to identify expressions which are necessary to the minimal set... The obvious place to start is with solution sets that contain only one expression. If a specific result can only be obtained by one expression, then that expression must be in the minimal set.

Here is my big breakthrough: That rule may be generalized by identifying sets of expressions that always appear together, for example, algebraically equivalent expressions. If a specific result is obtained by one of those expressions, it could be obtained just as well by one of the others... (more on that in the first attachment).

In the language of sets, equivalent expressions constitute a subset which is either all or none in every solution set.

I use that idea in the following algorithm:

Pick one solution set, and let's call it the trial set. We can pick any solution set, we will eventually try all solution sets, and the order in which we try them does not matter.

Compare the trial set to all the other solution sets. If, in every case, the trial set is either a subset (all elements in common) or is disjoint (no elements in common), then we know the trial set contains only equivalent expressions.

Then we may choose any one of those expressions for the minimal set, and eliminate all solution sets which contain any of those expressions.

If the trial set fails the test even once, that is, if in any case it is neither a subset nor disjoint, we leave it in the collection of solution sets (we do not eliminate it) and we pick another trial set.

Keep doing this until we have tried every solution set.

Before actually trying this approach, I had no idea how far it would go, and didn't see any reason to be optimistic. So you can imagine my surprise that it found 189 expressions that have to be in the minimal set.

(5) There is another trick, however, which allows us to grab one more equivalent set... (more on that in the first attachment).

(6) Following that, we are left with 7 solution sets, containing 19 different expressions. The brute-force search tries them in all combinations of 1, 2, and 3 expressions. The condition for a complete solution is that at least one expression in the combination is present in each solution set. Various sets of 3 expressions satisfy this condition.

I'll tidy up my python programs and post them in the next day or two.

After that, I intend to try it with the absolute value option. Assuming the algorithm works similarly well, that would be an independent validation of astrogeek's minimal set of 178.

Last edited by Beryllos; 04-24-2019 at 06:52 PM.
Reason: small clarification

Have downloaded both of your (Beryllos') last uploads. Your approach, while differing in details, is quite similar to my own. The mimimum expression list also similar, but not exactly. Looked at one of my lists of 193 expressions and compared with your list w/ alternatives, carefully checked off equivalent expressions found in both lists. In most cases each expression in my list was found in yours as well, and vice-versa. In a few cases, the expression didn't match exactly, but that was due to a different use of parentheses.

In six cases, I could find no exact algebraic match between the two files. Two expressions might very well solve the very same values, depending upon the values of the variables, especially depending upon the oddness or evenness of the two parts of a power operation. For example, the expression -a^b+c^d might solve the same values as a^b+c^d or a^b-c^d, depending upon whether b or d is even or odd.

This kind of discrepancy between the two lists was not a surprising discovery, since I'd already noticed such differences and near-equivalencies between my various lists of 193. I think what is happening here is that, in solving for all 46980 values, the six (in this example) 'disputed' expressions in each list each solve for slightly different values than any expression in the opposing list. But when taken as a whole, the collection of six expressions as a whole covers the same equations as the collection of six in the opposing list. And, between any two lists, there may be, not six, but 4 or 8 or 9 such 'disputed' expressions.

And maybe - just maybe - there might yet be a list of fewer than 193. I'd love to see such a list. Would love to see as well astrogeek's list of 178, using absolute value.

Of course, i may be completely missing something here. If so, please strighten me out.

@dogpatch, after reading your post, I looked closer at the alternative expression groups in the minimal set I posted. While many of those groups are indeed equivalent, I found several which are not. For example, the list I offer for expression 181 includes these:

Code:

(a/b)^(c+d)
(a/b)^(c*d)
(a/b)^(c^d)
# ... and 7 more

Clearly these are not algebraically equivalent. I modified one of my programs to see if they are equivalent in any other way, and the answer is no, they do not share the same solutions over all.

So I incorrectly jumped to the conclusion that all of the groups on my list are equivalent. What can be said more accurately is that each group offers alternative solutions for some New Year Puzzle results. Taking the above group as an example, this particular result is obtained by all 3 expressions:

Code:

year 1127, result 1:
1=(1/1)^(7+2)
1=(1/1)^(7*2)
1=(1/1)^(7^2)

... but another result is obtained by only 2 of those 3 expressions:

Code:

year 1127, result 49:
49=(7/1)^(2*1)
49=(7/1)^(2^1)
but no (a/b)^(c+d)

Therefore those 3 expressions are not functionally equivalent.

The expression group could still make it into the minimal set. It only requires that there be at least one result that can only be obtained by that group of expressions. I will look further into that.

I did some validation of my previous method and results, and now I have greater confidence in my minimal set listing and the number of expressions in it, 193.

I decided to drop one step of my procedure, the step 5 in my post of 2019-04-24, which involved removing expressions which are unshared between "equivalent" groups.

I added some code to cross-check each expression (or group) in the minimal set. It works by finding all the results that can be obtained only by that expression or group. Here is the full report for the case of no leading negative sign (the optional sign in front of the whole expression): beryllos-minimal-set-report-2019-05-02.txt
If we allow the leading negative sign, no new results are obtained, but it does add a few alternative solutions to already-solved results.

As an example from that, here is the report on one of the groups that we were suspicious of, because the expressions are algebraically inequivalent:

Code:

...
expression 179, select one of this group,
which is the only solution to 1 problem, (2226 81),
(a/b)^(c+d)
(a/b)^(c*d)
((a/b)^c)^d
(a/b)^(c^d)
(a/b)^(-(c+d))
(a/b)^(-(c*d))
((a/b)^c)^(-d)
((a/b)^(-c))^d
(a/b)^(-(c^d))
((a/b)^(-c))^(-d)

The notation (2226 81) signifies that the problem is for the year 2226 (or permutations of those digits) and the whole number result 81.

Using another program, we can search for all solutions of that result. (In order to do that, I had to modify an earlier program of mine to handle negative exponents. This program tries all operations in every order with every permutation of the specified digits, and reports all that match the specified value.) Here we see that the results correspond exactly:

In the same way, I manually checked out several other inequivalent expression groups in the minimal set, and spot-checked several more that are algebraically equivalent. I didn't check every expression or group, but that's enough to convince me that my minimal set method is working correctly.

Here are a couple of statistics: Out of the minimal set of 193 expressions or groups, 31 are needed only to obtain single results, like the example shown above. At the other extreme, there is one expression group {ab-c-d, ab-(c+d)} that gets 752 results that cannot be obtained without it.

... And here is a tar-gzip file with all the programs I have used for finding minimal sets. In order to upload it to LQ, I had to append .txt to the filename. Please remove the .txt suffix before unpacking the file. beryllos_newyear_2019-05-02.tar.gz.txt
And here is the README file (same as the one inside the tar) which describes the contents. README.txt

I've used the same methods now to explore the minimal set when the absolute value is taken...

It was pretty easy to modify my programs to handle this case. Mainly I had to put the absolute value in the few places where it calculates the value. The algorithm to identify necessary expressions and groups works just the same.

And the answer is...(drum roll, please)... 178. It turns out that each of the 178 expression groups can be linked to at least one result that can't be obtained without it. That means that every expression is required, and there can be no fewer.

Here are the modified programs, which are all very similar to the originals posted yesterday (packaged as tar.gz, renamed to tar.gz.txt so it can be uploaded here at LQ), beryllos_newyear_abs_2019-05-03.tar.gz.txt

and the README file (same as the one in the tar file): README.txt

I haven't yet compared my minimal set to astrogeek's. I have to believe that they agree, but I'll confirm it soon.

Pretty good rush seeing your confirmation of both minimal numbers 193 and 178. Look forward to studying your extensive work.

Meanwhile, have continued to play with decimal points in algbraic expressions, and using the 2019 Challenge to test and flush out bugs. My latest LQ 2019 program is now producing 54534 equations, 7554 more than the original 46980 totals, and 53 more than noted in my previous post. Still solving all 101 values for 28 4-digit numbers (648 of the 10000 'years' or permutations). All but two of these 'fully solved' 4-digit numbers contain 4 different digits, yielding 24 permutations each. Only '2238' and '2278' contain a repeating digit and 12 rather than 24 permutations. An example of a new solved value (for year 2238):

Code:

85 = .2^-3-8/.2

The best news is that my latest program doesn't run 20 times slower with decimal points. In fact, it runs almost twice as fast! That is, on my slow ancient home computer; have not yet run the new code on the server. The secret turned out to be in creating a list, not only of algebraic expressions, but of their resultant Reverse Polish Notation strings. My current lists contain 1941 expressions, generated as a header file:exp.lists.h.txt

The static list of rpn strings allows the program to fly through any year or the exhaustive run without generating any expressions and with a minimum of error checking. Note how easy it now is to avoid leading zeroes (or trailing zeroes after a decimal point) with the new pre-compiled rpn strings.

1941 expressions is, of course, not even close to being a minimum list. Am content for the present in having a 'concise' list. That is, solving (i think) all possible equations, giving a variety of results based upon user preferences, and with no algebraic redundancies. Were i to create a minimal list, i suppose it would contain over 200, perhaps over 300 expressions, and my program would really fly.

May post more updates at some point. Will probably take this whole thing out of my 'tmp' folder and post a new page w/ source code from within my 'calc' folder, where i also hope to further explore and develop Fractional-Exponential integer math.

LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.