THE PUZZLET PAGE

PUZZLET 87 - THE SOLUTION
' Puzzlet #87
' 12 digits are arranged in a 4 x 3 matrix,
' forming four 3-digit integers by reading
' across, and three 4-digit integers by
' reading down. All of them are triangular
' numbers. Your task: Reproduce the matrix.
' There is only one solution.
' By Dave Ellis.

declare CountTriNrs(size: int)
declare LoadDigTriNrs(size: int)
declare Matched()
declare ExtractTri3(i: int)
declare NoZeroes(n: int)
declare NotExistsTri3(tri3: int)
declare PrintResults()

def nr3DigTriNrs: int
def nr4DigTriNrs: int
def it1, it2, it3, size: int
def tri41, tri42, tri43: int
def done: int
def temp3DigTriNrs[5]: int
openconsole
print "Checking ... "

'count 3-digit tri nrs
size = 3
nr3DigTriNrs = CountTriNrs(size)

'define array to hold 3-digit tri nrs
def dig3TriNrs[nr3DigTriNrs + 1]: int

'count 4-digit tri nrs
size = 4
nr4DigTriNrs = CountTriNrs(size)

'define array to hold 4-digit tri nrs
def dig4TriNrs[nr4DigTriNrs + 1]: int

'load all in-range tri nrs into arrays
for size = 3 to 4
    LoadDigTriNrs(size)
next size

'main program
it1 = 1
do
    'get 1st 4-digit triangular nr
    tri41 = dig4TriNrs[it1]
    if NoZeroes(tri41)
        it2 = 1
        do
            'get 2nd 4-digit triangular nr
            tri42 = dig4TriNrs[it2]
             it3 = 1
            do
                'get 3nd 4-digit triangular nr
                tri43 = dig4TriNrs[it3]
                locate 3,1
                print tri41, tri42, tri43
                'do they produce 4 3-dig tri nrs?
                if Matched()
                    done = -1
                endif
                it3 = it3 + 1
            until done | it3 > nr4DigTriNrs
            it2 = it2 + 1
        until done | it2 > nr4DigTriNrs
    endif
    it1 = it1 + 1
until done | it1 > nr4DigTriNrs

PrintResults()
print: print "No more!"
print: print "Press any key to exit ..."
do: until inkey$ <> ""
closeconsole
end   

sub CountTriNrs(size)
'counts the triangular nrs with size digits
'and returns the count to the calling routine.
def count, flag, i, start, finish, triNr: int
start = 10^(size-1)
finish = 10^size
i = 1
triNr = 1
count = 0
flag = 0
do
    i = i + 1
    triNr = triNr + i
    if triNr > finish
        flag = -1
    else
        if triNr >= start
            count = count + 1
        endif
    endif
until flag
return count

sub LoadDigTriNrs(size)
'loads all possible tri nrs with size digits
'into the appropriate array.
def count, flag, i, start, finish, triNr: int
start = 10^(size-1)
finish = 10^size
i = 1
triNr = 1
count = 0
flag = 0
do
    i = i + 1
    triNr = triNr + i
    if triNr > finish
        flag = -1
    else
        if triNr >= start
            count = count + 1
            if size = 3
                dig3TriNrs[count] = triNr
            else
                dig4TriNrs[count] = triNr
            endif
        endif
    endif
until flag
return

sub Matched
'generates the four 3-digit nrs from
'the three 4-digit nrs currently being
'investigated in the main routine. If
'all of these are triangular, returns
'TRUE else returns FALSE.
def flag, i, tempTri3: int
i = 1
flag = -1
do
    tempTri3 = ExtractTri3(i)
    temp3DigTriNrs[i] = tempTri3
    if NotExistsTri3(tempTri3)
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > 4
return flag

sub ExtractTri3(i)
'generates a 3-digit tri nr from the i'th
'digits of the three 4-digit tri nrs
'currently being investigated by the main
'routine and returns it to the calling
'routine.
def tri3Nr$: string
def tri41$, tri42$, tri43$: string
tri41$ = ltrim$(str$(tri41))
tri42$ = ltrim$(str$(tri42))
tri43$ = ltrim$(str$(tri43))
select i
    case 1
        tri3Nr$= mid$(tri41$, 1, 1)
        tri3Nr$ = tri3Nr$ + mid$(tri42$, 1, 1)
        tri3Nr$ = tri3Nr$ + mid$(tri43$, 1, 1)
    case 2
        tri3Nr$= mid$(tri41$, 2, 1)
        tri3Nr$ = tri3Nr$ + mid$(tri42$, 2, 1)
        tri3Nr$ = tri3Nr$ + mid$(tri43$, 2, 1)
    case 3
        tri3Nr$= mid$(tri41$, 3, 1)
        tri3Nr$ = tri3Nr$ + mid$(tri42$, 3, 1)
        tri3Nr$ = tri3Nr$ + mid$(tri43$, 3, 1)
    case 4
        tri3Nr$= mid$(tri41$, 4, 1)
        tri3Nr$ = tri3Nr$ + mid$(tri42$, 4, 1)
        tri3Nr$ = tri3Nr$ + mid$(tri43$, 4, 1)
