[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.
Get a virtual cloud desktop with the Linux distro that you want in less than five minutes with Shells! With over 10 pre-installed distros to choose from, the worry-free installation life is here! Whether you are a digital nomad or just looking for flexibility, Shells can put your Linux machine on the device that you want to use.
Exclusive for LQ members, get up to 45% off per month. Click here for more info.
Am i the only one to do this in C? Anyway, that's how i'm approaching this challenge, since i am not very conversant with bash, and know nothing of python.
As to floating point / fractional inaccuracies, my C program sticks to integers. If the divide operation results in a fraction, i throw it away. Am I thereby missing some possible equations? Perhaps. Perhaps not. My next version step might be to accept interim fractional results and see if i can pick up a few more valid results that way, but am pretty sure i'll try to do that with my own indeterminate-accuracy integer math calulator engine (written in C and Assembly), and not with floating point math.
Another caveat about my approach: i have not done as some here have, to try to generate all possible equations for a given value 0 thru 100. Once my program finds at least one valid equation for a given value, it is satisfied with that, per the OP's original criteria.
What i have done beyond the original challenge is to generate equations for other 4-digit numbers, not just '2019'.
Since my last post, i have not been able to improve upon generating equations for 49 of the possible 101 values 0 thru 100 for '2019'. But i have improved to 97 equations for '1972', and 99 for '1983' and a couple other 4-digit numbers. Haven't (yet) succeeded in solving for all 101 values for a given 4-digit number.
Today i uploaded a php script which executes the C program online in a semi-conversational manner. You may view it here, if interested.
Since my last post, i have not been able to improve upon generating equations for 49 of the possible 101 values 0 thru 100 for '2019'. But i have improved to 97 equations for '1972', and 99 for '1983' and a couple other 4-digit numbers. Haven't (yet) succeeded in solving for all 101 values for a given 4-digit number.
You are doing great. I don't think it is possible for any 4-digit number to make all 101 values. I have heard that 99 is the largest possible, and I am trying to confirm it by running my program for every 4-digit number, 1000 through 9999. This is taking some time with my exhaustive-search approach.
I got the same totals as you for 2019, 1972, and 1983.
Thanks for posting your C program and php script. I'll take a close look at the C later.
I have heard that 99 is the largest possible, and I am trying to confirm it by running my program for every 4-digit number, 1000 through 9999. This is taking some time with my exhaustive-search approach.
I got the same totals as you for 2019, 1972, and 1983.
Hey, if we're getting the same results, we must both be spot on, right?
When you've done your exhaustive search, i'd be interested to compare notes once again. You can see my exhaustive (i think) results on my php script by selecting 4-digit '0000' and then selecting the radio button for 'Totals only'.
By the way, integer math can sometimes go awry as well. Did you know that
Code:
8^7*4^6
(8 to the 7th power times 4 to the 6th power) is equal to zero. That's right! (Hint: it's only a problem with long integers on my 32-bit home system. On the 64-bit server, long integers are not truncated [at that level])
I wrote a series of filters to select one "good looking" expression from the many that my program generates for each value. It may be silly but programming it was interesting. Attached below is the full program (the original math problem with the filters now tacked on at the end): newyear-v5.py.txt
and here is the output for 2019, one expression for each value:
When you do the exhaustive search, you needn't run all 4-digit integers 0000 thru 9999. According to the original specs, you do need to run all permutations of a given 4-digit number: When solving for '0001', for example, you will also try '0010', '0100', and '1000' as permutations that might yield additional equations. Then, when doing the exhaustive run, you needn't solve for '0010', since you've already solved for those 4 digits when solving for '0001'. So, in my exhaustive run from '0000' thru '9999', i skipped from '0009' to '0011', and again from '0019' to '0022', etc. Wound up with 715 4-digit starting numbers, with a total number of 10,000 permutations (of course).
In solving for a number with no permutations, there is no confusion. (The old '4x4' game was simpler). But i've found that, with a 4-digit number with (up to 24) permutations, the order of the digits might affect the way my program generates equations, but the equation count will always be the same. So, for example, if i run my program to solve for '1972', it will generate valid equations for 97 out of 101 values. Likewise, if i run it for '1792' or '9712', it will produce 97 equations for the same 97 values. Since it does not try to find ALL possible equations for a given value, it might print different equations for some values, but the equation count will be the same. For example, the '1972' run might generate
Code:
42 = 91-7^2
while the '1792' run yields
Code:
42 = 71-29
Those are clearly two different equations. Likewise
Code:
64 = 91-27
and
Code:
64 = 71-(9-2)
And many other values give clearly identical equations. But take
Code:
68 = 19+7^2
vs.
Code:
68 = 7^2+19
- are these the same, or are they different equations?
For this reason, am content to simply count the values for which at least one valid equation is generated, and not bother with tallying how many equations can yield the same value. With that approach, am getting identical equation counts for the same identical values, regardless of the order or permutation of the 4 starting digits. Am especially content that this seems to be in accord with the OP's original post.
Quote:
Originally Posted by Beryllos
I wrote a series of filters to select one "good looking" expression from the many that my program generates for each value.
I like the idea of selecting 'good looking' or 'clean' expressions. Have copied your python code, and, with your permission, i may look into converting some of that python code into C. But am not sure i agree with ranking the power operation as least desirable. In fact, my favorite equation so far (solve for '5397') is:
Code:
27 = 9^5/3^7
Is that cool, or what? Don't think i would ever have conceived that equation with my brain.
Hey, we're having fun here - that's the main thing.
I don't quite see how that works out to zero, unless every overflow is replaced with zero.
Edit: On second thought, it is 2^33. I can see how 2^32 would wrap around to zero, but 2^33?
Apparently, any power of 2^32 or greater will leave 0 in the 32-bit register. I would think the carry flag would get set or something, but i'm not really an expert on the inner workings of a 32 bit processor or the GCC compiler. At any rate, that is in fact what i'm getting on my 32 bit machine, that 2^33 = 0 (integer math). I suppose i could catch that in my code by rejecting any zero result for multiplication or power operations in which the operands are not zero.
Last edited by dogpatch; 01-16-2019 at 10:42 PM.
Reason: add 'integer math' parenthesis
But am not sure i agree with ranking the power operation as least desirable. In fact, my favorite equation so far (solve for '5397') is:
Code:
27 = 9^5/3^7
Is that cool, or what?
Very cool. It is totally arbitrary that I chose addition to be "most desirable," but it's a start. One could always change the selection criteria.
I made it a high priority to get the digits in the same order as the year. That looks cool, and it generates some unexpected results. A simple example for 2019 would be 7 = 2*(0-1)+9.
Thanks for pointing out the permutation of year digits. That can save a lot of CPU time.
You two are leaving me far behind now! I have been away from my computer most of the past week and unable to keep up, even if I could!
dogpatch's work on limiting the number of expressions generated, or evaluated is very important I think when you are permuting the digits and the operations.
My own approach only permutes the digits, the expressions are fixed. My emphasis was to limit the expressions to be evaluated by the number of zeroes among the permuted digits.
For all single digit numbers (0001, 7000, etc.) this reduces the number of expressions to a very short list which need not include anything with divisions and only one exponential, if we assume all other digits to be zero. If we allow for a few selected cases where all other digits may not be zero we can greatly reduce the "load" on the remaining cases up front (a-(b+c+d), a*(b+c+d), for example).
Similarly, for all two non-zero digit numbers (7400, 0308, etc.) the list of potential expressions and numeric permutations is greatly truncated (that word continues to work its way in here). Again, assuming all others are zero, but handling select cases where they may not be reduces requirements of fewer zeroes cases.
Three digit combinations require the longest set of expressions to evaluate, but still comprehensible (on the order of 40-ish expressions for all cases I think).
Four non-zero digits require a shorter list of expressions to produce results not obtained by tests for fewer non-zero digits (most will have been already found).
Another thing which reduces the number of evaluations is to realize that the sign of the number produced is irrelevant because you could change it by inverting the sign of any term, which is allowed. So I more or less ignore sign and simply take the absolute value of the result. This can reduce the number of expressions you have to evaluate depending on their order (For a simple example ,if 10-29 evaluates first, then there is no need to eval 29-10).
It will be a few more days before I can return to the party, am looking forward to looking at the new code posted!
Quote:
Originally Posted by dogpatch
Hey, we're having fun here - that's the main thing.
I made it a high priority to get the digits in the same order as the year. That looks cool, and it generates some unexpected results. A simple example for 2019 would be 7 = 2*(0-1)+9.
Cool. Unfortunately, since i am currently ignoring negative interim results (similar to astrogeek's explanation) i can't produce your cool equation (yet).
Really like your idea of getting the digits in the same order as the year, so i have made that my highest priority as well, where possible. My second priority is to select for shorter equations. This should have the effect of selecting in preference of concatenated digits and selecting against parentheses, with one simple test.
Am still probably generating unneeded paragraphs in places. I HOPE i'm not removing needed paragraphs.
My next upgrade, i hope to accept negative interim results. Then, accept fractional interim results. Am still inclined to try this using my own high precision math engine that doesn't employ floating point pitfalls. Too bad i don't have a Cobol compiler; that would be the natural language for something like this: fractional numbers using integer math.
Thanks for posting your latest source code. So far I have given it a quick skimming, and I'll go over it more carefully soon.
Quote:
Originally Posted by dogpatch
... But am not sure i agree with ranking the power operation as least desirable. In fact, my favorite equation so far (solve for '5397') is:
Code:
27 = 9^5/3^7
Is that cool, or what? ...
Let the user decide! I modified my program to allow the user to specify filters from a set of options. A single filter may be applied, or a series of filters in the order specified.
Usage: python3 newyear-v6.py YEAR [FILTERS]
YEAR = non-negative integer, leading zeroes allowed
FILTERS = one or more of the following characters
to guide the selection of arithmetic expressions:
y: digits in year order
c, C: less, more concatenation
r, R: lower-, higher-rank operations
p, P: less, more levels of parentheses
o, O: lower-, higher-rank operations to the left
n, N: smaller, larger numbers to the left
and optionally, as the last filter of the sequence,
f: select the first expression remaining in each group
Each filter selects the expressions which best and equally meet the specified criterion, throws out all other expressions, and passes the subset to the next filter.
Filters are applied sequentially in the order given.
Here are a few short demonstrations:
Select expressions which have lowest-rank operations, and then, of those, choose the first one for each whole number:
First, select expressions which have less concatenation; then from that subset, select those which have less parentheses; from that subset, select those with large numbers on the left; from that subset, select those with higher-rank operators on the left; finally, from that subset, choose the first one:
Whew! I admire your ambition. But don't think i will be adding user ranking options, at least not any time soon.
What i have done is more or less re-write my original program (different source code filename than before), using double precision float numbers in order to do a more complete job. Have picked up a few new equations that i was missing using integer math. But am having a hard time correcting for float inaccuracies. Some previous posts here may point me to some solutions, but i may yet do another re-write and use a more Cobol-like approach, in doing all math operations with integers, but using my own integer math engine with almost unlimited precision. Meanwhile, i give the user the option of trying to round the float to get a few more equations (with some invalid ones). I now see that astrogeek is also doing this challenge in C. Perhaps he can point me to some good ways to correct for floating point inaccuracies?
Just as importantly, i have taken a cue from igadoter, and am now generating RPN-like expressions, which i then evaluate and turn into normal expressions. That has simplified and sped things up, and makes parenthesis placement easier.
Still haven't broken the 49 equation barrier for 2019. My current totals for all 4-digit 'years' are:
715 4-digit numbers (unique combinations of 4 decimal digits)
10000 total permutations of those numbers
46967 total equations (that is, values 0-100 for which at least one equation is generated)
(Min=1 Max=99)
I can increase the total equations to 46982 with my current attempt to correct for float inaccuracies by rounding. Of the 15 new equations generated this way, 4 are invalid, 11 seem OK. An example of an invalid result of rounding would be (for year 4579):
Code:
5 = 4/7^9+5
An example of a valid equation that would otherwise be missed, but picked up with rounding logic (year 1358):
Wow! You guys have been busy while I have been away!
@Beryllos - v6 downloaded and I should be able to catch up over the weekend - but you have left me a lot to catch up on! I had not given enough thought to your early comments on floating point precision and may have dismissed some of your points too easily, or missed them entirely, sorry if I did so. I have had opportunity to refresh my memory on the subject, if not put it to use - more fun for the weekend.
I have not yet tried to use your latest code, but am not clear from the discussion whether the expression ranking produces different results sets...? And the same for your fractional math, did it produce any notably different results sets, or mostly increase the confidence level? Sorry in advance if you have answered those and I have missed it.
@dogpatch - Very nice! As with Beryllos' code, I have not had opportunity to compile yours yet, but have downloaded it and will work through it on the weekend.
Do either of you have one or more example "years" (i.e. any special four digits) which you use to demonstrate behavior of some specific expressions? Similarly, do you have a test case or two which demonstrate pass or fail with or without exact math vs language/platform default behavior?
Thanks for keeping the discussion going!
Last edited by astrogeek; 01-25-2019 at 03:32 PM.
Reason: typo, fixed sentence
Do either of you have one or more example "years" (i.e. any special four digits) which you use to demonstrate behavior of some specific expressions? Similarly, do you have a test case or two which demonstrate pass or fail with or without exact math vs language/platform default behavior?
See the post just above yours for example years for pass or fail equations for my attempt to correct for floating point inaccuracies by rounding. Still haven't devised an acceptable solution, but am working on it. Any tips would be welcome.
And - if you review my sloppy C code, please keep in mind that i've uploaded the source code 'as is', a work in progress.
LinuxQuestions.org is looking for people interested in writing
Editorials, Articles, Reviews, and more. If you'd like to contribute
content, let us know.