Rosetta Code

Nonoblock: Difference between revisions

Page Discussion

Nonoblock (view source)

Revision as of 11:00, 6 January 2024

96,448 bytes added ,  4 months ago
m
→‎{{header|Wren}}: Minor tidy
(Add an algorithm.)
m (→‎{{header|Wren}}: Minor tidy)
 
(73 intermediate revisions by 31 users not shown)
Line 1:
{{draft task}} [[Category:Puzzles]]
Nonoblock is a chip off the old [[Nonogram solver|Nonogram]] puzzle.
 
 
;Given:
* The number of cells in a row.
* The size of each, (space separated), connected block of cells to fit in the row, in left-to right order.
 
 
;Task:
* show all possible positions.
* show the number of positions of the blocks for the following cases within the row.
* show all output on this page.
* use a "neat" diagram of the block positions.
 
'''The task''' is to
* show all possible positions
* and the number of positions
of the blocks for the following cases
within the row. On this page. Using a "neat" diagram of the block positions.
 
;Enumerate the following configurations:
#   '''5'''   cells   and   '''[2, 1]'''   blocks
#   '''5'''   cells   and   '''[]'''   blocks   (no blocks)
#   '''10'''   cells   and   '''[8]'''   blocks
#   '''15'''   cells   and   '''[2, 3, 2, 3]'''   blocks
#   '''5'''   cells   and   '''[2, 3]'''   blocks   (Shouldshould give some indication of this not being possible).
 
 
;Example:
Given a row of five cells and a block of two cells followed by a block of one cell - in that order, the example could be shown as:
by a block of 1 cell - in that order, the example could be shown as:
 
|_|_|_|_|_| # 5 cells and [2, 1] blocks
Line 32 ⟶ 35:
 
 
Note how the sets of blocks are always separated by a space.
 
Note also that it is not necessary for each block to have a separate letter. Output approximating
Output approximating
 
This:
|#|#|_|#|_|
|#|#|_|_|#|
|_|#|#|_|#|
 
This would also work:
|#|#|_|#|_|
| #|#|_|_|.#|.
|_| #|#|_|..#|
.##.#
 
Or even this:
 
##.#.
##..#
.##.#
 
Would also work.
 
;An algorithm:
Line 54 ⟶ 55:
* The leftmost cell can legitimately be placed in all positions from the LHS up to a RH position that allows enough room for the rest of the blocks.
* for each position of the LH block recursively compute the position of the rest of the blocks in the ''remaining'' space to the right of the current placement of the LH block.
 
