Latest LQ Deal: Latest LQ Deals
 Home Forums HCL Reviews Tutorials Articles Register Search Today's Posts Mark Forums Read
 LinuxQuestions.org New Year Puzzle and fun programming challenge
 User Name Remember Me? 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

02-01-2019, 02:51 PM   #91
astrogeek
Moderator

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

Rep:

I too, have yielded to Beryllos' lead and am implementing a fractional solver. With my AST based version it was just a matter of redefining the nodes to hold fractional values then write a tree walking algorithm that works with those instead of the double valued node data. I have enjoyed working with that as much as learning how poor my own math skills have become!

Quote:
 Originally Posted by Beryllos I know you are on the right track, because you got the right answer for 8^(5/3)=32.
I will use this as my reference check!

One question Beryllos, (in v6) you correctly reject expressions with negative base values and an even valued denominator in the exponent (I had to relearn that too!), but is there a reason not to invoke the sign change rule at that point and produce a result that might still be a valid integer for the puzzle, other than keeping the solver strictly valid for all cases?

@dogpatch - I am not ignoring your progress, very nice! I had downloaded your linked code last week, but when I looked at it, it was not related to this thread, so probably not what you intended. The file I got was 'shkeys.c'. Let us know when you have a new version posted!

I have to work on this in 15 minute increments these days, but am still in the game, if spending time mostly on the bench!

Last edited by astrogeek; 02-01-2019 at 02:55 PM. Reason: typos

02-01-2019, 09:07 PM   #92
dogpatch
Member

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

Rep:
Quote:
 Originally Posted by astrogeek @dogpatch - I am not ignoring your progress, very nice! I had downloaded your linked code last week, but when I looked at it, it was not related to this thread, so probably not what you intended. The file I got was 'shkeys.c'. Let us know when you have a new version posted!
Sorry for the confusion - not sure how that happened. Anyway, the source code link is disabled right now. Will try to let you know when i have something new to post.

02-01-2019, 11:52 PM   #93
Beryllos
Member

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

Original Poster
Rep:
Quote:
 Originally Posted by astrogeek One question Beryllos, (in v6) you correctly reject expressions with negative base values and an even valued denominator in the exponent (I had to relearn that too!), but is there a reason not to invoke the sign change rule at that point and produce a result that might still be a valid integer for the puzzle, other than keeping the solver strictly valid for all cases?
If I correctly understand your suggestion, yes, given a negative value which is illegal, you could change its sign to make it legal, and work out what you can change in the original formula to get that sign.

By the way, I was thinking and wondering how important it really is to handle all the special cases for fractional powers of fractions. For problems starting with four digits, there are very few cases where it is possible to get an integer result:
• I think the form (a/b)^(c/d) cannot yield an integer unless a/b or b/a is an integer.
• There are a few integer solutions of the forms ((a/b)^c)*d and a/((b/c)^d).
• There are several more using a^(b/c) with one more digit and operation.
If we have more digits to work with, there are more formulas with fractional powers of fractions that could lead to integer results. While that could be an interesting mathematical and programming challenge, it goes way beyond the original specs!

Thoughts on that?

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

 02-02-2019, 06:57 PM #94 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 360 Blog Entries: 2 Rep: Have uploaded version 3.0.000, using fractional-exponential integer math. 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 46978 total equations (that is, values 0-100 for which at least one equation is generated) This is an exact match to the totals per year and overall totals that i was getting before. Makes me want to believe it is working. A bit more sluggish than with floating point numbers. This is 3.0.000 Alpha. Am under time constraints right now. Will try to test some more, maybe shake out a bug or two, and reply more verbosely, comparing notes on implementing fractional math, and other fun points. 1 members found this post helpful.
02-05-2019, 02:37 AM   #95
astrogeek
Moderator

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

Rep:
Quote:
 Originally Posted by Beryllos If I correctly understand your suggestion, yes, given a negative value which is illegal, you could change its sign to make it legal, and work out what you can change in the original formula to get that sign.
Yea, that would be going at the problem from the wrong though, wouldn't it! Thanks for the reply to my not well considered question!
Quote:
 Originally Posted by Beryllos By the way, I was thinking and wondering how important it really is to handle all the special cases for fractional powers of fractions. For problems starting with four digits, there are very few cases where it is possible to get an integer result:I think the form (a/b)^(c/d) cannot yield an integer unless a/b or b/a is an integer. There are a few integer solutions of the forms ((a/b)^c)*d and a/((b/c)^d). There are several more using a^(b/c) with one more digit and operation. If we have more digits to work with, there are more formulas with fractional powers of fractions that could lead to integer results. While that could be an interesting mathematical and programming challenge, it goes way beyond the original specs! Thoughts on that?
