# Create a Nonogram Puzzle

A nonogram is a two-dimensional logic puzzle that looks something like this (screenshots from the game Pixelo, my favourite nonogram game):

The goal of the game is to figure out what image those numbers are encoding. The rules are simple: A number on a column or row means that somewhere in that column or row, that many boxes are filled in in a row. For example, the bottom row in the above image must have no boxes filled in, while the one above it must have all of its boxes filled. The third row from the bottom has 8 filled boxes, and they will all be in a row.

Two or more numbers for the same column or row mean that there are multiple "runs" of filled boxes, with at least one space between, with those lengths. The order is preserved. For example, there are three filled in boxes on the very right column of the above image, at least one space below them, and then one more filled in box.

Here's that same puzzle, almost completed:

(The Xs aren't important, they're just a hint the player leaves for themself to say "This square is definitely not filled in". Think flags in Minesweeper. They have no rules meaning.)

Hopefully you can see that, for example, the middle columns with hints that say "2 2" have two 2-length runs of filled in boxes.

Your mission, should you choose to accept it, is to write a program or function that will create a puzzle like this. You are given the size of the board as a single integer (5 <= n <= 50) on stdin or as an argument (there's no reason why a nonogram puzzle has to be square, but for this challenge it will be). After that, you will be given a series of 1s and 0s representing filled and unfilled squares in the image, respectively. The first n of them are the top row, then the next row, etc. You will return or print to stdout a board of 2*1 cells (because they look better, and it gives you room for 2-digit hints for a column), all of them empty, with hints corresponding to the input data.

# Sample

Input:

./nonogram <<< '5 0 1 1 1 0 1 1 0 1 1 1 0 1 0 1 1 1 0 1 1 0 1 1 1 0'
OR
n(5,[0,1,1,1,0,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0])

Image:

Output:

1
2 1 2
3 2 1 2 3
+----------
3|
2 2|
1 1 1|
2 2|
3|

Input:

./nonogram <<< '15 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1'

Image:

Output:

1                       1
1 1 3       3 5   5 3   3 1
7 2 3 2 4 2 3 210 2 3 0 4 215
+------------------------------
2|
1|
1|
1|
1|
1 1|
3 3 1 1|
1 5 1 1|
3 5 3|
1 5 1|
1 3 1|
1 1 1 1 1|
1 1 1 1 1 1 1 1|
11 3|
11 3|

# Clarifications

• Your output need not be a solvable puzzle. Not all nonograms are solvable, but that isn't your concern. Just output the hints that correspond to the input, whether they make for a good puzzle or not.
• A program that takes arguments on the command line is allowed. This is kind of stated above, but it's possible to get the wrong idea. That's what clarifications are for.
• Printing a 0 for a row or column that has no filled in boxes is mandatory. I don't say this with words anywhere but it's in the sample data.
• I'm just about done with my solution. Can we assume that there will not be a 3-digit number of boxes in a row or column? Jun 3, 2014 at 15:43
• @voidpigeon: 5<=n<=50 is the spec, so there cannot be any 3-digit numbers Jun 3, 2014 at 15:51
• After posting this question, I started working on a solution myself. I won't post it yet (as per this meta answer), but I'll post my byte count so you guys have something to strive for: 404 bytes in Python 2.7 Jun 3, 2014 at 16:33
• Doesn't your first example output contain one more - than it should? Jun 3, 2014 at 16:37
• @Ventro You are correct! I knew how I would write a program to do this, but I didn't actually do it until just now, so my sample outputs were by hand. Oops! (I also screwed up the second sample output, but I fixed it before there were any answers.) Jun 3, 2014 at 16:38

~](:k/.{{1,%{,}%.!,+}%}:^~{' ':s*}%.{,}%$-1=:9{s*\+9~)>'|'n}+%\zip^.{,~}%$0=){.~[s]*@+>{s\+-2>}%}+%zip{9)s*\n}%$9s*'+''--'k*n]\ The input has to be provided on STDIN as space separated numbers. You can test the example here. Commented code: # Parse the input into an 2D array of digits. The width is saved to variable k ~](:k/ # Apply the code block ^ to a copy of this array . { # begin on code block { # for each line 1,% # split at 0s (1, => [0]) (leading, trailing, multiple 0s are # removed because of operator % instead of /) {,}% # calculate the length of each run of 1s .!,+ # special case: only zeros, i.e. [] # in this case the ! operator yiels 1, thus [0], else [] }% # end for }:^ # end of code block ~ # apply # Format row headers {' ':s*}% # join numbers with spaces .{,}%-1=:9 # calulate the length of the longest row header # and save it to variable <9> { # for each row s*\+ # prepend padding spaces 9~)> # and cut at length <9> from the right '|'n # append '|' and newline }+% # end for # Format column headers \zip^ # transpose input array and apply the code block ^ # i.e. calculate length of runs .{,~}%0=) # determine (negative) length of the longest column header { # for each column .~[s]*@+ # prepend enough spaces > # and cut at common length (from right) {s\+-2>}% # format each number/empty to 2 chars width }+% # end for zip # transpose column header into output lines {9)s*\n}% # prepend spaces to each line and append newline # Inject separator line \[ 9s* # spaces '+' # a plus sign '--'k* # k (width) number of '--' n # newline ]\ • +1 nice, I've learned quite a few good tricks from this post Jun 4, 2014 at 8:05 • I managed to golf it to 123 chars: ~](:k/.zip${{1,%{,}%.!,+}%}/{' ':^*}%{.{,}%$-1=}:f~:r{^*\+r~)>'|'n}+%\f{.~)\[^]*@+>{^\+-2>}%}+%zip{r)^*\n}%r^*'+''--'k*n]( (for some reason lettercount.com says 125 chars if you copy it, but I assure you, it is 123 chars). Some parts of the algorithm have been changed, but the majority is still the same. I also changed some variable names (having 9 as a variable is smart, but confusing as well), but you can change them back if you want. Jun 4, 2014 at 8:39 # Ruby, 216 255 n=$*.shift.to_i;k=*$*.each_slice(n) u=->k{k.map{|i|r=i.join.scan(/1+/).map{|i|"%2d"%i.size} [*[" "]*n,*r[0]?r:" 0"][-n,n]}} puts u[k.transpose].transpose.map{|i|" "*(n-~n)+i*""}," "*n+?++"--"*n,u[k].map{|i|i*""+?|} While this doesn't produce the exact sample output given in the question, it does follow the specs. The only difference to the examples is that I print a few leading spaces/newlines. Example:$ ruby nonogram.rb 15 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
# empty lines removed for brevity
1                       1
1 1 3       3 5   5 3   3 1
7 2 3 2 4 2 3 210 2 3 0 4 215
+------------------------------
2|
1|
1|
1|
1|
1 1|
3 3 1 1|
1 5 1 1|
3 5 3|
1 5 1|
1 3 1|
1 1 1 1 1|
1 1 1 1 1 1 1 1|
11 3|
11 3|