(This is the algorithm used in the [[Nonoblock#Python]] solution).
 
 
;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 [[Nonoblock#Python]] solution.
<br><br>
 
=={{header|D11l}}==
{{trans|pythonPython}}
<lang d>import std.stdio, std.array, std.algorithm, std.exception, std.conv;
 
<syntaxhighlight lang="11l">F nonoblocks([Int] &blocks, Int cells) -> [[(Int, Int)]]
struct Solution { uint pos, len; }
[[(Int, Int)]] r
I blocks.empty | blocks[0] == 0
r [+]= [(0, 0)]
E
assert(sum(blocks) + blocks.len - 1 <= cells, ‘Those blocks will not fit in those cells’)
V (blength, brest) = (blocks[0], blocks[1..])
V minspace4rest = sum(brest.map(b -> 1 + b))
 
L(bpos) 0 .. cells - minspace4rest - blength
struct NonoBlocks {
I brest.empty
const uint[] blocks;
r [+]= [(bpos, blength)]
const uint cells;
E
V offset = bpos + blength + 1
L(subpos) nonoblocks(&brest, cells - offset)
V rest = subpos.map((bp, bl) -> (@offset + bp, bl))
V vec = [(bpos, blength)] [+] rest
r [+]= vec
R r
 
F pblock(vec, cells)
int opApply(int delegate(ref const Solution[]) dg) {
‘Prettyprints each run of blocks with a different letter A.. for each block of filled cells’
int result;
V vector = [‘_’] * cells
L(bp_bl) vec
V ch = L.index + ‘A’.code
V (bp, bl) = bp_bl
L(i) bp .< bp + bl
vector[i] = I vector[i] == ‘_’ {Char(code' ch)} E Char(‘?’)
R ‘|’vector.join(‘|’)‘|’
 
if L(blocks.empty, ||cells) blocks[0] == 0) {
const vec = [Solution(0[2, 0)1];, 5),
result = dg(vec[Int](), 5);,
if([8], (result10) return result;,
} else {([2, 3, 2, 3], 15)
]
enforce(sum(cast(uint[])blocks) + blocks.length - 1 <= cells,//**
print("\nConfiguration:\n #. ## #. cells and #. blocks".format(pblock([(Int, Int)](), cells), cells, blocks))
"Those blocks cannot fit in those cells.");
print(‘ Possibilities:’)
immutable firstBl = blocks[0];
V const restBlnb = nonoblocks(&blocks[1 .., $];cells)
L(vector) nb
print(‘ ’pblock(vector, cells))
print(‘ A total of #. Possible configurations.’.format(nb.len))</syntaxhighlight>
 
{{out}}
// The other blocks need space.
<pre>
immutable minS = restBl.map!(b => b + 1).sum;
 
Configuration:
// Slide the start position from left to max RH
|_|_|_|_|_| # //5 indexcells allowingand for[2, other1] blocks.
Possibilities:
foreach (immutable bPos; 0 .. cells - minS - firstBl + 1) {
|A|A|_|B|_|
if (restBl.empty) {
|A|A|_|_|B|
// No other blocks to the right so just yield
|_|A|A|_|B|
// this one.
A total of 3 Possible configurations.
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;
 
Configuration:
// Recursive call to nonoBlocks yields multiple
|_|_|_|_|_| # 5 cells and [] blocks
// sub-positions.
Possibilities:
foreach (const subPos; NonoBlocks(restBl, newCells)) {
|_|_|_|_|_|
// Remove the offset from sub block positions.
A total of 1 Possible configurations.
const rest = subPos.map!(sol => Solution(offset + sol.pos,
sol.len)).array;
 
Configuration:
// Yield this block plus sub blocks positions.
|_|_|_|_|_|_|_|_|_|_| # 10 cells and [8] blocks
const vec = [Solution(bPos, firstBl)] ~ rest;
Possibilities:
result = dg(vec);
|A|A|A|A|A|A|A|A|_|_|
if (result) return result;
|_|A|A|A|A|A|A|A|A|_|
}
|_|_|A|A|A|A|A|A|A|A|
A total of 3 Possible configurations.
 
Configuration:
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| # 15 cells and [2, 3, 2, 3] blocks
Possibilities:
|A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
|A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
|A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
|A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
|A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
|A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
|A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
|A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
|A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
|A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
|_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
|_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
|_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
|_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
|_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
A total of 15 Possible configurations.
</pre>
 
=={{header|Action!}}==
<syntaxhighlight lang="action!">DEFINE MAX_BLOCKS="10"
DEFINE NOT_FOUND="255"
 
BYTE FUNC GetBlockAtPos(BYTE p BYTE ARRAY blocks,pos INT count)
INT i
FOR i=0 TO count-1
DO
IF p>=pos(i) AND p<pos(i)+blocks(i) THEN
RETURN (i)
FI
OD
RETURN (NOT_FOUND)
 
PROC PrintResult(BYTE cells BYTE ARRAY blocks,pos INT count)
BYTE i,b
 
Print("[")
FOR i=0 TO cells-1
DO
b=GetBlockAtPos(i,blocks,pos,count)
IF b=NOT_FOUND THEN
Put('.)
ELSE
Put(b+'A)
FI
OD
PrintE("]")
RETURN
 
BYTE FUNC LeftMostPos(BYTE cells BYTE ARRAY blocks,pos INT count,startFrom)
INT i
 
FOR i=startFrom TO count-1
DO
pos(i)=pos(i-1)+blocks(i-1)+1
IF pos(i)+blocks(i)>cells THEN
RETURN (0)
FI
OD
RETURN (1)
 
BYTE FUNC MoveToRight(BYTE cells BYTE ARRAY blocks,pos INT count,startFrom)
pos(startFrom)==+1
IF pos(startFrom)+blocks(startFrom)>cells THEN
RETURN (0)
FI
RETURN (LeftMostPos(cells,blocks,pos,count,startFrom+1))
 
PROC Process(BYTE cells BYTE ARRAY blocks INT count)
BYTE ARRAY pos(MAX_BLOCKS)
BYTE success
INT current
 
IF count=0 THEN
PrintResult(cells,blocks,pos,count)
RETURN
FI
 
pos(0)=0
success=LeftMostPos(cells,blocks,pos,count,1)
IF success=0 THEN
PrintE("No solutions")
RETURN
FI
current=count-1
WHILE success
DO
PrintResult(cells,blocks,pos,count)
DO
success=MoveToRight(cells,blocks,pos,count,current)
IF success THEN
current=count-1
ELSE
current==-1
IF current<0 THEN
EXIT
FI
FI
UNTIL success
OD
OD
RETURN
 
PROC Test(BYTE cells BYTE ARRAY blocks INT count)
BYTE CH=$02FC ;Internal hardware value for last key pressed
INT i
PrintB(cells) Print(" cells [")
FOR i=0 TO count-1
DO
PrintB(blocks(i))
IF i<count-1 THEN
Put(32)
FI
OD
PrintE("]")
 
Process(cells,blocks,count)
 
PutE()
PrintE("Press any key to continue...")
DO UNTIL CH#$FF OD
CH=$FF
PutE()
RETURN
 
PROC Main()
BYTE ARRAY t1=[2 1],t2=[],t3=[8],t4=[2 3 2 3],t5=[2 3]
 
Test(5,t1,2)
Test(5,t2,0)
Test(10,t3,1)
Test(15,t4,4)
Test(5,t5,2)
RETURN</syntaxhighlight>
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Nonoblock.png Screenshot from Atari 8-bit computer]
<pre>
5 cells [2 1]
[AA.B.]
[AA..B]
[.AA.B]
 
Press any key to continue...
 
5 cells []
[.....]
 
Press any key to continue...
 
10 cells [8]
[AAAAAAAA..]
[.AAAAAAAA.]
[..AAAAAAAA]
 
Press any key to continue...
 
15 cells [2 3 2 3]
[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]
 
Press any key to continue...
 
5 cells [2 3]
No solutions
 
Press any key to continue...
</pre>
 
=={{header|AutoHotkey}}==
<syntaxhighlight lang="autohotkey">;-------------------------------------------
NonoBlock(cells, blocks){
result := [], line := ""
for i, v in blocks
B .= v ", "
output := cells " cells and [" Trim(B, ", ") "] blocks`n"
if ((Arr := NonoBlockCreate(cells, blocks)) = "Error")
return output "No Solution`n"
for i, v in arr
line.= v ";"
result[line] := true
result := NonoBlockRecurse(Arr, result)
output .= NonoBlockShow(result)
return output
}
;-------------------------------------------
; create cells+1 size array, stack blocks to left with one gap in between
; gaps are represented by negative number
; stack extra gaps to far left
; for example : 6 cells and [2, 1] blocks
; returns [-2, 2, -1, 1, 0, 0, 0]
NonoBlockCreate(cells, blocks){
Arr := [], B := blocks.Count()
if !B ; no blocks
return [0-cells, 0]
for i, v in blocks{
total += v
Arr.InsertAt(1, blocks[B-A_Index+1])
Arr.InsertAt(1, -1)
}
if (cells < total + B-1) ; not possible
return "Error"
Arr[1] := total + B-1 - cells
loop % cells - Arr.Count() + 1
Arr.Push(0)
return Arr
}
;-------------------------------------------
; shift negative numbers from left to right recursively.
; preserve at least one gap between blocks.
; [-2, 2, -1, 1, 0, 0, 0]
; [-1, 2, -2, 1, 0, 0, 0]
NonoBlockRecurse(Arr, result, pos:= 1){
i := pos-1
while (i < Arr.count())
{
if ((B:=Arr[++i])>=0) || (B=-1 && i>1)
continue
if (i=Arr.count()-1)
return result
Arr[i] := ++B, Arr[i+2] := Arr[i+2] -1
result := NonoBlockRecurse(Arr.Clone(), result, i)
line := []
for k, v in Arr
line.=v ";"
result[line] := true
}
return result
}
;-------------------------------------------
; represent positve numbers by a block of "#", negative nubmers by a block of "."
NonoBlockShow(result){
for line in result{
i := A_Index
nLine := ""
for j, val in StrSplit(line, ";")
loop % Abs(val)
nLine .= val > 0 ? "#" : "."
output .= nLine "`n"
}
Sort, output, U
return output
}
;-------------------------------------------</syntaxhighlight>Examples:<syntaxhighlight lang="autohotkey">
Results .= NonoBlock(5, [2, 1]) "------------`n"
Results .= NonoBlock(5, []) "------------`n"
Results .= NonoBlock(10, [8]) "------------`n"
Results .= NonoBlock(15, [2, 3, 2, 3]) "------------`n"
Results .= NonoBlock(5, [2, 3]) "------------`n"
MsgBox, 262144, , % Results
return
</syntaxhighlight>
{{out}}
<pre>---------------------------
5 cells and [2, 1] blocks
##.#.
##..#
.##.#
------------
5 cells and [] blocks
.....
------------
10 cells and [8] blocks
########..
.########.
..########
------------
15 cells and [2, 3, 2, 3] blocks
##.###.##.###..
##.###.##..###.
##.###.##...###
##.###..##.###.
##.###..##..###
##.###...##.###
##..###.##.###.
##..###.##..###
##..###..##.###
##...###.##.###
.##.###.##.###.
.##.###.##..###
.##.###..##.###
.##..###.##.###
..##.###.##.###
------------
5 cells and [2, 3] blocks
No Solution
------------</pre>
 
=={{header|C}}==
<syntaxhighlight lang="c">#include <stdio.h>
#include <string.h>
 
void nb(int cells, int total_block_size, int* blocks, int block_count,
char* output, int offset, int* count) {
if (block_count == 0) {
printf("%2d %s\n", ++*count, output);
return;
}
int block_size = blocks[0];
int max_pos = cells - (total_block_size + block_count - 1);
total_block_size -= block_size;
cells -= block_size + 1;
++blocks;
--block_count;
for (int i = 0; i <= max_pos; ++i, --cells) {
memset(output + offset, '.', max_pos + block_size);
memset(output + offset + i, '#', block_size);
nb(cells, total_block_size, blocks, block_count, output,
offset + block_size + i + 1, count);
}
}
 
void nonoblock(int cells, int* blocks, int block_count) {
printf("%d cells and blocks [", cells);
for (int i = 0; i < block_count; ++i)
printf(i == 0 ? "%d" : ", %d", blocks[i]);
printf("]:\n");
int total_block_size = 0;
for (int i = 0; i < block_count; ++i)
total_block_size += blocks[i];
if (cells < total_block_size + block_count - 1) {
printf("no solution\n");
return;
}
char output[cells + 1];
memset(output, '.', cells);
output[cells] = '\0';
int count = 0;
nb(cells, total_block_size, blocks, block_count, output, 0, &count);
}
 
int main() {
int blocks1[] = {2, 1};
nonoblock(5, blocks1, 2);
printf("\n");
nonoblock(5, NULL, 0);
printf("\n");
 
int blocks2[] = {8};
nonoblock(10, blocks2, 1);
printf("\n");
int blocks3[] = {2, 3, 2, 3};
nonoblock(15, blocks3, 4);
printf("\n");
int blocks4[] = {2, 3};
nonoblock(5, blocks4, 2);
 
return 0;
}</syntaxhighlight>
 
{{out}}
<pre>
5 cells and blocks [2, 1]:
1 ##.#.
2 ##..#
3 .##.#
 
5 cells and blocks []:
1 .....
 
10 cells and blocks [8]:
1 ########..
2 .########.
3 ..########
 
15 cells and blocks [2, 3, 2, 3]:
1 ##.###.##.###..
2 ##.###.##..###.
3 ##.###.##...###
4 ##.###..##.###.
5 ##.###..##..###
6 ##.###...##.###
7 ##..###.##.###.
8 ##..###.##..###
9 ##..###..##.###
10 ##...###.##.###
11 .##.###.##.###.
12 .##.###.##..###
13 .##.###..##.###
14 .##..###.##.###
15 ..##.###.##.###
 
5 cells and blocks [2, 3]:
no solution
</pre>
 
=={{header|C sharp}}==
This solution uses a StringBuilder. Spaces are moved from right to left and the problem is then solved recursively.
<syntaxhighlight lang="csharp">using System;
using System.Linq;
using System.Text;
 
public static class Nonoblock
{
public static void Main() {
Positions(5, 2,1);
Positions(5);
Positions(10, 8);
Positions(15, 2,3,2,3);
Positions(5, 2,3);
}
 
public static void Positions(int cells, params int[] blocks) {
if (cells < 0 || blocks == null || blocks.Any(b => b < 1)) throw new ArgumentOutOfRangeException();
Console.WriteLine($"{cells} cells with [{string.Join(", ", blocks)}]");
if (blocks.Sum() + blocks.Length - 1 > cells) {
Console.WriteLine("No solution");
return;
}
var spaces = new int[blocks.Length + 1];
}
int total = -1;
for (int i = 0; i < blocks.Length; i++) {
total += blocks[i] + 1;
spaces[i+1] = total;
}
spaces[spaces.Length - 1] = cells - 1;
var sb = new StringBuilder(string.Join(".", blocks.Select(b => new string('#', b))).PadRight(cells, '.'));
Iterate(sb, spaces, spaces.Length - 1, 0);
Console.WriteLine();
}
 
private static void Iterate(StringBuilder output, int[] spaces, int index, int offset) {
return result;
Console.WriteLine(output.ToString());
}
if (index <= 0) return;
int count = 0;
while (output[spaces[index] - offset] != '#') {
count++;
output.Remove(spaces[index], 1);
output.Insert(spaces[index-1], '.');
spaces[index-1]++;
Iterate(output, spaces, index - 1, 1);
}
if (offset == 0) return;
spaces[index-1] -= count;
output.Remove(spaces[index-1], count);
output.Insert(spaces[index] - count, ".", count);
}
 
}</syntaxhighlight>
{{out}}
<pre style="height:50ex;overflow:scroll">
5 cells with [2, 1]
##.#.
##..#
.##.#
 
5 cells with []
.....
 
10 cells with [8]
########..
.########.
..########
 
15 cells with [2, 3, 2, 3]
##.###.##.###..
##.###.##..###.
##.###..##.###.
##..###.##.###.
.##.###.##.###.
##.###.##...###
##.###..##..###
##..###.##..###
.##.###.##..###
##.###...##.###
##..###..##.###
.##.###..##.###
##...###.##.###
.##..###.##.###
..##.###.##.###
 
5 cells with [2, 3]
No solution</pre>
 
=={{header|C++}}==
<syntaxhighlight lang="cpp">
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <string>
#include <vector>
 
typedef std::pair<int, std::vector<int> > puzzle;
 
class nonoblock {
public:
void solve( std::vector<puzzle>& p ) {
for( std::vector<puzzle>::iterator i = p.begin(); i != p.end(); i++ ) {
counter = 0;
std::cout << " Puzzle: " << ( *i ).first << " cells and blocks [ ";
for( std::vector<int>::iterator it = ( *i ).second.begin(); it != ( *i ).second.end(); it++ )
std::cout << *it << " ";
std::cout << "] ";
int s = std::accumulate( ( *i ).second.begin(), ( *i ).second.end(), 0 ) + ( ( *i ).second.size() > 0 ? ( *i ).second.size() - 1 : 0 );
if( ( *i ).first - s < 0 ) {
std::cout << "has no solution!\n\n\n";
continue;
}
std::cout << "\n Possible configurations:\n\n";
std::string b( ( *i ).first, '-' );
solve( *i, b, 0 );
std::cout << "\n\n";
}
}
 
private:
void solve( puzzle p, std::string n, int start ) {
if( p.second.size() < 1 ) {
output( n );
return;
}
std::string temp_string;
int offset,
this_block_size = p.second[0];
 
int space_need_for_others = std::accumulate( p.second.begin() + 1, p.second.end(), 0 );
space_need_for_others += p.second.size() - 1;
 
int space_for_curr_block = p.first - space_need_for_others - std::accumulate( p.second.begin(), p.second.begin(), 0 );
 
std::vector<int> v1( p.second.size() - 1 );
std::copy( p.second.begin() + 1, p.second.end(), v1.begin() );
puzzle p1 = std::make_pair( space_need_for_others, v1 );
 
for( int a = 0; a < space_for_curr_block; a++ ) {
temp_string = n;
 
if( start + this_block_size > n.length() ) return;
 
for( offset = start; offset < start + this_block_size; offset++ )
temp_string.at( offset ) = 'o';
 
if( p1.first ) solve( p1, temp_string, offset + 1 );
else output( temp_string );
 
start++;
}
}
void output( std::string s ) {
char b = 65 - ( s.at( 0 ) == '-' ? 1 : 0 );
bool f = false;
std::cout << std::setw( 3 ) << ++counter << "\t|";
for( std::string::iterator i = s.begin(); i != s.end(); i++ ) {
b += ( *i ) == 'o' && f ? 1 : 0;
std::cout << ( ( *i ) == 'o' ? b : '_' ) << "|";
f = ( *i ) == '-' ? true : false;
}
std::cout << "\n";
}
 
unsigned counter;
};
 
int main( int argc, char* argv[] )
{
std::vector<puzzle> problems;
std::vector<int> blocks;
blocks.push_back( 2 ); blocks.push_back( 1 );
problems.push_back( std::make_pair( 5, blocks ) );
blocks.clear();
problems.push_back( std::make_pair( 5, blocks ) );
blocks.push_back( 8 );
problems.push_back( std::make_pair( 10, blocks ) );
blocks.clear();
blocks.push_back( 2 ); blocks.push_back( 3 );
problems.push_back( std::make_pair( 5, blocks ) );
blocks.push_back( 2 ); blocks.push_back( 3 );
problems.push_back( std::make_pair( 15, blocks ) );
 
nonoblock nn;
nn.solve( problems );
 
return 0;
}
</syntaxhighlight>
{{out}}
<pre>
Puzzle: 5 cells and blocks [ 2 1 ]
Possible configurations:
 
1 |A|A|_|B|_|
2 |A|A|_|_|B|
3 |_|A|A|_|B|
 
 
Puzzle: 5 cells and blocks [ ]
Possible configurations:
 
1 |_|_|_|_|_|
 
 
Puzzle: 10 cells and blocks [ 8 ]
Possible configurations:
 
1 |A|A|A|A|A|A|A|A|_|_|
2 |_|A|A|A|A|A|A|A|A|_|
3 |_|_|A|A|A|A|A|A|A|A|
 
 
Puzzle: 5 cells and blocks [ 2 3 ] has no solution!
 
 
Puzzle: 15 cells and blocks [ 2 3 2 3 ]
Possible configurations:
 
1 |A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
2 |A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
3 |A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
4 |A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
5 |A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
6 |A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
7 |A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
8 |A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
9 |A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
10 |A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
11 |_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
12 |_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
13 |_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
14 |_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
15 |_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
 
</pre>
 
=={{header|D}}==
{{trans|python}}
<syntaxhighlight 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) {
yield([Solution(0, 0)]);
} else {
enforce(blocks.sum + blocks.length - 1 <= cells,
"Those blocks cannot fit in those cells.");
immutable firstBl = blocks[0];
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
// 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.
yield([Solution(bPos, firstBl)]);
} 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.
auto rest = subPos.map!(sol => Solution(offset + sol.pos, sol.len));
 
// Yield this block plus sub blocks positions.
yield(Solution(bPos, firstBl) ~ rest.array);
}
}
}
}
});
}
 
 
/// 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; NonoBlocks(prob.tupleof))
show foreach (const sol,; nonoBlocks(prob.nCellstupleof).writeln;) {
show(sol, prob.nCells).writeln;
nConfigs++;
}
}
}</lang>
writefln("A total of %d possible configurations.", nConfigs);
writeln;
}
}</syntaxhighlight>
{{out}}
<pre>Configuration (5 cells and [2, 1] blocks):
Line 160 ⟶ 870:
[AA__B]
[_AA_B]
A total of 3 possible configurations.
 
