http://stackoverflow.com/questions/2553522/interview-question-check-if-one-string-is-a-rotation-of-other-string

I created a solution, but I don't want D to look bad, so I won't post it. It's a bit for loop heavy...
At least it's shorter than the c example, but I don't know about speed or readability..

Suggestions for D-ifying the code is welcome.

import std.range;

bool isRotated(T)(T[] s, T[] d) {
	if( s.length != d.length )
		return false;

	auto cycled = cycle(s);
	for(int loopIdx, matchIdx; loopIdx < d.length || matchIdx > 0; ++loopIdx && cycled.popFront()) {
		if( cycled.front == d[matchIdx] )
			++matchIdx;
		else
			matchIdx = 0;

		if( matchIdx == d.length )
			return true;
	}

	return false;
}
unittest
{
	auto a = "rotato";
	assert(isRotated(a, "rotato"));
	assert(isRotated(a, "otator"));
	assert(isRotated(a, "tatoro"));
	assert(isRotated(a, "atorot"));
	assert(isRotated(a, "torota"));
	assert(isRotated(a, "orotat"));

	assert(!isRotated(a, "rotator"));
	assert(!isRotated(a, "rotat"));
	assert(!isRotated(a, "rotata"));
}

simendsjo:
> Suggestions for D-ifying the code is welcome.

Your unit tests are not good enough, they miss some important corner cases. This my first version in D2:

import std.string: indexOf;

/// return True if s1 is a rotated version of s2
bool isRotated(T)(T[] s1, T[] s2) {
    return (s1.length + s2.length == 0) ||
           (s1.length == s2.length && indexOf(s1 ~ s1, s2) != -1);
}

unittest { // of isRotated
    assert(isRotated("", ""));
    assert(!isRotated("", "x"));
    assert(!isRotated("x", ""));
    assert(isRotated("x", "x"));

    string s = "rotato";
    assert(isRotated(s, "rotato"));
    assert(isRotated(s, "otator"));
    assert(isRotated(s, "tatoro"));
    assert(isRotated(s, "atorot"));
    assert(isRotated(s, "torota"));
    assert(isRotated(s, "orotat"));

    assert(!isRotated(s, "rotator"));
    assert(!isRotated(s, "rotat"));
    assert(!isRotated(s, "rotata"));
}

void main() {}

Bye,
bearophile

> bool isRotated(T)(T[] s1, T[] s2) {

A better signature for the same function, I need to train myself to use pure and const more often :-)

