## Is Rotation?

Wednesday, October 13, 2010

I noticed an “interview question” that was posted on StackOverflow awhile ago. It’s not particularly complicated – basically asking “given two strings, how to tell if one is the rotated version of the other?”

Some discussion in the question deals with various faster methods, but the simplest answer is a Python version:

```
def isrotation(s1, s2):
return len(s1) == len(s2) and s1 in 2*s2
```

If we wanted to implement this in Factor,
we might want to consider using “short
circuit”
combinators (which will apply a series of boolean tests and stop on the
first test that fails). We will also use the convention that a `word?`

(ending in a “?”) returns a boolean.

```
: rotation? ( s1 s2 -- ? )
{ [ [ length ] bi@ = ] [ dup append subseq? ] } 2&& ;
```

We can test it, to make sure it works:

```
IN: scratchpad "stack" "tacks" rotation? .
t
IN: scratchpad "foo" "bar" rotation? .
f
```

Since strings are sequences of characters and this solution uses
sequence
operations
(`length`

, `append`

, and `subseq?`

), it is already generalized to
operate on other types of sequences. For example, arrays:

```
IN: scratchpad { 1 2 3 } { 2 3 1 } rotation? .
t
```

So, the next time you get this question in an interview, maybe you can solve it in Factor!