[2020-03-09] Challenge #383 [Easy] Necklace matching

20200309.asm

;; [2020-03-09] Challenge #383 [Easy] Necklace matching
;;
;; Imagine a necklace with lettered beads that can slide along the
;;  string. Here's an example image. In this example, you could take
;;  the N off NICOLE and slide it around to the other end to make
;;  ICOLEN. Do it again to get COLENI, and so on. For the purpose of
;;  today's challenge, we'll say that the strings "nicole", "icolen",
;;  and "coleni" describe the same necklace.
;;
;; Generally, two strings describe the same necklace if you can remove
;;   some number of letters from the beginning of one, attach them to
;;   the end in their original ordering, and get the other
;;   string. Reordering the letters in some other way does not, in
;;   general, produce a string that describes the same necklace.
;;
;; Write a function that returns whether two strings describe the same
;;   necklace.
;;
;; Examples
;;
;; same_necklace("nicole", "icolen") => true
;; same_necklace("nicole", "lenico") => true
;; same_necklace("nicole", "coneli") => false
;; same_necklace("aabaaaaabaab", "aabaabaabaaa") => true
;; same_necklace("abc", "cba") => false
;; same_necklace("xxyyy", "xxxyy") => false
;; same_necklace("xyxxz", "xxyxz") => false
;; same_necklace("x", "x") => true
;; same_necklace("x", "xx") => false
;; same_necklace("x", "") => false
;; same_necklace("", "") => true
;;

        org     &8000
        jp      start

txtout  equ     &bb5a

strtrue db      "true",0
strfals db      "false",0
crlf    db      13,10,0

pair_s1 equ     0
pair_s2 equ     64
pair_e  equ     pair_s2 + 64

pair1
org pair1 + pair_s1
        db  "nicole",0
org pair1 + pair_s2
        db  "icolen",0

pair2
org pair2 + pair_s1
        db  "nicole",0
org pair2 + pair_s2
        db  "lenico",0

pair3
org pair3 + pair_s1
        db  "nicole",0
org pair3 + pair_s2
        db  "coneli",0

pair4
org pair4 + pair_s1
        db  "aabaaaaabaab",0
org pair4 + pair_s2
        db  "aabaabaabaaa",0

pair5
org pair5 + pair_s1
        db  "abc",0
org pair5 + pair_s2
        db  "cba",0

pair6
org pair6 + pair_s1
        db  "xxyyy",0
org pair6 + pair_s2
        db  "xxxyy",0

pair7
org pair7 + pair_s1
        db  "xyxxz",0
org pair7 + pair_s2
        db  "xxyxz",0

pair8
org pair8 + pair_s1
        db  "x",0
org pair8 + pair_s2
        db  "x",0

pair9
org pair9 + pair_s1
        db  "x",0
org pair9 + pair_s2
        db  "xx",0

pair10
org pair10 + pair_s1
        db  "x",0
org pair10 + pair_s2
        db  "",0

pair11
org pair11 + pair_s1
        db  "",0
org pair11 + pair_s2
        db  "",0

pairtbl dw      pair1
        dw      pair2
        dw      pair3
        dw      pair4
        dw      pair5
        dw      pair6
        dw      pair7
        dw      pair8
        dw      pair9
        dw      pair10
        dw      pair11
        dw      0

; IN HL holds string to print
prints  ld      a, (hl)
        or      a
        ret     z
        call    txtout
        inc     hl
        jr      prints

; IN HL holds source string
; OUT A holds length
; Corrupts A, B, HL
strlen  xor     a          ; A = 0 comparator
        ld      b, a       ; B = counter
strlen2 cp      (hl)
        jr      nz, strlen1
        ld      a, b
        ret
strlen1 inc     b
        inc     hl
        jr      strlen2

; IN HL holds input string 1
;    DE holds input string 2 with offset
;    BC holds beginning of string 2
; OUT c is reset if strings are "same necklace"
strcmp  ld      a, (hl)         ; Get cur char of str1
        or      a               ; Is end of str1?
        jr      nz, strcmp1
        and     a               ; Clear carry
        ret                     ; And return
strcmp1 ex      de, hl
        cp      (hl)
        ex      de, hl
        jr      z, strcmp2      ; Are they equal?
        scf                     ; If not, then set carry
        ret                     ; And return
strcmp2 inc     hl              ; Advance pointer of str1
        inc     de              ; Advance pointer of str2
        ld      a, (de)         ; Read next/cur of str2
        or      a               ; Is it nul terminator?
        jr      nz, strcmp      ; Not yet, so repeat
        ld      e, c
        ld      d, b            ; Restore beginning of str2
        jr      strcmp          ; Repeat


; IN HL holds pair struct that is to solve
; Prints 0 if two strings are same necklace
; 1 otherwise
solve   ld      (solve9), hl    ; Backup pair struct
        call    strlen          ; Get length of str1
        ld      c, a            ; Save in C
        ld      hl, (solve9)
        ld      de, pair_s2
        add     hl, de
        call    strlen          ; Get lenght of str2
        cp      c               ; Is A == C?
        jr      z, solve0
        call    printf
        ret
solve0  ld      hl, (solve9)
        ld      de, pair_s2
        add     hl, de
        ex      de, hl
        ld      c, e
        ld      b, d
        ld      hl, (solve9)
        ld      (solve8), de    ; Backup str2
solve1  ld      hl, (solve9)    ; Reset str1
        ld      de, (solve8)    ; Restore cur str2
        call    strcmp
        jr      c, solve2       ; Are they equalish?
        call    printt
        ret
solve2  ld      hl, (solve8)    ; Increment str2 pointer
        inc     hl
        ld      (solve8), hl
        ld      a, (hl)         ; Get nxt str2 char
        or      a               ; Is it nul terminator?
        jr      nz, solve1      ; Repeat
        call    printf
        ret
solve8  dw      0               ; Backup for str1 pointer
solve9  dw      0               ; Backup pair struct

printt  ld      hl, strtrue
        call    prints
        ret

printf  ld      hl, strfals
        call    prints
        ret

start   ld      hl, pairtbl     ; Save current pair pointer
        ld      (cur2), hl
start1  ld      hl, (cur2)
        ld      a, (hl)
        inc     hl
        ld      h, (hl)
        ld      l, a            ; Dereference
        ld      (cur1), hl      ; Save for later
        xor     a
        cp      l
        jr      nz, start2
        cp      h
        jr      nz, start2
        ret
start2  ld      a, &22           ; " character
        call    txtout
        ld      hl, (cur1)
        call    prints
        ld      a, &22           ; " character
        call    txtout
        ld      a, ' '
        call    txtout
        ld      a, &22           ; " character
        call    txtout
        ld      hl, (cur1)
        ld      de, pair_s2
        add     hl, de
        call    prints
        ld      a, &22           ; " character
        call    txtout
        ld      a, ' '
        call    txtout
        ld      a, '='
        call    txtout
        ld      a, ' '
        call    txtout
        ld      hl, (cur1)
        call    solve
        ld      hl, crlf
        call    prints
        ld      hl, (cur2)
        inc     hl
        inc     hl
        ld      (cur2), hl
        jr      start1
        
cur1    dw      0               ; Current pair struct
cur2    dw      0               ; Current pair struct pointer