pure bool isRotated(T)(const T[] s1, const T[] s2) {

Bye,
bearophile

On 02.09.2010 22:24, bearophile wrote:
> simendsjo:
>> Suggestions for D-ifying the code is welcome.
>
> Your unit tests are not good enough, they miss some important corner cases.
> This my first version in D2:
>
> import std.string: indexOf;
>
> /// return True if s1 is a rotated version of s2
> bool isRotated(T)(T[] s1, T[] s2) {
>      return (s1.length + s2.length == 0) ||
>             (s1.length == s2.length&&  indexOf(s1 ~ s1, s2) != -1);
> }
>
> unittest { // of isRotated
>      assert(isRotated("", ""));
>      assert(!isRotated("", "x"));
>      assert(!isRotated("x", ""));
>      assert(isRotated("x", "x"));
>

(...)
I agree that's much simpler, but s1 ~ s1 doesn't perform too well I think. Always creates a new heap allocation and copies the array..

On 09/02/2010 10:24 PM, bearophile wrote:
> simendsjo:
>> Suggestions for D-ifying the code is welcome.
>
> Your unit tests are not good enough, they miss some important corner cases.
> This my first version in D2:
>
> import std.string: indexOf;
>
> /// return True if s1 is a rotated version of s2
> bool isRotated(T)(T[] s1, T[] s2) {
>      return (s1.length + s2.length == 0) ||
>             (s1.length == s2.length&&  indexOf(s1 ~ s1, s2) != -1);
> }
>
> unittest { // of isRotated
>      assert(isRotated("", ""));
>      assert(!isRotated("", "x"));
>      assert(!isRotated("x", ""));
>      assert(isRotated("x", "x"));
>
>      string s = "rotato";
>      assert(isRotated(s, "rotato"));
>      assert(isRotated(s, "otator"));
>      assert(isRotated(s, "tatoro"));
>      assert(isRotated(s, "atorot"));
>      assert(isRotated(s, "torota"));
>      assert(isRotated(s, "orotat"));
>
>      assert(!isRotated(s, "rotator"));
>      assert(!isRotated(s, "rotat"));
>      assert(!isRotated(s, "rotata"));
> }
>
> void main() {}
>
> Bye,
> bearophile

This is what I wrote:

bool isRotated(T)(T[] a, T[] b) {
    return a.length == b.length && (a.length == 0 || canFind(chain(a,a), b));
}

Use chain to avoid allocation.

canFind isn't really the best possible name, is it?

Pelle wrote:
> On 09/02/2010 10:24 PM, bearophile wrote:
>> simendsjo:
>>> Suggestions for D-ifying the code is welcome.
>>
>> Your unit tests are not good enough, they miss some important corner cases.
>> This my first version in D2:
>>
>> import std.string: indexOf;
>>
>> /// return True if s1 is a rotated version of s2
>> bool isRotated(T)(T[] s1, T[] s2) {
>>      return (s1.length + s2.length == 0) ||
>>             (s1.length == s2.length&&  indexOf(s1 ~ s1, s2) != -1);
>> }
>>
>> unittest { // of isRotated
>>      assert(isRotated("", ""));
>>      assert(!isRotated("", "x"));
>>      assert(!isRotated("x", ""));
>>      assert(isRotated("x", "x"));
>>
>>      string s = "rotato";
>>      assert(isRotated(s, "rotato"));
>>      assert(isRotated(s, "otator"));
>>      assert(isRotated(s, "tatoro"));
>>      assert(isRotated(s, "atorot"));
>>      assert(isRotated(s, "torota"));
>>      assert(isRotated(s, "orotat"));
>>
>>      assert(!isRotated(s, "rotator"));
>>      assert(!isRotated(s, "rotat"));
>>      assert(!isRotated(s, "rotata"));
>> }
>>
>> void main() {}
>>
>> Bye,
>> bearophile
> 
> This is what I wrote:
> 
> bool isRotated(T)(T[] a, T[] b) {
>     return a.length == b.length && (a.length == 0 || canFind(chain(a,a), b));
> }
> 
> Use chain to avoid allocation.
> 
> canFind isn't really the best possible name, is it?

Sweet! Thats what I was looking for!

simendsjo:
> I agree that's much simpler, but s1 ~ s1 doesn't perform too well I think. Always creates a new heap allocation and copies the array..

The version written by Pelle is better. On the other hand performance is not an absolute thing, it's "good enough" or "not good enough", and in many situations you don't need a high-performance rotate test function.

Bye,
bearophile

Pelle:

> bool isRotated(T)(T[] a, T[] b) {
>      return a.length == b.length && (a.length == 0 ||
> canFind(chain(a,a), b));
> }

Nice clean solution. I suggest to add "pure" and two "const" in the signature.


> canFind isn't really the best possible name, is it?

Some name/APIs of Phobos are not the best possible, they were often invented by a single person. I don't know if contains() or isIn() are better.

Bye,
bearophile

On 09/03/2010 01:35 PM, bearophile wrote:
> Pelle:
>
>> bool isRotated(T)(T[] a, T[] b) {
>>       return a.length == b.length&&  (a.length == 0 ||
>> canFind(chain(a,a), b));
>> }
>
> Nice clean solution. I suggest to add "pure" and two "const" in the signature.
>
>
>> canFind isn't really the best possible name, is it?
>
> Some name/APIs of Phobos are not the best possible, they were often invented by a single person. I don't know if contains() or isIn() are better.
>
> Bye,
> bearophile

Heh, I actually tried that before posting, but chain doesn't seem to support const. :-)

Should probably be two forward ranges, not two arrays, as well.

On Friday 03 September 2010 04:35:30 bearophile wrote:
> > canFind isn't really the best possible name, is it?
> 
> Some name/APIs of Phobos are not the best possible, they were often
> invented by a single person. I don't know if contains() or isIn() are
> better.

It used to be that all you had was find(), and you had to check whether the result was empty if you were looking to see whether what you were trying to find was in the range or not. I pointed out that that was overly verbose and less efficient in cases where all you cared about was whether the item or items was in the range rather than getting the range starting at the point where the item was found. I probably suggested contains() for the new function name, but I'd have go look at the bug report. In either case, Andrei agreed that it was a good idea and added the function. However, he named it canFind() - presumably because that's what you're trying to do. You're seeing whether you could find it with find(). So, from that perspective, it's a perfect name. However, I don't think that's really how people think about it. They're looking for whether an element is in a range, not whether they can find it there. So, from that perspective, it's a poor name. Personally, I think that contains() would be better, but canFind() does make sense depending on how you look at it.

Now, canFind() might be going away. I opened a bug report asking for all() and any() (all() returning whether all of the elements of a range satisfied a predicate, and and any() returning whether any of them did) and pointed out that while there is no function in std.algorithm which does all(), the version of canFind() which takes a predicate and a haystack but no needle is effectively any(). Andrei thought that any() was better and decided that canFind() should be replaced with any(). After that, I pointed out that while any() is definitely better for the case where it's a just a predicate and a haystack, the other cases would still make more sense as canFind(), and he didn't say anything further on that bug report, so I don't know what he intends to do, and canFind() may or may not be going away.

Regardless, contains() is definitely a better name for the other versions of canFind(), so perhaps a bug report should be opened on the matter. Still, naming functions is a bit of an art and most function names are debatable as to how good they are, so you're bound to have functions in any API that aren't named the way that you think they should be.

- Jonathan M Davis