Nonoblock: Difference between revisions

Content added Content deleted

Inline

@@ Line 52: / Line 52: @@
 ;Reference:
 * The blog post [http://paddy3118.blogspot.co.uk/2014/03/nonogram-puzzle-solver-part-1.html Nonogram puzzle solver (part 1)] Inspired this task and donated its Python solution.
+=={{header|D}}==
+{{trans|python}}
+<lang d>import std.stdio, std.array, std.algorithm, std.exception, std.conv;
+struct Solution { uint pos, len; }
+struct NonoBlocks {
+  const uint[] blocks;
+  const uint cells;
+  int opApply(int delegate(ref const Solution[]) dg) {
+    int result;
+    if (blocks.empty || blocks[0] == 0) {
+      const vec = [Solution(0, 0)];
+      result = dg(vec);
+      if (result) return result;
+    } else {
+      enforce(sum(cast(uint[])blocks) + blocks.length - 1 <= cells,//**
+              "Those blocks cannot fit in those cells.");
+      immutable firstBl = blocks[0];
+      const restBl = blocks[1 .. $];
+      // The other blocks need space.
+      immutable minS = restBl.map!(b => b + 1).sum;
+      // Slide the start position from left to max RH
+      // index allowing for other blocks.
+      foreach (immutable bPos; 0 .. cells - minS - firstBl + 1) {
+        if (restBl.empty) {
+          // No other blocks to the right so just yield
+          // this one.
+          const vec = [Solution(bPos, firstBl)];
+          result = dg(vec);
+          if (result) return result;
+        } 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,
+                                                     sol.len)).array;
+            // Yield this block plus sub blocks positions.
+            const vec = [Solution(bPos, firstBl)] ~ rest;
+            result = dg(vec);
+            if (result) return result;
+          }
+        }
+      }
+    }
+    return result;
+  }
+}
+/// 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;
+    foreach (const sol; NonoBlocks(prob.tupleof))
+      show(sol, prob.nCells).writeln;
+    writeln;
+  }
+}</lang>
+{{out}}
+<pre>Configuration (5 cells and [2, 1] blocks):
+[_____]
+Possibilities:
+[AA_B_]
+[AA__B]
+[_AA_B]
+Configuration (5 cells and [] blocks):
+[_____]
+Possibilities:
+[_____]
+Configuration (10 cells and [8] blocks):
+[__________]
+Possibilities:
+[AAAAAAAA__]
+[_AAAAAAAA_]
+[__AAAAAAAA]
+Configuration (15 cells and [2, 3, 2, 3] blocks):
+[_______________]
+Possibilities:
+[AA_BBB_CC_DDD__]
+[AA_BBB_CC__DDD_]
+[AA_BBB_CC___DDD]
+[AA_BBB__CC_DDD_]
+[AA_BBB__CC__DDD]
+[AA_BBB___CC_DDD]
+[AA__BBB_CC_DDD_]
+[AA__BBB_CC__DDD]
+[AA__BBB__CC_DDD]
+[AA___BBB_CC_DDD]
+[_AA_BBB_CC_DDD_]
+[_AA_BBB_CC__DDD]
+[_AA_BBB__CC_DDD]
+[_AA__BBB_CC_DDD]
+[__AA_BBB_CC_DDD]
+Configuration (10 cells and [4, 3] blocks):
+[__________]
+Possibilities:
+[AAAA_BBB__]
+[AAAA__BBB_]
+[AAAA___BBB]
+[_AAAA_BBB_]
+[_AAAA__BBB]
+[__AAAA_BBB]
+Configuration (5 cells and [2, 1] blocks):
+[_____]
+Possibilities:
+[AA_B_]
+[AA__B]
+[_AA_B]
+Configuration (10 cells and [3, 1] blocks):
+[__________]
+Possibilities:
+[AAA_B_____]
+[AAA__B____]
+[AAA___B___]
+[AAA____B__]
+[AAA_____B_]
+[AAA______B]
+[_AAA_B____]
+[_AAA__B___]
+[_AAA___B__]
+[_AAA____B_]
+[_AAA_____B]
+[__AAA_B___]
+[__AAA__B__]
+[__AAA___B_]
+[__AAA____B]
+[___AAA_B__]
+[___AAA__B_]
+[___AAA___B]
+[____AAA_B_]
+[____AAA__B]
+[_____AAA_B]
+Configuration (5 cells and [2, 3] blocks):
+[_____]
+Possibilities:
+Possibilities:
+object.Exception@nonoblock.d(17): Those blocks cannot fit in those cells.
+----------------
+x0040AC17 in pure @safe void std.exception.bailOut(immutable(char)[], uint, const(char[]))
+...</pre>
 =={{header|Python}}==