Previous page Next page Navigation bar

Puzzles

Prior to 2001 Puzzles

8 August 1999 (Absolute Triangle)

The problem statement from the Ole Miss Problems of the Week page is:

Absolute difference triangle; see text for description The numbers 1 through 6 are arranged in an absolute difference triangle as shown to the left. Notice that the absolute value of the difference between two adjacent numbers appears directly below them. Arrange the numbers 1 through 10 in an absolute value triangle using 10 positions.

Well, let us see what we have here. We have a set of numbers arranged in a triangle, and we have a specified relationship among various of the numbers. With 10 numbers, the triangle will have four rows. The topmost row will have four numbers in it; the second row, three numbers; the third, two; and the fourth, one. For convenience, we assign labels to these positions as in the diagram below.

Triangle with row 1 positions labeled P1 through P4, row 2 labeled P5 through P7, row 3 labeled P8 and P9, and row 4 labeled P10

Note that the diagram assigns each position a label that consists of “P” followed by a number from 1 to 10. This helps us to distinguish discussion about a position from discussion about the number we place in a position.

The first thing to do is to be able to determine when we are done. We have a solution to the puzzle when all of the following statements are true:

Mulling this over, we realize we need a permutation. A permutation of the numbers 1 through 10 will assign the numbers simultaneously to ten distinct positions, which we can associate with the positions P1 through P10.

Fortunately, we have a permutation engine in the Permutations program in the mathematics section of this site. The PERMUTE program takes a number of items to permute — 10, in this case — and a length of a permutation to generate, calls a routine we supply to determine if a permutation prefix is to be pursued, and calls a permutation handler to do whatever we need with the permutation.

We could simply generate all permutations of length 10 of 10 items, and check them to see if we have a solution. This would check all possible arrangements of the numbers 1 through 10 in the positions P1 through P10; if a solution exists, this would find it. However, this would require checking 10! = 3,648,800 possibilities. This is a little more than we would like to ask a programmable calculator to do.

Looking at the PERMUTE program a little deeper, we see it makes a call out to a user supplied routine to determine if a family of permutations should be generated. We could use this routine, for example, to determine if the number in position P5 was in fact the absolute value of the differences of the numbers in positions P1 and P2. If this were not true, there would be no point in assigning numbers to the remaining positions in the permutation. We could perform the appropriate check as values are assigned to each of P6, P7, and on through P10. When we accepted a number into P10 — which would be the first time the “handle a full permutation” routine would be called — we would have a solution.

A little more thought, however, convinces us this is still asking the calculator to do too much work. Assigning 1 to P1 and 2 to P2, for example, would never work: the absolute value of their differences is 1, which will never be generated in position P5, as 1 has already been used in the permutation. In fact, once we have numbers assigned to P1 through P4, we can determine whether there is a solution starting with these values — all the other values are determined. If the values in the difference triangle are all distinct, then the values in position P1 through P4 determine a solution, and otherwise not.

So we can instead ask PERMUTE to generate all permutations of length 4 from 10 elements, and use the acceptance routine to determine whether the difference triangle has distinct values. We can in fact start this checking as soon as values are assigned to both P1 and P2: we then have a derived value, the absolute value of the difference of the values assigned to P1 and P2, which must be distinct from both the value assigned to P1 and the value assigned to P2.

The solution to this puzzle, therefore, falls into two pieces: firstly, use the PERMUTE program to generate permutations of length 4 from 10 elements, and secondly, reject permutations and partial permutations that lead to non-distinct difference entries.

Rejecting non-distinct difference entries is troublesome. We could compute the entire difference triangle, then check all pairs for duplicates. From this, we could tell not only that there is a duplication, but we can tell what the duplication is. However, we really do not need to know what the duplication is, only that one exists. So we come up with the idea of using a bit vector to represent the set of values that a permutation, and its difference values, has already used: if a difference value duplicates a value already in the set, the permutation or partial permutation can be rejected.

