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.

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 11: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 paragraphs, 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.

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