An Elisp Challenge

Here's a simple Elisp challenge suggested by a problem from by ProgrammingPraxis. We call one string a cycle of another if one string can be transformed into the other by a rotation of the characters. Note that this means

  1. They have the same number of characters.
  2. They have the same characters.
  3. The characters are in the same order when considered as a cycle.

Thus, “abc” and “cab” are cycles of each other because if “abc” is rotated right by 1 (or left by 2) it equals “cab.” Notice that "abc" and “acb” are not cycles of each other even though they meet conditions 1 and 2.

The challenge is to write an Elisp function, cyclep, that tests whether two strings are cycles of each other.

This entry was posted in Programming and tagged , . Bookmark the permalink.
  • csar

    straightforward brute-force:
    (defun sort-string (str)
    (apply #'string (sort (loop for i across str collect i) #'<)))

    (defun cyclep (str1 str2)
    (and (= (length str1) (length str2))
    (string= (sort-string str1) (sort-string str2))
    (loop for i from 0 to (length str1)
    thereis (string= str1 (rotate-string-left str2 i)))))

  • Juan Pechiar

    Double one of the strings, and search for the other. Note that I use string-match, which searches for a regexp rather than a string, so this implementation is fragile.

    (defun cyclep( st1 st2 )
    (let ((st11 (concat st1 st1)))
    (and (eq (length st1) (length st2))
    (numberp (string-match st2 st11)))))

    • Use `regexp-quote` to quote the string you're searching for and we have a winner. Very clean solution.

      • Also, use `string-match-p`, that works the same but does not modify the global match tables (which, if you'd ever use this funciton in some code could seriously bite you)

  • (defun cyclep (target candidate)
    (let ((target-length (length target))
    (candidate-copy (rotate-string candidate))
    (result nil))
    (while (> target-length 0)
    (when (string= target candidate-copy)
    (setq result t))
    (setf candidate-copy (rotate-string candidate-copy))
    (decf target-length))

    (defun rotate-string (candidate)
    (let ((first-char (substring candidate 0 1))
    (rest (substring candidate 1)))
    (concat rest first-char)))

    This is my solution, although I could probably should do a look for the first matching character of one sequence on the other and then do n times (where n is the length) char= for each successive char with modulo arithmetic to take care of the bounds. And check for matching length previous to starting the computation.

  • Lars Brinkhoff

    (require 'cl)
    (defun cyclep (str1 str2) (search str1 (concat str2 str2)))

    • Gregor Kappler

      Nice solution but without checking string lengths this will not work:
      (cyclep "abc" "cabcab")
      (defun cyclep (str1 str2) (and (= (length str1) (length str2)) (search str1 (concat str2 str2))))