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

 01-16-2019, 05:31 PM #61 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 323 Blog Entries: 2 Rep: 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.
01-16-2019, 05:44 PM   #62
Beryllos
Member

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

Original Poster
Rep:
Quote:
 Originally Posted by dogpatch 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.

Last edited by Beryllos; 01-16-2019 at 05:45 PM.

1 members found this post helpful.
01-16-2019, 07:39 PM   #63
dogpatch
Member

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

Rep:
Quote:
 Originally Posted by Beryllos 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'.

 01-16-2019, 07:50 PM #64 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 323 Blog Entries: 2 Rep: 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]) Last edited by dogpatch; 01-16-2019 at 07:51 PM.
 01-16-2019, 09:57 PM #65 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 434 Original Poster Rep: 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? Last edited by Beryllos; 01-16-2019 at 10:01 PM.
 01-16-2019, 10:01 PM #66 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 434 Original Poster Rep: 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: Code: ```\$ python3 newyear-v5.py 2019 0 = 921*0 1 = 20-19 2 = 2+0*19 3 = 12-9+0 4 = 9-10/2 5 = (9+1)/2+0 6 = 9-(2+1+0) 7 = 2*(0-1)+9 8 = 9*2-10 9 = 21*0+9 10 = 20-(1+9) 11 = 20*1-9 12 = 20+1-9 13 = 12+9^0 14 = 10/2+9 16 = 2*(0-1+9) 17 = 19-2+0 18 = 19-2^0 19 = 29-10 20 = 2^0+19 21 = 2+0+19 22 = 21+9^0 27 = (2+0+1)*9 28 = 20-1+9 29 = 20*1+9 30 = 20+1+9 38 = 2*(0+19) 39 = 20+19 44 = 90/2-1 45 = 90/2*1 46 = 90/2+1 64 = (9-1)^2+0 69 = 90-21 70 = 10*(9-2) 71 = 91-20 72 = (10-2)*9 78 = 90-12 80 = 9^2-1+0 81 = 9^2*1+0 82 = 92-10 87 = 90-(2+1) 88 = 90-2*1 89 = 91-2+0 90 = 90*(2-1) 91 = 92-1+0 92 = 92*1+0 93 = 102-9 95 = 190/2 100 = (9+1)^2+0 49 2019``` 2 members found this post helpful.
01-16-2019, 11:16 PM   #67
dogpatch
Member

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

Rep:

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.

2 members found this post helpful.
01-16-2019, 11:39 PM   #68
dogpatch
Member

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

Rep:
Quote:
 Originally Posted by Beryllos 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

1 members found this post helpful.
01-16-2019, 11:54 PM   #69
Beryllos
Member

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

Original Poster
Rep:
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?
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.

Last edited by Beryllos; 01-17-2019 at 12:02 AM.

1 members found this post helpful.
01-17-2019, 03:56 PM   #70
astrogeek
Moderator

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

Rep:
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.
Enjoy!

Yesterday, 07:34 PM   #71
dogpatch
Member

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

Rep:
Quote:
 Originally Posted by Beryllos 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.

 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 12:54 PM LXer Syndicated Linux News 0 06-19-2011 04:50 PM General General 6 06-25-2010 07:35 AM Simon Bridge General 6 08-26-2007 08:46 PM

LinuxQuestions.org

All times are GMT -5. The time now is 05:42 PM.

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