### Changelog:

• 240 -> 231: Changed input format to use command line arguments instead of stdin.
• 231 -> 230: Eliminated a space by moving the value check from chunk to map.
• 230 -> 226: Subtract [nil] instead of calling Array#compact.
• 226 -> 216: Simplify hint generation.
• You do print some extra newlines and spaces, but so far in all of my tests they've fit the "0 or more" specification, so you're good. I'm warning you now, though, if I start seeing numbers floating in the air to the left my monitor, I'm going to have to disqualify this answer :) Jun 3, 2014 at 17:00
• @undergroundmonorail: The output is printed in such a way that length(leading spaces + numbers to the left) == 2*n and height(leading newlines + numbers at the top) == n ... so as long as your monitor is big enough for 3*n+1 × 2*n+2 characters, you shouldn't have to disqualify me. :) Jun 3, 2014 at 17:04

# Ruby, 434

n=$*[i=0].to_i a,b=[],[] a.push$*.slice!(1..n)*""while $*.size>1 (b.push a.map{|c|c[i]}*"";i+=1)while i<n a,b=*[a,b].map{|c|c.map{|d|e=d.split(/[0]+/).map(&:size).select{|f|f>i=0}.map &:to_s;(e.size>0)?e:[?0]}} m,k=*[a,b].map{|c|c.map(&:size).max} s=" "*m k.times{$><<s+"  "+b.map{|c|(" "+((c.size==k-i)?(c.shift):(" ")))[-2..-1]}*"";i+=1;puts}
puts s+" "+?++?-*n*2
a.each{|c|puts"  "*(m-c.size)+" "+c.map{|d|(" "+d)[-2..-1]}*""+?|}
• How do you run this? I tried ruby $yourprogram <<<$input but got ruby_nanograms:7:in '<main>': undefined method '+' for nil:NilClass (NoMethodError). Jun 3, 2014 at 16:40
• @undergroundmonorail ruby nonogram.rb 2 1 0 0 1 for a 2x2 Jun 3, 2014 at 16:42
• This is a good answer, but you don't print the 0 for the fourth-last column in the second example. Jun 3, 2014 at 16:48
• I just noticed that the +------... line is indented by one too many spaces, too. Jun 3, 2014 at 17:23
• @undergroundmonorail Fixed both. Jun 3, 2014 at 17:28