Configuration (5 cells and [] blocks):
Line 165 ⟶ 876:
Possibilities:
[_____]
A total of 1 possible configurations.
 
Configuration (10 cells and [8] blocks):
Line 172 ⟶ 884:
[_AAAAAAAA_]
[__AAAAAAAA]
A total of 3 possible configurations.
 
Configuration (15 cells and [2, 3, 2, 3] blocks):
Line 191 ⟶ 904:
[_AA__BBB_CC_DDD]
[__AA_BBB_CC_DDD]
A total of 15 possible configurations.
 
Configuration (10 cells and [4, 3] blocks):
Line 201 ⟶ 915:
[_AAAA__BBB]
[__AAAA_BBB]
A total of 6 possible configurations.
 
Configuration (5 cells and [2, 1] blocks):
Line 208 ⟶ 923:
[AA__B]
[_AA_B]
A total of 3 possible configurations.
 
Configuration (10 cells and [3, 1] blocks):
Line 233 ⟶ 949:
[____AAA__B]
[_____AAA_B]
A total of 21 possible configurations.
 
Configuration (5 cells and [2, 3] blocks):
[_____]
Possibilities:
Possibilities:
object.Exception @nonoblock.d(17): Those blocks cannot fit in those cells.
Line 242 ⟶ 958:
0x0040AC17 in pure @safe void std.exception.bailOut(immutable(char)[], uint, const(char[]))
...</pre>
 