I have had a similar thought, there really are few cases that can be produced from four digits which could produce an integer between 0 and 100! I have my fractional support working at last (producing 8^(5/3)-1 == 31, yay!) but find only the same small set of expressions already posted which produce (few) integer results.

I have not yet done so, but I will send a subset of as many expressions I can come up with which involve fractional exponents through my code for all 4 digit years, once each with fractional and floating point solvers and see what the actual difference is. I'll keep you posted!

1 members found this post helpful.
 02-05-2019, 03:25 AM #96 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_10{.0|.1|.2} Posts: 4,986 Blog Entries: 11 Rep: I had hoped to put together a new blog page tonight to post my current code, but will not get that done for another day or two. But while here I want to post a hopefully useful update about progress. First, I have added fractional math support to my little program at last! I wrestled with how to most easily do that for the past week, but without much ability to actually code. When I finally sat down to do it, I had it working fairly quickly. My approach is a bit different from both Beryllos and dogpatch, in that I do not permute ther operators, only the digits. My program allows you to enter an expression to be evaluated, and a year (set of four digits) which you may permute or not, optionally. It can also read expressions from a file, always in symbolic form, a^(b/c)-d for a now familiar example. I build an AST of the expression under test to assure correct precedence and associativity then walk the tree to evaluate the numeric result. As I had that working for floating point math it was fairly easy to add the fractional solver functions as an option, so you can choose either mode at runtime. Here is the help screen... Code: ```./years -h Usage: ./years [OPTIONS] [-f filename] YEAR -a, --ast Show AST for expressions -d, --dot Generate graphviz dot markup of AST (implies -p) -e, --expression Enter an expression to be evaluated -f, --file filename Read expressions from file (overrides -e) -F, --fractional Evaluate with fractional math (default floating-point) -h, --help Print this help message and exit -m, --matrix Display solutions in square matrix -o, --opts Print runtime options state -p, --nopermu Do not permute digits -v, --verbose Show more info, may be used more than once (-, -vv) -x, --exact Show exact decimal solution for all expressions``` And the famous test case which convertted me to a true believer in fractional math, first with floating point, then fractions: Code: ```./years -f expressions2.txt 1385 -m Matrix of found solutions 0: 0 1 2 3 4 5 6 7 8 9 10: 10 11 12 13 14 15 16 17 18 19 20: 20 21 22 23 24 25 26 27 28 29 30: 30 . 32 33 34 35 36 37 38 39 40: 40 41 42 43 44 45 46 . 48 49 50: 50 51 52 53 54 55 56 57 58 59 60: 60 61 62 63 64 65 66 . 68 69 70: . 71 72 73 . 75 . 77 78 79 80: 80 81 82 83 84 85 86 87 88 89 90: . . . 93 . . 96 . 98 99 100: . Total = 88 ./years -f expressions2.txt 1385 -mF Matrix of found solutions 0: 0 1 2 3 4 5 6 7 8 9 10: 10 11 12 13 14 15 16 17 18 19 20: 20 21 22 23 24 25 26 27 28 29 30: 30 31 32 33 34 35 36 37 38 39 40: 40 41 42 43 44 45 46 . 48 49 50: 50 51 52 53 54 55 56 57 58 59 60: 60 61 62 63 64 65 66 . 68 69 70: . 71 72 73 . 75 . 77 78 79 80: 80 81 82 83 84 85 86 87 88 89 90: . . . 93 . . 96 . 98 99 100: . Total = 89``` And the line which makes me smile most tonight... Code: `31 = 8^(5/3)-1 = a^(b/c)-d` My fractional exponent algorithm uses Beryllos rearrangement of the equation: Code: ```struct term *fpowterm(struct term * lterm, struct term *rterm){ /* Handle fractional exponents of fractional terms */ int status = lterm->status + rterm->status; int i, limit = 20, sign; long bnumer = lterm->numer, bdenom = lterm->denom; long xnumer = rterm->numer, xdenom = rterm->denom; long temp, temp2; if((status != 2) || (bnumer==0 && xnumer<=0) || //0^0, 0^-x (bdenom==0 && xdenom==0) || (bnumer<0 && !xdenom%2) || //even root of negative number (bnumer>=limit || xnumer>=limit) || (bnumer<=-limit || xnumer<=-limit) || (bdenom>=limit || xdenom>=limit) || (bdenom<=-limit || xdenom<=-limit) || (bdenom==0 || xdenom==0) //Shouldn't see these, but just in case... ) return newterm(0, 0, 0, -1); if((bnumer==1 && bdenom==1) || xnumer==0) //1^any, any^0 return newterm(1, 1, 0, 1); if(xnumer==1 && xdenom==1) //any^1 return newterm(bnumer, bdenom, 0, 1); if(xnumer<0)//negative exponent xnumer=-xnumer, temp=bnumer, bnumer=bdenom, bdenom=temp; if(bdenom<0) bnumer=-bnumer, bdenom=-bdenom; if(xdenom==1){//integer exponent for(i=0, sign=temp=temp2=1; i 0 && bnumer > 0 && LONG_MAX/temp >= bnumer) && (temp2 > 0 && bdenom > 0 && LONG_MAX/temp2 >= bdenom)) { temp*=bnumer, temp2*=bdenom; } else return newterm(0, 0, 0, -1); } return newterm(temp*sign, temp2, 0, 1); } /* Everything else involves a fractional exponent We use Beryllos' rearrangement of the expression: bnumer xnumer {bnumer^{1/xdenom}}^xnumer {------}^{------} = -------------------------- bdenom xdenom {bdenom^{1/xdenom}}^xnumer Determine whether {bnumer|bdenom}^{1/xdenmom} have solutions, if both have integer solutions then complete the math and return as a term, else return a -1 status term */ temp = fracpwr(bnumer, xnumer, xdenom); temp2 = fracpwr(bdenom, xnumer, xdenom); if(temp && temp2) return newterm(temp, temp2, 0, 1); return newterm(0, 0, 0, -1); }``` The fracpwr(...) function is a simple bisecting algorithm that finds the integer root if one exists, and returns that raised to the power xnumer, if it exists, else returns zero. I am over my upload limit here on LQ, but will try to put a tarball where you can reach it, or post the complete code to my blog within a day or two, as time and energy permit. Thanks for the continuing fun! Last edited by astrogeek; 02-06-2019 at 01:13 PM. Reason: Removed free() leftover testing lines... 1 members found this post helpful.
 02-05-2019, 04:49 AM #97 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 12,463 Rep: just one remark: for fibonacci numbers we have: F(n) = a(n) + b(n) where F(n) is the nth [integer] fibonacci number and a(n) and b(n) are both irrational expressions. So actually (speaking about the current problem) can we allow any kind of intermediate result? (For example a^(-b) + c/d or something similar may give an integer: year:2378->2).
