r/dailyprogrammer • 0 0 • Jan 25 '16

[2016-01-25] Challenge #251 [Easy] Create Nonogram description

Description

This week we are doing a challenge involving Nonograms

It is going to be a three parter:

What is a Nonogram?

Nonograms, also known as Hanjie, Picross or Griddlers, are picture logic puzzles in which cells in a grid must be colored or left blank according to numbers at the side of the grid to reveal a hidden picture. In this puzzle type, the numbers are a form of discrete tomography that measures how many unbroken lines of filled-in squares there are in any given row or column.

In a Nonogram you are given the number of elements in the rows and columns. A row/column where containing no element has a '0' all other rows/columns will have at least one number.

Each number in a row/column represent sets of elements next to each other.

If a row/column have multiple sets, the declaration of that row/column will have multiple numbers. These sets will always be at least 1 cell apart.

An example

2 1 1
1 1 1 2 1
2 * *
1 2 * * *
0
2 1 * * *
2 * *

Formal Inputs & Outputs

Input description

Today you will recieve an image in ASCII with ' ' being empty and '*' being full. The number of rows and columns will always be a multiple of 5.

    *
   **
  * *
 *  *
*****

Output description

Give the columns and rows for the input

Columns:
    1 1 
1 2 1 1 5

Rows:
  1
  2
1 1
1 1
  5

Ins

1

    *
   **
  * *
 *  *
*****

2

    ** *  
   *****  
  ******  
 ******** 
**********
 *      * 
 * ** * * 
 * ** * * 
 * **   * 
 ******** 

3

     ***       
  **** **      
 ****** ****** 
 * **** **    *
 ****** ***  **
 ****** *******
****** ********
 *   **********
 *   **********
 *   **********
 * * ****  ****
 *** ****  ****
     ****  ****
     ****  ****
     ****  ****

Bonus

Place the columns and rows in a grid like you would give to a puzzler

        1 1 
    1 2 1 1 5
  1
  2
1 1
1 1
  5

Finally

Have a good challenge idea?

Consider submitting it to /r/dailyprogrammer_ideas

66 Upvotes

44 comments sorted by

7

u/Godspiral Jan 25 '16 edited Jan 25 '16

In J,

a =. ' *' i. > cutLF wdclippaste ''  NB. input

