Challenging Christmas Puzzle

[Platypus]

D'oh! It will probably take at least an hour to code up

I'm trying 'quick n dirty' variation before I do that!

Taking your idea, after populating 3 rows, I can do a quick 'yes/no' lookup. For example, let's say that I have
54141
54213
54222
I ask the question 'are there are columns which begin 555?' and go no further if the answer is no
And 'are there any columns which begin 444?' and go no further if the answer is no
And 'are there any columns which begin 122?' and go no further if the answer is no
Similarly for the final two columns

Not anything like as selective as your 'complete' solution, but perhaps a useful short cut. And much easier to code!

EDIT: Bah humbug, only fractionally quicker than before, as suspected (i.e. it should execute in 117/125ths of the time)

[OwlHoot]

You may be able to whittle down your code a bit more with the observation that for every solution there is a sort of "dual" solution whose terms are 6 less the corresponding terms of the original. i.e.

a b ...

c d ...

:::

has the dual array :

(6 - a) (6 - b) ..

(6 - c) (6 - d) ..

:::

In particular, you can assume that the top-left element (or element at whatever position suits your script) doesn't exceed 3

Apologies if this has already been mentioned, but it's been a while since I read the whole thread.

edit: I've completed my algebraic solution (see posts on screen 3), and the indications are there are shed loads of solutions! If you want a confirmation of the results your script produces, maybe I'll knock up a script based on my solution.

[Platypus]

edit: I've completed my algebraic solution (see posts on screen 3), and the indications are there are shed loads of solutions! If you want a confirmation of the results your script produces, maybe I'll knock up a script based on my solution.

That'd be great, if you could. I'm very impressed with the algebraic solution indeed. I suspect it's the version that will run the fastest once implemented.

Thanks to some great contributions from Timberwolf, my 'brute force' method has become much more refined, with far fewer negative checks than previous incarnations.

In fact, the latest version of the code finished running in the early hours and also indicated shed loads of solutions. Reassuringly, the number of solutions is divisible by 8, which I believe is as it should be.

I'm now removing some unnecessary 'belt and braces' cross-checking in my program to see how fast it will run unbridled.
My version is written in compiled 'C' so be be fair I have a massive speed advantage over any script-based solution, and anyway, my Perl skills aren't strong enough to allow me to code it quickly

OH, when you get your results, let's compare and then we can pretend to be totally non-plussed when the answers match, which of course they should!

[Platypus]

Run time was 13 minutes

Number of solutions: less than 1 million, more than 500,000

I'll spend some time cross-checking this and that before I pat myself on the back.

[OwlHoot]

In fact, the latest version of the code finished running in the early hours and also indicated shed loads of solutions. Reassuringly, the number of solutions is divisible by 8, which I believe is as it should be.

Yup, each one comes in a pack of up to 8, obtained by rotating it four times then flipping it about a diagonal or row or column and rotating another four times (easier to picture of it that way I think than all those flips I listed earlier). However, there may be symmetric solutions for which some of these 8 collapse down to fewer distinct arrays. So a total divisible by 8 wasn't a certainty up front.

OH, when you get your results, let's compare and then we can pretend to be totally non-plussed when the answers match, which of course they should!

Right, I'm on it. (Wasn't sure if you were still working on it).

That was a good idea not to mention your result just yet.

[OwlHoot]

Run time was 13 minutes

Number of solutions: less than 1 million, more than 500,000

I'll spend some time cross-checking this and that before I pat myself on the back.

Hmm, my perl script gives a slightly different answer, although still pretty huge:

Number of HVD-merge solutions: 11
Number of HV-merge solutions: 40
Number of H-merge solutions: 12124
Number of original solutions: 162688 <--
time taken: 0 mins 50 secs

It's also divisible by 8, but has rather strange prime factors 2, 31, 41 which I wouldn't have expected. I'd have thought it would be more likely to have lots of 2s, 3s, and 5s.

