www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - SO rotate question

reply simendsjo <simen.endsjo pandavre.com> writes:
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"));
}
Sep 02 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Sep 02 2010
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
 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
Sep 02 2010
prev sibling next sibling parent reply simendsjo <simen.endsjo pandavre.com> writes:
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..
Sep 02 2010
parent bearophile <bearophileHUGS lycos.com> writes:
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
Sep 03 2010
prev sibling parent reply Pelle <pelle.mansson gmail.com> writes:
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?
Sep 02 2010
next sibling parent simendsjo <simen.endsjo pandavre.com> writes:
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!
Sep 03 2010
prev sibling parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Sep 03 2010
next sibling parent Pelle <pelle.mansson gmail.com> writes:
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.
Sep 03 2010
prev sibling parent reply Jonathan M Davis <jmdavisprog gmail.com> writes:
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
Sep 03 2010
parent reply bearophile <bearophileHUGS lycos.com> writes:
Jonathan M Davis:

 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.


I don't like what you say.

If you take a look at how in the last ten years every small feature was
designed by Python devs, you see how much care they have for naming things. For
each name of feature/built-in all people of the development mailing list
propose their names and the rationale behind those names. Then they write down
a list of all the ideas, and they vote for each name. The name with most votes
usually gets accepted, and then they start over with the next name to choose.
This is a bit time consuming, but one of the most important qualities of Python
its refined and natural design.

You are right that good names are purpose-specific, and often a name that is
good for me is not good for you.

Every single person has some quirks, so if you let a single person choose a
name, there's some risk the name will reflect only the specific quirks of that
person.

On the other hand the good names for a specific feature are not totally random.
If you take 100 smart persons, and you ask them what name to use to define a
certain feature, you will often receive something like 15-20 answers, and among
them one or two answers are the most common. The most common choice is the the
right name choice.

It's true that this most common name is not always the same name that each
person is willing to chose, but such average process smooths out the quirks
each single person has, and very often the names chosen by this process are
simple to remember and natural.

This is how I'd like Phobos names to be chosen. Andrei is smart and
intelligent, but as everyone else he has quirks (and his usage of English is
not the most common you may find), so letting the choice of many names to any
single person is bad.

-----------------

I have also added this one:
http://d.puremagic.com/issues/show_bug.cgi?id=4803

Bye,
bearophile
Sep 03 2010
parent Jonathan M Davis <jmdavisprog gmail.com> writes:
On Friday 03 September 2010 10:14:24 bearophile wrote:

 Jonathan M Davis:

 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.


 
 I don't like what you say.
 
 If you take a look at how in the last ten years every small feature was
 designed by Python devs, you see how much care they have for naming
 things. For each name of feature/built-in all people of the development
 mailing list propose their names and the rationale behind those names.
 Then they write down a list of all the ideas, and they vote for each name.
 The name with most votes usually gets accepted, and then they start over
 with the next name to choose. This is a bit time consuming, but one of the
 most important qualities of Python its refined and natural design.
 
 You are right that good names are purpose-specific, and often a name that
 is good for me is not good for you.
 
 Every single person has some quirks, so if you let a single person choose a
 name, there's some risk the name will reflect only the specific quirks of
 that person.
 
 On the other hand the good names for a specific feature are not totally
 random. If you take 100 smart persons, and you ask them what name to use
 to define a certain feature, you will often receive something like 15-20
 answers, and among them one or two answers are the most common. The most
 common choice is the the right name choice.
 
 It's true that this most common name is not always the same name that each
 person is willing to chose, but such average process smooths out the
 quirks each single person has, and very often the names chosen by this
 process are simple to remember and natural.
 
 This is how I'd like Phobos names to be chosen. Andrei is smart and
 intelligent, but as everyone else he has quirks (and his usage of English
 is not the most common you may find), so letting the choice of many names
 to any single person is bad.


I didn't say anything that contradicts what you just said. All I said was that 
picking a function name is an art, and there _are_ going to be function names
in 
an API that people aren't going to like simply because they think differently. 
Heck, you could really like one of your own names when you first create the 
function, and then later decide that it was a poor choice.

What you're proposing is a way to reduce the odds that the average programmer 
will think that a name is bad, because more people will have input. I have no 
problem with that, and I didn't suggest that the way that names in Phobos is 
picked is perfect. I didn't even say anything about whether having one person 
pick the names was good or bad. So, I really don't know why you're unhappy with 
what I said.

In any case, it looks like Andrei is looking to have more of a review process 
for stuff entering Phobos - akin to what Boost does. That review process would 
likely be the time to suggest better names for functions if they are poorly 
named.

- Jonathan M Davis
Sep 03 2010