Threaded Mode | Linear Mode

Don Shepherd · 04-02-2015, 10:08 PM

(04-02-2015 08:58 PM)RayAtHP Wrote: Don, maybe you should reconsider your initial request ...

Quote:I expect a one line RPL solution, as usual! I would love to see a BASIC solution.

A quick scan of Mings transcript could lead to massive exhaustion under RPL programmers if they try to comply to your request.

Oh, I didn't really expect a one-line RPL solution. But I've posted several puzzle challenges over the years in which the very clever RPL people posted very short RPL solutions to what I thought would be rather complex problems, and I am always kind of in awe of those people and their programs.

But I am not awed quite enough to want to learn RPL myself!

Claudio L. · 04-02-2015, 10:53 PM

(04-01-2015 12:25 PM)Claudio L. Wrote: Back to the drawing board.

To speed up the program, it seems is optimum (Paul made a good call there) to choose the corners as the independent variables. This makes the first 6 equations to try also the shortest (3 elements), fastest, and completely decoupled, only dependent on the 6 known variables. This allows for quickly discarding a lot of cases.
The 7th variable needs to be in the inner hexagon, but not the center (choosing the center results in coupled equations, so you can't solve all variables one by one without working out the algebra to decouple the equations first).
I'll see if I can rework the RPL code to work with this new numbering scheme and will report on the speed improvement.

Paul Dale · 04-02-2015, 11:11 PM

Early pruning of the search is probably also advisable, I suspect it doesn't save a lot of searching but every bit helps.

The search space can be reduced by forcing the first corner chosen to be the smallest corner and not producing the six rotations for each solution. The first corner can then only range from 1 through 14 and the other corners must be larger.

- Pauli

Claudio L. · 04-03-2015, 11:31 AM

(04-02-2015 10:53 PM)Claudio L. Wrote: I'll see if I can rework the RPL code to work with this new numbering scheme and will report on the speed improvement.

I think I found a way to simplify the algorithm to solve the outer ring.

If we number the values consecutively n(i), turns out that for any two values in the outer ring:

n(i)+n(i-1)>=19

Which limits a lot the set of numbers we can pick from.

Also from the equations:

n(i+1)=38-n(i)-n(i-1)

So the algorithm can work like this:

Put a number on the stack from 1 to 19 (in a FOR loop), as the first number, and call the recursive routine.

A recursive routine will simply do:

Add a number on the stack from 19-n(i) to 19 in a FOR loop.
Check that the new number is not taken (as in not already present in the stack).
If not taken, add a second number n(i+1)=38-n(i)-n(i-1)
Check that this new number is not taken. If not taken, recurse, otherwise drop the last two values and continue to loop.

This routine also has to check if we already did the 6 corners. In such case, needs to do the special case to connect the last corner with the first, and if it works, we have a solution to the outer ring.

The inner ring is easy: there's one independent variable and can only take 7 possible numbers, so it's easy to check in a separate routine, once the outer ring is solved.

With this algorithm, there's very little math, most of the time is spent checking that a number in level 1 of the stack is not present in the stack already, which should be fast I think.

I'll see if I can put this together during the weekend. Feel free to beat me to it!

Claudio L. · 04-03-2015, 07:04 PM

Good news. The outer ring solution only took about 40 minutes on the 50g to complete the checks for one initial value, and determine all solutions for the other 5 independent variables.
When I add the inner ring checks (which only need to be checked for the solutions found in the outer ring, which were 160 for the initial value of 3, so they are not that many), I estimate it will be about 1 hr per initial value worst case.
To cover all 19 initial values, the total running time is now down to 19 hrs to obtain all solutions.
This is now into "tolerable" territory.
newRPL should be able to do this with a speedup of about 200x (per these results), which would put it around 6 minutes.

I'll report back with the source code once I complete the inner ring checks.

**rprosperi** · 04-03-2015, 07:36 PM

(04-03-2015 07:04 PM)Claudio L. Wrote: Good news. The outer ring solution only took about 40 minutes on the 50g to complete the checks for one initial value, and determine all solutions for the other 5 independent variables.
When I add the inner ring checks (which only need to be checked for the solutions found in the outer ring, which were 160 for the initial value of 3, so they are not that many), I estimate it will be about 1 hr per initial value worst case.
To cover all 19 initial values, the total running time is now down to 19 hrs to obtain all solutions.
This is now into "tolerable" territory.
newRPL should be able to do this with a speedup of about 200x (per these results), which would put it around 6 minutes.

I'll report back with the source code once I complete the inner ring checks.

Hope you have a nice supply of batteries handy.... wow, 19 hours of continuous 50g run-time. Now that's a serious amount of calculating. Did you peek at the author's paper to know the answer you should be getting?

Han · 04-03-2015, 08:09 PM

(04-03-2015 07:36 PM)rprosperi Wrote:
(04-03-2015 07:04 PM)Claudio L. Wrote: Good news. The outer ring solution only took about 40 minutes on the 50g to complete the checks for one initial value, and determine all solutions for the other 5 independent variables.
When I add the inner ring checks (which only need to be checked for the solutions found in the outer ring, which were 160 for the initial value of 3, so they are not that many), I estimate it will be about 1 hr per initial value worst case.
To cover all 19 initial values, the total running time is now down to 19 hrs to obtain all solutions.
This is now into "tolerable" territory.
newRPL should be able to do this with a speedup of about 200x (per these results), which would put it around 6 minutes.

I'll report back with the source code once I complete the inner ring checks.

Hope you have a nice supply of batteries handy.... wow, 19 hours of continuous 50g run-time. Now that's a serious amount of calculating. Did you peek at the author's paper to know the answer you should be getting?

Just plug it into a USB port and you can run without batteries :-)