One thing that slows my script down is the need to check you have the right number of 1s, 2s, .. Presumably yours does that too.

But the script is so damned intricate, I wouldn't be at all surprised if your answer wasn't correct and mine wrong.

[TimberWolf]

I'll knock out a quick program, probably on a similar theme to that used by Platypus, and see how many I get.

[OwlHoot]

I'll knock out a quick program, probably on a similar theme to that used by Platypus, and see how many I get.

Great stuff - I'll look forward to seeing the result, and so I'm sure will Platypus.

Maybe a moderately efficient approach, starting with a list of every 5-sequence (in any order) summing to 15, would be to build a list of "crosses", which could serve both as diagonal pairs and centre row/column pairs.

(These cross lists would just be a list of 5-sequence indexes for each centre value of the sequence (from which the crosses could easily be inferred on the fly by a double-loop through one of these lists).

Then, for each value 1 - 5 set up a list of 5-sequence indexes of all 5-sequences starting with that value, and looping through these starting value lists joining 5-sequences head-to-tail to construct "perimeters" i.e. every possible outermost square.

As each perimeter is constructed, run through the cross lists twice to fit into it every possible pair of diagonals and centre row/column pair.

To allow rapid choice of crosses for a perimeter you would need 625 (= 5^4) "join tables", calculated as a one-off exercise up front, one per pair of start and end sequence values and with each such table listing: cross centre value, cross index#1, cross index #2 (where the cross centre value indicates the cross table to use).

For each such double cross fit to a perimeter, check that five of each value has been used in the construct so far plus the remaining 4 values, and finally try the 16 possible combinations of these remaining values in the remaining 4 positions.

Job done

[TimberWolf]

Great stuff - I'll look forward to seeing the result, and so I'm sure will Platypus.

Maybe a moderately efficient approach, starting with a list of every 5-sequence (in any order) summing to 15, would be to build a list of "crosses", which could serve both as diagonal pairs and centre row/column pairs.

(These cross lists would just be a list of 5-sequence indexes for each centre value of the sequence (from which the crosses could easily be inferred on the fly by a double-loop through one of these lists).

Then, for each value 1 - 5 set up a list of 5-sequence indexes of all 5-sequences starting with that value, and looping through these starting value lists joining 5-sequences head-to-tail to construct "perimeters" i.e. every possible outermost square.

As each perimeter is constructed, run through the cross lists twice to fit into it every possible pair of diagonals and centre row/column pair.

To allow rapid choice of crosses for a perimeter you would need 625 (= 5^4) "join tables", calculated as a one-off exercise up front, one per pair of start and end sequence values and with each such table listing: cross centre value, cross index#1, cross index #2 (where the cross centre value indicates the cross table to use).

For each such double cross fit to a perimeter, check that five of each value has been used in the construct so far plus the remaining 4 values, and finally try the 16 possible combinations of these remaining values in the remaining 4 positions.

Job done

I've gone simple. Just combinations of the 381 'Platypus lines', for 4 rows (381^4 combinations, which is a lot, but a minimal amount of code will be inside that loop before rejection). The last row being inferred from the rest.

Then simple rejection rules:

New columns, last row and diagonals must sum to 15
Count the number of digits in the entire grid (must be 5 of each)

That should be all rows, diagonals, columns and tiles counted and checked.

It's running now.

[TimberWolf]

I get 836,864 solutions after 19 minutes running time in debug mode in VB.Net. 21, 071,715,921 positions examined, if only very briefly for the majority of them.

How many combinations are the on this grid, including those that don't add up to 15? Clearly this isn't as simple to calculate as 25! What is the divisor (I assume it's 25! divided by something), where there are 5 (*5) of each digit the same? Knowing that might give some indication of how inefficient these simple searches are compared to the efficiency they could approach. Certainly 836,864 is a drop in the ocean compared to 21, 071,715,921.