02-05-2019, 07:41 AM   #98
ntubski
Senior Member

Registered: Nov 2005
Distribution: Debian, Arch
Posts: 3,429

Rep:
Quote:
 Originally Posted by pan64 just one remark: for fibonacci numbers we have: F(n) = a(n) + b(n) where F(n) is the nth [integer] fibonacci number and a(n) and b(n) are both irrational expressions.
Isn't Fibonacci formula entirely integer: F(n) = F(n-1) + F(n-2)

Wikipedia shows a non-recursive formula using √5, but it's not in the form a(n) + b(n). I think the only way to get an integer from that is if a(n) = -b(n) + m; where m is an integer.

 02-05-2019, 08:52 AM #99 pan64 LQ Guru   Registered: Mar 2012 Location: Hungary Distribution: debian/ubuntu/suse ... Posts: 12,463 Rep: Code: ```let ϕ1=(1+√5)/2 let ϕ2=(1-√5)/2 a(n)=ϕ1^n/√5 b(n)=ϕ2^n/√5 F(n)=a(n)-b(n)``` this is how can you calculate F(n) without knowing any other element. And you can prove F(n) is (still) equal to F(n-1) + F(n-2) for every n, so this will definitely produce integers, the fibonacci numbers. This is equivalent to the one mentioned on the wiki you posted. 1 members found this post helpful.
 02-05-2019, 12:44 PM #100 Beryllos Member   Registered: Apr 2013 Location: Massachusetts Distribution: Debian Posts: 500 Original Poster Rep: Yes, in this puzzle, non-integer intermediate results are allowed. Irrational intermediate results are allowed too, although we haven't discussed how to solve them. The Fibonacci formula you described can be evaluated "on paper" for a specific n, and I can dimly see how it could yield an integer. (Even and odd powers of √5 alternately add and subtract, and are divided by √5... I haven't worked it all out, but I see a pattern.) Very interesting!
