4
\$\begingroup\$

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?

\$\endgroup\$
  • \$\begingroup\$ All US-format palindrome dates are all ISO-8601-format palindrome dates, of course. \$\endgroup\$ – Toby Speight Feb 25 at 15:45
2
\$\begingroup\$

This program lists all palindrome days according to MM.DD.YYYY.

The code makes all the valid month and day combinations (366 in all).
It uses 4 pre-sorted lookup tables (embedded for speed) to obtain a chronological list.

In the MM.DD.YYYY format the most significant part of the year YYYY reflects in the day DD. This will be used for the outer loop.
The outer loop runs through the T31 list so as to process all the possible day numbers.

In the MM.DD.YYYY format the least significant part of the year YYYY reflects in the month MM. This will be used for the inner loop. However the number of iterations will vary depending on the day value being greater (a), equal (b) or smaller (c) than 30:

(a).The inner loop runs through the T7 list when the outer loop processes the day number 31. Stored as '31'.
(b).The inner loop runs through the T11 list when the outer loop processes the day number 30. Stored as '30'.
(c).The inner loop runs through the T12 list for every other day number that the outer loop processes.

The T31 list is an ordered list of the 2-characters ASCII representation of the numbers in the range [1,31].
The T12 list is an ordered list of the 2-characters ASCII representation of the numbers in the set {1,2,3,4,5,6,7,8,9,10,11,12}. Months that have 29+ days. (For the purpose of this program February has 29 days.)
The T11 list is an ordered list of the 2-characters ASCII representation of the numbers in the set {1,3,4,5,6,7,8,9,10,11,12}. Months that have 30+ days.
The T7 list is an ordered list of the 2-characters ASCII representation of the numbers in the set {1,3,5,7,8,10,12}. Months that have 31 days.

        2-chars    List    List
Number   ASCII     Entry   Order
---------------------------------
   1  ->  '01' ->  3130h    4th
   2  ->  '02' ->  3230h    8th
   3  ->  '03' ->  3330h   11th

  10  ->  '10' ->  3031h    1st
  11  ->  '11' ->  3131h    5th
  12  ->  '12' ->  3231h    9th

  20  ->  '20' ->  3032h    2nd
  21  ->  '21' ->  3132h    6th
  22  ->  '22' ->  3232h   10th

  30  ->  '30' ->  3033h    3rd
  31  ->  '31' ->  3133h    7th

The chronological ordering of the final result, which demands digits reversal, comes naturally from sorting these text-based tables.

  mov   si, T31
  lodsw
Outer:
  push  si
  mov   si, T7
  cmp   ax, "31"
  je    @f
  mov   si, T11
  cmp   ax, "30"
  je    @f
  mov   si, T12
@@:
  mov   [String+3], ax  ;Day
  mov   [String+6], ah  ;Century
  mov   [String+7], al
  lodsw
Inner:
  mov   [String], ax    ;Month
  mov   [String+8], ah  ;Year
  mov   [String+9], al
  mov   dx, String
  mov   ah, 09h         ;Print string
  int   21h
  lodsw
  test  ax, ax
  jnz   Inner
  pop   si
  lodsw
  test  ax, ax
  jnz   Outer

  mov   ax, 4C00h       ;Exit to DOS
  int   21h

  ALIGN 2
T7:
  db '10011203050708'
  dw 0
T11:
  db '1001111203040506070809'
  dw 0
T12:
  db '100111021203040506070809'
  dw 0
T31:
  db '10203001112131021222031323041424051525061626071727081828091929'
  dw 0
String:
  db '..........',13,10,'$'
| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.