Dinesman's multiple-dwelling problem: Difference between revisions
Content deleted Content added
→{{header|D}}: generate permutations lazily |
|||
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.range, std.math; |
<lang d>import std.stdio, std.exception, std.range, std.algorithm, std.math; |
||
pure T fact(T)(T n) { |
|||
// From http://rosettacode.org/wiki/Permutations#D |
|||
T result = 1; |
|||
auto permutations(size_t n) { |
|||
for (T i = 2; i <= n; i++) |
|||
result *= i; |
|||
⚫ | |||
return result; |
|||
} |
|||
void perms(size_t[] s, size_t[] pre = []) { |
|||
⚫ | |||
struct LazyPermutation { |
|||
⚫ | |||
private uint[] seq; |
|||
perms(s[0 .. i] ~ s[i + 1 .. $], pre ~ c); |
|||
⚫ | |||
private size_t num; |
|||
this (size_t num) { |
|||
enforce(num > 1, "LazyPermutation: num must be > 1"); |
|||
this.seq = array(iota(0, num)); |
|||
this.tot = fact(num); |
|||
this.num = num; |
|||
⚫ | |||
@property uint[] front() { |
|||
return seq; |
|||
⚫ | |||
@property bool empty() { |
|||
return tot == 0; |
|||
⚫ | |||
void popFront(){ |
|||
⚫ | |||
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; |
|||
⚫ | |||
swap(seq[s], seq[r]); |
|||
r--; |
|||
s++; |
|||
} |
|||
} |
|||
} |
|||
} |
} |
||
size_t[] solve(T : size_t, F...)(T len, F predicates) { |
size_t[] solve(T : size_t, F...)(T len, F predicates) { |
||
outer: |
outer: |
||
foreach (p; |
foreach (p; LazyPermutation(len)) { |
||
foreach (pred; predicates) |
foreach (pred; predicates) |
||
if (!pred(p)) |
if (!pred(p)) |
||
continue outer; |
continue outer; |
||
return p; |
return p; |
||
Line 161: | Line 195: | ||
enum Floors = 5; |
enum Floors = 5; |
||
enum {Baker, Cooper, Fletcher, Miller, Smith}; |
enum {Baker, Cooper, Fletcher, Miller, Smith}; |
||
⚫ | |||
auto p1 = (uint[] s){ return s[Baker] != s.length-1; }; |
auto p1 = (uint[] s){ return s[Baker] != s.length-1; }; |
||
auto p2 = (uint[] s){ return s[Cooper] != 0; }; |
auto p2 = (uint[] s){ return s[Cooper] != 0; }; |
||
auto p3 = (uint[] s){ return s[Fletcher] != 0 && s[Fletcher] != s.length-1; }; |
auto p3 = (uint[] s){ return s[Fletcher] != 0 && s[Fletcher] != s.length-1; }; |
||
auto p4 = (uint[] s){ return s[Miller] > s[Cooper]; }; |
auto p4 = (uint[] s){ return s[Miller] > s[Cooper]; }; |
||
auto p5 = (uint[] s){ return abs(cast(int)(s[Smith] - s[Fletcher])) != 1; }; |
auto p5 = (uint[] s){ return abs(cast(int)(s[Smith] - s[Fletcher])) != 1; }; |
||
auto p6 = (uint[] s){ return abs(cast(int)(s[Cooper] - s[Fletcher])) != 1; }; |
auto p6 = (uint[] s){ return abs(cast(int)(s[Cooper] - s[Fletcher])) != 1; }; |
||
⚫ | |||
if (auto sol = solve(Floors, p1, p2, p3, p4, p5, p6)) |
if (auto sol = solve(Floors, p1, p2, p3, p4, p5, p6)) |
||
writeln(sol); |
writeln(sol); |