Now we are ready to write our program. The program falls into three pieces: a main program to call PERMUTE and receive control when it is done; a routine that must be named PERMPREF to determine whether a permutation prefix or permutation is to be pursued; and a routine that must be named PERMITEM to handle a permutation. Both PERMPREF and PERMITEM must return 0 in variable B to halt processing, and a non-zero value to allow processing to continue. In the case of PERMPREF, the “processing” is further processing of permutations with the generated prefix; in the case of PERMITEM, the “processing” is the further generation of permutations. The PERMITEM program will do the uniqueness testing; the PERMITEM routine will simply save the permutation found so the main program can report it, and cause processing to stop. Control will then return to the main program, which can find the permutation where PERMITEM stashed it, and report the solution.

As always, these programs are available in a text file with .CAT file contents.

First, the simple program: PERMITEM. PERMUTE will pass it the permutation length (4) in variable A, and the permutation itself (four distinct numbers between 1 and 10) in List 1. All PERMITEM does is copy List 1 to List 4. To halt processing (as a solution has been found), PERMITEM sets variable B to zero.

; Program PERMITEM
;
; Description:
;   Saves a 4-element permutation generated by PERMUTE into List 4 so
;   the main program can report it.
;
; Variables:
;   B - The continue flag (output). Set to 0 to indicate processing
;       should stop
;   List 4 - The saved permutation.
;
; Symbols:
;   -> is the assignment arrow
 
Prog "VRSAVFJ"     ; Save variables (not strictly necessary, but...)
List 1->List 4     ; Put the permutation into List 4
0->B               ; Set continue flag to false
Prog "VRRESFJ"     ; Restore variables

Now, the other simple program: P080899, the main program. This program needs only set up the variable save stack, put 10 into the variable A and 4 into the variable B, call PERMUTE, and report on the solution found.

; Program P080899
;
; Description:
;   Finds and reports a 4-element permutation of 10 elements acceptable
;   to PERMITEM.  The four elements are reported in a single line as
;   four adjacent two-digit numbers; the three absolute differences
;   are similarly reported as three two-digit numbers; the two absolute
;   differences of those are reported as two two-digit numbers; and the
;   absolute difference of those is also reported.
;
; Variables:
;   A - The number of items to be permuted (input to PERMUTE). Also
;       the row counter of the triangle reported.
;   B - The length of the permutation (input to PERMUTE). Also the
;       display value of the row reported.
;   C - The "column" of the value.
;   List 3 - A work area for generating the differences.
;   List 4 - The saved permutation from PERMITEM.
;
; Symbols:
;   -> is the assignment arrow
;   (-) is the unary negation operator
;   _ is the display triangle
 
Prog "VRPRE"       ; Set up variable save stack
Seq(0,A,1,4,1)->List 3
                   ; Perpare List 3 for PERMITEM's use
10->A              ; Set up number of symbols as 10
4->B               ; Set up permutation length as 4
Prog "PERMUTE"     ; Generate permutations
List 4->List 3     ; Recover the solution
For 4->A To 1 Step (-)1
                   ; Loop through row lengths
0->B               ;   Zero row display accumulator
For 1->C To A      ;   Loop through row values
List 3[C]+100B->B  ;     Insert the value into the accumulator
Next               ;   [End of loop through row values]
B_                 ;   Display the row values
For 1->C To A-1    ;   Loop through all elements but last
Abs (List 3[C]-List 3[C+1])->List 3[C]
                   ;     Compute contents of next row
Next               ;   [End of loop through all elements but last]
Next               ; [End of loop through row lengths]
"DONE"             ; Say "Done"

Finally, the program that does the heavy lifting for this solution: PERMPREF. This program receives a permutation or partial permutation in List 1. It computes the bit vector corresponding to the values in the permutation and the absolute differences arising from those values. If there are no duplicates, it return 1 (continue generation) in variable B; if there are duplicates, it returns 0 (abandon this partial permutation) in variable B.

