LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
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


Reply
  Search this Thread
Old 01-16-2019, 05:31 PM   #61
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 323
Blog Entries: 2

Rep: Reputation: 93

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.
 
Old 01-16-2019, 05:44 PM   #62
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 434

Original Poster
Rep: Reputation: 196Reputation: 196
Quote:
Originally Posted by dogpatch View Post
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.
Old 01-16-2019, 07:39 PM   #63
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 323
Blog Entries: 2

Rep: Reputation: 93
Quote:
Originally Posted by Beryllos View Post
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'.
 
Old 01-16-2019, 07:50 PM   #64
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 323
Blog Entries: 2

Rep: Reputation: 93
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.
 
Old 01-16-2019, 09:57 PM   #65
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 434

Original Poster
Rep: Reputation: 196Reputation: 196
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.
 
Old 01-16-2019, 10:01 PM   #66
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 434

Original Poster
Rep: Reputation: 196Reputation: 196
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.
Old 01-16-2019, 11:16 PM   #67
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 323
Blog Entries: 2

Rep: Reputation: 93
A couple additional thoughts:

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 View Post
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.
Old 01-16-2019, 11:39 PM   #68
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 323
Blog Entries: 2

Rep: Reputation: 93
Quote:
Originally Posted by Beryllos View Post
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.
Old 01-16-2019, 11:54 PM   #69
Beryllos
Member
 
Registered: Apr 2013
Location: Massachusetts
Distribution: Debian
Posts: 434

Original Poster
Rep: Reputation: 196Reputation: 196
Quote:
Originally Posted by dogpatch View Post
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.
Old 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: Reputation: 2748Reputation: 2748Reputation: 2748Reputation: 2748Reputation: 2748Reputation: 2748Reputation: 2748Reputation: 2748Reputation: 2748Reputation: 2748Reputation: 2748
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 View Post
Hey, we're having fun here - that's the main thing.
Enjoy!
 
Old Yesterday, 07:34 PM   #71
dogpatch
Member
 
Registered: Nov 2005
Location: Central America
Distribution: Mepis, Android
Posts: 323
Blog Entries: 2

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

Have uploaded the latest version to my aforementioned web page.

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.
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

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



Similar Threads
Thread Thread Starter Forum Replies Last Post
LXer: Minilens Fun Open Source Puzzle Platform Game LXer Syndicated Linux News 0 10-27-2017 12:54 PM
LXer: SpaceChem, One of the Best Indie Puzzle Game Released this Year for Linux LXer Syndicated Linux News 0 06-19-2011 04:50 PM
Puzzle Challenge: Collecting lots of files from many people? General General 6 06-25-2010 07:35 AM
<fun> The Windows Crash </fun> Simon Bridge General 6 08-26-2007 08:46 PM

LinuxQuestions.org > Forums > Non-*NIX Forums > Programming

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

Main Menu
Advertisement
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration