Thank you, astrogeek, for posting your code. Much more elegant than my stuff. Hard to compare speeds, since my exhaustive run only processes for the 715 combinations of 4 digits; for each of those it then permutes to as many as 24 passes, for a total of 10,000 passes. That takes my exhaustive run a tad over 60 seconds to complete on my old 32 bit Dell, and a bit under 2 seconds on the 64 bit server - can't tell you either cpu clock speed off the top of my head. Since you output 10000 lines of totals to my 715, i may have to run a little script to compare year by year. But at first glance we seem to have the same totals, which for me have been stable through my last several updates. You can see my exhaustive run totals on my web page, just updated to v. 3.0.200. (Select 'Totals only' and year '0000'.)

Also on this latest update, i've included some user-specified equation ranking. You may opt in or out of three checkbox specs, and on two of these you can radio button select one of two states. There's also a command line way to do this, if you choose to download my code (fx.h and LQpz_3.c) and compile it. Doing this, i've seen some pretty funky equations, and have caught a nasty little oversight (was rejecting fractional exponents of negative numbers). It seems quite stable now. If i were still doing this stuff for a livelihood, i'd be sending the client a Beta version, with the final release promised soon, and up to six months of free bug fixes and minor changes as they happen to come up.

Have downloaded astrogeek's code, and may well simplify my fractional math, using your (and Beryllos') pattern (n/n)^(n/n) rather than my too-complex n^(n/n)/n^(n/n). May enjoy perusing your AST logic as well, but for now i think i'll stick to RPN - am familiar with it, and it seems to be stable now as well.

2 members found this post helpful.

Re-reading your original post, i may have misread the part about leading negative signs. Currently am allowing a negative sign prepended to any of the (up to) 4 input numbers. Ought i to only allow a leading negative sign to the first number in the equation? That would simplify and speed up the process, without affecting the exhaustive run totals. None of the individual equations gained by added leading negative signs are really needed, and, beyond the first number, most contain too many ugly and confusing parentheses e.g.:

2 members found this post helpful.

I have been wondering that too. I must confess, so far I have not implemented leading negative signs at all. I meant to look into it, but sort of forgot. astrogeek's recent posts have brought it back to my attention, and I think I must get back to that and see if it leads to any useful or unique solutions.

The exhaustive approach (practically my trademark!) would be very inefficient because many negative signs will be redundant. For example, a+(-b) is the same as a-b, a*(-b) is the same as (-a)*b, (-a)/(-b) is the same as a/b, and many more.

Negative signs shouldn't be restricted to the first number. There is at least one other situation where it might be needed: negative powers (negative exponents), because the negative sign in the exponent does not have the same effect as a negative sign anywhere else.

2 members found this post helpful.

@astrogeek and @dogpatch, I apologize for not commenting on your recent developments. Briefly, they look awesome! Over the weekend I'll try to settle down and go over your programs carefully and try them out.

1 members found this post helpful.

I concluded at the outset that any sign change of the result would be equivalent to rearrangement of terms and/or change of sign of some term, so adopted the rule of simply using absolute value of the result. Mind you, I say "concluded" not "proved", but I think that is a safe bet with four digits and the four arithmetic operators.

I have added an option to suppress use of absolute values of results this evening so we can find anything that produces a different result. When I originally wrote my expression set I had in mind to cover both cases and so far I have not produced any differences, although I am sure there will be some that require an additional properly signed expression or two.

I had not considered negative exponents in expressions, but now allow those, so will think more about their effect. In my fractional handlers I know that I handle negative exponents, as I am sure your python code does as well. They can occur easily enough without an actual sign change anyway ( a^(b-c)-d where c>b for example), so it comes down to identifying a few notable test cases to evaluate.

FYI - I have added overflow detection to my fractional multiply and divide handlers - oops had forgotten to put that in there... I did have overflow detection for exponential terms in the uploaded code.

I have also added some output filtering options including filtering by number of solutions found, which produces some interesting result sets!

I'll get the updated code uploaded in a day or two.

Thanks for the comments!

1 members found this post helpful.

An excellent point.

Am disallowing -(-a) and +(-a). Will look into the other examples you cite, and also ought to be doing a better job eliminating unneeded parentheses, e.g. ((-a)/b)

My experience, so far, is that negation does lead to some useful and interesting equations, but doesn't solve for any value that would otherwise be unsolvable - as you suspected from the beginning.

1 members found this post helpful.

Just an off-topic note (apologies to the mods), but if LQ were to have a classics forum, this thread would be the first one in the door, imo.

Despite my not really understanding the code, mathematics and arguments at times, the collaborative, interesting and amiable way this thread is being conducted is extremely refreshing. Keep it up guys! I look forward to one of these challenges being presented every year.

2 members found this post helpful.

Thanks! In that way it reminds me of another Programming thread:
https://www.linuxquestions.org/quest...amming-466789/
We had a lot of fun with that, learning from each other, swapping code, and raising the bar until we had totally flogged the problem. It's great when that happens.

Thumbs up for the thumbs up!

