[SOLVED] New Year Puzzle and fun programming challenge

astrogeek · 02-01-2019, 02:51 PM

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!

dogpatch · 02-01-2019, 09:07 PM

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.

Beryllos · 02-01-2019, 11:52 PM

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?

dogpatch · 02-02-2019, 06:57 PM

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.

astrogeek · 02-05-2019, 02:37 AM

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!

astrogeek · 02-05-2019, 03:25 AM

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<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!

pan64 · 02-05-2019, 04:49 AM

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

ntubski · 02-05-2019, 07:41 AM

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.

pan64 · 02-05-2019, 08:52 AM

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.

Beryllos · 02-05-2019, 12:44 PM

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!

pan64 · 02-05-2019, 02:06 PM

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.

dogpatch · 02-05-2019, 07:38 PM

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.

dogpatch · 02-05-2019, 08:14 PM

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.

astrogeek · 02-07-2019, 01:51 AM

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)

astrogeek · 02-08-2019, 02:38 AM

I have now posted my code for anyone interested! Find it in my related LQ blog page with additional comments.