## GolfScript 149 147

~](:s/.zip{{[0]%{,}%['0']or}%.{,}%$)\;:¶;{.,¶\-[' ']*\+}%}:f~¶:v;\[f~]\zip{{{.,2\-' '*\+}%''*}:d~¶2*)' '*:z\+{puts}:o~}%z(;'+'s'-'2**++o~{d'|'+o}/ Edits: • removed useless space • defined a reusable one-char function for puts to save one more char ### Online demos ### A somewhat annotated version of the code # split lines ~](:s/ # make transposed copy .zip #prepare numbers to show in the header {{[0]%{,}%['0']or}%.{,}%$)\;:¶;{.,¶\-[' ']*\+}%}:f~¶:v;

# prepare numbers to show in the left column
\[f~]\zip

{  {{.,2\-' '*\+}%''*}:d~  ¶2*)' '*:z\+puts}%

#print first line
z(;'+'s'-'2**++puts

#print horizontal hints
~{d'|'+ puts}/

# Javascript (E6) 314 334 357 410

N=(d,l)=>{J=a=>a.join(''),M=s=>(s.match(/1+/g)||['']).map(x=>x.length),f=' '.repeat(d+1),c=[n='\n'],o=n+f+'+'+'--'.repeat(d);for(i=-1;++i<d;)c[i]=M(J(l.map((e,p)=>p%d-i?'':e))),o+=n+(f+J(M(J(l).substr(i*d,d)).map(P=n=>n>9?n:n<10?' '+n:'  '))+'|').slice(-d-2);for(;--i;)o=n+f+' '+J(c.map(e=>P(e.pop())))+o;return o}

Ungolfed

N=(d,l)=> {
J = a => a.join(''),
M = s => (s.match(/1+/g)||['']).map(x=>x.length),
f=' '.repeat(d+1), c=[n='\n'], o=n+f+'+'+'--'.repeat(d);
for(i = -1; ++i < d;)
c[i] = M(J(l.map((e,p)=>p%d-i?'':e))),
o += n+(f+J(M(J(l).substr(i*d,d)).map(P=n=>n>9?n:n<10?' '+n:'  '))+'|').slice(-d-2);
for(;--i;)
o=n+f+' '+J(c.map(e=>P(e.pop())))+o;
return o
}

Usage

N(5,[0,1,1,1,0,1,1,0,1,1,1,0,1,0,1,1,1,0,1,1,0,1,1,1,0])

N(15,[0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1,1,1,1,0,0,0,0,1,1,1,0,0,1,0,1,0,0,1,0,0,0,1,1,1,1,1,0,1,0,1,1,1,1,0,0,0,1,1,1,1,1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,1,0,0,0,1,1,0,0,0,0,0,0,1,1,1,0,0,0,0,1,1,0,0,0,1,0,0,0,1,0,0,0,1,0,1,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1])

Edit history

1 Removed regexp used to find columns.Overkill
2 Simpler is better. Output to a string, not to an array. Removed helper function FILL (F)
3 Even simpler. I can't do better than this. Still can't compare to Golfscript :(

• Nice. I tried a Javascript version too but ended with something around 500 bytes and decided I was too big to put it here. Would be good to post ungolfed version with original variables names (if you still have it). Also, how do you run this ? If I copy paste it into chrome console window I get "ReferenceError: Invalid left-hand side in assignment". Is there something to change or to add before running ? Jun 4, 2014 at 10:59
• @tigrou sorry the "=>" sintax works only in firefox. Variables: c colunns hints, d dimension, l list of input, o output, i loop variable, q and z temp Jun 4, 2014 at 12:31
• Jun 4, 2014 at 22:00
• @nderscore fiddling around with the code, I got 326. In your code R is not initialized (easy mistake when you try again and again...) Jun 5, 2014 at 6:20

## R, 384 chars

a=scan();p=function(x)paste(x,collapse="");P=paste0;s=sapply;l=length;f=function(i)lapply(apply(matrix(a[-1],nr=a,b=T),i,rle),function(x)if(any(x$v)){x$l[!!x$v]}else{0});g=function(j,i)apply(s(j,function(x)sprintf("%2s",c(rep("",max(s(j,l))-l(x)),x))),i,p);c=P(g(f(1),2),"|");d=g(f(2),1);h=p(rep(" ",nchar(c[1])-1));e=P(h,"+",p(rep("-",nchar(d[1]))));d=P(h," ",d);cat(d,e,c,sep="\n") With indentations and some explanations: a=scan() #Takes input p=function(x)paste(x,collapse="") #Creates shortcuts P=paste0 s=sapply l=length #This function finds the number of subsequent ones in a line (using rle = run length encoding). #It takes 1 or 2 as argument (1 being row-wise, 2 column-wise f=function(i)lapply(apply(matrix(a[-1],nr=a,b=T),i,rle),function(x)if(any(x$v)){x$l[!!x$v]}else{0})

#This function takes the result of the previous and format the strings correctly (depending if they are rows or columns)
g=function(j,i)apply(s(j,function(x)sprintf("%2s",c(rep("",max(s(j,l))-l(x)),x))),i,p)

c=paste0(g(f(1),2),"|") #Computes the rows
d=g(f(2),1) #Computes the columns
h=p(rep(" ",nchar(c[1])-1))
e=paste0(h,"+",p(rep("-",nchar(d[1])))) #Prepare vertical border
d=paste0(h," ",d) #Pad column indices with spaces
cat(d,e,c,sep="\n") #Prints

Usage:

> a=scan();p=function(x)paste(x,collapse="");P=paste0;s=sapply;l=length;f=function(i)lapply(apply(matrix(a[-1],nr=a,b=T),i,rle),function(x)if(any(x$v)){x$l[!!x\$v]}else{0});g=function(j,i)apply(s(j,function(x)sprintf("%2s",c(rep("",max(s(j,l))-l(x)),x))),i,p);c=P(g(f(1),2),"|");d=g(f(2),1);h=p(rep(" ",nchar(c[1])-1));e=P(h,"+",p(rep("-",nchar(d[1]))));d=P(h," ",d);cat(d,e,c,sep="\n")
1: 15 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 1 1 1 0 0 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
227:
1                       1
1 1 3       3 5   5 3   3 1
7 2 3 2 4 2 3 210 2 3 0 4 215
+------------------------------
2|
1|
1|
1|
1|
1 1|
3 3 1 1|
1 5 1 1|
3 5 3|
1 5 1|
1 3 1|
1 1 1 1 1|
1 1 1 1 1 1 1 1|
11 3|
11 3|

# C - 511

C was definitely not made for formatting output nicely. Character count includes only necessary spaces/new lines.

Input is from STDIN, numbers separated by spaces.

#define P printf
#define L(x) for(x=0;x<s/2+1;x++)
#define l(x) for(x=0;x<s;x++)
#define B(x,y) x[i][j]||y==s/2?P("%2d",x[i][j]):P("  ");
a[50][50],i,j,s,h[25][50],v[50][25],H[50],V[50],x[25],y[25];
main(){
scanf("%d",&s);
L(j)x[j]=y[j]=s/2+1;
l(i)l(j)scanf("%d",&a[i][j]);
for(i=s-1;i>=0;i--)
for(j=s-1;j>=0;j--)
a[i][j]?
!H[j]&&(x[j]--,H[j]=1),
h[x[j]][j]++,
!V[i]&&(y[i]--,V[i]=1),
v[i][y[i]]++:
(H[j]=V[i]=0);
L(i){
L(j)P("  ");
P(" ");
l(j)B(h,i);
P("\n");
}
L(i)P("  ");
P("+");
l(i)P("--");
P("\n");
l(i){
L(j)B(v,j);
P("|\n");
}
}

It's been a few days and no one's answered in python, so here's my (probably pretty poor) attempt:

# Python 2.7 - 404397 380 bytes

def p(n,m):
k=str.join;l=[];g=lambda y:[['  ']*(max(map(len,y))-len(t))+t for t in[[' '*(a<10)+afor a in map(len,k("",c).split('0'))if a]or[' 0']for c in y]]
while m:l+=[map(str,m[:n])];m=m[n:]
x=g(l);j=k('\n',['  '*max(map(len,x))+'+'+k("",a)for a in zip(*[list(a)+['--']for a in g(zip(*l))])]);return j.replace('+',' ',j.count('+')-1)+'\n'+k('\n',[k("",a+['|'])for a in x])

I'll post an ungolfed version soon, but at the moment I think it's pretty readable. :)

EDIT: While writing the ungolfed version, I noticed some improvements I could make that added up to be fairly significant! For some reason that I can't explain, it now has additional newlines at the top and spaces at the left (even though I don't think I changed anything functional), but it still meets spec. Ungolfed version is coming!

