02/02/2020 is a palindrome day because reading the date left-to-right or right-to-left still refers to the same calendar date. And because it doesn't matter whether you use the DD/MM/YYYY format or the MM.DD.YYYY format, it's called a Universal Palindrome Day.
No one year can have more than 1 palindrome day. This is important because we need only consider the year to obtain a chronological list through sorting.
In the 10000 year period, that we can express using 4 decimal digits, there are precisely 366 palindrome days.
366 is (31 + 29 + 31 + 30 + 31 + 30 + 31 + 31 + 30 + 31 + 30 + 31)
Every combination of day and month numbers produces a valid date. No special care has to be taken of the 29th of February since both 2092 (29/02/2092) and 9220 (02.29.9220) will indeed be leap years. Let's hope we're still around...
Combining day and month is done using nested loops. The outer loop necessarily iterates over the month because we can only know the iteration count for the inner loop once we have chosen a month and consulted a lookup table (LUT) to find out how many days that particular month has.
Just combining alone will not produce the sought for chronological order. Ordinarily we would sort the outputs from the combining operation, but I've discovered that sorting the inputs to the combining part can be much faster. Even faster than producing an unsorted list! Moreover, where sorting the outputs heavily depends on the quality of the chosen sort method, sorting the inputs does not (much). My code never has to sort more than 31 values.
I could easily have opted to not sort at all, if only I would have used more lookup tables. The trouble with lookup tables is to know when enough is
enough. The extreme being one big lookup table with the final results at the ready. Where's the fun in that?
That's not to say that I've not explored it: replacing the 70 code bytes in PALINDR1.ASM_Part1 with the 214 bytes of 4 embedded lookup tables will bring the execution time down from 5.4 µsec to 3.0 µsec.
5.4 µsec PALINDR1.ASM Sorted inputs
6.9 µsec PALINDR2.ASM Unsorted
111.8 µsec PALINDR3.ASM Sorted outputs
Of course these timings don't include the int 21h DOS.PrintString call.
; PALINDR1.ASM (c) 2020 Sep Roland
; --------------------------------
; assemble with FASM
ORG 256
; This program lists all palindrome days according to DD/MM/YYYY
; It sorts the inputs to obtain a chronological list
; Part 1 fills 4 ordered tables with the reversed textual representations
; of months and days
push 31 30 29 12 ; (1)
mov bp, 1010'1101'0101b ; LUT DaysPerMonth (1 is 31, 0 is less)
mov di, T12
mov bx, 1
NextT: pop dx ; (1) -> DX={12,29,30,31}
push di ; (2) DI points behind a sentinel zero
lea cx, [bx-1]
rep movsw ; Copy the mother table
mov cl, 10 ; CONST
.Next: mov ax, bx
div cl
add ax, 3030h
shr bp, 1 ; Hiding the DaysPerMonth info
rcl ax, 1 ; ... in bit 0
add di, 2
push di ; (3)
.Sort: mov [di], si ; Garbage the 1st time
sub di, 2
mov si, [di-2] ; This could read the sentinel
cmp si, ax
jg .Sort
mov [di], ax
pop di ; (3)
inc bx
cmp bx, dx
jbe .Next
xor ax, ax ; Zero terminator on each table is at
stosw ; the same time sentinel of next table
pop si ; (2) New table is mother of next table
cmp dx, 31
jb NextT
; Part 2 makes all the valid month and day combinations (366 in all)
mov si, T12
lodsw
shr ax, 1 ; -> CF (*) Extract DaysPerMonth info
; The outer loop updates the month and century fields
Outer: push si ; (4)
mov si, T12+(12+1+29+1+30+1)*2 ; Point at T31
jc .a ; (*) OK, 31 days
sub si, (30+1)*2 ; Point at T30
cmp ax, "02" ; Is it February ?
jne .a ; No, 30 days
sub si, (29+1)*2 ; Point at T29, 29 days
.a: mov [String+3], ax ; 2-digit month
mov [String+6], ah ; 2-digit century
mov [String+7], al
lodsw
shr ax, 1
; The inner loop updates the day and year fields
Inner: mov [String+0], ax ; 2-digit day
mov [String+8], ah ; 2-digit year
mov [String+9], al
mov dx, String
mov ah, 09h ; DOS.PrintString
int 21h
lodsw
shr ax, 1 ; No info to extract, but
jnz Inner ; ... used as iterator test
pop si ; (4)
lodsw
shr ax, 1 ; -> CF (*) Extract DaysPerMonth info
jnz Outer
mov ax, 4C00h ; DOS.Terminate
int 21h
; --------------------------------------
String: db '../../....', 13, 10, '$'
ALIGN 2
dw 0 ; Sentinel
T12: rw 12+1+29+1+30+1+31+1
For comparison here are the unsorted and post-sorted DD/MM/YYYY versions:
; PALINDR2.ASM (c) 2020 Sep Roland
; --------------------------------
; assemble with FASM
ORG 256
; This program lists all palindrome days according to DD/MM/YYYY
; It does not produce a chronological list
; The code makes all the valid month and day combinations (366 in all)
xor si, si ; Month
; The outer loop updates the month and century fields
Outer: mov cl, [MDays+si] ; LUT DaysPerMonth
inc si
mov ax, si
aam
add ax, "00"
mov [String+6], ax ; 2-digit century
mov [String+3], ah ; 2-digit month
mov [String+4], al
xor di, di ; Day
; The inner loop updates the day and year fields
Inner: inc di
mov ax, di
aam
add ax, "00"
mov [String+8], ax ; 2-digit year
mov [String+0], ah ; 2-digit day
mov [String+1], al
mov dx, String
mov ah, 09h ; DOS.PrintString
int 21h
dec cl ; Next day
jnz Inner
cmp si, 12 ; Next month
jb Outer
mov ax, 4C00h ; DOS.Terminate
int 21h
; --------------------------------------
String: db '../../....', 13, 10, '$'
MDays: db 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
; PALINDR3.ASM (c) 2020 Sep Roland
; --------------------------------
; assemble with FASM
ORG 256
; This program lists all palindrome days according to DD/MM/YYYY
; It sorts the outputs to produce a chronological list
; Part 1 creates an ordered list of palindrome years
xor dx, dx ; Table size
xor si, si ; Month
; The outer loop inserts the reversed textual representation of the month
; as the most significant part of the 4-byte string in EBX
; e.g. for February - EBX=5048____h (EBX="__02")
Outer: mov cl, [MDays+si] ; LUT DaysPerMonth
inc si
mov ax, si
aam
add ax, "00"
xchg al, ah
mov bx, ax
shl ebx, 16
xor di, di ; Day
; The inner loop inserts the reversed textual representation of the day
; as the least significant part of the 4-byte string in EBX
; e.g. for 1 February - EBX=50484948h (EBX="0102")
Inner: inc di
mov ax, di
aam
add ax, "00"
xchg al, ah
mov bx, ax
; MergeSorting EBX into the growing table
; e.g. EBX=50484948h (EBX="0102") corresponds to the year 2010
mov bp, dx
Look: mov eax, [Table+bp-4] ; This could read the sentinel
cmp eax, ebx
jb Found
mov [Table+bp], eax
sub bp, 4
jnz Look
Found: mov [Table+bp], ebx ; Add new element
add dx, 4 ; The array grows
dec cl ; Next day
jnz Inner
cmp si, 12 ; Next month
jb Outer
; Part 2 displays the whole list of completed palindrome days
mov si, Table
mov di, String
mov dx, di
Show: lodsd
mov [di], ax ; 2-digit day
bswap eax
mov [di+3], ah ; \ 2-digit month
mov [di+4], al ; /
mov [di+6], eax ; 4-digit year
mov ah, 09h ; DOS.PrintString
int 21h
cmp si, Table+366*4
jb Show
mov ax, 4C00h ; DOS.Terminate
int 21h
; --------------------------------------
String: db '../../....', 13, 10, '$'
MDays: db 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31
ALIGN 4
dd 0 ; Sentinel
Table: rd 366
Final note on the MM.DD.YYYY format (not shown)
Quoting one paragraph:
Combining day and month is done using nested loops. The outer loop necessarily iterates over the month because we can only know the iteration count for the inner loop once we have chosen a month and consulted a lookup table (LUT) to find out how many days that particular month has.
This constraint is of no importance for the unsorted and post-sorted MM.DD.YYYY versions, but for the pre-sorted MM.DD.YYYY version I don't see any way around it. Any ideas?
