Dinesman's multiple-dwelling problem: Difference between revisions
Content added Content deleted
(→{{header|D}}: fix overflow issue) |
(Updated D entry) |
||
Line 129: | Line 129: | ||
=={{header|D}}== |
=={{header|D}}== |
||
As for flexibility: the solve function is parameterized, accepting a length argument and a variable number of function predicates. |
As for flexibility: the solve function is parameterized, accepting a length argument and a variable number of function predicates. |
||
<lang d>import std.stdio, std.exception, std.range, std.algorithm, |
<lang d>import std.stdio, std.exception, std.range, std.algorithm, |
||
std.math, std.traits; |
|||
struct Permutations { |
|||
pure ulong fact(uint n) { |
|||
private immutable size_t num; |
|||
for (uint i = 2; i <= n; i++) |
|||
⚫ | |||
⚫ | |||
} |
|||
struct LazyPermutation { |
|||
private uint[] seq; |
private uint[] seq; |
||
private ulong tot; |
private ulong tot; |
||
private size_t num; |
|||
this (size_t |
this (in size_t n) /*pure*/ nothrow |
||
in { |
|||
enforce(num > 1, "LazyPermutation: num must be > 1"); |
|||
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) |
|||
⚫ | |||
⚫ | |||
⚫ | |||
this.seq = array(iota(n)); // not pure |
|||
⚫ | |||
⚫ | |||
} |
} |
||
@property uint[] front() { |
@property const(uint[]) front() const pure nothrow { |
||
return seq; |
return seq; |
||
} |
} |
||
@property bool empty() { |
@property bool empty() const pure nothrow { |
||
return tot == 0; |
return tot == 0; |
||
} |
} |
||
void popFront(){ |
void popFront() pure nothrow { |
||
tot--; |
|||
⚫ | |||
size_t j = num - 2; |
size_t j = num - 2; |
||
while (seq[j] > seq[j + 1]) |
while (seq[j] > seq[j + 1]) |
||
j--; |
j--; |
||
⚫ | |||
size_t k = num - 1; |
size_t k = num - 1; |
||
while (seq[j] > seq[k]) |
while (seq[j] > seq[k]) |
||
k--; |
k--; |
||
⚫ | |||
swap(seq[k], seq[j]); |
swap(seq[k], seq[j]); |
||
Line 181: | Line 183: | ||
} |
} |
||
const(uint[]) solve(T : size_t, F...)(in T len, in F predicates) |
|||
/*pure*/ nothrow { |
|||
outer: |
outer: |
||
foreach (p; |
foreach (p; Permutations(len)) { |
||
foreach (pred; predicates) |
foreach (pred; predicates) |
||
if (!pred(p)) |
if (!pred(p)) |
||
Line 193: | Line 196: | ||
void main() { |
void main() { |
||
⚫ | |||
enum Floors = 5; |
|||
⚫ | |||
alias bool function(in uint[]) pure nothrow MutablePredicate; |
|||
alias immutable(MutablePredicate) P; |
|||
auto p2 = (uint[] s){ return s[Cooper] != 0; }; |
|||
P p1 = s => s[N.Baker] != s.length-1; |
|||
P p2 = s => s[N.Cooper] != 0; |
|||
P p3 = s => s[N.Fletcher] != 0 && s[N.Fletcher] != s.length-1; |
|||
P p4 = s => s[N.Miller] > s[N.Cooper]; |
|||
P p5 = s => abs(cast(int)(s[N.Smith] - s[N.Fletcher])) != 1; |
|||
P p6 = s => abs(cast(int)(s[N.Cooper] - s[N.Fletcher])) != 1; |
|||
enum nFloors = EnumMembers!N.length; |
|||
if (auto sol = solve( |
if (auto sol = solve(nFloors, p1, p2, p3, p4, p5, p6)) |
||
writeln(sol); |
writeln(map!(p => [EnumMembers!N][p])(sol)); |
||
}</lang> |
}</lang> |
||
Output: |
|||
<pre>[ |
<pre>[Fletcher, Cooper, Miller, Smith, Baker]</pre> |
||
=={{header|Haskell}}== |
=={{header|Haskell}}== |