@astrogeek: My first glance at our totals was incorrect. My code seems to be generating more equations than yours. Tried to compile your code, but get a link error: undefined reference to 'isfinite', so i can only guess at where the discrepancies come from. All my equations 'seem' legit, but i may be mistaken. Look especially at year '1151' (and '1511' and other permutations), for which my code gives 40 solutions, yours 36.

You've promised an updated version of your code, to which i look forward. Perhaps you've already addressed this, or perhaps you can point to some invalid equations of mine.

The link error - is it because i'm running an ancient version of gcc and am missing the 'isfinite' definition in my math.h?

I have not yet had a chance to explore your code as I have Beryllos', but it is on my table for tonight. I'll reserve comment until I have given it a worthy workout.

The older math.h sounds like a likely suspect. I don't think those checks catch much of anything anyway, so you might give it a try with them commented out, or replace them with your own checks.

I have found a problem with my root bisector (Yikes!!) and will update that tonight as well, along with a few other changes, although I doubt that accounts for the difference in totals. The difference more likely results from expression cases generated by your code and not yet included in my expressions file. Beryllos' program produces 40 solutions for 1151, which is probably correct.

For those kind enough to be reviewing or using my code, the root finder error results in small roots sometimes being missed. I will post here when I have uploaded the fixed, and properly validated version.

Happy to know I am not the only one still turning the crank on older hardware!

The new code is now avaliable here, v1.0.1.

Sorry for any inconvenience to others who were testing the original version, it was not time wasted I hope! The necessary change was relatively minor, and obvious. In addition to that fix, I have improved error handling for several cases, and added a couple of output filtering options.

1 members found this post helpful.

Have uploaded my version 3.0.220 to the same web page as before. Still getting the same overall totals. Have simplified my fractional-exponential routines. My C struct is now
much simpler than before. This, and a couple other minor changes have gotten my exhaustive run time down to under 50 seconds on my home Dell and 1311 milliseconds on the server.

By the way, in just a couple cases, my code makes a pre-process distinction between my home Dell and the web server. Since the server runs FreeBSD, my code tests thus:Mostly, this has to do with displaying in terminal mode (at home) vs on a web page.

@astrogeek: May not get around to downloading and trying out your updated code and/or testing it w/ the 'isfinite' tests commented out.for a couple days. Hope to compare notes soon.

1 members found this post helpful.

@astrogeek and @dogpatch, I have taken a pretty close look at your source code. I haven't mastered the details, but I've at least got a good start on the concepts and framework.

I am amazed and delighted that the three of us have approached and solved this problem in such different ways. My own expression evaluator, the way I visualize it, operates in a horizontal workspace like a formula written on a line, guided by permuted schedules of operations. dogpatch's program finds expressions by generating every valid RPN sequence, also using permutation methods. I think his method and mine generate the same set of expressions, the only difference likely being the inadvertently redundant expressions. (When you permute everything — digits, operations, and order of operations — you are likely to get a lot of redundancy.)

astrogeek has adopted another paradigm, the abstract syntax tree (AST), both to represent expressions and solve them. I suspect that all three methods — my sequencer, RPN, and AST — must be equivalent at some level. Also it's probably no coincidence that all three are implemented as recursive functions. I made a chart showing how expressions look in these different representations: comparison.pdf

One really big difference in astrogeek's approach is that he didn't fall back on the brute-force "exhaustive" approach, trying all combinations and permutations of operations. At first I thought one would need to use every possible expression. It turns out that the New Year Puzzle can be solved with a much smaller subset. This is a very interesting discovery. I wonder what the minimal set is.

I'll continue to tie up some loose ends and have some more fun with this. Thanks, Everyone!

2 members found this post helpful.

Thanks, I'll grab a copy while I am in here!

I have been finally able to spend some time with your v3 and v3.0.1 (not really sure of the update number, but the updated LQpz_3 and fx.h).

I wrote a shell script to generate result sets using yours for comparison with my own and using the differences have added a few expressions to my base file. It now argees completely with yours and Beryllos' from 2000 to 3000 and every spot range I have tested outside that range.

I found one expression generated by yours which appears to be mishandled, and unique, however:

It is an oddity that does not seem to show up in other years, and all other results I have seen appear to be correct. This was with your v3, I do not see it with v3.01, but you might want to double check the cause.

I have also found that many of the differences between min and yours appear in expressions generated by your exhaustive expressions which include a sign change on one or more digits. Although my own code handles such sign changes, I have written my own expressions to not include them. In every case I have found in your results I have been able to rewrite the expression without the sign change, including negative fractional exponents, so I would say that generating those is not necessary and as you have noted the way they multiply the processing speed, you could safely do without them.

Here are a few examples:

This works because you can change sign of the exponent and invert the base, which happens anyway with permutation of the digits:

A few other examples for confidence (the uncommented replace the preceeding negated versions)...

That might simplify your expression generator a bit as well.

It is reassuring that in all our cases we seem to continue to get the same overall totals with each refinement, and even in the presence of corrected errors. It seems to say our results are good and the effects of those errors small... so far!

Entirely at your convenience. I'll upload an updated expression set within the next few days, but unless I see need for yet more options, or an error shows its ugly head, I think I will leave the code itself alone for a while. I am having fun using it now, not writing it!