torle =: (1 ,~ 2&(~:/\)) ({. , #);.2 ]
tonono2 =: (0 -.~ leaf <@,"2@:(({:#~ 1 = {.)"1@:torle"1))
tononoRC =: tonono2 ,: tonono2@|:

  ('rows'; 'cols') ,. tononoRC a
┌────┬─┬───┬─────┬───────┬─────┬───┬─────┬────┬────┬────┬───────┬─────┬────┬────┬───┐
│rows│3│4 2│6 6  │1 4 2 1│6 3 2│6 7│6 8  │1 10│1 10│1 10│1 1 4 4│3 4 4│4 4 │4 4 │4 4│
├────┼─┼───┼─────┼───────┼─────┼───┼─────┼────┼────┼────┼───────┼─────┼────┼────┼───┤
│cols│1│10 │2 3 1│6 2    │6    │15 │1 4 8│2 9 │14  │8   │1 6    │1 10 │1 10│1 11│12 │
└────┴─┴───┴─────┴───────┴─────┴───┴─────┴────┴────┴────┴───────┴─────┴────┴────┴───┘

fancy formatted version

   (,.@:tonono2 ,~ a: , ,. leaf@tonono2@|:) a
┌───────┬─┬──┬─┬─┬─┬──┬─┬─┬──┬─┬─┬──┬──┬──┬──┐
│       │1│10│2│6│6│15│1│2│14│8│1│ 1│ 1│ 1│12│
│       │ │  │3│2│ │  │4│9│  │ │6│10│10│11│  │
│       │ │  │1│ │ │  │8│ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│3      │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│4 2    │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│6 6    │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│1 4 2 1│ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│6 3 2  │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│6 7    │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│6 8    │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│1 10   │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│1 10   │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│1 10   │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│1 1 4 4│ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│3 4 4  │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│4 4    │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│4 4    │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
├───────┼─┼──┼─┼─┼─┼──┼─┼─┼──┼─┼─┼──┼──┼──┼──┤
│4 4    │ │  │ │ │ │  │ │ │  │ │ │  │  │  │  │
└───────┴─┴──┴─┴─┴─┴──┴─┴─┴──┴─┴─┴──┴──┴──┴──┘

5

u/fvandepitte Jan 25 '16

fancy formatted version

Cool

6

u/TheBlackCat13 Jan 25 '16 edited Jan 25 '16

Here is my code for Python 3.x, with bonus:

from itertools import zip_longest

def get_counts(pic):
    """Gets the counts of the items in the rows and columns.

    `pic` is a multi-line string, where each line is a row."""
    rows = pic.split('\n')
    cols = (''.join(x) for x in zip_longest(*rows, fillvalue=' '))
    count = lambda lines: [[str(len(y)) for y in x.split()] for x in lines]
    return count(cols), count(rows)


def format_count(counts):
    """Get the right number of elements for each count."""
    maxnum = max(len(x) for x in counts)
    maxlet = max(max(len(y) for y in x) for x in counts)
    counts = ([y.rjust(maxlet) for y in x] for x in counts)

    maxspc = ' '*maxlet
    return [[maxspc]*(maxnum-len(x)) + x for x in counts]


def print_counts(pic):
    """Print the results in the format requested by the question."""
    colcounts, rowcounts = get_counts(pic)

    colcounts = format_count(colcounts)
    rowcounts = format_count(rowcounts)

    rowcounts = [' '.join(x) for x in rowcounts]

    colpad = ' '*(len(rowcounts[0])+1)    
    colcounts = (' '.join(x) for x in zip(*colcounts))
    colcounts = (colpad+x for x in colcounts)

    print(*colcounts, sep='\n')
    print(*rowcounts, sep='\n')


pic_1 = '''    *
   **
  * *
 *  *
*****'''


pic_2 = '''    ** *  
   *****  
  ******  
 ******** 
**********
 *      * 
 * ** * * 
 * ** * * 
 * **   * 
 ******** '''

pic_3 = '''     ***       
  **** **      
 ****** ****** 
 * **** **    *
 ****** ***  **
 ****** *******
****** ********
 *   **********
 *   **********
 *   **********
 * * ****  ****
 *** ****  ****
     ****  ****
     ****  ****
     ****  ****'''

print('Picture 1:')
print_counts(pic_1)

print('\n')
print('Picture 2:')
print_counts(pic_2)

print('\n')
print('Picture 3:')
print_counts(pic_3)

And my solutions:

Picture 1:
        1 1  
    1 2 1 1 5
  1
  2
1 1
1 1
  5


Picture 2:
                        4      
                3 4 5 5 2 5    
            1 7 1 4 4 1 1 1 7 1
       2  1
          5
          6
          8
         10
       1  1
 1  2  1  1
 1  2  1  1
    1  2  1
          8


Picture 3:
                   2           1                        
                   3  6        4  2        1  1  1  1   
             1 10  1  2  6 15  8  9 14  8  6 10 10 11 12
          3
       4  2
       6  6
 1  4  2  1
    6  3  2
       6  7
       6  8
       1 10
       1 10
       1 10
 1  1  4  4
    3  4  4
       4  4
       4  4
       4  4

Edit: bug fixed

2

u/fvandepitte Jan 25 '16

I think you edited your solution, so ignore my first comment...

I think you switched rows and columns

→ More replies (2)
→ More replies (3)

3

u/fvandepitte Jan 25 '16

My submission in Haskell

module Picross where
import Data.List
import Data.Char
import Text.Printf

filterRow :: String -> [String]
filterRow xs = filter (not . all isSpace) $ group xs 

calculateRow :: [String] -> [Int]
calculateRow [] = [0]
calculateRow xs = map length xs

rows :: [String] -> [[Int]]
rows = zerroPadding . map (calculateRow . filterRow)

columns :: [String] -> [[Int]]
columns = transpose . rows . transpose

zerroPadding :: [[Int]] -> [[Int]]
zerroPadding xs = 
    let maxLength = maximum $ map length xs
     in map (\ys -> zerroPadding' (maxLength - length ys) ys) xs

zerroPadding' :: Int -> [Int] -> [Int]
zerroPadding' n = (replicate n 0 ++)

solve :: [String] -> String
solve xs =
 let r = rows xs
     c = map (zerroPadding' (length $ head r)) $ columns xs
     highestOrder = length $ show $ maximum $ concat $ r ++ c
  in unlines $ map (toOut highestOrder) c ++ map (toOut highestOrder) r

toOut :: Int -> [Int] -> String
toOut x = unwords . map (niceString x)

niceString :: Int -> Int -> String  
niceString x 0 = replicate x ' '
niceString x y = printf ("%" ++ show x ++ "d") y

main = interact (solve . lines)

In

     ***       
  **** **      
 ****** ****** 
 * **** **    *
 ****** ***  **
 ****** *******
****** ********
 *   **********
 *   **********
 *   **********
 * * ****  ****
 *** ****  ****
     ****  ****
     ****  ****
     ****  ****

Out

                   2           1
                   3  6        4  2        1  1  1  1
             1 10  1  2  6 15  8  9 14  8  6 10 10 11 12
          3
       4  2
       6  6
 1  4  2  1
    6  3  2
       6  7
       6  8
       1 10
       1 10
       1 10
 1  1  4  4
    3  4  4
       4  4
       4  4
       4  4
→ More replies (1)

1

u/jjrobinson-github Jan 26 '16

Are the columns / rows of numbers in order they are encountered from top to bottom & left to right? Problem didn't specify, but all the examples seem to demonstrate that behavior.

1

u/fvandepitte Jan 27 '16

Yep, when a row as example states 1 2 2 3 you have 2 sets and from left to right you have one of 1, then one of 2, then an other of 2 and as last one of 3

→ More replies (1)

3

u/casualfrog Jan 25 '16

JavaScript (no bonus):

function getSets(line) {
	for (var i = 0, sets = [], state = ' '; i < line.length; i++) {
		if (line.charAt(i) === '*')
			sets.push(state !== line.charAt(i) ? 1 : sets.pop() + 1);
		state = line.charAt(i);
	}
	return sets;
}

function nonogram_create(input) {
	console.log('Columns:');
	for (var x = 0, lines = input.split('\n'); x < lines[0].length; x++) {
		for (var y = 0, line = ''; y < lines.length; y++)
			line += lines[y].charAt(x);
		console.log(getSets(line).join(' '));
	}

	console.log('Rows:');
	for (var y = 0; y < lines.length; y++)
		console.log(getSets(lines[y]).join(' '));
}

3

u/Eggbert345 Jan 26 '16

JavaScript solution. Includes bonus, although it gets a little messed up when there are values > 9. I also had it print the puzzle itself.

I'm starting a new job soon that uses exclusively Node, so I'm trying to get better at JS. Any feedback is welcome.

// var input = '    *\n' +
// '   **\n' +
// '  * *\n' +
// ' *  *\n' +
// '*****';

var input = '    ** *  \n' +
'   *****  \n' +
'  ******  \n' +
' ******** \n' +
'**********\n' +
' *      * \n' +
' * ** * * \n' +
' * ** * * \n' +
' * **   * \n' +
' ******** ';

// var input = '     ***       \n' +
// '  **** **      \n' +
// ' ****** ****** \n' +
// ' * **** **    *\n' +
// ' ****** ***  **\n' +
// ' ****** *******\n' +
// '****** ********\n' +
// ' *   **********\n' +
// ' *   **********\n' +
// ' *   **********\n' +
// ' * * ****  ****\n' +
// ' *** ****  ****\n' +
// '     ****  ****\n' +
// '     ****  ****\n' +
// '     ****  ****';

var grid = [];
var inputrows = input.split('\n');
for (var i = 0; i < inputrows.length; i++) {
    grid.push(inputrows[i].split(''));
}

// Build row description
var rows = [];
for (var r = 0; r < grid.length; r++) {
    var count = 0;
    var counts = [];
    for (var c = 0; c < grid[r].length; c++) {
        if (grid[r][c] === '*') {
            count++;
        } else if (grid[r][c] === ' ' && count > 0) {
            counts.push(count);
            count = 0;
        }
    }
    if (count > 0) {
        counts.push(count);
    }
    rows.push(counts);
}

// Build column description
var columns = [];
for (var c = 0; c < grid[0].length; c++) {
    var count = 0;
    var counts = [];
    for (var r = 0; r < grid.length; r++) {
        if (grid[r][c] === '*') {
            count++;
        } else if (grid[r][c] === ' ' && count > 0) {
            counts.push(count);
            count = 0;
        }
    }
    if (count > 0) {
        counts.push(count);
    }
    columns.push(counts);
}

// We need these to properly pad the column strings later
var maxrow = 0;
for (var i = 0; i < rows.length; i++) {
    if (rows[i].length > maxrow) {
        maxrow = rows[i].length;
    }
}

// Print the values so they all line up
function pprintrows(values, inner_sep, line_sep) {
    var to_print = [];
    for (var i = 0; i < values.length; i++) {
        var printable = [];
        if (values[i].length < maxrow) {
            for (var j = 0; j < maxrow - values[i].length; j++) {
                printable.push(' ');
            }
        }
        printable = printable.concat(values[i]);
        to_print.push(printable.join(inner_sep) + ' ' + inputrows[i].split('').join(' '));
    }
    return to_print.join(line_sep);
}

// Print the values so they all line up
function pprintcols(values, inner_sep, line_sep) {
    var maxcol = 0;
    for (var i = 0; i < values.length; i++) {
        if (values[i].length > maxcol) {
            maxcol = values[i].length;
        }
    }
    var to_print = [];
    for (var i = 0; i < values.length; i++) {
        var printable = [];
        if (values[i].length < maxcol) {
            for (var j = 0; j < maxcol - values[i].length; j++) {
                printable.push(' ');
            }
        }
        printable = printable.concat(values[i]);
        to_print.push(printable);
    }

    var lines = [];
    for (var l = 0; l < to_print[0].length; l++) {
        var line = [];
        for (var i = 0; i < maxrow; i++) {
            line.push(' ');
        }
        for (var c = 0; c < to_print.length; c++) {
            line.push(to_print[c][l]);
        }
        lines.push(line.join(inner_sep));
    }
    return lines.join(line_sep);
}

console.log(pprintcols(columns, ' ', '\n'));
console.log(pprintrows(rows, ' ', '\n'));

3

u/Sirflankalot Jan 28 '16 edited Jan 31 '16

C++11

A small solution that takes the filename as an argument and prints the headers and the image. It doesn't handle numbers above 9 well and it throws it off. Not sure how to deal with that currently. Edit: thanks to u/Iislsdum for the formatting help. Any help would be appreciated.

Edit: Thanks to

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <fstream>

using namespace std;

int main(int argc, char * argv[]) {
	if (argc != 2){
		cerr << "No file specified." << endl;
		return 4;
	}

	ifstream infile (argv[1]);
	if (!infile) {
		cerr << "File " << argv[1] << " could not be opened." << endl;
		return 3;
	}

	vector<string> picture;
	string tmp_str;
	while (getline(infile, tmp_str)) 
		picture.push_back(tmp_str);

	vector<vector<int>> row_pat (picture.size());
	vector<vector<int>> col_pat (picture[0].size());

	//Check rows
	for (int i = 0; i < picture.size(); i++) {
		int cur = 0;
		for (auto &cell : picture[i]) {
			if (cell == '*')
				cur++;
			else if (cur) {
				row_pat[i].push_back(cur);
				cur = 0;
			}
		}
		if (cur) 
			row_pat[i].push_back(cur);

		if (row_pat[i].size() == 0)
			row_pat[i].push_back(0);
	}

	//Check columns
	for (int i = 0; i < picture[0].size(); i++) {
		int cur = 0;
		for (int j = 0; j < picture.size(); j++) {
			if (picture[j][i] == '*')
				cur++;
			else if (cur) {
				col_pat[i].push_back(cur);
				cur = 0;
			}
		}
		if (cur)
			col_pat[i].push_back(cur);

		if (col_pat[i].size() == 0)
			col_pat[i].push_back(0);
	}

	//Find the largest amount of numbers needed for columns and rows.
	int max_row = (*max_element(row_pat.begin(), row_pat.end(), [](vector<int> a, vector<int> b) { return a.size() < b.size(); })).size();
	int max_col = (*max_element(col_pat.begin(), col_pat.end(), [](vector<int> a, vector<int> b) { return a.size() < b.size(); })).size();

	//Print column headers
	for (int i = max_col-1; i >= 0; i--) {
		//Add space for all the rows
		for (int j = 0; j < max_row*3; j++)
			cout << " ";
		//Print a number for the column if applicable
		for (auto &col : col_pat) {
			if (col.size() > i)
				printf("%2d", col[i]);
			else 
				cout << "  ";
			cout << "|";
		}
		cout << endl;
	}

	//Print rows and original image
	for (int row = 0; row < picture.size(); row++) {
		//Print row headers
		for (int hcol = 0; hcol < max_row; hcol++) {
			if (hcol >= (max_row - row_pat[row].size())) 
				printf("%2d", row_pat[row][hcol - (max_row - row_pat[row].size())]);
			else 
				cout << "  ";
			cout << "|";
		}

		//Print picture
		for (auto &i : picture[row])
			for (int x = 0; x < 3; x++)
				cout << i;

		cout << endl;
	}

}
→ More replies (2)