Testing for rotations
14th March 2022
I was recently browsing through some programming interview questions, and found one that I thought was quite interesting:
Write a function that takes two lists, and checks whether one list is a rotated version of the other.
For example:
(rotation-p '(a b c d e f) '(e f a b c d))
should return t, whereas:
(rotation-p '(a b c d e f) '(f e a b c d))
should return nil.
You can assume that the two lists are the same length.
Have a go at the problem before reading my four attempts at solving it below.
Check each rotation
Perhaps the most obvious solution is to generate each of the n rotations of the test list, where n is the length of each list, and then compare each of them with the target list:
(defun rotation-p (x y)
(dotimes (n (length x) nil)
(when (equal x (append (subseq y n) (subseq y 0 n))) (return t))))
The good thing about this solution is that it's easy to understand, but it's quite inefficient, and does a lot of appending of lists. Is there a more efficient way?
Find how far each item has moved
A more efficient solution is to do the following: for each item in the test list, find how far its position has moved to its new position in the target list, taking the distance modulo the length of the lists to allow for wrapping round.
If and only if all the distances are the same, the test list is a rotation of the target list:
(defun rotation-p (x y)
(let ((len (length x))
(d (position (first x) y))
(i -1))
(every #'(lambda (e) (= d (mod (- (position e y) (incf i)) len))) x)))
Here d is the distance that each item has moved as a result of the rotation.
Note that this solution assumes that there are no repeated items in the lists. It is relative easy to extend it to allow for that: check the position of each matching item in the target list and make sure that at least one has moved distance d.
Check if it is a subsequence
A very simple solution, if you're allowed to use search, is to check whether the test list occurs in the target list appended to a copy of itself:
(defun rotation-p (x y) (search x (append y y)))
Recursive version
Finally, for many problems it's possible to write a very neat recursive solution, but in this case I struggled a bit to find one. Here's the best I could do. The logic is as follows:
- If the lists are length 1 they are trivially rotations of each other.
- Find the positions of the first two items from the test list in the target list. If they don't differ by 1, modulo the length of the lists, the test fails.
- Otherwise call rotation-p on the test list and the target list with the first item of the test list removed from each.
Here's the definition:
(defun rotation-p (x y)
(cond
((= (length x) 1) t)
((/= (mod
(- (position (second x) y) (position (first x) y))
(length x))
1)
nil)
(t (rotation-p (cdr x) (remove (first x) y)))))
If you can do better let me know!
blog comments powered by Disqus