Ungolfed:

def nonogram(board_size, pixels):
def hints(board):
output = []
for row in board:
# Convert the row to a string of 1s and 0s, then get a list of strings
# that came between two 0s.
s = "".join(row).split('0')

# A list of the length of each string in that list.
l = map(len, s)

# We now have our horizontal hints for the board, except that anywhere
# there were two 0s consecutively we have a useless 0.
# We can get rid of the 0s easily, but if there were no 1s in the row at
# all we want exactly one 0.
# Solution:
output.append([h for h in l if h != 0] or [0])
# In this context, foo or bar means foo if foo is a truthy value, bar
# otherwise.
# An empty list is falsey, so if we strip out all the strings we hardcode
# the 0.
return output

def num_format(hints):
# For both horizontal and vertical hints, we want a space before single-
# digit numbers and no space otherwise. Convert hints to strings and add
# spaces as necessary.
output = []

for row in hints:
output.append([' '*(a < 10) + str(a) for a in row])
# Multiplying a string by n repeats it n times, e.g. 'abc'*3=='abcabcabc'
# The only numbers that need a space are the ones less than 10.
# ' '*(a < 10) first evaluates a < 10 to get a True or False value.
# Python automatically converts True to 1 and False to 0.
# So, if a is a one digit number, we do ' '*(1) + str(a).
# If it's a two digit number, we do ' '*(0) + str(a).
return output

