[SOLVED] New Year Puzzle and fun programming challenge

astrogeek · 02-24-2019, 05:30 PM

Most excellent!

dogpatch · 02-24-2019, 08:16 PM

Quote:

Originally Posted by Beryllos

Breaking news: My brute-force (exhaustive) search has found two new results so far:

Code:

year 2278:  58 = 8*(7+2^(-2)) = a*(b+c^(-d))

year 2288:  62 = 8*(8-2^(-2)) = a*(b-c^(-d))

and it is so far about 60% through the list of all valid expressions (396 out of 683).

Didn't know whether to cheer or cry when i saw your new results, after all three of us were sure we had the same definitive totals. And i've been employing leading negatives for some time, so didn't know how i missed those two equations. Turns out, i was resolving the negative exponent, but failed to simplify the number by applying the now positive exponent to the now fractional base. Dumb!

So, i owe you a beer, Beryllos. (You'd have to come to Nicaragua to collect.) Have now corrected the oversight in my logic, and am getting 46980 total equations, exactly two more than previously. Am also getting new valid equations in other places, which do not apparently add to the totals. Good catch!

Hope to soon upload my corrected logic, and possibly more comments and questions to come.

And may have to noodle about what other things I/we may have missed all along.

dogpatch · 02-24-2019, 10:11 PM

post deleted. some confusion here, my apologies.

dogpatch · 02-25-2019, 12:56 AM

Have uploaded version 3.0.240, which i THINK is stable and more or less correct. Thought i was getting more new solutions but was mistaken. Am still getting 46980, the new total solutions, two more than the old 'definitive' total.

Here's one of several new equations made possible by leading negative signs and the corrected resolution of a negative exponent, but which do not add to the final total (year 2559):

Code:

32 = (5+9/-2)^-5

pan64 · 02-25-2019, 01:05 AM

Quote:

Originally Posted by dogpatch

Here's one of several new equations made possible by leading negative signs and the corrected resolution of a negative exponent, but which do not add to the final total (year 2559):

Code:

32 = (5+9/-2)^-5

I think that is occasional. I mean using different numbers (another year) the final total will consist of different equations.

Beryllos · 02-25-2019, 01:08 AM

Okay, I have just completed my search for new results with negative signs. The only ones that turned up are the two which I reported earlier.

I don't think there is anything special about the expressions themselves. Leading negative signs surely generate many other interesting equations. Those two are special only because they happened to find holes (vacancies) in the midst of the solutions we had already found.

In the near future I will run some tests on the program I used for this search. I put it together hastily, and I wouldn't be surprised if it has some bugs. The most likely kind of error would be that a particular order of operations was incorrectly modified for negative signs. (The new code includes an if...else if...else structure to handle 15 combinations of parentheses and concatenation, so that's 15 chances to get something wrong.) I will post the code after these tests. If it checks out okay, I would be pretty sure there are no other new results to be had.

astrogeek · 02-25-2019, 01:44 PM

Thanks for the update!

I reviewed my own signed exponent inversions and see that I had only considered cases where the base could be inverted without introducing an additional digit, like these:

Code:

(a/b)^(c*-d)

Removing sign from exponent...

(b/a)^(c*d)

Which in presence of permutated variables becomes...

(a/b)^(c*d)

a+(b/c)^-d

Removing sign from exponent...

a+(c/b)^d

Which in presence of permutated variables becomes...

a+(b/c)^d

From the cases I handled I concluded, wrongly, that this could be done in every case. But I had obviously not considered every case!

With your new finds, I see no way to remove the sign from the exponent without conjuring up an extra digit with which to invert the base, so they produce unique results.

Code:

a*(b+c^(-d))

We could obviously do it like this...

a*(b+1/c^d)

But where would that magic "1" come from!?

