[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.

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.

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

@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.

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!

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.

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!

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:

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<xnumer; i++){
/* Bail on overflow! */
if(bnumer < 0)
sign=-1, bnumer=-bnumer;
if ((temp > 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...

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).

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.

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.

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!

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.

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.

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.

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!

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

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