Category : Assembly Language Source Code
Archive   : TRI.ZIP
Filename : TRI.ASM

;------------------------------------------------------------------
TITLE DIFFERENCE TRIANGLE
; (c) W.C. Parke 1989
;------------------------------------------------------------------
;
; This is a PcConnect Programmer's Corner Puzzler solution.
;
; Puzzle Preamble:
;
; One often hears that 'Artificial Intelligence' code is best written
; in dedicated high level languages, such as LISP. The argument is
; based on the built-in tree-like decision making structures. There
; is no doubt that very sophisticated programs can be generated in
; LISP, such as REDUCE, which performs arduous algebraic (symbolic)
; manipulations in times much shorter than a human and without error.
; Even so, such programs are far slower than they could be on a given
; CPU, simply because there are several layers of general routines
; not optimized for the given process. For example, REDUCE is first
; written in a language called R-LISP. R-LISP is written in LISP.
; LISP is often written in C. C is written in Assembly.
;
; Clearly, there is no intrinsic reason for not writing symbolic
; manipulation programs in Assembly directly. The advantage of
; speed and smaller code may outweigh the cost of longer development
; time. This would be particularly true of routines that one might
; expect to use many times in another code.

; Puzzle: Is it possible to protect data in several files on
; a public hard disk in a way that will make the files hidden
; from all directory utilities (including those which show
; hidden files)? If so, what way(s) are there for doing so?
; What risks for data loss or data compromise exist for each
; way. Would the code for creating the files and reading
; them be strongly dependent on the type of hard disk?
;
; Solution:
;
; The following is a program to determine the triangle of
; integers of N rows arranged in 'pool-table form' with the
; property that any 'ball' below a pair has a number which is
; the difference of the pair above. N =1 to 9. It is known
; that no solution exists for N= 6, 7, or 8. N=9 requires
; several hundred years of continuous running to find
; solutions by the trial and error method below.
;
; Run time for N=5 is 40 seconds on an 8 MHz 8088. Run time is
; proportional to [N(N+1)/2]**N, i.e. faster than an
; exponentially rise:
;
; N time
; 4 1.6 secs
; 5 2 mins
; 6 3 hr 45 mins
;------------------------------------------------------------------
TRIG SEGMENT
ASSUME CS:TRIG,DS:TRIG,ES:TRIG,SS:TRIG
ORG 100H
;------------------------------------------------------------------
PUBLIC BEGIN,START,NXT,RECD,CHKTRI
;------------------------------------------------------------------
BEGIN: JMP START
;------------------------------------------------------------------
BMAT DB 1,45 DUP(0) ; space for the triangle numbers
INDX DB 9 DUP(0),0 ; top row numbers
NUM DW 0 ; input N
NUT DW 0 ; N(N+1)/2
ROW DB 15 ; screen rows left
DB 0
FLAG DB 0 ; flag 1 if solution found

DINVOK DB 'Difference Triangles, W.C. Parke, (c) 1989'
DB 13,10,10,'Syntax: TRI N where N=number of rows in triangle (1 to 9).'
DB 13,10,10,'Difference triangles are formed by the integers from 1 to N(N+1)/2'
DB 13,10,'in an inverted triangle array, with the difference of any'
DB 13,10,'adjacent pair giving the number below.',13,10,'$'
DNON DB 13,10,'Improper or no number N given.$'
DSRCH DB 13,10,'Searching for solutions to difference triangle with '
DNUM DB ' rows...',13,10,'$'
DCRLF DB 13,10,'$'
DNONE DB 13,10,'No solution found.$'
DSOME DB 13,10,'No more solutions found.$'
DMORE DB 13,'More...$'
DBLANK DB 13,' ',13,'$'
;------------------------------------------------------------------
START: MOV DX,OFFSET DINVOK
MOV AH,9
INT 21H ; invocation screen
MOV SI,WORD PTR 80H
LODSB
AND AL,AL
JNZ STAR1 ; got a command line tail
STAR0: MOV DX,OFFSET DNON
MOV AH,9
INT 21H ; no number given
INT 20H
STAR1: MOV CL,AL
XOR CH,CH ; cx=length of tail
STAR2: LODSB
CMP AL,20H
JZ STAR2 ; skip spaces
DEC CX
JCXZ STAR0
CALL CKNUM ; get number (single digit)
JC STAR0
MOV AL,BYTE PTR NUM
ADD AL,30H
MOV BYTE PTR DNUM,AL
MOV DX,OFFSET DSRCH
MOV AH,9
INT 21H ; begin searching
MOV DI,OFFSET BMAT ; triangle matrix storage
MOV SI,OFFSET INDX ; first row storage
MOV AX,NUT ; largest number n(n+1)/2
MOV CX,NUM ; number of numbers in top row n
MOV BP,CX ; save this number n
MOV DX,AX ; save n(n+1)/2
PUSH DI
MOV DI,SI
REP STOSB ; fill in initial top row
POP DI
CMP BP,1
JZ RECD ; nothing to do if 1
NXT: PUSH SI
PUSH DI
MOV CX,BP
REP MOVSB ; put in top row of numbers
POP DI
POP SI
CALL CHKTRI ; find full triangle and check for repeats
JZ RECD ; no repeats! got triangle!
MORE: MOV BX,BP ; get back N
MOV CX,BX
DEC BX