PANAMATIK · 04-03-2015, 08:43 PM

Perhaps you are aware, perhaps not, that many other members or nonmembers are reading this thread with great pleasure, seeing your efforts and results, without being able to participate in these kind of mathematics games, but admiring it. I'm one of these quiet readers and want to congratulate any of you in advance for finding all the n-th order solution eggs.

Happy Easter!
Bernhard

Claudio L. · (This post was last modified: 04-05-2015 02:37 AM by Claudio L..)

(04-03-2015 08:43 PM)PANAMATIK Wrote: Perhaps you are aware, perhaps not, that many other members or nonmembers are reading this thread with great pleasure, seeing your efforts and results, without being able to participate in these kind of mathematics games, but admiring it. I'm one of these quiet readers and want to congratulate any of you in advance for finding all the n-th order solution eggs.

Happy Easter!
Bernhard

Thanks for the encouragement. You shall be rewarded with the full source code:

For proper code optimization, this is the variable numbering (quite strange for humans, but optimized for the machine:

Code:

       A   B   C

     L   R   M   D

   K   Q   S   N   E

     J   P   O   F

       I   H   G

A trough L are the outer ring, where we can write the first 6 equations with only 3 letters each, and completely decoupled from the rest. This allows to solve for the first 6 variables out of seven. As explained in my previous post, the code walks the perimeter setting a number for A, then trying all values of B knowing A+B>=19, and computing C per the corresponding equation C=38-(A+B).

This is done by this code:

Code:

@@ AUXILIARY ROUTINE 'TAKEN' CHECKS IF THE NUMBER ON LEVEL 1

@@ WAS ALREADY PRESENT IN THE STACK, RETURNS 1=WAS TAKEN, 0=NOT REPEATED

<< DEPTH IF 1 <= THEN 0 ELSE

         0 -> RESULT << 

         DEPTH 1 + 3 SWAP FOR K DUP K PICK 

         IF == THEN 1 'RESULT' STO 1000 'K' STO END NEXT 

         RESULT >> 

         END

 >> 'TAKEN' STO 

@@ ROUTINE DOLOOP DOES THE RECURSION FOR THE OUTER RING

@@ EXPECTS THE FIRST VALUE TO BE ON THE STACK ALREADY

@@ IT LEAVES ONLY THAT ORIGINAL VALUE ON THE STACK UPON EXIT

@@ TRIES ALL POSSIBLE COMBINATIONS OF THE OUTER RING

 << DEPTH IF 11 == THEN 

@@ SPECIAL CASE TO "CLOSE" THE RING ONCE WE HAVE ALL VARIABLES

        11 PICK OVER + 38 SWAP - 

             IF TAKEN NOT OVER 1 >= AND OVER 19 <= AND THEN 

@@ IF THE RING "CLOSED", THEN DO THE INNER RING CHECK...

                  CHKINNER 

             END DROP 

        ELSE 

@@ REGULAR CASE, TRY ALL VALUES IN A LOOP FOR THE NEXT NUMBER

            19 OVER - DUP 1 < + 19 SWAP FOR K K 

                    IF TAKEN THEN DROP ELSE

                            2 DUPN + 38 SWAP -

                            IF TAKEN NOT THEN DOLOOP END

                            DROP DROP

                    END

            -1 STEP

        END

 >> 'DOLOOP' STO

M is the 7th independent variable. Once the outer ring is known, trying all possible values for M allows to calculate all letters N through R in the "inner ring" by using the 4-term equations.
N=38-(B+M+F)
O=38-(D+N+H)
...

The inner ring code expects to find already on the stack the 12 variables A through L with L on level 1.
The inner ring is solved by this code:

Code:

@@ ROUTINE CHKINNER, COMPUTES THE LAST REMAINING INDEP. VARIABLE

@TRY ALL NUMBERS FROM 1 THROUGH 19 IN A LOOP

 << 1 19 FOR K 

          K IF TAKEN THEN DROP ELSE

@@ IF THE NUMBER WAS VALID, THEN SOLVE FOR N THROUGH R

@@ USING THE EQUATIONS WITH 4-TERMS

                   IF  1 -> INNERCHECK << 1 5 FOR J 13 J 2 * - DUP 

                                                       IF 1 < THEN 12 + END J + PICK 

                                                       10 J 2 * - DUP

                                                       IF 1 < THEN 12 + END J + PICK

                                                       + OVER + 38 SWAP -

                                                       IF TAKEN OVER 1 < OR OVER 19 > OR THEN 

                                                       J DROPN 0 'INNERCHECK' STO 1000 'J' STO

                                                       END

                                                       NEXT

                                                       INNERCHECK >> 

                   THEN

@@ INNER RING CHECKS OUT, NOW CHECK THE 

@@ CENTER VALUE BEFORE WE CLAIM TO HAVE A SOLUTION

                         IF CHKCENTER THEN

@@ WE HAVE A SOLUTION, ADD IT TO A LIST CALLED 'SOLUTIONS'

                              19 DUPN 19 ->LIST 1 ->LIST

                              SOLUTIONS SWAP + 'SOLUTIONS' STO

                              7 DROPN

                         ELSE 6 DROPN 

                         END

                  ELSE DROP

                  END

       END

       NEXT

  >> 'CHKINNER' STO

Finally, we need to do the proper checks with the center value (last position, S).
All we have to do is find the only number that was not taken in the stack and check all 3 equations with 5-terms.

This is done here:

Code:

@@ ROUTINE CHKCENTER CHECKS IF THE CENTER VALUE IS CORRECT

@@ USING THE 5-TERM EQUATIONS

 << 1 19 FOR K

       K IF TAKEN NOT THEN 1000 'K' STO ELSE DROP END

       NEXT

        19 PICK 3 PICK + OVER + 6 PICK + 14 PICK + IF 38 == THEN

                  17 PICK 8 PICK + OVER + 5 PICK + 12 PICK + IF 38 == THEN

                            9 PICK 4 PICK + OVER + 7 PICK + 16 PICK + IF 38 == THEN

                                         1

                            ELSE DROP 0 END

                  ELSE DROP 0 END

        ELSE DROP 0 END

 >> 'CHKCENTER' STO

And to wrap it all up, the code above needs a couple of things to run properly:

A variable named 'SOLUTIONS' initialized to an empty list
A clear stack
A loop to try all 19 initial values

This is done here:

Code:

@@ ROUTINE RUNIT DOES THE COMPLETE TEST

 << { } 'SOLUTIONS' STO

       CLEAR

       1 19 FOR I I DOLOOP DROP NEXT

       SOLUTIONS LIST->

 >> 'RUNIT' STO

For the short of patience, partial tests can be ran, if you put a partial list of numbers (must be a valid partial solution, of course), and run the DOLOOP test to see if any solutions are found.
Just make sure 'SOLUTIONS' contains an empty list and that there's nothing else in the stack but your partial solution.
The partial solution has to contain 1, 3, 5... elements. In other words, think of the corners as the independent variables, then to give 2 independent variables you must also provide the intermediate value between them (A, B and C).

This is tested and finds all 12 solutions, but of course I tested it on a PC with newRPL, don't have the patience to wait 19 hours, but if somebody does, please measure time and report here.

Happy coding.

PS: Still not a one-line RPL solution... but faster than my first try at 97 days!

EDIT:
Forgot to mention, if you don't wait to wait 19 hours, and don't care about the different rotations, you can get a nice solution by doing:

Code:

 { } 'SOLUTIONS' STO 3 DOLOOP

This will leave SOLUTIONS with all solutions that have a 3 in the first variable: exactly 2 solutions, one mirror of the other, and only for about 1 hr of your time.

Claudio L. · 04-04-2015, 12:53 PM

(04-03-2015 07:36 PM)rprosperi Wrote: Did you peek at the author's paper to know the answer you should be getting?

No author's paper, just this thread, paper, pencil and a PC with newRPL.

Don Shepherd · 04-04-2015, 03:06 PM

(04-04-2015 12:48 PM)Claudio L. Wrote: PS: Still not a one-line RPL solution... but faster than my first try at 97 days!

Claudio, that is great work, thank you.

Can you clarify, is there only one real solution, the others being reflections or rotations of the one? The puzzle-maker claimed several solutions, but I have a feeling that they are all reflections/rotations of the original.

Don

Claudio L. · 04-04-2015, 06:44 PM

(04-04-2015 03:06 PM)Don Shepherd Wrote: Claudio, that is great work, thank you.

Can you clarify, is there only one real solution, the others being reflections or rotations of the one? The puzzle-maker claimed several solutions, but I have a feeling that they are all reflections/rotations of the original.

Don

There's only one "true" solution. The rest are rotations and mirror images.
There's all kinds of interesting observations on this problem.
For example, I replaced the routine CHKINNER to always store the solution instead of checking the inner ring, to obtain all the outer ring solutions:

Code:

@@ CHKINNER REPLACEMENT THAT ACCEPTS ALL SOLUTIONS

   << 12 DUPN 12 ->LIST 1 ->LIST SOLUTIONS SWAP + 'SOLUTIONS' STO >>

Turns out that starting with the number 3 as the first variable, there's 160 solutions of the outer ring (actually 80 if you remove the mirrors). Among these sets, only 2 (one and its mirror) will pass the inner ring check.
Starting with number 4, there's 184 solutions to the outer ring (actually 92), but none of them will pass the inner ring check.

Claudio L. · 04-04-2015, 07:02 PM

(04-02-2015 11:11 PM)Paul Dale Wrote: Early pruning of the search is probably also advisable, I suspect it doesn't save a lot of searching but every bit helps.

The search space can be reduced by forcing the first corner chosen to be the smallest corner and not producing the six rotations for each solution. The first corner can then only range from 1 through 14 and the other corners must be larger.

- Pauli

If we are discarding, then the count would start from 3, as 1 and 2 are easy to discard as follows:

If a vertex contains 1, the 2 adjacent variables can only be 18 and 19 (left and right, or viceversa doesn't matter), because n(i)+n(i-1)>=19.
The following corners would have to be:
38-18-1 = 19
38-19-1 = 18
But both numbers are already being used, so we can conclude the number 1 cannot appear on any vertex.
Similar deal with number 2, the adjacent can only be 17, 18 and 19, and the following corners would be 17,18 or 19, it's easy to see that we have 3 valid numbers to fill in 4 spaces, so there's no solution, concluding that 2 cannot be on any vertex of the solution.

There might be other logical rules like these ones to discard more options that could help a human solve the problem by hand.

Paul Dale · 04-04-2015, 11:43 PM

(04-04-2015 07:02 PM)Claudio L. Wrote: If we are discarding, then the count would start from 3, as 1 and 2 are easy to discard as follows:

I thought there was a way to exclude these two but didn't think it through enough.

Getting rid of reflections is easy by forcing the order of two adjacent edge middles. E.g. B>D. This would give an early pruning of the search space.

- Pauli

Claudio L. · 04-05-2015, 02:29 AM

(04-04-2015 11:43 PM)Paul Dale Wrote: Getting rid of reflections is easy by forcing the order of two adjacent edge middles. E.g. B>D. This would give an early pruning of the search space.

I think it eliminates some reflections but may not work all the time, because depending on your choice of variables you are using a different axis of symmetry.
For example, the 2 solutions with initial variable A=3 are:

Code:

A  B  C  D ...

3 19 16 12 10 13 15 14 9 11 18 17 | 2 4 8 6 1 7 5

3 17 18 11 9 14 15 13 10 12 16 19 | 1 6 8 4 2 7 5

These two solutions are clearly reflections, but B>D is true in both cases.
In this case, B>L would be perhaps a better choice since it is mirroring about the axis that passes through the initial value and the center of the hexagon.
But this would only eliminate a solution after we computed L, which means we already have the outer ring completely solved, so not much of a speedup in this algorithm. Also, it wouldn't eliminate the reflections of the rotated solutions, since the axis of symmetry is different. Perhaps if the algorithm tried to advance in both directions at once it would be much quicker to eliminate the reflections (but what a mess trying to find values with PICK for the equations!).

In any case, I'm inclined to leave those optimizations "as an exercise for the reader".

Paul Dale · 04-05-2015, 03:24 AM

You are correct, it has to be B and L. You could force C to be smallest in which case it would be B and D but this complicates.

Thinking about it more, H and F would also work since they are on the same axis of symmetry. They'd likely be better than B and L since the pruning would occur earlier.

- Pauli