July 2018 little math problem

[Albert Chan]

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 ...

[DavidM]

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
  \>>
\>>

[Albert Chan]

(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]

[Albert Chan]

(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.

Prove by contradiction:

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

[Albert Chan]

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

[Komanguy]

Cyrille de Brebisson, could you explain your algorithm?

[Albert Chan]

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[1] + slot[2] + slot[3]
        if filled == 5:
            if sum != slot[3] + slot[4] + slot[5]: return
        elif filled == 7:
            if sum != slot[5] + slot[6] + slot[7]: return
        elif filled == 8:       # same as filled == 9, but faster
            if sum == slot[7] + slot[8] + slot[9]: 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

[Komanguy]

Thanks a lot, Albert.

Cheers.

[pier4r]

Albert kudos for the effort and sharing!

[Albert Chan]

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[1]] #< A[M[2]],       % 2X solution by swap head pairs
  A[M[N-1]] #< A[M[N]],     % 2X solution by swap tail pairs
  A[M[3]] #< 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[3]]
  ),

  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)

[Dave Britten]

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[1] + Nums[2] + Nums[3]
            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.