; Program PERMPREF
;
; Description:
;   Determines whether a 1- to 4-element permutation of 10 elements
;   is acceptable from the standpoint of the absolute differences
;   triangle.
;
; Variables:
;   A - The number of items in the permutation (input).
;   B - A flag indicating whether the partial permutation should be
;       continued (1) or abandoned (0). If the permutation is not
;       acceptable from the standpoint of the absolute differences
;       triangle, the permutation is abandoned.
;   F - The row index: 1 through A
;   G - The column index: 1 through A-F+1 (A, A-1, A-2, ...)
;   H - The "bit mask" of values already used.
;   I - The "bit mask" of the value being examined.
;   List 1 - The permutation or partial permutation (input).
;   List 3 - A work area for generating the differences.
;
; Symbols:
;   -> is the assignment arrow
;   ^ is the exponentiation operator
;   / is the division operator
;   <> is the not equal relational operator
 
Prog "VRSAVFJ"     ; Save variables F through J
List 1->List 3     ; Copy permutation to a work area
0->B               ; Assume the permutation is not acceptable
0->H               ; Zero value used bit mask
For 1->F To A      ; Loop through rows
For 1->G To A-F+1  ;   Loop through values in row
List 3[G]->I       ;     Get value
2^I->I             ;     Get bit corresponding to value
If Frac (Int (H/I)/2)<>0
                   ;     Determine if the value was already used
Then Prog "VRRESFJ";       If so, restore variables
Return             ;       Return (with permutation "unacceptable")
IfEnd              ;     [End of determine if the value was used]
H+I->H             ;     Set the bit corresponding to value
If G<>A-F+1        ;     If we are not at the end of the row
Then Abs (List 3[G]-List 3[G+1])->List 3[G]
                   ;       Compute the value for the next row
IfEnd              ;     [End of if we are not at the end of the row]
Next               ;   [End of loop through values in row]
Next               ; [End of loop through rows]
1->B               ; This one passed the tests
Prog "VRRESFJ"     ; Restore variables and return

So we type these programs into the calculator, along with the PERMUTE program from the Permutations page and the VRPRE, VRSAVFJ, and VRRESFJ programs from the Variable Save/Restore Routines page, and run the P080899 program. About half an hour later, the calculator reports:

6011008
50902
407
3

which we interpret as the following:

Difference triangle showing 6, 1, 10, 8 as the first row, 5, 9, 2 as the second row, 4, 7 as the third row, and 3 as the fourth row

A quick scan shows that all the items are indeed the absolute values of the differences of the two values above them, and all values from 1 to 10 are represented.

Now, it is true that by terminating the search after the first solution was found, we did not find the other three solutions — or seven if you count reflection. If we wanted all solutions, we could move the reporting into PERMITEM and have PERMITEM return 1, to permit further processing. If we do this, the remaining solutions are generated relatively quickly — by the time the first solution is found, we have already gone through over half the search space. This is clear as the first element of the solution is 6.

Finally, it is also true that a Java version of this algorithm, running on a 300 MHz Pentium Pro, finds all four (or eight) solutions in 30 milliseconds rather than 30 to 45 minutes, but we need not dwell on that part.

[ Previous page | Top of page | Next page ]

Previous page Top of page Next page Navigation bar

Copyright © 2001 Brian Hetrick
Page last updated 25 November 2001.

Brian’s Casio Calculator Corner

Home

Programs

Tutorial

Puzzles

Index

2001/2002

Previous years

Index

3 December 2000

27 October 2000

16 April 2000

9 April 2000

19 March 2000

13 February 2000

6 February 2000

28 November 1999

12 September 1999

8 August 1999

25 July 1999

11 July 1999

30 May 1999

4 April 1999

29 April 1996

In memoriam: Dijkstra

Site Information

Your Privacy

Site Map

E-mail

Site Technical Data