output = []
longest = max(map(len, hints)) # how long is the longest row?
for row in hints:
output.append(['  ']*(longest - len(row)) + row)
# Add '  ' to the beginning of every row until it's the same length
# as the longest one. Because all hints are two characters wide, this
# ensures all rows of hints are the same length.
return output

board = []

while pixels: # non-empty list == True
# Make a list of the first (board_size) pixels converted to strings, then
# add that list to board. Remove those pixels from the list of pixels.
# When pixels is empty, board has a seperate list for each row.
board.append([str(n) for n in pixels[:board_size]])
pixels = pixels[board_size:]

# zip(*l) is a common way to transpose l.
# zip([1,2,3], [4,5,6], [7,8,9]) == [(1, 4, 7), (2, 5, 8), (3, 6, 9)]
# the star operator unpacks an iterable so the contents can be used as
# multiple arguments, so
# zip(*[[1,2,3],[4,5,6],[7,8,9]]) is the same as what we just did.
# Transposing the board and getting the horizontal hints gives us the
# vertical hints of the original, but transposed. We'll transpose it back,
# but we'll also add '--' to the end of all of them to make up the line
vertical_hints = zip(*[a + ['--'] for a in vertical_hints])

# add n spaces, where n is the length of the longest horizontal hint, plus
# one space to the beginning of each line in the vertical hints, then join
# with newlines to make it all one string.
vertical_hints = '\n'.join(['  '*max(map(len, horizontal_hints)) + '+' +
''.join(a) for a in vertical_hints])

# find the number of plus signs in the string
# replace the first (that many - 1) plus signs with spaces
vertical_hints = vertical_hints.replace('+', ' ', vertical_hints.count('+')-1)

# add a pipe to each row of horizontal hints, then join it with newlines
horizontal_hints = '\n'.join([''.join(a + ['|']) for a in horizontal_hints])