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
next sibling 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 next 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 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
prev sibling parent 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
prev sibling 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