July 2018 little math problem
07-28-2018, 01:15 PM
Post: #21
 Albert Chan Senior Member Posts: 1,842 Joined: Jul 2018
RE: July 2018 little math problem, mini-challenge
I like to show why Complement Symmetry work, and why it sometimes does not.

I use a simpler 3-sided zigzag to illustrate.
Instead of using numbers 1 to 7, think of it shifted, from -3 to 3.
So, complement symmetry is just changing the sign of all numbers.

If a solution with a non-zero sum S, complement symmetrical solution has sum -S
Swapping values, reversing ... is not going to change the new sum back to S
Thus, the complement solution is unique.

If all cases were like that, we could return half as many solutions, and let user build the other half.

If the solution had zero sum, it's complement symmetrical solution also had zero sum.
Example: [-2,3,-1,0,1,-3,2]

Above solution, complement (sign change) + reversing digits = itself.

The 2 symmetries overlap (*) :-(

In order to "cut" primary in half, above situation cannot happen.
We required half of solutions to be able to derive from the other half.

Mini-Challenge:

(*) 2 symmetries does not overlap for sides = 4, 6, 8, 10, 12, 14, ... Why ?

In other words, for even sided zigzag, we can indeed reduce primary solutions in half.

You do not need a calculator to prove this ...
07-28-2018, 04:22 PM
Post: #22
 DavidM Senior Member Posts: 849 Joined: Dec 2013
RE: July 2018 little math problem
Thanks to all who are sharing their various analyses of this deceivingly simple-looking puzzle! It's a great example of how the application of deductive reasoning can greatly reduce the work needed to solve a problem.

(07-26-2018 03:43 PM)Thomas Klemm Wrote:  We can start with $$e\in\{1\ldots9\}$$. And then let $$c$$ and $$g$$ be different digits with $$c<g$$. This gives us $$9\times\binom{8}{2}=252$$ possibilities.

...

So far I've made it up to Thomas' optimizations, which I've translated into an RPL/ListExt implementation.

As expected, this brought the run time down considerably from the previous versions.
Real 50g: 63.9s
Emu48+ on laptop: 1.68s

I'm still trying to wrap my ahead around Albert's and Valentin's approach, especially in terms of how they might translate to a more familiar language.

This has proven to be an intriguing problem!

Code:
Spoiler... \<<   9. LSEQ DUP LIST\-> \-> dig a b c d e f g h i s   \<<     dig     1.     \<<       { e } STO       CRMNT       2.       \<<         IF           DUP EVAL <         THEN           { c g } STO           c e g 45. + + + DUP 's' STO           IF             4. MOD NOT           THEN             s 4. / DUPDUP 's' STO             c e + - DUP 'd' STO             SWAP e g + - DUP 'f' STO             IF               DUP2 MIN 0. >               UNROT MAX 10. <               AND             THEN               IF                 { c d e f g } LRCL LDDUP SIZE 5. SAME               THEN                 dig { c d e f g } LRCL LRMOV                 4.                 \<<                   { a b h i } STO                   IF                     a b c + + s SAME                     g h i + + s SAME                     AND                   THEN                     { a b c d e f g h i } LRCL R\->I                     DUP REV                   END                 \>>                 DOPERM EVAL               END             END           END         ELSE           DROP         END       \>>       DOPERM EVAL     \>>     DOPERM   \>> \>> The same code, with comments added: \<<   @ create digits list and declare locals   9. LSEQ DUP LIST\-> \-> dig a b c d e f g h i s   \<<     @ permute all single digits     @ I'm using DOPERM here instead of a FOR loop     @ so that I can take advantage of CRMNT to easily obtain remaining digits     dig     1.     \<<       @ save e       { e } STO       @ permute all remaining digits, in combinations of 2       CRMNT       2.       \<<         IF           @ only proceed if c < g           DUP EVAL <         THEN           @ save c,g           { c g } STO           @ determine whether s would be valid with this c,e,g           c e g 45. + + + DUP 's' STO           IF             @ only proceed if trial s is evenly divisible by 4             4. MOD NOT           THEN             @ convert trial s (4s) to final s             s 4. / DUPDUP 's' STO             @ compute d and f             c e + - DUP 'd' STO             SWAP e g + - DUP 'f' STO             IF               @ only proceed if d and f are valid digits               DUP2 MIN 0. >               UNROT MAX 10. <               AND             THEN               IF                 @ only proceed if c,d,e,f,g are all unique                 { c d e f g } DUP SIZE SWAP LRCL LDDUP SIZE SAME               THEN                 @ select remaining digits for a b h i, then                 @ check all permutations                 dig { c d e f g } LRCL LRMOV                 4.                 \<<                   @ store a,b,h,i                   { a b h i } STO                   IF                     @ only proceed if sum(a,b,c) and sum(g,h,i) = s                     a b c + + s SAME                     g h i + + s SAME                     AND                   THEN                     @ all checks passed, add digits and their                     @ mirrored form to result                     @ (R->I simply added to remove fraction marks)                     { a b c d e f g h i } LRCL R\->I                     DUP REV                   END                 \>>                 DOPERM EVAL               END             END           END         ELSE           DROP         END       \>>       DOPERM EVAL     \>>     DOPERM   \>> \>>
07-29-2018, 12:10 AM (This post was last modified: 07-29-2018 08:12 PM by Albert Chan.)
Post: #23
 Albert Chan Senior Member Posts: 1,842 Joined: Jul 2018
RE: July 2018 little math problem
(07-28-2018 04:22 PM)DavidM Wrote:  I'm still trying to wrap my ahead around Albert's and Valentin's approach,
especially in terms of how they might translate to a more familiar language.

This has proven to be an intriguing problem!

Hi, DavidM:

With comments, I can finally understand the code. Thanks.
I do not own any HP calculators (except a hand-me-down HP-12C)

I tried coding in Python, and possibilities is not as high as 252

Brute force all possible values of sum, and it only need 144
Even if sum of 15 is added (why?), it will only reach 180
With complement symmetry, it could be reduced to 72

4 s = 45 + c + e + g
= (45 + 1 + 2 + 3) to (45 + 7 + 8 + 9)
= 51 to 69
= 52, 56, 60, 64, 68

--> s = 13, 14, 15, 16, 17

when s = c + d + e =15, c + e + g = 4 s - 45 = 15, which imply d=g, thus s != 15

Code:
for s in [13, 14, 16, 17]:     ceg = 4*s - 45     for c in range(1,9):         for g in range(c+1, 10):             e = ceg - c - g             d = s - e - c             f = s - e - g             valid = range(10);              # all single digits             try: valid[c] = valid[d] = valid[e] = valid[f] = valid[g] = 0             except IndexError: continue                         if valid.count(0) != 6: continue             head = s - c                    # almost done!, now confirm             valid = filter(None, valid)     # remove the zeroes             for x in valid:                 if head - x == x: continue                 if head - x in valid: head = [x, head-x]; break             if type(head) == int: break     # head no good ?             tail = [x for x in valid if x not in head]             print head, c, d, e, f, g, tail

And, the expected result ...

[3, 9] 1 8 4 7 2 [5, 6]
[6, 7] 1 5 8 4 2 [3, 9]
[5, 8] 1 6 7 4 3 [2, 9]
[4, 8] 2 9 3 5 6 [1, 7]
[1, 9] 4 8 2 7 5 [3, 6]
[2, 8] 4 9 1 7 6 [3, 5]
[5, 7] 4 3 9 1 6 [2, 8]
[3, 9] 4 5 7 1 8 [2, 6]
[4, 7] 5 3 8 2 6 [1, 9]
[1, 8] 7 6 3 4 9 [2, 5]
[1, 7] 8 6 2 5 9 [3, 4]
[4, 5] 8 3 6 2 9 [1, 7]
07-29-2018, 01:02 PM
Post: #24
 Albert Chan Senior Member Posts: 1,842 Joined: Jul 2018
RE: July 2018 little math problem
(07-28-2018 01:15 PM)Albert Chan Wrote:  Mini-Challenge:

(*) 2 symmetries does not overlap for sides = 4, 6, 8, 10, 12, 14, ... Why ?

In other words, for even sided zigzag, we can indeed reduce primary solutions in half.

You do not need a calculator to prove this ...

The problem of complement symmetry was its overlap with reversing digits symmetry.
This led to its inability to generate unique symmetrical solutions.

To follow the notation of the 4-sided zigzag, let e be middle number of an even-sided zigzag.
Let's shift the numbers, so available digits = -side to side

Assume 2 symmetries overlap, middle zigzag look like this:

(c d e f g) => (c d 0 -d -c)

For the center, sum = 0, e = 0, we have:

(c d e f g) => (c -c 0 f -f)

so, for both equation g = -c = -f, or c = f
But, all numbers must be different, assumption was wrong => 2 symmetries have no overlap.

For even-sided zigzag, we can cut primary solutions in half.

QED
07-29-2018, 10:27 PM
Post: #25
 Albert Chan Senior Member Posts: 1,842 Joined: Jul 2018
RE: July 2018 little math problem
Slight changes to my posted Python code (post 23) dramatically reduce checks down to 17 cases

Only patch is to change the loop range:
s range = [13, 14]
c range = range(max(1, ceg-8-9), min(9, ceg//2))
g range = range(c+1, min(10, 10 - s + ceg))

s range is reduced by taking advantage of 10-Complement Symmetry

c range is reduce because of this: c + e + g = ceg
min(c) = ceg - max(e + g) = ceg - 8 - 9
max(c) = ceg - min(e) - min(g) = ceg - 1 - (max(c) + 1)
max(c) * 2 = ceg - 2
max(c) < floor(ceg / 2)

g range is reduced because d = s - c - e = (s - ceg) + g
Since g is increasing inside loop, d is also increasing, remove invalid d, we get:
max(d) = (s - ceg) + max(g) < 10
max(g) < 10 - s + ceg

With above ranges, these are the only cases checked:

#1: 1 8 4 7 2 => [3, 9] 1 8 4 7 2 [5, 6]
#2: 1 9 3 7 3
#3: 2 9 2 8 3
#4: 1 5 8 4 2 => [6, 7] 1 5 8 4 2 [3, 9]
#5: 1 6 7 4 3 => [5, 8] 1 6 7 4 3 [2, 9]
#6: 1 7 6 4 4
#7: 1 8 5 4 5
#8: 1 9 4 4 6
#9: 2 6 6 5 3
#10: 2 7 5 5 4
#11: 2 8 4 5 5
#12: 2 9 3 5 6 => [4, 8] 2 9 3 5 6 [1, 7]
#13: 3 7 4 6 4
#14: 3 8 3 6 5
#15: 3 9 2 6 6
#16: 4 8 2 7 5 => [1, 9] 4 8 2 7 5 [3, 6]
#17: 4 9 1 7 6 => [2, 8] 4 9 1 7 6 [3, 5]

16X Symmetries: head swap, tail swap, reversing digits, 10-complement

Solutions = 6 primary solutions * 16 = 96
07-31-2018, 08:19 PM
Post: #26
 Komanguy Junior Member Posts: 49 Joined: Jul 2018
RE: July 2018 little math problem
Cyrille de Brebisson, could you explain your algorithm?

Guy R. KOMAN, hp 50G, hp Prime Rev. C
07-31-2018, 10:49 PM
Post: #27
 Albert Chan Senior Member Posts: 1,842 Joined: Jul 2018
RE: July 2018 little math problem
Hi, Komanguy

I did a Python version of the zigzag Hp Prime program. With comments, perhaps this is easier to follow:

Code:
def zigzag_prime(slot, filled):     if filled >= 5:             # 2 or more sums to match         sum = slot + slot + slot         if filled == 5:             if sum != slot + slot + slot: return         elif filled == 7:             if sum != slot + slot + slot: return         elif filled == 8:       # same as filled == 9, but faster             if sum == slot + slot + slot: print slot[1:]             return              # success or not, quit     next = filled + 1           # validated, add next digit     old = slot[next]     for i in range(next, 10):   # slot[1 to filled] is FIXED         new = slot[i]         slot[next], slot[i] = new, old      # try it all         zigzag_prime(slot, next)            # recurse         slot[next], slot[i] = old, new      # restore slot          zigzag_prime(range(10), 0)      # nothing filled yet
08-01-2018, 11:31 AM
Post: #28
 Komanguy Junior Member Posts: 49 Joined: Jul 2018
RE: July 2018 little math problem
Thanks a lot, Albert.

Cheers.

Guy R. KOMAN, hp 50G, hp Prime Rev. C
08-01-2018, 02:13 PM
Post: #29
 pier4r Senior Member Posts: 2,090 Joined: Nov 2014
RE: July 2018 little math problem
Albert kudos for the effort and sharing!

Wikis are great, Contribute :)
08-03-2018, 05:25 PM (This post was last modified: 05-19-2019 11:31 PM by Albert Chan.)
Post: #30
 Albert Chan Senior Member Posts: 1,842 Joined: Jul 2018
RE: July 2018 little math problem
I revised zigzag.pi with better constraints

Code:
import cp.                  % Usage: picat zigzag.pi [Sides=4] main => main(4).            % Default: 4-sided zigzag main([Sides]) => main(to_integer(Sides)). main( Sides ) => Sides > 2, (zigzag(Sides), fail; true). zigzag(Sides) =>   N = 2*Sides + 1,          % number of numbers (always Odd)   A = new_list(N),          % unknown variables   A :: 1..N,   all_different(A),   M = [N-1,N] ++ (1..N-2),  % head moved to back for speedup   A[M] #< A[M],       % 2X solution by swap head pairs   A[M[N-1]] #< A[M[N]],     % 2X solution by swap tail pairs   A[M] #< A[M[N-2]],     % 2X solution by flip the zigzag   C = N + 1,                % C-complement Symmetry   Center = C * 3 // 2,      % C-Complement Sum Center   S #<= Center,             % Symmetry with slight over-count   Total = N*(N+1) // 2,     % Speed-up with non-vertices constraint   K = Sides//2 + 1,         % Remove as much vertices as possible   (odd(Sides) ->            % For odd-Sided zigzag, no vertices left    sum([A[M[I]]: I in N-3..-4..4]) #= Total - K*S ;    sum([A[M[I]]: I in N-3..-4..4]) #= Total - K*S + A[M]   ),   foreach(I in 1..2..N-4)   % All sides sum to S (tail side skipped)     A[M[I]] + A[M[I+1]] + A[M[I+2]] #= S   end,   solve(A),   writeln([A[I]: I in M]),   % Add C-Complement Symmetry Solution   S < Center, writeln([C-A[I]: I in M]).

For 10-sided zigzag, speed (vs. original) = 2.37X, or 137% faster (finished in 111 seconds)
08-13-2018, 01:54 AM
Post: #31
 Dave Britten Senior Member Posts: 2,074 Joined: Dec 2013
RE: July 2018 little math problem
Here's my straight-forward Turbo Pascal version. It's just depth-first tree traversal with bail-out checks at each vertex. Takes about 12 seconds to find 96 solutions to the 4-sided 1-9 puzzle on my 200LX.

Code:
 Program Zigzag; Var     Used : Array[1..9] Of Boolean;     Nums : Array[1..9] Of ShortInt;     Total : ShortInt;     Solutions, FillCalls : Integer; Procedure WriteNums; Var     i : ShortInt; Begin     For i := 1 To 9 Do     Begin         If i > 1 Then Write(', ');         Write(Nums[i]);     End;     WriteLn(' (', Total, ')');     Inc(Solutions); End; Procedure Fill(Pos : ShortInt); Var     i : ShortInt; Label     Skip; Begin     Inc(FillCalls);     For i := 1 To 9 Do     Begin         If Not Used[i] Then         Begin             Used[i] := True;             Nums[Pos] := i;             If Pos = 3 Then                 Total := Nums + Nums + Nums             Else If (Pos = 5) Or (Pos = 7) Or (Pos = 9) Then             Begin                 If Nums[Pos] + Nums[Pos - 1] + Nums[Pos - 2] <> Total Then                     Goto Skip;             End;             If Pos = 9 Then                 WriteNums             Else                 Fill(Pos + 1); Skip:             Used[i] := False;             Nums[Pos] := 0;         End;     End; End; Begin     FillChar(Used, Sizeof(Used), #0);     FillChar(Nums, Sizeof(Nums), #0);     Total := 0;     Solutions := 0;     FillCalls := 0;     Fill(1);     WriteLn;     WriteLn('Total solutions: ', Solutions);     WriteLn('Recursive calls: ', FillCalls); End.
 « Next Oldest | Next Newest »

User(s) browsing this thread: 1 Guest(s)