That should have been obvious in hindsight... perhaps someone else can show us a way to remove the sign from the exponent. I see none (but I've been wrong before!).

Congratz on your thoroughness!

Beryllos · 02-26-2019, 02:59 PM

Quote:

Originally Posted by Beryllos

In the near future I will run some tests...

Done with that testing, for now. I did find two errors where I copied some lines as a template and somehow forgot to edit them. This affected only expressions of the forms (a?bc)?d and ab?(c?d) (? being any operator). I corrected them and re-ran just those expressions, and nothing new turned up.

I also visually confirmed that the modified expressions are correctly arranged for each of the arrangement cases, and the signs are correctly cycled. That's all the validation I planned on doing.

Before I post my latest programs, I am going to clean them up a little. Also I am thinking of posting them on a LQ blog (as astrogeek has done), and posting only the highlights and a link here in the thread. It will be at least a few days before that happens.

I am also investigating minimal sets of expressions and making some progress. I'll report that when it's further along.

astrogeek · 02-26-2019, 03:54 PM

Thanks for the update!

I have added your two new "jewels" to my own minimal expressions set and regenerated all my results. The only changes I see are the year totals you have indicated, and a few new solutions which do not affect other totals.

I agree posting more complete code and data to our LQ blogs complements the forum space nicely while keeping everything on LQ for long term availability. We have now produced so much code and data in this thread that it seems better to post the essential announcements here, but maintain complete details and code archives separately in blog posts.

I have refrained from updating my own blog so as to incorporate your new results in my data, and using the delay as cover to generally improve the quality of my own posts. I'll try to push those through as quickly as possible now.

astrogeek · 02-28-2019, 03:08 AM

In addition to finding all solutions to the puzzle, which Beryllos now seems to have done, we have also been concerned with finding a minimal set, or sets of expressions which will produce the complete solution set.

Understanding and answering such questions is the job of graph theory and set theory, so casting our solutions, permutations and expressions into a form accessible to those tools is a natural way begin to find those answers. Relational data models and query languages allow us to do that, and to formulate the problem directly in terms of set expressions, applying set operators to produce the answers.

I have imported the solution and expression sets into a relational model and performed a few such early explorations.

As an example of what can be found by this method, below is a partial answer to the problem...

Code:

For a given year, or combination, find a minimal set of expressions and permutations which will produce all solutions.

A slightly more complete discussion may be found in my most recent blog post on the topic. For 2003 one answer is:

Code:

+-------------+
| expression  |
+-------------+
| ((a+b)/c)^d |
| (a*b)+(c*d) |
| (a+b)*(c+d) |
| (a+b)^c-d   |                                           Matrix of found solutions
| a*(b+c)^d   |                                     0:    0   1   2   3   4   5   6   .   8   9
| a+b+c+d     |        +-------------+             10:   10   .   .   .   .  15   .  17   .  19
| ab*(c+d)    |        | permutation |             20:   20  21   .  23   .   .   .   .  28  29
| ab*c^d      |        +-------------+             30:   30  31  32   .   .   .   .   .   .   .
| ab+c+d      |    X   | 2030        |     =       40:    .   .   .   .   .   .   .   .   .   .
| ab+cd       |        | 3020        |             50:   50   .   .   .   .   .   .   .   .   .
| ab+c^d      |        +-------------+             60:   60   .   .   .   .   .   .   .   .   .
| ab-c+d      |                                    70:    .   .   .   .   .   .   .   .   .   .
| ab-cd       |                                    80:    .   .   .   .   .   .   .   .   .   .
| ab-c^d      |                                    90:    .   .   .   .   .   .   .   .   .   .
| ab/(c+d)    |                                   100:    .
| a^b+c+d     |                                   Total solutions 2003 = 23
+-------------+

I have only just begun to decide what questions to ask, and how to ask them, but this looks like a very interesting way to extend our explorations of this puzzle!

Beryllos · 02-28-2019, 10:27 AM

Quote:

Originally Posted by astrogeek

In addition to finding all solutions to the puzzle, which Beryllos now seems to have done, we have also been concerned with finding a minimal set, or sets of expressions which will produce the complete solution set.

Understanding and answering such questions is the job of graph theory and set theory, so casting our solutions, permutations and expressions into a form accessible to those tools is a natural way begin to find those answers. Relational data models and query languages allow us to do that, and to formulate the problem directly in terms of set expressions, applying set operators to produce the answers.

I have imported the solution and expression sets into a relational model and performed a few such early explorations...

A slightly more complete discussion may be found in my most recent blog post on the topic.

That is a fascinating and thought-provoking blog post. I too am interested in the problem of minimal sets of expressions. I have been playing around with it, looking at it from a different angle, of course.

A question: Does your program, in the default abs mode, take the absolute value just at the end, or also at earlier stages in the calculation? (In the source code, it appears to be at the very end, when you test whether the result is in the range 0 to 100, but I just wanted to make sure.)

And a related remark: Since my basic program (before looking into negative signs) doesn't change signs or take absolute value, I began looking for minimal sets in that mode. I can use your program with the -n option to do the calculations that way, and then I get the same totals.

So far I had only considered looking for minimal sets for the full set of 4-digit years. I have come up with a number: 193 expressions to reach the original 46978 results (or 195 including the 2 additional expressions with negative exponent, reaching 46980). More on that later!

astrogeek · 02-28-2019, 01:19 PM

Quote:

Originally Posted by Beryllos

A question: Does your program, in the default abs mode, take the absolute value just at the end, or also at earlier stages in the calculation? (In the source code, it appears to be at the very end, when you test whether the result is in the range 0 to 100, but I just wanted to make sure.)

My program only tests for negative values and applies the sign inversion at the final result*, not intermediate steps.

(*With the exception of negative exponents which are refactored to move the sign into the numerator of the base. I believe your program does the same thing.)

In my data model I capture the sign before that test so that I can know when the inversion has been applied and the signed value produced by the expression. I have not yet made use of that information but it will allow easy answers to whether that has occurred, and how many results are affected by it, for example.

Quote:

Originally Posted by Beryllos

And a related remark: Since my basic program (before looking into negative signs) doesn't change signs or take absolute value, I began looking for minimal sets in that mode. I can use your program with the -n option to do the calculations that way, and then I get the same totals.

I put that option in the program for that very purpose - glad to see you using it... again!

Quote:

Originally Posted by Beryllos

So far I had only considered looking for minimal sets for the full set of 4-digit years. I have come up with a number: 193 expressions to reach the original 46978 results (or 195 including the 2 additional expressions with negative exponent, reaching 46980). More on that later!

My own set is now at 178 expressions, including your two recent finds. With the above sign inversion (absolute value rule) that produces the same 46980 solutions. Which makes me ask, "How many additional expressions would there need to be in my set without the sign inversion? 193 total, maybe?". I'll try to find an answer to that.

astrogeek · 03-01-2019, 01:37 AM

It has been a while, so I read up on graphs and covering sets through the day (Elements Of Discrete Mathematics, R. E. Prather 1986 - highly recommended!) and had a few ideas for improving my algorithm for generating the minimal set as a result. Out of the gate it produced a new minimal set which has a cost of 140 as compared to 160 and 176 for the examples in my blog post. It is also a more expensive algorithm which I will want to optimize before generating new results for all combinations.

I still cannot say that this is "the" optimal set, but the fact that it led to a dramatic new solution indicates that solutions based on graph theory are on a fruitful path!

Code:

2019 Optimal 1 produces full result set, evaluation cost is 140...

+-------------+
| expression  |
+-------------+
| (a+b)/(c+d) |
| (a+b)^(c+d) |
| (a-b)^(c+d) |
| (ab/c)^d    |
| (abc)/d     |          +-------------+                   Matrix of found solutions
| a*(b-c+d)   |          | permutation |             0:    0   1   2   3   4   5   6   7   8   9
| a*(bc-d)    |          +-------------+            10:   10  11  12  13  14   .  16  17  18  19
| a+b-c^d     |          | 1029        |            20:   20  21  22   .   .   .   .  27  28  29
| ab*(c-d)    |          | 1092        |            30:   30   .   .   .   .   .   .   .  38  39
| ab+(c*d)    |          | 1290        |            40:    .   .   .   .  44  45  46   .   .   .
| ab+c+d      |    X     | 1902        |     =      50:    .   .   .   .   .   .   .   .   .   .
| ab+cd       |          | 2190        |            60:    .   .   .   .  64   .   .   .   .  69
| ab+c^d      |          | 9021        |            70:   70  71  72   .   .   .   .   .  78   .
| ab-c-d      |          | 9102        |            80:   80  81  82   .   .   .   .  87  88  89
| ab-cd       |          +-------------+            90:   90  91  92  93   .  95   .   .   .   .
| ab-c^d      |          (7 rows)                  100:  100
| ab/c+d      |                                    Total solutions 2019 = 49
| ab/c-d      |
| a^(b+c)*d   |
| a^b-c+d     |
+-------------+
(20 rows)

Beryllos · 03-02-2019, 11:09 PM

I was thinking about how inefficient it is to try 128 combinations of + and - signs for each expression, as I described a few posts back. That was fine for a one-time survey, but it's too slow for repetitive use. So I finally bit the bullet and looked at how to simplify expressions with leading negative signs anywhere.

It turns out to be really simple:
The only negative signs that we need to consider (as we look for new results) are those within exponents and the one that negates the whole expression. Here is a brief explanation of that:

For addition, subtraction, multiplication, and division, negative signs can be either "absorbed" inside the expression, as in these examples:

Code:

(-a)+b     equals    b-a
a-(-b)     equals    a+b
(-a)*(-b)  equals    a*b

or "pushed out" of the expression, as in these examples:

Code:

(-a)+(-b)  equals  -(a+b)
(-a)/b     equals  -(a/b)

In larger expressions, the negative signs can similarly be pushed out and moved to the front of the whole expression:

Code:

(-a)/b-(-c)/d  equals  -(a/b)-(-(c/d))  equals  -(a/b-c/d)

For the power operation, a negative base either has no effect, as in squaring, or it changes the sign of the result, as in cubing, or it may be rejected for fractional powers:

Code:

for positive a,
(-a)^2     equals    a^2    (sign "absorbed")
(-a)^3     equals  -(a^3)   (sign "pushed out")
(-a)^(3/2) rejected square root of negative number

The exponent is the only place where a negative sign might have to stay where it is:

Code:

a+b^(-c)   (no way to move the sign out)

but not always:

Code:

a*b^(-c)  equals  a/b^c

So the bottom line is that an expression with any arrangement of leading negative signs can be equated to another expression having only negative exponents, or a negative sign in front of the whole expression, or both.

What that means for our programming efforts is that we don't need to construct a huge number of new expressions to cover all possible combinations of signs. I have yet to work out how many independent expressions there are, but that will be my next step.

Also I see that this nicely validates astrogeek's method of taking the absolute value of negative results. It is very satisfying to see that the same result could be obtained without absolute value, using a similar expression with negative signs somewhere within.

dogpatch · 03-05-2019, 09:46 PM

Whew! You two are leaving me in the dust here!

Have not been completely idle in my long absence, flailed around some trying to produce a list of expressions to generate the full 46980 solutions. Am currently stalled at 194 expressions producing only 46890 (90 lacking). So, would be interested in your shorter list(s), and your methodology for creating them.

As a means to attempting the above, have also been working on translating algebraic expressions into RPN, instead of vice-versa as my program is doing. This seems to hold some promise for practical calculation and database routines, which i may report on when/if i have developed something substantial.