Best shuffle: Difference between revisions

Line 342:

=={{header|D}}==

<lang d>import std.stdio, std.random, std.algorithm, std.array;

<lang d>import std.stdio, std.random, std.algorithm, std.array, std.range;

int bestShuffle(in dchar[] s1) {

⚫

~~int~~ ~~countSamePositions~~(in dchar[] r1, dchar[] r2, ~~size_t~~ ~~len~~) {

bool hasSamePositions(in dchar[] r1, in dchar[] r2, uint ignore) {

~~int~~ ~~count~~;

foreach (r; zip(r1, r2)) {

~~for~~ (~~size_t~~ i; i < ~~len;~~ ~~i++~~)

if (r[0] == r[1] && ignore-- == 0) return true;

⚫

}

if (r2[i] != '-' && r1[i] == r2[i]) {

~~count++~~;

return false;

⚫

}

⚫

return ~~count~~;

}

const size_t len = s1.length;

auto s2 = s1.dup;

uint numToIgnore;

if (len < 3) {

if (len > 0) {

⚫

auto numProbChars = sort!("a[1] > b[1]")(array(group(s2.sort)))[0][1];

⚫

~~s2.reverse;~~

⚫

if (numProbChars > len / 2) {

⚫

} ~~else~~ {

numToIgnore = numProbChars - (len - numProbChars);

⚫

auto ~~problemChar~~ = sort!("a[1] > b[1]")(array(group(s2.sort)))[0];

⚫

if (~~problemChar[1]~~ > len / 2) {

int j, numToRemove = problemChar[1] - (len - problemChar[1]);

foreach (ref c; s2)

if (c == problemChar[0]) {

c = '-';

if (++j >= numToRemove) break;

}

do {

for (size_t i = len; i > 1; i--)

for (size_t i = len; i > 1; i--) {

swap(s2[i - 1], s2[uniform(0, i)]);

⚫

}

⚫

} while (hasSamePositions(s1, s2, numToIgnore));

⚫

}

⚫

writefln ("%s %s (%s)", s1, s2, numToIgnore);

⚫

return numToIgnore;

⚫

} while (~~countSamePositions~~(s1, s2, ~~len~~) ~~> 0~~);

}</lang>

foreach (ref c; s2)

if (c == '-') c = problemChar[0];

}

int samePos = countSamePositions(s1, s2, len);

⚫

writefln("%s %s (%s)", s1, s2, ~~samePos~~);

return samePos;

}

unittest {

<lang d>unittest {

assert(bestShuffle("immediately"d.dup) == 0);

assert(bestShuffle("seesaw"d.dup) == 0);

assert(bestShuffle("abracadabra"d.dup) == 0);

assert(bestShuffle("~~elk~~"d.dup) == 0);

assert(bestShuffle("pop"d.dup) == 1);

assert(bestShuffle("a"d.dup) == 1);

assert(bestShuffle(""d.dup) == 0);

assert(bestShuffle("grrrrrr"d.dup) == 5);

}</lang>