NXTL: DEC BYTE PTR [SI+BX] ; try next number down
JNZ NXT
MOV [SI+BX],DL ; replace by high value
DEC BX
LOOP NXTL ; borrow 1 from next number to left

NON: TEST BYTE PTR FLAG,1 ; any solutions?
JNZ SOME
MOV DX,OFFSET DNONE ; none
EXIT: MOV AH,9
INT 21H
INT 20H
SOME: MOV DX,OFFSET DSOME ; some
JMP SHORT EXIT
;------------------------------------------------------------------
RECD: ; show a solution triangle
PUSH BX
PUSH DX
PUSH SI
PUSH DI
MOV BX,BP ; n
CMP BX,WORD PTR ROW
JC RECDA
MOV ROW,1 ; insure we wait for keyboard
RECDA: CALL SCRLF
MOV SI,DI
RECDB: MOV CX,BX
RECDR: LODSB
CALL SHOW ; show a triangle row
LOOP RECDR
CALL SCRLF
CALL SPACE ; shift to right
DEC BX
JNZ RECDB
POP DI
POP SI
POP DX
POP BX
OR BYTE PTR FLAG,1 ; flag solution found
JMP MORE
;------------------------------------------------------------------
CKNC: STC
RET
CKNUM: ; check for input number
CMP AL,'1'
JC CKNC
CMP AL,'9'+1
CMC
JC CKNC
SUB AL,30H
MOV BYTE PTR NUM,AL ; got a number n
MOV AH,AL
INC AH
MUL AH
SHR AX,1
MOV BYTE PTR NUT,AL ; n(n+1)/2
LODSB
CMP AL,20H
JZ CKOK
CMP AL,0DH
JNZ CKNC ; only following space or CR allowed
CKOK: RET

;------------------------------------------------------------------
SPACE: ; add space between triangle numbers
MOV CX,NUM
INC CX
SUB CX,BX
SHL CX,1
MOV AH,2
MOV DL,20H
SPAC: INT 21H ; send spaces
LOOP SPAC
RET

;------------------------------------------------------------------
SCRLF: ; send CR,LF and drop row count
MOV DX,OFFSET DCRLF
MOV AH,9
INT 21H ; issue CR LF
DEC BYTE PTR ROW
JZ SWAIT
RET
SWAIT: MOV DX,OFFSET DMORE
MOV AH,9
INT 21H ; display More...
MOV BYTE PTR ROW,24
MOV AH,1
INT 21H ; wait for keyboard
MOV DX,OFFSET DBLANK
MOV AH,9
INT 21H
RET

;------------------------------------------------------------------
SHOW: ; show a triangle number
AAM ; convert to BCD
ADD AX,3030H
MOV DX,AX
CMP DH,30H
JNZ SHOW1 ; above 10
MOV DH,20H ; blank the leading 0
SHOW1: MOV AH,2
PUSH DX
MOV DL,DH
INT 21H ; show 10's digit
POP DX
INT 21H ; show 1's digit
MOV DL,20H
INT 21H
INT 21H ; add another two spaces
RET

;------------------------------------------------------------------
CHKTRI: ; check for solution triangle
MOV BX,BP ; n
DEC BX
PUSH DI
CHKB: MOV CX,BX ; number of pairs to check in this row
CHK0: MOV AX,[DI]
SUB AL,AH
JZ CHKNZ
CHK1: JNC CHK2
NEG AL ; make positive
CHK2: MOV [DI+BX+1],AL ; save under pair
INC DI
LOOP CHK0 ; continue across row
INC DI
DEC BX
JNZ CHKB ; do next row
POP DI
PUSH DI
MOV BX,DX ; n(n+1)/2
DEC BX
CHK3: MOV CX,BX
INC CX
MOV AL,[DI] ; get a triangle value
INC DI
PUSH DI
REPNZ SCASB ; see if this value is repeated in triangle
POP DI
AND CX,CX
JNZ CHKZ
DEC BX
JNZ CHK3 ; compare next value with those further down
CHKZ: POP DI
RET
CHKNZ: INC AH ; set NZ
POP DI
RET
;------------------------------------------------------------------
TRIG ENDS
END BEGIN
;------------------------------------------------------------------