endselect
return val(tri3Nr$)

sub NotExistsTri3(tri3)
'checks whether tri3 is in the list of
'3-digit triangular nrs stored in the
'array dig3TriNrs[].  If it's there,
'returns TRUE, otherwise FALSE.
def flag, i: int
i = 1
flag = -1
do
    if dig3TriNrs[i] = tri3
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > nr3DigTriNrs
return flag   

sub NoZeroes(n)
'checks n to see if it contains any
'zeroes.  If it finds one, returns
'FALSE, else returns TRUE.
def flag, L, i: int
def num$: string
num$ = ltrim$(str$(n))
L = len(num$)
flag = -1
i = 1
do
    if mid$(num$, i, 1) = "0"
        flag = 0
    endif
    i = i + 1
until flag = 0 | i > n
return flag

sub PrintResults
' pretty printer
def i: int
print: print "The Matrix:"
print: print space$(10),tri41
print space$(10), tri42
print space$(10), tri43
print: print "4-digit Triangular Nrs:"
print: print tri41, tri42, tri43
print: print "3-digit Triangular Nrs:"
print
for i = 1 to 4
    print temp3DigTriNrs[i],
next i
print
return



PROGRAM NOTES

Before the program begines, it needs to know just how many 3- and 4-digit triangular numbers exist, and, instead of relying on the programmer to supply this information, finds the facts out for itself. Two variables, nr3DigNrs and nr4DigNrs, are created to hold this information once it has been established. The function CountTriNrs() is created to get this information.

CountTriNrs() is designed to work for any size of triangular number. The required size is passed to it as a parameter called, appropriately, size. As soon as CountTriNrs() returns just how many triangular numbers of size exist, an array of the correct size is set up to hold them, dig3TriNrs[].

Armed with this information, you can see exactly how the following lines do their job:
'count 3-digit tri nrs
size = 3
nr3DigTriNrs = CountTriNrs(size)

'define array to hold 3-digit tri nrs
def dig3TriNrs[nr3DigTriNrs + 1]: int

'count 4-digit tri nrs
size = 4
nr4DigTriNrs = CountTriNrs(size)
def dig4TriNrs[nr4DigTriNrs + 1]: int

'define array to hold 4-digit tri nrs
def dig4TriNrs[nr4DigTriNrs + 1]: int
Now these arrays can be populated, using subroutine LoadDigTriNrs(). The parameter is size. The parameter allows the process to be automated, so that the correct type of triangular number is searched and loaded into the right array. This is the code that does it:
'load all in-range tri nrs into arrays
for size = 3 to 4
    LoadDigTriNrs(size)
next size
Now we're ready to use these data, and the main program begins.

Using it1 as overall iterator together with it2 and it3, the code pulls out three different 4-digit triangular numbers from the array dig4TriNrs[]. If the first of these contains a zero, it's rejected. This is because that would mean one of the downward 3-digit triangular numbers would have to begin with a zero, obviously not acceptable here.

Each set is stored in variables tri41, tri42, and tri43. If you study the code, you'll see its purpose is to test every permutation rather than just all combinations. This is because order of the triangular numbers here is just as important as which values are being investigated.

You'll notice that, once each set of three 4-digit triangular numbers has been assembled, it's printed out even though, obviously, most sets will not constitute a valid solution. This is simply to show the user that something is happening - he or she needs the reassurance, as the code runs quite slowly!

For each set, we can check to see if they produce a set of four 3-digit triangular numbers using function Matched().  If they do, variable done is set to signify the search is over, and the looping stops. If not, the process continues with a new set of values of 4-digit triangular numbers.

On completion, the program prints the results out to the screen using subroutine PrintResults(). It uses tri41, tri42, and tri43 to print the matrix, then separately prints out the details of every triangular number. The 3-digit triangular numbers are obtained from array temp3DigTriNrs[i], where they were stored by function Matched() while it was making its tests.

There are some interesting subroutines and functions in the program, but they're all self-explaratory. If you'd like a more detailed explanation of anything, please e-mail me.


When you run the program, you'll see the inset printed out onto your screen.

As required, the matrix contains four 3-digit triangular numbers across and three 4-digit triangular numbers down.

The code finds the result eventually, but it runs only very slowly. Maybe you can produce an algorithm that speeds things up. If so, please share it with me!
  

Checking ...

3321 5050 1035

The Matrix:

          3321
          5050
          1035

4-digit Triangular Nrs:

3321 5050 1035

3-digit Triangular Nrs:

351 300 253 105

No more!

Press any key to exit ...

Site design/maintenance: Dave Ellis E-mail me!
Last Updated: May 2nd, 2004.