Best shuffle: Difference between revisions
Content deleted Content added
m moved Bestshuffle to Best shuffle |
|||
Line 39:
do {
swap(
}
} while(countSamePositions(s, ch, len) > 0);
|
Revision as of 14:23, 11 December 2010
Best shuffle
You are encouraged to solve this task according to the task description, using any language you may know.
You are encouraged to solve this task according to the task description, using any language you may know.
Shuffle the characters of a string in such a way that as many of the characters are in a different position as possible. Print the result as follows: original string, shuffled string, (num characters ignored)
For example: tree, eetr, (0)
The words to test with are: abracadabra, seesaw, elk, grrrrrr, up, a
D
D v.2 <lang d>int bestShuffle(string s) {
int countSamePositions(T, U)(T s1, U s2, uint len) { int count; for (int i; i < len; i++) { if (s2[i] != '-' && s2[i] == s1[i]) { count++; } } return count; }
const len = s.length; if (len == 0) { throw new Exception("input string cannot have zero length"); }
char[] ch = s.dup.sort;
auto problemChar = sort!("a[1] > b[1]")(array(group(ch)))[0]; if ((problemChar[1] - len / 2) > 0) { int numToRemove = problemChar[1] - (len - problemChar[1]); for (int i, j; i < len && j < numToRemove; i++) { if (ch[i] == problemChar[0]) { ch[i] = '-'; j++; } } }
do { for (int i = len; i > 1; i--) { swap(ch[i-1], ch[uniform(0, i)]); } } while(countSamePositions(s, ch, len) > 0);
string result = replace(to!string(ch), "-", to!string(problemChar[0])); int samePos = countSamePositions(s, result, len);
writefln("%s %s (%s)", s, result, samePos);
return samePos;
}</lang>
output:
abracadabra baadacbraar (0) seesaw easwes (0) elk lke (0) grrrrrr rrrrrgr (5) up pu (0) a a (1)
<lang d>unittest {
assert(bestShuffle("abracadabra") == 0); assert(bestShuffle("seesaw") == 0); assert(bestShuffle("elk") == 0); assert(bestShuffle("grrrrrr") == 5); assert(bestShuffle("up") == 0); assert(bestShuffle("a") == 1);
}</lang>