Anonymous user
Nonoblock: Difference between revisions
Updated D entry
(→Tcl: Added implementation) |
(Updated D entry) |
||
Line 61:
=={{header|D}}==
{{trans|python}}
<lang d>import std.stdio, std.array, std.algorithm, std.exception, std.conv
std.concurrency, std.range;
struct Solution { uint pos, len; }
Generator!(Solution[]) nonoBlocks(in uint[] blocks, in uint cells) {
return new typeof(return)({
if (blocks.empty || blocks[0] == 0) {▼
} else {▼
enforce(blocks.sum + blocks.length - 1 <= cells,▼
const restBl = blocks.dropOne;
// The other blocks need space.▼
immutable minS = restBl.map!(b => b + 1).sum;▼
// Slide the start position from left to max RH▼
▲ if (blocks.empty || blocks[0] == 0) {
// index allowing for other blocks.▼
▲ const vec = [Solution(0, 0)];
foreach (immutable bPos; 0 .. cells - minS - firstBl + 1) {
if (
// this one.▼
▲ enforce(blocks.sum + blocks.length - 1 <= cells,
// of placing the restBl blocks in the cells one
// space to the right of the RHS of this block.▼
immutable offset = bPos + firstBl + 1;▼
immutable newCells = cells - offset;
// Recursive call to nonoBlocks yields multiple▼
▲ // The other blocks need space.
// sub-positions.▼
▲ immutable minS = restBl.map!(b => b + 1).sum;
// Remove the offset from sub block positions.▼
// Yield this block plus sub blocks positions.▼
▲ // Slide the start position from left to max RH
▲ // index allowing for other blocks.
▲ // this one.
▲ } else {
▲ // More blocks to the right so create a sub-problem
▲ // of placing the restBl blocks in the cells one
▲ // space to the right of the RHS of this block.
▲ immutable offset = bPos + firstBl + 1;
▲ immutable newCells = cells - offset;
▲ // Recursive call to nonoBlocks yields multiple
▲ // sub-positions.
▲ foreach (const subPos; NonoBlocks(restBl, newCells)) {
▲ // Remove the offset from sub block positions.
▲ const rest = subPos.map!(sol => Solution(offset + sol.pos,
▲ // Yield this block plus sub blocks positions.
▲ const vec = [Solution(bPos, firstBl)] ~ rest;
}▼
}
}
/// Pretty prints each run of blocks with a
/// different letter for each block of filled cells.
string show(in Solution[] vec, in uint nCells) pure {
auto result = ['_'].replicate(nCells);
foreach (immutable i, immutable sol; vec)
foreach (immutable j; sol.pos .. sol.pos + sol.len)
result[j] = (result[j] == '_') ? to!char('A' + i) : '?';
return '[' ~ result ~ ']';
}
void main() {
static struct Problem { uint[] blocks; uint nCells; }
immutable Problem[] problems = [{[2, 1], 5},
{[], 5},
{[8], 10},
{[2, 3, 2, 3], 15},
{[4, 3], 10},
{[2, 1], 5},
{[3, 1], 10},
{[2, 3], 5}];
foreach (immutable prob; problems) {
writefln("Configuration (%d cells and %s blocks):",
prob.nCells, prob.blocks);
show([], prob.nCells).writeln;
"Possibilities:".writeln;
auto nConfigs = 0;
foreach (const sol;
show(sol, prob.nCells).writeln;
nConfigs++;
writefln("A total of %d possible configurations.", nConfigs);▼
writeln;▼
}
▲ writefln("A total of %d possible configurations.", nConfigs);
▲ writeln;
}</lang>
{{out}}
|