Dinesman's multiple-dwelling problem: Difference between revisions
Content added Content deleted
(Shorter D entry) |
(Don't-Repeat-Yourself D entry) |
||
Line 128: | Line 128: | ||
=={{header|D}}== |
=={{header|D}}== |
||
This code uses second lazy permutations function of '''[[Permutations#Lazy_version]]'''. |
|||
⚫ | |||
⚫ | |||
⚫ | |||
struct LazyPermutations { |
|||
⚫ | |||
private immutable size_t num; |
|||
import perms: permutations; // from rosettacode |
|||
private uint[] seq; |
|||
private ulong tot; |
|||
this (in size_t n) /*pure*/ nothrow |
|||
in { |
|||
enforce(n > 1, "Permutations: n must be > 1"); |
|||
} body { |
|||
static ulong factorial(in uint n) pure nothrow { |
|||
ulong result = 1; |
|||
foreach (i; 2 .. n + 1) |
|||
result *= i; |
|||
return result; |
|||
} |
|||
this.seq = array(iota(n)); // not pure |
|||
this.tot = factorial(n); |
|||
this.num = n; |
|||
} |
|||
@property const(uint[]) front() const pure nothrow { |
|||
return seq; |
|||
} |
|||
@property bool empty() const pure nothrow { |
|||
return tot == 0; |
|||
} |
|||
void popFront() pure nothrow { |
|||
tot--; |
|||
if (tot > 0) { |
|||
size_t j = num - 2; |
|||
while (seq[j] > seq[j + 1]) |
|||
j--; |
|||
size_t k = num - 1; |
|||
while (seq[j] > seq[k]) |
|||
k--; |
|||
swap(seq[k], seq[j]); |
|||
size_t r = num - 1; |
|||
size_t s = j + 1; |
|||
while (r > s) { |
|||
swap(seq[s], seq[r]); |
|||
r--; |
|||
s++; |
|||
} |
|||
} |
|||
} |
|||
} |
|||
void main() { |
void main() { |
||
⚫ | |||
//import std.traits: EnumMembers; |
|||
import std.traits; |
|||
⚫ | |||
alias /*immutable*/ bool function(in |
alias /*immutable*/ bool function(in N[]) pure nothrow P; |
||
P p1 = s => s[N.Baker] != s.length-1; |
P p1 = s => s[N.Baker] != s.length-1; |
||
P p2 = s => s[N.Cooper] != 0; |
P p2 = s => s[N.Cooper] != 0; |
||
Line 195: | Line 145: | ||
P p6 = s => abs(cast(int)(s[N.Cooper] - s[N.Fletcher])) != 1; |
P p6 = s => abs(cast(int)(s[N.Cooper] - s[N.Fletcher])) != 1; |
||
enum nNames = EnumMembers!N.length; |
|||
immutable predicates = [p1, p2, p3, p4, p5, p6]; |
immutable predicates = [p1, p2, p3, p4, p5, p6]; |
||
foreach (sol; |
foreach (sol; permutations([EnumMembers!N])) |
||
if (!canFind!(p => !p(sol))(predicates)) |
if (!canFind!(p => !p(sol))(predicates)) |
||
writeln |
writeln(sol); |
||
}</lang> |
}</lang> |
||
Output: |
Output: |