July 2018 little math problem
07-28-2018, 01:15 PM
Post: #21
 Albert Chan Senior Member Posts: 1,676 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: 835 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
\>>
\>>

\<<
@ 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,676 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
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,676 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,676 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,676 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,076 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,676 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]),

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: 1,960 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)