02-05-2019, 02:06 PM   #101
pan64
LQ Guru

Registered: Mar 2012
Location: Hungary
Distribution: debian/ubuntu/suse ...
Posts: 12,463

Rep:
Quote:
 Originally Posted by Beryllos Yes, in this puzzle, non-integer intermediate results are allowed. Irrational intermediate results are allowed too, although we haven't discussed how to solve them.
I don't think it is important here, with this puzzle, because four digits and the given operations look insufficient to construct similar cases. But obviously it is not [yet] proven.
The only exception I know at this moment: (a^(b/c))^d will/may work, assuming we have a zero (a, b or d) in our input or b*d/c is an integer.

1 members found this post helpful.
 02-05-2019, 07:38 PM #102 dogpatch Member   Registered: Nov 2005 Location: Central America Distribution: Mepis, Android Posts: 360 Blog Entries: 2 Rep: Have been putting my C code through its paces, cleaning up and annotating a bit; still getting the same totals. Have added the last piece to fully comply with Beryllos' original specs: allowing negation of the input digits. Not surprisingly, this netted a number of interesting equations, with no effect on the totals. But to my surprise, it also yielded nearly a 10-fold increase in expressions to evaluate, and 10-fold increase in processing time for the exhaustive run. Investigating that, i found, also to my surprise, that, in many cases, two or more different rpn expressions were generating the exact same arithmetic expression. So, for example, these two rpn strings Code: ```6_|8-|4_|7/* 6_|8-|4_*|7/``` correctly yield the same arithmetic expression Code: `(-6-8)*(-4)/7` By way of explanation, my implementation of reverse polish notation is based upon how my old programmable HP calculator worked, complete with 4-position stack. In the above example, the vertical bar '|' means that all numeric values already present are pushed one level, and the new number (1 or more digits) is entered on the accumulator or base register (stack[0]). This is equivalent to pressing the Enter key on the HP calculator, and then inputting another number. The underscore '_' is my designation of the negate key '-x' on the HP calculator, negating the number just entered. This is distinguished from the minus sign which, like other arithmetic operations, operates on stack[1] and stack[0], leaving the result in stack[0] and popping other stack values. So, in the above examples, the value 6 is entered, negated, pushed; 8 entered and subtracted from -6, then 4 is entered and negated. In the first rpn expression, the 7 is then entered and divided into the -4, then that value is multiplied times the result of the -6-8. In the second rpn, the -4 is multiplied by the result of -6-8, then 7 is entered and divided into everything else. It ends up being the exact same arithmetic, so that my rpn logic was generating many duplicate arithmetic equations. I have since made my rpn generation logic a bit smarter. I THINK it is now avoiding duplicate equation generation, and i THINK that no unique equations are being lost. Have uploaded my version 3.0.100 (Beta). Next will try to catch up with Beryllos in implementing user-specified equation ranking. 2 members found this post helpful.
02-05-2019, 08:14 PM   #103
dogpatch
Member

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

Rep:
Quote:
 Originally Posted by astrogeek My approach is a bit different from both Beryllos and dogpatch, in that I do not permute ther operators, only the digits. My program allows you to enter an expression to be evaluated, and a year (set of four digits) which you may permute or not, optionally. It can also read expressions from a file, always in symbolic form, a^(b/c)-d for a now familiar example.
Briefly considered such an approach myself. In your method, the user must supply the symbolic expression(s)? Do you yourself have a file of such expressions? Is it exhaustive?

Perhaps that's what prevented me taking that approach - that i suspected developing an exhaustive list of possible expressions would be more work, and more processing time, than generating rpn expressions. But, based upon what i've just posted above, am pssibly willing to re-think my decision to go with rpn.

02-07-2019, 01:51 AM   #104
astrogeek
Moderator

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

Rep:
Quote:
 Originally Posted by dogpatch Briefly considered such an approach myself. In your method, the user must supply the symbolic expression(s)? Do you yourself have a file of such expressions? Is it exhaustive? Perhaps that's what prevented me taking that approach - that i suspected developing an exhaustive list of possible expressions would be more work, and more processing time, than generating rpn expressions. But, based upon what i've just posted above, am pssibly willing to re-think my decision to go with rpn.