=={{header|EchoLisp}}==
<syntaxhighlight lang="scheme">
;; size is the remaining # of cells
;; blocks is the list of remaining blocks size
;; cells is a stack where we push 0 = space or block size.
(define (nonoblock size blocks into: cells)
(cond
((and (empty? blocks) (= 0 size)) (print-cells (stack->list cells)))
((<= size 0) #f) ;; no hope - cut search
((> (apply + blocks) size) #f) ;; no hope - cut search
(else
(push cells 0) ;; space
(nonoblock (1- size) blocks cells)
(pop cells)
 
(when (!empty? blocks)
(when (stack-empty? cells) ;; first one (no space is allowed)
(push cells (first blocks))
(nonoblock (- size (first blocks)) (rest blocks) cells)
(pop cells))
 
(push cells 0) ;; add space before
(push cells (first blocks))
(nonoblock (- size (first blocks) 1) (rest blocks) cells)
(pop cells)
(pop cells)))))
(string-delimiter "")
(define block-symbs #( ? 📦 💣 💊 🍒 🌽 📘 📙 💰 🍯 ))
 
(define (print-cells cells)
(writeln (string-append "|"
(for/string ((cell cells))
(if (zero? cell) "_"
(for/string ((i cell)) [block-symbs cell]))) "|")))
(define (task nonotest)
(for ((test nonotest))
(define size (first test))
(define blocks (second test))
(printf "\n size:%d blocks:%d" size blocks)
(if
(> (+ (apply + blocks)(1- (length blocks))) size)
(writeln "❌ no solution for" size blocks)
(nonoblock size blocks (stack 'cells)))))
</syntaxhighlight>
{{out}}
<pre>
(define nonotest '((5 (2 1)) (5 ()) (10 (8)) (15 (2 3 2 3)) (5 (2 3))))
(task nonotest)
 
size:5 blocks:(2 1)
|💣💣__📦|
|💣💣_📦_|
|_💣💣_📦|
 
size:5 blocks:()
|_____|
 
size:10 blocks:(8)
|__💰💰💰💰💰💰💰💰|
|💰💰💰💰💰💰💰💰__|
|_💰💰💰💰💰💰💰💰_|
 
size:15 blocks:(2 3 2 3)
|__💣💣_💊💊💊_💣💣_💊💊💊|
|💣💣___💊💊💊_💣💣_💊💊💊|
|💣💣__💊💊💊__💣💣_💊💊💊|
|💣💣__💊💊💊_💣💣__💊💊💊|
|💣💣__💊💊💊_💣💣_💊💊💊_|
|💣💣_💊💊💊___💣💣_💊💊💊|
|💣💣_💊💊💊__💣💣__💊💊💊|
|💣💣_💊💊💊__💣💣_💊💊💊_|
|💣💣_💊💊💊_💣💣___💊💊💊|
|💣💣_💊💊💊_💣💣__💊💊💊_|
|💣💣_💊💊💊_💣💣_💊💊💊__|
|_💣💣__💊💊💊_💣💣_💊💊💊|
|_💣💣_💊💊💊__💣💣_💊💊💊|
|_💣💣_💊💊💊_💣💣__💊💊💊|
|_💣💣_💊💊💊_💣💣_💊💊💊_|
 
size:5 blocks:(2 3)
❌ no solution for 5 (2 3)
</pre>
 
=={{header|Elixir}}==
{{trans|Ruby}}
<syntaxhighlight lang="elixir">defmodule Nonoblock do
def solve(cell, blocks) do
width = Enum.sum(blocks) + length(blocks) - 1
if cell < width do
raise "Those blocks will not fit in those cells"
else
nblocks(cell, blocks, "")
end
end
defp nblocks(cell, _, position) when cell<=0, do:
display(String.slice(position, 0..cell-1))
defp nblocks(cell, blocks, position) when length(blocks)==0 or hd(blocks)==0, do:
display(position <> String.duplicate(".", cell))
defp nblocks(cell, blocks, position) do
rest = cell - Enum.sum(blocks) - length(blocks) + 2
[bl | brest] = blocks
Enum.reduce(0..rest-1, 0, fn i,acc ->
acc + nblocks(cell-i-bl-1, brest, position <> String.duplicate(".", i) <> String.duplicate("#",bl) <> ".")
end)
end
defp display(str) do
IO.puts nonocell(str)
1 # number of positions
end
def nonocell(str) do # "##.###..##" -> "|A|A|_|B|B|B|_|_|C|C|"
slist = String.to_char_list(str) |> Enum.chunk_by(&(&1==?.)) |> Enum.map(&List.to_string(&1))
chrs = Enum.map(?A..?Z, &List.to_string([&1]))
result = nonocell_replace(slist, chrs, "")
|> String.replace(".", "_")
|> String.split("") |> Enum.join("|")
"|" <> result
end
defp nonocell_replace([], _, result), do: result
defp nonocell_replace([h|t], chrs, result) do
if String.first(h) == "#" do
[c | rest] = chrs
nonocell_replace(t, rest, result <> String.replace(h, "#", c))
else
nonocell_replace(t, chrs, result <> h)
end
end
end
 
conf = [{ 5, [2, 1]},
{ 5, []},
{10, [8]},
{15, [2, 3, 2, 3]},
{ 5, [2, 3]} ]
Enum.each(conf, fn {cell, blocks} ->
try do
IO.puts "Configuration:"
IO.puts "#{Nonoblock.nonocell(String.duplicate(".",cell))} # #{cell} cells and #{inspect blocks} blocks"
IO.puts "Possibilities:"
count = Nonoblock.solve(cell, blocks)
IO.puts "A total of #{count} Possible configurations.\n"
rescue
e in RuntimeError -> IO.inspect e
end
end)</syntaxhighlight>
 
{{out}}
<pre>
Configuration:
|_|_|_|_|_| # 5 cells and [2, 1] blocks
Possibilities:
|A|A|_|B|_|
|A|A|_|_|B|
|_|A|A|_|B|
A total of 3 Possible configurations.
 
Configuration:
|_|_|_|_|_| # 5 cells and [] blocks
Possibilities:
|_|_|_|_|_|
A total of 1 Possible configurations.
 
Configuration:
|_|_|_|_|_|_|_|_|_|_| # 10 cells and '\b' blocks
Possibilities:
|A|A|A|A|A|A|A|A|_|_|
|_|A|A|A|A|A|A|A|A|_|
|_|_|A|A|A|A|A|A|A|A|
A total of 3 Possible configurations.
 
Configuration:
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| # 15 cells and [2, 3, 2, 3] blocks
Possibilities:
|A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
|A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
|A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
|A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
|A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
|A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
|A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
|A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
|A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
|A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
|_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
|_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
|_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
|_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
|_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
A total of 15 Possible configurations.
 
Configuration:
|_|_|_|_|_| # 5 cells and [2, 3] blocks
Possibilities:
%RuntimeError{message: "Those blocks will not fit in those cells"}
</pre>
 
=={{header|Go}}==
{{trans|Kotlin}}
<syntaxhighlight lang="go">package main
 
import (
"fmt"
"strings"
)
 
func printBlock(data string, le int) {
a := []byte(data)
sumBytes := 0
for _, b := range a {
sumBytes += int(b - 48)
}
fmt.Printf("\nblocks %c, cells %d\n", a, le)
if le-sumBytes <= 0 {
fmt.Println("No solution")
return
}
prep := make([]string, len(a))
for i, b := range a {
prep[i] = strings.Repeat("1", int(b-48))
}
for _, r := range genSequence(prep, le-sumBytes+1) {
fmt.Println(r[1:])
}
}
 
func genSequence(ones []string, numZeros int) []string {
if len(ones) == 0 {
return []string{strings.Repeat("0", numZeros)}
}
var result []string
for x := 1; x < numZeros-len(ones)+2; x++ {
skipOne := ones[1:]
for _, tail := range genSequence(skipOne, numZeros-x) {
result = append(result, strings.Repeat("0", x)+ones[0]+tail)
}
}
return result
}
 
func main() {
printBlock("21", 5)
printBlock("", 5)
printBlock("8", 10)
printBlock("2323", 15)
printBlock("23", 5)
}</syntaxhighlight>
 
{{out}}
<pre>
blocks [2 1], cells 5
11010
11001
01101
 
blocks [], cells 5
00000
 
blocks [8], cells 10
1111111100
0111111110
0011111111
 
blocks [2 3 2 3], cells 15
110111011011100
110111011001110
110111011000111
110111001101110
110111001100111
110111000110111
110011101101110
110011101100111
110011100110111
110001110110111
011011101101110
011011101100111
011011100110111
011001110110111
001101110110111
 
blocks [2 3], cells 5
No solution
</pre>
 
=={{header|J}}==
 
Implementation:
 
<syntaxhighlight lang="j">nonoblock=:4 :0
s=. 1+(1+x)-+/1+y
pad=.1+(#~ s >+/"1)((1+#y)#s) #: i.s^1+#y
~.pad (_1}.1 }. ,. #&, 0 ,. 1 + i.@#@])"1]y,0
)
 
neat=: [: (#~ # $ 0 1"_)@": {&(' ',65}.a.)&.></syntaxhighlight>
 
Task example:
 
<syntaxhighlight lang="j"> neat 5 nonoblock 2 1
│A│A│ │B│ │
│A│A│ │ │B│
│ │A│A│ │B│
neat 5 nonoblock ''
│ │ │ │ │ │
neat 10 nonoblock 8
│A│A│A│A│A│A│A│A│ │ │
│ │A│A│A│A│A│A│A│A│ │
│ │ │A│A│A│A│A│A│A│A│
neat 15 nonoblock 2 3 2 3
│A│A│ │B│B│B│ │C│C│ │D│D│D│ │ │
│A│A│ │B│B│B│ │C│C│ │ │D│D│D│ │
│A│A│ │B│B│B│ │C│C│ │ │ │D│D│D│
│A│A│ │B│B│B│ │ │C│C│ │D│D│D│ │
│A│A│ │B│B│B│ │ │C│C│ │ │D│D│D│
│A│A│ │B│B│B│ │ │ │C│C│ │D│D│D│
│A│A│ │ │B│B│B│ │C│C│ │D│D│D│ │
│A│A│ │ │B│B│B│ │C│C│ │ │D│D│D│
│A│A│ │ │B│B│B│ │ │C│C│ │D│D│D│
│A│A│ │ │ │B│B│B│ │C│C│ │D│D│D│
│ │A│A│ │B│B│B│ │C│C│ │D│D│D│ │
│ │A│A│ │B│B│B│ │C│C│ │ │D│D│D│
│ │A│A│ │B│B│B│ │ │C│C│ │D│D│D│
│ │A│A│ │ │B│B│B│ │C│C│ │D│D│D│
│ │ │A│A│ │B│B│B│ │C│C│ │D│D│D│
neat 5 nonoblock 2 3
</syntaxhighlight>
 
=={{header|Java}}==
{{works with|Java|8}}
<syntaxhighlight lang="java">import java.util.*;
import static java.util.Arrays.stream;
import static java.util.stream.Collectors.toList;
 
public class Nonoblock {
 
public static void main(String[] args) {
printBlock("21", 5);
printBlock("", 5);
printBlock("8", 10);
printBlock("2323", 15);
printBlock("23", 5);
}
 
static void printBlock(String data, int len) {
int sumChars = data.chars().map(c -> Character.digit(c, 10)).sum();
String[] a = data.split("");
 
System.out.printf("%nblocks %s, cells %s%n", Arrays.toString(a), len);
if (len - sumChars <= 0) {
System.out.println("No solution");
return;
}
 
List<String> prep = stream(a).filter(x -> !"".equals(x))
.map(x -> repeat(Character.digit(x.charAt(0), 10), "1"))
.collect(toList());
 
for (String r : genSequence(prep, len - sumChars + 1))
System.out.println(r.substring(1));
}
 
// permutation generator, translated from Python via D
static List<String> genSequence(List<String> ones, int numZeros) {
if (ones.isEmpty())
return Arrays.asList(repeat(numZeros, "0"));
 
List<String> result = new ArrayList<>();
for (int x = 1; x < numZeros - ones.size() + 2; x++) {
List<String> skipOne = ones.stream().skip(1).collect(toList());
for (String tail : genSequence(skipOne, numZeros - x))
result.add(repeat(x, "0") + ones.get(0) + tail);
}
return result;
}
 
static String repeat(int n, String s) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < n; i++)
sb.append(s);
return sb.toString();
}
}</syntaxhighlight>
<pre>blocks [2, 1], cells 5
11010
11001
01101
 
blocks [], cells 5
00000
 
blocks [8], cells 10
1111111100
0111111110
0011111111
 
blocks [2, 3, 2, 3], cells 15
110111011011100
110111011001110
110111011000111
110111001101110
110111001100111
110111000110111
110011101101110
110011101100111
110011100110111
110001110110111
011011101101110
011011101100111
011011100110111
011001110110111
001101110110111
 
blocks [2, 3], cells 5
No solution</pre>
 
 
=={{header|JavaScript}}==
<syntaxhighlight lang="javascript">const compose = (...fn) => (...x) => fn.reduce((a, b) => c => a(b(c)))(...x);
const inv = b => !b;
const arrJoin = str => arr => arr.join(str);
const mkArr = (l, f) => Array(l).fill(f);
const sumArr = arr => arr.reduce((a, b) => a + b, 0);
const sumsTo = val => arr => sumArr(arr) === val;
const zipper = arr => (p, c, i) => arr[i] ? [...p, c, arr[i]] : [...p, c];
const zip = (a, b) => a.reduce(zipper(b), []);
const zipArr = arr => a => zip(a, arr);
const hasInner = v => arr => arr.slice(1, -1).indexOf(v) >= 0;
const choose = (even, odd) => n => n % 2 === 0 ? even : odd;
const toBin = f => arr => arr.reduce(
(p, c, i) => [...p, ...mkArr(c, f(i))], []);
 
 
const looper = (arr, max, acc = [[...arr]], idx = 0) => {
if (idx !== arr.length) {
const b = looper([...arr], max, acc, idx + 1)[0];
if (b[idx] !== max) {
b[idx] = b[idx] + 1;
acc.push(looper([...b], max, acc, idx)[0]);
}
}
return [arr, acc];
};
 
const gapPerms = (grpSize, numGaps, minVal = 0) => {
const maxVal = numGaps - grpSize * minVal + minVal;
return maxVal <= 0
? (grpSize === 2 ? [[0]] : [])
: looper(mkArr(grpSize, minVal), maxVal)[1];
}
 
const test = (cells, ...blocks) => {
const grpSize = blocks.length + 1;
const numGaps = cells - sumArr(blocks);
 
// Filter functions
const sumsToTrg = sumsTo(numGaps);
const noInnerZero = compose(inv, hasInner(0));
 
// Output formatting
const combine = zipArr([...blocks]);
const choices = toBin(choose(0, 1));
const output = compose(console.log, arrJoin(''), choices, combine);
 
console.log(`\n${cells} cells. Blocks: ${blocks}`);
gapPerms(grpSize, numGaps)
.filter(noInnerZero)
.filter(sumsToTrg)
.map(output);
};
 
test(5, 2, 1);
test(5);
test(5, 5);
test(5, 1, 1, 1);
test(10, 8);
test(15, 2, 3, 2, 3);
test(10, 4, 3);
test(5, 2, 3);
</syntaxhighlight>
{{out}}
<pre>5 cells. Blocks: 2,1
11010
11001
01101
 
5 cells. Blocks:
00000
 
5 cells. Blocks: 5
11111
 
5 cells. Blocks: 1,1,1
10101
 
10 cells. Blocks: 8
1111111100
0111111110
0011111111
 
15 cells. Blocks: 2,3,2,3
110111011011100
110111011001110
110111011000111
110111001101110
110111001100111
110111000110111
110011101101110
110011101100111
110011100110111
110001110110111
011011101101110
011011101100111
011011100110111
011001110110111
001101110110111
 
10 cells. Blocks: 4,3
1111011100
1111001110
1111000111
0111101110
0111100111
0011110111
 
5 cells. Blocks: 2,3
 
 
</pre>
 
=={{header|Julia}}==
<syntaxhighlight lang="julia">minsized(arr) = join(map(x->"#"^x, arr), ".")
minlen(arr) = sum(arr) + length(arr) - 1
function sequences(blockseq, numblanks)
if isempty(blockseq)
return ["." ^ numblanks]
elseif minlen(blockseq) == numblanks
return minsized(blockseq)
else
result = Vector{String}()
allbuthead = blockseq[2:end]
for leftspace in 0:(numblanks - minlen(blockseq))
header = "." ^ leftspace * "#" ^ blockseq[1] * "."
rightspace = numblanks - length(header)
if isempty(allbuthead)
push!(result, rightspace <= 0 ? header[1:numblanks] : header * "." ^ rightspace)
elseif minlen(allbuthead) == rightspace
push!(result, header * minsized(allbuthead))
else
map(x -> push!(result, header * x), sequences(allbuthead, rightspace))
end
end
end
result
end
 
function nonoblocks(bvec, len)
println("With blocks $bvec and $len cells:")
len < minlen(bvec) ? println("No solution") : for seq in sequences(bvec, len) println(seq) end
end
 
nonoblocks([2, 1], 5)
nonoblocks(Vector{Int}([]), 5)
nonoblocks([8], 10)
nonoblocks([2, 3, 2, 3], 15)
nonoblocks([2, 3], 5)
</syntaxhighlight> {{output}} <pre>
With blocks [2, 1] and 5 cells:
##.#.
##..#
.##.#
With blocks Int64[] and 5 cells:
.....
With blocks [8] and 10 cells:
########..
.########.
..########
With blocks [2, 3, 2, 3] and 15 cells:
##.###.##.###..
##.###.##..###.
##.###.##...###
##.###..##.###.
##.###..##..###
##.###...##.###
##..###.##.###.
##..###.##..###
##..###..##.###
##...###.##.###
.##.###.##.###.
.##.###.##..###
.##.###..##.###
.##..###.##.###
..##.###.##.###
With blocks [2, 3] and 5 cells:
No solution
</pre>
 
=={{header|Kotlin}}==
{{trans|Java}}
<syntaxhighlight lang="scala">// version 1.2.0
 
fun printBlock(data: String, len: Int) {
val a = data.toCharArray()
val sumChars = a.map { it.toInt() - 48 }.sum()
println("\nblocks ${a.asList()}, cells $len")
if (len - sumChars <= 0) {
println("No solution")
return
}
val prep = a.map { "1".repeat(it.toInt() - 48) }
for (r in genSequence(prep, len - sumChars + 1)) println(r.substring(1))
}
 
fun genSequence(ones: List<String>, numZeros: Int): List<String> {
if (ones.isEmpty()) return listOf("0".repeat(numZeros))
val result = mutableListOf<String>()
for (x in 1 until numZeros - ones.size + 2) {
val skipOne = ones.drop(1)
for (tail in genSequence(skipOne, numZeros - x)) {
result.add("0".repeat(x) + ones[0] + tail)
}
}
return result
}
 
fun main(args: Array<String>) {
printBlock("21", 5)
printBlock("", 5)
printBlock("8", 10)
printBlock("2323", 15)
printBlock("23", 5)
}</syntaxhighlight>
 
{{out}}
<pre>
blocks [2, 1], cells 5
11010
11001
01101
 
blocks [], cells 5
00000
 
blocks [8], cells 10
1111111100
0111111110
0011111111
 
blocks [2, 3, 2, 3], cells 15
110111011011100
110111011001110
110111011000111
110111001101110
110111001100111
110111000110111
110011101101110
110011101100111
110011100110111
110001110110111
011011101101110
011011101100111
011011100110111
011001110110111
001101110110111
 
blocks [2, 3], cells 5
No solution
</pre>
 
=={{header|Lua}}==
<syntaxhighlight lang="lua">local examples = {
{5, {2, 1}},
{5, {}},
{10, {8}},
{15, {2, 3, 2, 3}},
{5, {2, 3}},
}
 
function deep (blocks, iBlock, freedom, str)
if iBlock == #blocks then -- last
for takenFreedom = 0, freedom do
print (str..string.rep("0", takenFreedom) .. string.rep("1", blocks[iBlock]) .. string.rep("0", freedom - takenFreedom))
total = total + 1
end
else
for takenFreedom = 0, freedom do
local str2 = str..string.rep("0", takenFreedom) .. string.rep("1", blocks[iBlock]) .. "0"
deep (blocks, iBlock+1, freedom-takenFreedom, str2)
end
end
end
 
function main (cells, blocks) -- number, list
local str = " "
print (cells .. ' cells and {' .. table.concat(blocks, ', ') .. '} blocks')
local freedom = cells - #blocks + 1 -- freedom
for iBlock = 1, #blocks do
freedom = freedom - blocks[iBlock]
end
if #blocks == 0 then
print ('no blocks')
print (str..string.rep("0", cells))
total = 1
elseif freedom < 0 then
print ('no solutions')
else
print ('Possibilities:')
deep (blocks, 1, freedom, str)
end
end
 
for i, example in ipairs (examples) do
print ("\n--")
total = 0
main (example[1], example[2])
print ('A total of ' .. total .. ' possible configurations.')
end</syntaxhighlight>
 
{{out}}
<pre>
--
5 cells and {2, 1} blocks
Possibilities:
11010
11001
01101
A total of 3 possible configurations.
 
--
5 cells and {} blocks
no blocks
00000
A total of 1 possible configurations.
 
--
10 cells and {8} blocks
Possibilities:
1111111100
0111111110
0011111111
A total of 3 possible configurations.
 
--
15 cells and {2, 3, 2, 3} blocks
Possibilities:
110111011011100
110111011001110
110111011000111
110111001101110
110111001100111
110111000110111
110011101101110
110011101100111
110011100110111
110001110110111
011011101101110
011011101100111
011011100110111
011001110110111
001101110110111
A total of 15 possible configurations.
 
--
5 cells and {2, 3} blocks
no solutions
A total of 0 possible configurations.
</pre>
 
=={{header|M2000 Interpreter}}==
===Recursive===
<syntaxhighlight lang="m2000 interpreter">
Module NonoBlock {
Form 80,40
Flush
Print "Nonoblock"
Data 5, (2, 1)
Data 5, (,)
Data 10, (8,)
Data 15, (2,3,2,3)
Data 5, (2,3)
Def BLen(a$)=(Len(a$)-1)/2
Function UseLetter(arr) {
Dim Base 0, Res$(Len(arr))
Link Res$() to Res()
Def Ord$(a$)=ChrCode$(Chrcode(a$)+1)
L$="A"
i=each(arr)
While i {
Res$(i^)=String$("|"+L$, Array(i))+"|"
L$=Ord$(L$)
}
=Res()
}
Count=0
For i=1 to 5
Read Cells, Blocks
Blocks=UseLetter(Blocks)
Print str$(i,"")+".", "Cells=";Cells, "", iF(len(Blocks)=0->("Empty",), Blocks)
PrintRow( "|", Cells, Blocks, &Count)
CheckCount()
Next I
Sub CheckCount()
If count=0 Then Print " Impossible"
count=0
End Sub
Sub PrintRow(Lpart$, Cells, Blocks, &Comp)
If len(Blocks)=0 Then Comp++ :Print Format$("{0::-3} {1}", Comp, lpart$+String$("_|", Cells)): Exit Sub
If Cells<=0 Then Exit Sub
Local TotalBlocksLength=0, Sep_Spaces=-1
Local Block=Each(Blocks), block$
While Block {
Block$=Array$(Block)
TotalBlocksLength+=Blen(Block$)
Sep_Spaces++
}
Local MaxLengthNeed=TotalBlocksLength+Sep_Spaces
If MaxLengthNeed>Cells Then Exit Sub
block$=Array$(Car(Blocks))
local temp=Blen(block$)
block$=Mid$(Block$, 2)
If Len(Blocks)>1 Then block$+="_|" :temp++
PrintRow(Lpart$+block$, Cells-temp, Cdr(Blocks), &Comp)
PrintRow(lpart$+String$("_|", 1), Cells-1,Blocks, &Comp)
End Sub
}
NonoBlock
</syntaxhighlight>
 
{{out}}
<pre style="height:30ex;overflow:scroll">
Nonoblock
1. Cells=5 |A|A| |B|
1 |A|A|_|B|_|
2 |A|A|_|_|B|
3 |_|A|A|_|B|
2. Cells=5 Empty
1 |_|_|_|_|_|
3. Cells=10 |A|A|A|A|A|A|A|A|
1 |A|A|A|A|A|A|A|A|_|_|
2 |_|A|A|A|A|A|A|A|A|_|
3 |_|_|A|A|A|A|A|A|A|A|
4. Cells=15 |A|A| |B|B|B| |C|C| |D|D|D|
1 |A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
2 |A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
3 |A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
4 |A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
5 |A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
6 |A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
7 |A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
8 |A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
9 |A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
10 |A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
11 |_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
12 |_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
13 |_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
14 |_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
15 |_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
5. Cells=5 |A|A| |B|B|B|
Impossible
 
</pre >
===Non Recursive===
<syntaxhighlight lang="m2000 interpreter">
Module Nonoblock (n, m) {
Print "Cells:",n," Blocks:",m
Dim n(1 to n), m(1 to m), sp(1 to m*2), sk(1 to m*2), part(1 to m)
queue=0
If m>0 Then {
Print "Block Size:",
For i=1 to m {
Read m(i)
Print m(i),
}
Print
part(m)=m(m)
If m>1 Then {
For i=m-1 to 1 {
part(i)=m(i)+part(i+1)+1
}
}
}
If part(1)>n Then {
Print "Impossible"
} Else {
p1=0
l=0
Counter=0
While p1<=n-part(1) {
k=0
p=p1+1
For i=1 to n {
n(i)=0
}
flag=True
Repeat {
While k<m {
k++
l=0
While l<m(k) and p<=n {
l++
n(p)=1
p++
}
If p<n Then {
n(p)=0
p++
If k<m Then {
If p+part(k+1)<n+1 Then {
queue++
sp(queue)=p
sk(queue)=k
}
}
}
}
flag=True
If l=m(k) Then {
counter++
Print Str$(counter,"0000 ");
For i=1 to n {
Print n(i);" ";
}
Print
If queue>0 Then {
p=sp(queue)
k=sk(queue)
queue--
For i=p to n {
n(i)=0
}
p++
If k<m Then {
If p+part(k+1)<n+1 Then {
queue++
sp(queue)=p
' sk(queue)=k
}
}
flag=False
}
}
} Until flag
p1++
If k=0 Then Exit
}
}
}
 
Nonoblock 5,2,2,1
Nonoblock 5,0
Nonoblock 10,1,8
Nonoblock 15,4,2,3,2,3
Nonoblock 5,2,3,2
</syntaxhighlight>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang="mathematica">ClearAll[SpacesDistributeOverN, Possibilities]
SpacesDistributeOverN[s_, p_] :=
Flatten[
Permutations /@ (Join[#, ConstantArray[0, p - Length[#]]] & /@
IntegerPartitions[s, p]), 1]
Possibilities[hint_, len_] :=
Module[{p = hint, l = len, b = Length[hint], Spaces, out},
Spaces = # + (Prepend[Append[ConstantArray[1, b - 1], 0],
0]) & /@ (SpacesDistributeOverN[l - Total@p - (b - 1), b + 1]);
out = Flatten /@ (
Riffle[#, Map[Table[1, {#}] &, p, {1}]] & /@
Map[Table[0, {#}] &, Spaces, {2}]);
StringJoin @@@ (out /. {0 -> ".", 1 -> "#"})
]
Possibilities[{}, len_] := Module[{},
{StringJoin[ConstantArray[".", len]]}
]
Possibilities[{2, 1}, 5]
Possibilities[{}, 5]
Possibilities[{8}, 10]
Possibilities[{2, 3, 2, 3}, 15]
Possibilities[{2, 3}, 5]</syntaxhighlight>
{{out}}
<pre>{".##.#", "##..#", "##.#."}
{"....."}
{"..########", "########..", ".########."}
{"..##.###.##.###", "##...###.##.###", "##.###...##.###", "##.###.##...###", "##.###.##.###..", ".##..###.##.###", ".##.###..##.###", ".##.###.##..###", ".##.###.##.###.", "##..###..##.###", "##..###.##..###", "##..###.##.###.", "##.###..##..###", "##.###..##.###.", "##.###.##..###."}
{}</pre>
 
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">import math, sequtils, strformat, strutils
 
 
proc genSequence(ones: seq[string]; numZeroes: Natural): seq[string] =
if ones.len == 0: return @[repeat('0', numZeroes)]
for x in 1..(numZeroes - ones.len + 1):
let skipOne = ones[1..^1]
for tail in genSequence(skipOne, numZeroes - x):
result.add repeat('0', x) & ones[0] & tail
 
 
proc printBlock(data: string; length: Positive) =
 
let a = mapIt(data, ord(it) - ord('0'))
let sumBytes = sum(a)
 
echo &"\nblocks {($a)[1..^1]} cells {length}"
if length - sumBytes <= 0:
echo "No solution"
return
 
var prep: seq[string]
for b in a: prep.add repeat('1', b)
 
for r in genSequence(prep, length - sumBytes + 1):
echo r[1..^1]
 
 
when isMainModule:
printBlock("21", 5)
printBlock("", 5)
printBlock("8", 10)
printBlock("2323", 15)
printBlock("23", 5)</syntaxhighlight>
 
{{out}}
<pre>blocks [2, 1] cells 5
11010
11001
01101
 
blocks [] cells 5
00000
 
blocks [8] cells 10
1111111100
0111111110
0011111111
 
blocks [2, 3, 2, 3] cells 15
110111011011100
110111011001110
110111011000111
110111001101110
110111001100111
110111000110111
110011101101110
110011101100111
110011100110111
110001110110111
011011101101110
011011101100111
011011100110111
011001110110111
001101110110111
 
blocks [2, 3] cells 5
No solution</pre>
 
=={{header|Pascal}}==
A console application in Free Pascal, created with the Lazarus IDE.
 
With 15 cells and [2,3,2,3] blocks, it's a question of how to distribute 5 gap characters among 5 gaps (including the 2 gaps at the ends). To allow for the requirement that the 3 inner gaps must be strictly positive, we can reduce the size of each inner gap by 1, provided we remember to restore the deleted gap character when printing the result. Then 2 gap characters need to be distributed among 5 non-negative gaps. In general, for integers n > 0 and s, the task amounts to finding all arrays of n non-negative integers that sum to s. An iterative method is shown below.
<syntaxhighlight lang="pascal">
program Nonoblock;
uses SysUtils;
 
// Working through solutions to the problem:
// Fill an array z[] with non-negative integers
// whose sum is the passed-in integer s.
function GetFirstSolution( var z : array of integer;
s : integer) : boolean;
var
j : integer;
begin
result := (s >= 0) and (High(z) >= 0); // failed if s < 0 or array is empty
if result then begin // else initialize to solution 0, ..., 0, s
j := High(z); z[j] := s;
while (j > 0) do begin
dec(j); z[j] := 0;
end;
end;
end;
 
// Next solution: return true for success, false if no more solutions.
// Solutions are generated in lexicographic order.
function GetNextSolution( var z : array of integer) : boolean;
var
h, j : integer;
begin
h := High(z);
j := h; // find highest index j such that z[j] > 0.
while (j > 0) and (z[j] = 0) do dec(j);
result := (j > 0); // if index is 0, or there is no such index, failed
if result then begin // else update caller's array to give next solution
inc(z[j - 1]);
z[h] := z[j] - 1;
if (j < h) then z[j] := 0;
end;
end;
 
// Procedure to print solutions to nonoblock task on RosettaCode
procedure PrintSolutions( nrCells : integer;
blockSizes : array of integer);
const // cosmetic
MARGIN = 4;
GAP_CHAR = '.';
BLOCK_CHAR = '#';
var
sb : SysUtils.TStringBuilder;
nrBlocks, blockSum, gapSum : integer;
gapSizes : array of integer;
i, nrSolutions : integer;
begin
nrBlocks := Length( blockSizes);
 
// Print a title, showing the number of cells and the block sizes
sb := SysUtils.TStringBuilder.Create();
sb.AppendFormat('%d cells; blocks [', [nrCells]);
for i := 0 to nrBlocks - 1 do begin
if (i > 0) then sb.Append(',');
sb.Append( blockSizes[i]);
end;
sb.Append(']');
WriteLn( sb.ToString());
 
blockSum := 0; // total of block sizes
for i := 0 to nrBlocks - 1 do inc( blockSum, blockSizes[i]);
 
gapSum := nrCells - blockSum;
// Except in the trivial case of no blocks,
// we reduce the size of each inner gap by 1.
if nrBlocks > 0 then dec( gapSum, nrBlocks - 1);
 
// Work through all solutions and print them nicely.
nrSolutions := 0;
SetLength( gapSizes, nrBlocks + 1); // include the gap at each end
if GetFirstSolution( gapSizes, gapSum) then begin
repeat
inc( nrSolutions);
sb.Clear();
sb.Append( ' ', MARGIN);
for i := 0 to nrBlocks - 1 do begin
sb.Append( GAP_CHAR, gapSizes[i]);
// We reduced the inner gaps by 1; now we restore the deleted char.
if (i > 0) then sb.Append( GAP_CHAR);
sb.Append( BLOCK_CHAR, blockSizes[i]);
end;
sb.Append( GAP_CHAR, gapSizes[nrBlocks]);
WriteLn( sb.ToString());
until not GetNextSolution( gapSizes);
end;
sb.Free();
WriteLn( SysUtils.Format( 'Number of solutions = %d', [nrSolutions]));
WriteLn('');
end;
 
// Main program
begin
PrintSolutions( 5, [2,1]);
PrintSolutions( 5, []);
PrintSolutions( 10, [8]);
PrintSolutions( 15, [2,3,2,3]);
PrintSolutions( 5, [2,3]);
end.
</syntaxhighlight>
{{out}}
<pre>
5 cells; blocks [2,1]
##.#.
##..#
.##.#
Number of solutions = 3
 
5 cells; blocks []
.....
Number of solutions = 1
 
10 cells; blocks [8]
########..
.########.
..########
Number of solutions = 3
 
15 cells; blocks [2,3,2,3]
##.###.##.###..
##.###.##..###.
##.###.##...###
##.###..##.###.
##.###..##..###
##.###...##.###
##..###.##.###.
##..###.##..###
##..###..##.###
##...###.##.###
.##.###.##.###.
.##.###.##..###
.##.###..##.###
.##..###.##.###
..##.###.##.###
Number of solutions = 15
 
5 cells; blocks [2,3]
Number of solutions = 0
</pre>
 
=={{header|Perl}}==
<syntaxhighlight lang="perl">use strict;
use warnings;
 
while( <DATA> )
{
print "\n$_", tr/\n/=/cr;
my ($cells, @blocks) = split;
my $letter = 'A';
$_ = join '.', map { $letter++ x $_ } @blocks;
$cells < length and print("no solution\n"), next;
$_ .= '.' x ($cells - length) . "\n";
1 while print, s/^(\.*)\b(.*?)\b(\w+)\.\B/$2$1.$3/;
}
 
__DATA__
5 2 1
5
10 8
15 2 3 2 3
5 2 3</syntaxhighlight>
{{out}}
<pre>
5 2 1
=====
AA.B.
AA..B
.AA.B
 
5
=
.....
 
10 8
====
AAAAAAAA..
.AAAAAAAA.
..AAAAAAAA
 
15 2 3 2 3
==========
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
 
5 2 3
=====
no solution
 
</pre>
 
=={{header|Phix}}==
<!--<syntaxhighlight lang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">nobr</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">neat</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ni</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">b</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span>
<span style="color: #000000;">blocks</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">[</span><span style="color: #000000;">2</span><span style="color: #0000FF;">..$]</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">(</span><span style="color: #7060A8;">sum</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)+</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span>
<span style="color: #000000;">e</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">)-</span><span style="color: #000000;">l</span><span style="color: #0000FF;">-</span><span style="color: #000000;">b</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">ni</span> <span style="color: #008080;">to</span> <span style="color: #000000;">e</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">j</span><span style="color: #0000FF;">=</span><span style="color: #000000;">i</span> <span style="color: #008080;">to</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">-</span><span style="color: #000000;">2</span> <span style="color: #008080;">by</span> <span style="color: #000000;">2</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">neat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">ch</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nobr</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">b</span><span style="color: #0000FF;">*</span><span style="color: #000000;">2</span><span style="color: #0000FF;">+</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ch</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">neat</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">' '</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">nonoblock</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">len</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">sequence</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">neat</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">"|"</span><span style="color: #0000FF;">&</span><span style="color: #7060A8;">join</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">' '</span><span style="color: #0000FF;">,</span><span style="color: #000000;">len</span><span style="color: #0000FF;">),</span><span style="color: #008000;">'|'</span><span style="color: #0000FF;">)&</span><span style="color: #008000;">"|"</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">nobr</span><span style="color: #0000FF;">({},</span><span style="color: #000000;">neat</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #008000;">'A'</span><span style="color: #0000FF;">,</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">tests</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,{}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">8</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">15</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">4</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">10</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">3</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">}},</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">5</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">3</span><span style="color: #0000FF;">}}}</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">len</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">blocks</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">res</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">tests</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #0000FF;">{</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">}</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">tests</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">ti</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">sprintf</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"%d cells with blocks %s"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">sprint</span><span style="color: #0000FF;">(</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)})</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%s\n%s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">repeat</span><span style="color: #0000FF;">(</span><span style="color: #008000;">'='</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">ti</span><span style="color: #0000FF;">))})</span>
<span style="color: #000000;">res</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">nonoblock</span><span style="color: #0000FF;">(</span><span style="color: #000000;">len</span><span style="color: #0000FF;">,</span><span style="color: #000000;">blocks</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"No solutions.\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">else</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">ri</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"%3d: %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">[</span><span style="color: #000000;">ri</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<!--</syntaxhighlight>-->
{{out}}
<pre>
5 cells with blocks {2,1}
=========================
1: |A|A| |B| |
2: |A|A| | |B|
3: | |A|A| |B|
 
5 cells with blocks {}
======================
1: | | | | | |
 
10 cells with blocks {8}
========================
1: |A|A|A|A|A|A|A|A| | |
2: | |A|A|A|A|A|A|A|A| |
3: | | |A|A|A|A|A|A|A|A|
 
15 cells with blocks {2,3,2,3}
==============================
1: |A|A| |B|B|B| |C|C| |D|D|D| | |
2: |A|A| |B|B|B| |C|C| | |D|D|D| |
3: |A|A| |B|B|B| |C|C| | | |D|D|D|
4: |A|A| |B|B|B| | |C|C| |D|D|D| |
5: |A|A| |B|B|B| | |C|C| | |D|D|D|
6: |A|A| |B|B|B| | | |C|C| |D|D|D|
7: |A|A| | |B|B|B| |C|C| |D|D|D| |
8: |A|A| | |B|B|B| |C|C| | |D|D|D|
9: |A|A| | |B|B|B| | |C|C| |D|D|D|
10: |A|A| | | |B|B|B| |C|C| |D|D|D|
11: | |A|A| |B|B|B| |C|C| |D|D|D| |
12: | |A|A| |B|B|B| |C|C| | |D|D|D|
13: | |A|A| |B|B|B| | |C|C| |D|D|D|
14: | |A|A| | |B|B|B| |C|C| |D|D|D|
15: | | |A|A| |B|B|B| |C|C| |D|D|D|
 
10 cells with blocks {4,3}
==========================
1: |A|A|A|A| |B|B|B| | |
2: |A|A|A|A| | |B|B|B| |
3: |A|A|A|A| | | |B|B|B|
4: | |A|A|A|A| |B|B|B| |
5: | |A|A|A|A| | |B|B|B|
6: | | |A|A|A|A| |B|B|B|
 
5 cells with blocks {2,1}
=========================
1: |A|A| |B| |
2: |A|A| | |B|
3: | |A|A| |B|
 
10 cells with blocks {3,1}
==========================
1: |A|A|A| |B| | | | | |
2: |A|A|A| | |B| | | | |
3: |A|A|A| | | |B| | | |
4: |A|A|A| | | | |B| | |
5: |A|A|A| | | | | |B| |
6: |A|A|A| | | | | | |B|
7: | |A|A|A| |B| | | | |
8: | |A|A|A| | |B| | | |
9: | |A|A|A| | | |B| | |
10: | |A|A|A| | | | |B| |
11: | |A|A|A| | | | | |B|
12: | | |A|A|A| |B| | | |
13: | | |A|A|A| | |B| | |
14: | | |A|A|A| | | |B| |
15: | | |A|A|A| | | | |B|
16: | | | |A|A|A| |B| | |
17: | | | |A|A|A| | |B| |
18: | | | |A|A|A| | | |B|
19: | | | | |A|A|A| |B| |
20: | | | | |A|A|A| | |B|
21: | | | | | |A|A|A| |B|
 
5 cells with blocks {2,3}
=========================
No solutions.
</pre>
 
=={{header|Python}}==
<langsyntaxhighlight lang="python">def nonoblocks(blocks, cells):
if not blocks or blocks[0] == 0:
yield [(0, 0)]
Line 295 ⟶ 2,416:
for i, vector in enumerate(nonoblocks(blocks, cells)):
print(' ', pblock(vector, cells))
print(' A total of %i Possible configurations.' % (i+1))</langsyntaxhighlight>
 
{{out}}
Line 349 ⟶ 2,470:
'Those blocks will not fit in those cells'
AssertionError: Those blocks will not fit in those cells</pre>
 
=={{header|Racket}}==
 
This implementation does not "error" on the impossible case.
 
Knowing that there are no solutions (empty result list) is good enough.
 
Also, the blocks are not identified. I suppose they could be easily enough, but in the nonogram task, these patterns are converted to bit-fields shortly after the nonoblock generation, and bits have no names (sad, but true).
 
<syntaxhighlight lang="racket">#lang racket
(require racket/trace)
 
(define add1-to-car (match-lambda [(cons (app add1 p1) t) (cons p1 t)]))
 
;; inputs:
;; cells -- available cells
;; blocks -- list of block widths
;; output:
;; gap-block+gaps
;; where gap-block+gaps is:
;; (list gap) -- a single gap
;; (list gap block-width gap-block+gaps) -- padding to left, a block, right hand side
(define (nonoblock cells blocks)
(match* ((- cells (apply + (length blocks) -1 blocks)) #| padding available on both sides |# blocks)
[(_ (list)) (list (list cells))] ; generates an empty list of padding
[((? negative?) _) null] ; impossible to satisfy
[((and avp
;; use add1 with in-range because we actually want from 0 to available-padding
;; without add1, in-range iterates from 0 to (available-padding - 1)
(app add1 avp+1))
(list block))
(for/list ((l-pad (in-range 0 avp+1)))
(define r-pad (- avp l-pad)) ; what remains goes to right
(list l-pad block r-pad))]
[((app add1 avp+1) (list block more-blocks ...))
(for*/list ((l-pad (in-range 0 avp+1))
(cells-- (in-value (- cells block l-pad 1)))
(r-blocks (in-value (nonoblock cells-- more-blocks)))
(r-block (in-list r-blocks)))
(list* l-pad block (add1-to-car r-block)))])) ; put a single space pad on left of r-block
 
(define (neat rslt)
(define dots (curryr make-string #\.))
(define Xes (curryr make-string #\X))
(define inr
(match-lambda
[(list 0 (app Xes b) t ...)
(string-append b (inr t))]
[(list (app dots p) (app Xes b) t ...)
(string-append p b (inr t))]
[(list (app dots p)) p]))
(define (neat-row r)
(string-append "|" (inr r) "|"))
(string-join (map neat-row rslt) "\n"))
 
(define (tst c b)
(define rslt (nonoblock c b))
(define rslt-l (length rslt))
(printf "~a cells, ~a blocks => ~a~%~a~%" c b
(match rslt-l
[0 "impossible"]
[1 "1 solution"]
[(app (curry format "~a solutions") r) r])
(neat rslt)))
 
(module+ test
(tst 5 '[2 1])
(tst 5 '[])
(tst 10 '[8])
(tst 15 '[2 3 2 3])
(tst 5 '[2 3]))</syntaxhighlight>
 
{{out}}
<pre>5 cells, (2 1) blocks => 3 solutions
|XX.X.|
|XX..X|
|.XX.X|
5 cells, () blocks => 1 solution
|.....|
10 cells, (8) blocks => 3 solutions
|XXXXXXXX..|
|.XXXXXXXX.|
|..XXXXXXXX|
15 cells, (2 3 2 3) blocks => 15 solutions
|XX.XXX.XX.XXX..|
|XX.XXX.XX..XXX.|
|XX.XXX.XX...XXX|
|XX.XXX..XX.XXX.|
|XX.XXX..XX..XXX|
|XX.XXX...XX.XXX|
|XX..XXX.XX.XXX.|
|XX..XXX.XX..XXX|
|XX..XXX..XX.XXX|
|XX...XXX.XX.XXX|
|.XX.XXX.XX.XXX.|
|.XX.XXX.XX..XXX|
|.XX.XXX..XX.XXX|
|.XX..XXX.XX.XXX|
|..XX.XXX.XX.XXX|
5 cells, (2 3) blocks => impossible
</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
{{trans|Perl}}
<syntaxhighlight lang="raku" line>for (5, [2,1]), (5, []), (10, [8]), (5, [2,3]), (15, [2,3,2,3]) -> ($cells, @blocks) {
say $cells, ' cells with blocks: ', @blocks ?? join ', ', @blocks !! '∅';
my $letter = 'A';
my $row = join '.', map { $letter++ x $_ }, @blocks;
say "no solution\n" and next if $cells < $row.chars;
say $row ~= '.' x $cells - $row.chars;
say $row while $row ~~ s/^^ (\.*) <|w> (.*?) <|w> (\w+) \.<!|w> /$1$0.$2/;
say '';
}</syntaxhighlight>
{{out}}
<pre>5 cells with blocks: 2, 1
AA.B.
AA..B
.AA.B
 
5 cells with blocks: ∅
.....
 
10 cells with blocks: 8
AAAAAAAA..
.AAAAAAAA.
..AAAAAAAA
 
5 cells with blocks: 2, 3
no solution
 
15 cells with blocks: 2, 3, 2, 3
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</pre>
 
=={{header|REXX}}==
<syntaxhighlight lang="rexx">/*REXX program enumerates all possible configurations (or an error) for nonogram puzzles*/
$.=; $.1= 5 2 1
$.2= 5
$.3= 10 8
$.4= 15 2 3 2 3
$.5= 5 2 3
do i=1 while $.i\==''
parse var $.i N blocks /*obtain N and blocks from array. */
N= strip(N); blocks= space(blocks) /*assign stripped N and blocks. */
call nono /*incoke NONO subroutine for heavy work*/
end /*i*/
exit /*stick a fork in it, we're all done. */
/*──────────────────────────────────────────────────────────────────────────────────────*/
nono: say copies('=', 70) /*display seperator for title.*/
say 'For ' N " cells and blocks of: " blocks /*display the title for output*/
z= /*assign starter value for Z. */
do w=1 for words(blocks) /*process each of the blocks. */
z= z copies('#', word(blocks,w) ) /*build a string for 1st value*/
end /*w*/ /*Z now has a leading blank. */
#= 1 /*number of positions (so far)*/
z= translate( strip(z), ., ' '); L= length(z) /*change blanks to periods. */
if L>N then do; say '***error*** invalid blocks for number of cells.'; return
end
@.0=; @.1= z; !.=0 /*assign default and the first position*/
z= pad(z) /*fill─out (pad) the value with periods*/
 
do prepend=1 while words(blocks)\==0 /*process all the positions (leading .)*/
new= . || @.prepend /*create positions with leading dots. */
if length(new)>N then leave /*Length is too long? Then stop adding*/
call add /*add position that has a leading dot. */
end /*prepend*/ /* [↑] prepend positions with dots. */
 
do k=1 for N /*process each of the positions so far.*/
do c=1 for N /* " " " " position blocks. */
if @.c=='' then iterate /*if string is null, skip the string. */
p= loc(@.c, k) /*find location of block in position. */
if p==0 | p>=N then iterate /*Location zero or out─of─range? Skip.*/
new= strip( insert(., @.c, p),'T',.) /*insert a dot and strip trailing dots.*/
if strip(new,'T',.)=@.c then iterate /*Is it the same value? Then skip it. */
if length(new)<=N then call add /*Is length OK? Then add position. */
end /*k*/
end /*c*/
say
say '─position─' center("value", max(7, length(z) ), '─') /*show hdr for output.*/
 
do m=1 for #
say center(m, 10) pad(@.m) /*display the index count and position.*/
end /*m*/
return
/*──────────────────────────────────────────────────────────────────────────────────────*/
loc: _=0; do arg(2); _=pos('#.',pad(arg(1)),_+1); if _==0 then return 0; end; return _+1
add: if !.new==1 then return; #= # + 1; @.#= new; !.new=1; return
pad: return left( arg(1), N, .)</syntaxhighlight>
{{out|output|text=&nbsp; when using the default inputs:}}
<pre>
======================================================================
For 5 cells and blocks of: 2 1
 
─position─ ─value─
1 ##.#.
2 .##.#
3 ##..#
======================================================================
For 5 cells and blocks of:
 
─position─ ─value─
1 .....
======================================================================
For 10 cells and blocks of: 8
 
─position─ ──value───
1 ########..
2 .########.
3 ..########
======================================================================
For 15 cells and blocks of: 2 3 2 3
 
─position─ ─────value─────
1 ##.###.##.###..
2 .##.###.##.###.
3 ..##.###.##.###
4 ##..###.##.###.
5 .##..###.##.###
6 ##...###.##.###
7 ##.###..##.###.
8 .##.###..##.###
9 ##..###..##.###
10 ##.###...##.###
11 ##.###.##..###.
12 .##.###.##..###
13 ##..###.##..###
14 ##.###..##..###
15 ##.###.##...###
======================================================================
For 5 cells and blocks of: 2 3
***error*** invalid blocks for number of cells.
</pre>
 
=={{header|Ruby}}==
'''Simple version:'''
<syntaxhighlight lang="ruby">def nonoblocks(cell, blocks)
raise 'Those blocks will not fit in those cells' if cell < blocks.inject(0,:+) + blocks.size - 1
nblock(cell, blocks, '', [])
end
 
def nblock(cell, blocks, position, result)
if cell <= 0
result << position[0..cell-1]
elsif blocks.empty? or blocks[0].zero?
result << position + '.' * cell
else
rest = cell - blocks.inject(:+) - blocks.size + 2
bl, *brest = blocks
rest.times.inject(result) do |res, i|
nblock(cell-i-bl-1, brest, position + '.'*i + '#'*bl + '.', res)
end
end
end
 
conf = [[ 5, [2, 1]],
[ 5, []],
[10, [8]],
[15, [2, 3, 2, 3]],
[ 5, [2, 3]], ]
conf.each do |cell, blocks|
begin
puts "#{cell} cells and #{blocks} blocks"
result = nonoblocks(cell, blocks)
puts result, result.size, ""
rescue => e
p e
end
end</syntaxhighlight>
 
{{out}}
<pre>
5 cells and [2, 1] blocks
##.#.
##..#
.##.#
3
 
5 cells and [] blocks
.....
1
 
10 cells and [8] blocks
########..
.########.
..########
3
 
15 cells and [2, 3, 2, 3] blocks
##.###.##.###..
##.###.##..###.
##.###.##...###
##.###..##.###.
##.###..##..###
##.###...##.###
##..###.##.###.
##..###.##..###
##..###..##.###
##...###.##.###
.##.###.##.###.
.##.###.##..###
.##.###..##.###
.##..###.##.###
..##.###.##.###
15
 
5 cells and [2, 3] blocks
#<RuntimeError: Those blocks will not fit in those cells>
</pre>
 
===Class version===
The output form consulted the one of the python.
<syntaxhighlight lang="ruby">class NonoBlock
def initialize(cell, blocks)
raise 'Those blocks will not fit in those cells' if cell < blocks.inject(0,:+) + blocks.size - 1
@result = []
nonoblocks(cell, blocks, '')
end
def result(correct=true)
correct ? @result.map(&:nonocell) : @result
end
private
def nonoblocks(cell, blocks, position)
if cell <= 0
@result << position[0..cell-1]
elsif blocks.empty? or blocks[0].zero?
@result << position + '.' * cell
else
rest = cell - blocks.inject(0,:+) - blocks.size + 2
bl, *brest = blocks
rest.times do |i|
nonoblocks(cell-i-bl-1, brest, position + '.'*i + '#'*bl + '.')
end
end
end
end
 
class String
def nonocell # "##.###..##" -> "|A|A|_|B|B|B|_|_|C|C|"
chr = ('A'..'Z').each
s = tr('.','_').gsub(/#+/){|sharp| chr.next * sharp.size}
"|#{s.chars.join('|')}|"
end
end
 
if __FILE__ == $0
conf = [[ 5, [2, 1]],
[ 5, []],
[10, [8]],
[15, [2, 3, 2, 3]],
[ 5, [2, 3]] ]
conf.each do |cell, blocks|
begin
puts "Configuration:",
"#{('.'*cell).nonocell} # #{cell} cells and #{blocks} blocks",
"Possibilities:"
result = NonoBlock.new(cell, blocks).result
puts result,
"A total of #{result.size} Possible configurations.", ""
rescue => e
p e
end
end
end</syntaxhighlight>
 
{{out}}
<pre style="height: 64ex; overflow: scroll">
Configuration:
|_|_|_|_|_| # 5 cells and [2, 1] blocks
Possibilities:
|A|A|_|B|_|
|A|A|_|_|B|
|_|A|A|_|B|
A total of 3 Possible configurations.
 
Configuration:
|_|_|_|_|_| # 5 cells and [] blocks
Possibilities:
|_|_|_|_|_|
A total of 1 Possible configurations.
 
Configuration:
|_|_|_|_|_|_|_|_|_|_| # 10 cells and [8] blocks
Possibilities:
|A|A|A|A|A|A|A|A|_|_|
|_|A|A|A|A|A|A|A|A|_|
|_|_|A|A|A|A|A|A|A|A|
A total of 3 Possible configurations.
 
Configuration:
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| # 15 cells and [2, 3, 2, 3] blocks
Possibilities:
|A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
|A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
|A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
|A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
|A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
|A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
|A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
|A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
|A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
|A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
|_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
|_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
|_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
|_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
|_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
A total of 15 Possible configurations.
 
Configuration:
|_|_|_|_|_| # 5 cells and [2, 3] blocks
Possibilities:
#<RuntimeError: Those blocks will not fit in those cells>
</pre>
 
=={{header|Rust}}==
{{works with|Rust|1.29.2}}
<syntaxhighlight lang="rust">struct Nonoblock {
width: usize,
config: Vec<usize>,
spaces: Vec<usize>,
}
 
impl Nonoblock {
pub fn new(width: usize, config: Vec<usize>) -> Nonoblock {
Nonoblock {
width: width,
config: config,
spaces: Vec::new(),
}
}
 
pub fn solve(&mut self) -> Vec<Vec<i32>> {
let mut output: Vec<Vec<i32>> = Vec::new();
self.spaces = (0..self.config.len()).fold(Vec::new(), |mut s, i| {
s.push(match i {
0 => 0,
_ => 1,
});
s
});
if self.spaces.iter().sum::<usize>() + self.config.iter().sum::<usize>() <= self.width {
'finished: loop {
match self.spaces.iter().enumerate().fold((0, vec![0; self.width]), |mut a, (i, s)| {
(0..self.config[i]).for_each(|j| a.1[a.0 + j + *s] = 1 + i as i32);
return (a.0 + self.config[i] + *s, a.1);
}) {
(_, out) => output.push(out),
}
let mut i: usize = 1;
'calc: loop {
let len = self.spaces.len();
if i > len {
break 'finished;
} else {
self.spaces[len - i] += 1
}
if self.spaces.iter().sum::<usize>() + self.config.iter().sum::<usize>() > self.width {
self.spaces[len - i] = 1;
i += 1;
} else {
break 'calc;
}
}
}
}
output
}
}
 
fn main() {
let mut blocks = [
Nonoblock::new(5, vec![2, 1]),
Nonoblock::new(5, vec![]),
Nonoblock::new(10, vec![8]),
Nonoblock::new(15, vec![2, 3, 2, 3]),
Nonoblock::new(5, vec![2, 3]),
];
 
for block in blocks.iter_mut() {
println!("{} cells and {:?} blocks", block.width, block.config);
println!("{}",(0..block.width).fold(String::from("="), |a, _| a + "=="));
let solutions = block.solve();
if solutions.len() > 0 {
for solution in solutions.iter() {
println!("{}", solution.iter().fold(String::from("|"), |s, f| s + &match f {
i if *i > 0 => (('A' as u8 + ((*i - 1) as u8) % 26) as char).to_string(),
_ => String::from("_"),
}+ "|"));
}
} else {
println!("No solutions. ");
}
println!();
}
}</syntaxhighlight>
{{out}}
<pre>
5 cells and [2, 1] blocks
===========
|A|A|_|B|_|
|A|A|_|_|B|
|_|A|A|_|B|
 
5 cells and [] blocks
===========
|_|_|_|_|_|
 
10 cells and [8] blocks
=====================
|A|A|A|A|A|A|A|A|_|_|
|_|A|A|A|A|A|A|A|A|_|
|_|_|A|A|A|A|A|A|A|A|
 
15 cells and [2, 3, 2, 3] blocks
===============================
|A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
|A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
|A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
|A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
|A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
|A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
|A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
|A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
|A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
|A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
|_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
|_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
|_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
|_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
|_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
 
5 cells and [2, 3] blocks
===========
No solutions.
</pre>
 
=={{header|Swift}}==
<syntaxhighlight lang="swift">import Foundation
 
func nonoblock(cells: Int, blocks: [Int]) {
print("\(cells) cells and blocks \(blocks):")
let totalBlockSize = blocks.reduce(0, +)
if cells < totalBlockSize + blocks.count - 1 {
print("no solution")
return
}
 
func solve(cells: Int, index: Int, totalBlockSize: Int, offset: Int) {
if index == blocks.count {
count += 1
print("\(String(format: "%2d", count)) \(String(output))")
return
}
let blockSize = blocks[index]
let maxPos = cells - (totalBlockSize + blocks.count - index - 1)
let t = totalBlockSize - blockSize
var c = cells - (blockSize + 1)
for pos in 0...maxPos {
fill(value: ".", offset: offset, count: maxPos + blockSize)
fill(value: "#", offset: offset + pos, count: blockSize)
solve(cells: c, index: index + 1, totalBlockSize: t,
offset: offset + blockSize + pos + 1)
c -= 1
}
}
 
func fill(value: Character, offset: Int, count: Int) {
output.replaceSubrange(offset..<offset+count,
with: repeatElement(value, count: count))
}
var output: [Character] = Array(repeating: ".", count: cells)
var count = 0
solve(cells: cells, index: 0, totalBlockSize: totalBlockSize, offset: 0)
}
 
nonoblock(cells: 5, blocks: [2, 1])
print()
 
nonoblock(cells: 5, blocks: [])
print()
 
nonoblock(cells: 10, blocks: [8])
print()
 
nonoblock(cells: 15, blocks: [2, 3, 2, 3])
print()
 
nonoblock(cells: 5, blocks: [2, 3])</syntaxhighlight>
 
{{out}}
<pre>
5 cells and blocks [2, 1]:
1 ##.#.
2 ##..#
3 .##.#
 
5 cells and blocks []:
1 .....
 
10 cells and blocks [8]:
1 ########..
2 .########.
3 ..########
 
15 cells and blocks [2, 3, 2, 3]:
1 ##.###.##.###..
2 ##.###.##..###.
3 ##.###.##...###
4 ##.###..##.###.
5 ##.###..##..###
6 ##.###...##.###
7 ##..###.##.###.
8 ##..###.##..###
9 ##..###..##.###
10 ##...###.##.###
11 .##.###.##.###.
12 .##.###.##..###
13 .##.###..##.###
14 .##..###.##.###
15 ..##.###.##.###
 
5 cells and blocks [2, 3]:
no solution
</pre>
 
=={{header|Tcl}}==
{{works with|Tcl|8.6}}
{{tcllib|generator}}
{{trans|Python}}
<syntaxhighlight lang="tcl">package require Tcl 8.6
package require generator
 
generator define nonoblocks {blocks cells} {
set sum [tcl::mathop::+ {*}$blocks]
if {$sum == 0 || [lindex $blocks 0] == 0} {
generator yield {{0 0}}
return
} elseif {$sum + [llength $blocks] - 1 > $cells} {
error "those blocks will not fit in those cells"
}
 
set brest [lassign $blocks blen]
for {set bpos 0} {$bpos <= $cells - $sum - [llength $brest]} {incr bpos} {
if {![llength $brest]} {
generator yield [list [list $bpos $blen]]
return
}
set offset [expr {$bpos + $blen + 1}]
generator foreach subpos [nonoblocks $brest [expr {$cells - $offset}]] {
generator yield [linsert [lmap b $subpos {
lset b 0 [expr {[lindex $b 0] + $offset}]
}] 0 [list $bpos $blen]]
}
}
}
 
if {[info script] eq $::argv0} {
proc pblock {cells {vec {}}} {
set vector [lrepeat $cells "_"]
set ch 64
foreach b $vec {
incr ch
lassign $b bp bl
for {set i $bp} {$i < $bp + $bl} {incr i} {
lset vector $i [format %c $ch]
}
}
return |[join $vector "|"]|
}
proc flist {items} {
return [format "\[%s\]" [join $items ", "]]
}
foreach {blocks cells} {
{2 1} 5
{} 5
{8} 10
{2 3 2 3} 15
{2 3} 5
} {
puts "\nConfiguration:"
puts [format "%s # %d cells and %s blocks" \
[pblock $cells] $cells [flist $blocks]]
puts " Possibilities:"
set i 0
try {
generator foreach vector [nonoblocks $blocks $cells] {
puts " [pblock $cells $vector]"
incr i
}
puts " A total of $i possible configurations"
} on error msg {
puts " --> ERROR: $msg"
}
}
}
 
package provide nonoblock 1</syntaxhighlight>
{{out}}
<pre>
 
Configuration:
|_|_|_|_|_| # 5 cells and [2, 1] blocks
Possibilities:
|A|A|_|B|_|
|A|A|_|_|B|
|_|A|A|_|B|
A total of 3 possible configurations
 
Configuration:
|_|_|_|_|_| # 5 cells and [] blocks
Possibilities:
|_|_|_|_|_|
A total of 1 possible configurations
 
Configuration:
|_|_|_|_|_|_|_|_|_|_| # 10 cells and [8] blocks
Possibilities:
|A|A|A|A|A|A|A|A|_|_|
|_|A|A|A|A|A|A|A|A|_|
|_|_|A|A|A|A|A|A|A|A|
A total of 3 possible configurations
 
Configuration:
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| # 15 cells and [2, 3, 2, 3] blocks
Possibilities:
|A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
|A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
|A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
|A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
|A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
|A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
|A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
|A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
|A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
|A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
|_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
|_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
|_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
|_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
|_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
A total of 15 possible configurations
 
Configuration:
|_|_|_|_|_| # 5 cells and [2, 3] blocks
Possibilities:
--> ERROR: those blocks will not fit in those cells
</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-math}}
<syntaxhighlight lang="wren">import "./math" for Nums
 
var genSequence // recursive
genSequence = Fn.new { |ones, numZeros|
if (ones.isEmpty) return ["0" * numZeros]
var result = []
for (x in 1...numZeros - ones.count + 2) {
var skipOne = ones[1..-1]
for (tail in genSequence.call(skipOne, numZeros - x)) {
result.add("0" * x + ones[0] + tail)
}
}
return result
}
 
var printBlock = Fn.new { |data, len|
var a = data.toList
var sumChars = Nums.sum(a.map { |c| c.bytes[0] - 48 }.toList)
System.print("\nblocks %(a), cells %(len)")
if (len - sumChars <= 0) {
System.print("No solution")
return
}
var prep = a.map { |c| "1" * (c.bytes[0] - 48) }.toList
for (r in genSequence.call(prep, len - sumChars + 1)) {
System.print(r[1..-1])
}
}
 
printBlock.call("21", 5)
printBlock.call("", 5)
printBlock.call("8", 10)
printBlock.call("2323", 15)
printBlock.call("23", 5)</syntaxhighlight>
 
{{out}}
<pre>
blocks [2, 1], cells 5
11010
11001
01101
 
blocks [], cells 5
00000
 
blocks [8], cells 10
1111111100
0111111110
0011111111
 
blocks [2, 3, 2, 3], cells 15
110111011011100
110111011001110
110111011000111
110111001101110
110111001100111
110111000110111
110011101101110
110011101100111
110011100110111
110001110110111
011011101101110
011011101100111
011011100110111
011001110110111
001101110110111
 
blocks [2, 3], cells 5
No solution
</pre>
 
=={{header|zkl}}==
{{trans|Python}}
<syntaxhighlight lang="zkl">fcn nonoblocks(blocks,cells){
if(not blocks or blocks[0]==0) vm.yield( T(T(0,0)) );
else{
if(not ( blocks.sum(0) + blocks.len() -1<=cells ))
throw(Exception.AssertionError("Those blocks will not fit in those cells"));
blength,brest:=blocks[0], blocks[1,*]; # Deal with the first block of length
minspace4rest:=brest.reduce('+(1),0); # The other blocks need space
# Slide the start position from left to max RH index allowing for other blocks.
foreach bpos in (cells - minspace4rest - blength +1){
if(not brest) # No other blocks to the right so just yield this one.
vm.yield(T(T(bpos,blength)));
else{
# More blocks to the right so create a *sub-problem* of placing
# the brest blocks in the cells one space to the right of the RHS of
# this block.
offset:=bpos + blength +1;
# recursive call to nonoblocks yields multiple sub-positions
foreach subpos in (Utils.Generator(nonoblocks,brest,cells - offset)){
# Remove the offset from sub block positions
rest:=subpos.pump(List,'wrap([(bp,bl)]){ T(offset + bp, bl) });
# Yield this block plus sub blocks positions
vm.yield(T( T(bpos,blength) ).extend(rest) );
}
}
}
}
}
# Pretty print each run of blocks with a different letter for each block of filled cells
fcn pblock(vec,cells){
vector,ch:=cells.pump(List(),"_".copy), ["A".."Z"];
vec.apply2('wrap([(a,b)]){ a.walker(b).pump(Void,vector.set.fp1(ch.next())) });
String("|",vector.concat("|"),"|");
}</syntaxhighlight>
<syntaxhighlight lang="zkl">foreach blocks,cells in (T( T(T(2,1),5), T(T,5), T(T(8),10), T(T(2,3,2,3),15),
T(T(2,3),5) )){
println("\nConfiguration:\n %s # %d cells and %s blocks"
.fmt(pblock(T,cells),cells,blocks));
println(" Possibilities:");
Utils.Generator(nonoblocks,blocks,cells).reduce('wrap(n,vector){
println(" ",pblock(vector,cells));
n+1
},0)
: println(" A total of %d possible configurations.".fmt(_));
}</syntaxhighlight>
{{out}}
<pre>
Configuration:
|_|_|_|_|_| # 5 cells and L(2,1) blocks
Possibilities:
|A|A|_|B|_|
|A|A|_|_|B|
|_|A|A|_|B|
A total of 3 possible configurations.
 
Configuration:
|_|_|_|_|_| # 5 cells and L() blocks
Possibilities:
|_|_|_|_|_|
A total of 1 possible configurations.
 
Configuration:
|_|_|_|_|_|_|_|_|_|_| # 10 cells and L(8) blocks
Possibilities:
|A|A|A|A|A|A|A|A|_|_|
|_|A|A|A|A|A|A|A|A|_|
|_|_|A|A|A|A|A|A|A|A|
A total of 3 possible configurations.
 
Configuration:
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_| # 15 cells and L(2,3,2,3) blocks
Possibilities:
|A|A|_|B|B|B|_|C|C|_|D|D|D|_|_|
|A|A|_|B|B|B|_|C|C|_|_|D|D|D|_|
|A|A|_|B|B|B|_|C|C|_|_|_|D|D|D|
|A|A|_|B|B|B|_|_|C|C|_|D|D|D|_|
|A|A|_|B|B|B|_|_|C|C|_|_|D|D|D|
|A|A|_|B|B|B|_|_|_|C|C|_|D|D|D|
|A|A|_|_|B|B|B|_|C|C|_|D|D|D|_|
|A|A|_|_|B|B|B|_|C|C|_|_|D|D|D|
|A|A|_|_|B|B|B|_|_|C|C|_|D|D|D|
|A|A|_|_|_|B|B|B|_|C|C|_|D|D|D|
|_|A|A|_|B|B|B|_|C|C|_|D|D|D|_|
|_|A|A|_|B|B|B|_|C|C|_|_|D|D|D|
|_|A|A|_|B|B|B|_|_|C|C|_|D|D|D|
|_|A|A|_|_|B|B|B|_|C|C|_|D|D|D|
|_|_|A|A|_|B|B|B|_|C|C|_|D|D|D|
A total of 15 possible configurations.
 
Configuration:
|_|_|_|_|_| # 5 cells and L(2,3) blocks
Possibilities:
VM#2 caught this unhandled exception:
AssertionError : Those blocks will not fit in those cells
<stack traces deleted>
</pre>
PureFox
9,482

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/245631...352435"