I do have such a file which I will post below (thanks to Jeremy for fixing my upload limit!)... whether it is exhaustive or not I cannot say. What I can say is that with roughly 150 expressions I can now produce the same result as Beryllos' v6 python script for almost all years I have compared. There are undoubtedly still some exceptions, but it seems realistic to think that the list should be able to reach a "complete" state at some point.

I managed to get some quality play time today and added some improved output format handling which really helps! I am sorry to be so slow posting my code but I have not wanted to do so, followed by daily fixes and updates, but I am almost there!

Quote:
 Originally Posted by dogpatch Have been putting my C code through its paces, cleaning up and annotating a bit; still getting the same totals. Have added the last piece to fully comply with Beryllos' original specs: allowing negation of the input digits.
I also added support for sign change on digits to my parser today. As you found, I don't see that it adds any new results, but haven't really tried many expressions using it. Of course, adding one more operator would multiply the number of expression permutations "factorially", hope that is a real word!

One feature I added was the ability to process ranges of years, so I ran the full ten thousand year range - in about 37 seconds on my old 32 bit 1.7Ghz laptop!

Attached is a tarball,
tenK.tar.gz.txt, with two files:

ten_K_years.txt - All ten thousand four digit "years" totals produced by my current code
expressions2.txt - The expressions file used to generate the ten thousand results

I have appended .txt to the filename so that it will upload, simply remove that extension and untar to see the results.

Code:
```time ./years -f expressions2.txt 0000 -Fr 9999 >ten_K_years.txt

real    0m37.047s
user    0m36.872s
sys     0m0.033s```
The -F indicates it was run with the fractional solver.

I would be interested in comparisons of totals from either of your programs, too!

EDIT: I forgot to include the diff in the tarball, but I also ran the full ten thousand with floating point solver and find 498 years which produce a different result. Most are different by a single result, I have not yet tried to identify the most common expressions which make that difference. Floating point solver runs in about 30 seconds.

Here is the current help screen for my code by the way. I repeat again that my goal was to make a tool for exploring the expressions interactively, not so much for generating all possible numbers automatically, and I am finally getting there I think:

Code:
``` ./years -h
Usage: ./years [OPTIONS] [-f filename] YEAR
-a, --ast              Show AST for expressions
-d, --dot              Generate graphviz dot markup of AST (implies -p)
-e, --expression       Enter an expression to be evaluated
-f, --file filename    Read expressions from file (overrides -e)
-F, --fractional       Evaluate with fractional math (default floating-point)
-h, --help             Print this help message and exit
-l, --line             List sorted solutions on a single line
-m, --matrix           Display solutions in square matrix
-N, --nans             List results which are not numbers
-o, --opts             Print runtime options state
-p, --nopermu          Do not permute digits
-r, --range num        Process num years beginning with YEAR, 0<=num<=9999
-s, --solutions        List unique solution expressions, w/-v for all
-S, --nonsolns         List valid numeric results which are not solutions
-v, --verbose          Show more info, may be used more than once (-, -vv)```

Last edited by astrogeek; 02-07-2019 at 02:38 AM. Reason: More comments and typos

2 members found this post helpful.
 02-08-2019, 02:38 AM #105 astrogeek Moderator   Registered: Oct 2008 Distribution: Slackware [64]-X.{0|1|2|37|-current} ::12<=X<=14, FreeBSD_10{.0|.1|.2} Posts: 4,986 Blog Entries: 11 Rep: I have now posted my code for anyone interested! Find it in my related LQ blog page with additional comments. 3 members found this post helpful.

 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 Forum Rules

 Similar Threads Thread Thread Starter Forum Replies Last Post LXer Syndicated Linux News 0 10-27-2017 11:54 AM LXer Syndicated Linux News 0 06-19-2011 03:50 PM General General 6 06-25-2010 06:35 AM Simon Bridge General 6 08-26-2007 07:46 PM

LinuxQuestions.org

All times are GMT -5. The time now is 01:27 AM.

 Contact Us - Advertising Info - Rules - LQ Merchandise - Donations - Contributing Member - LQ Sitemap -
 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.
 Syndicate Latest Threads   LQ News Twitter: @linuxquestions Facebook: linuxquestions Google+: linuxquestions