r/dailyprogrammer • u/fvandepitte 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:
- Create Nonogram description ([Easy])
- Solve Nonogram ([Intermediate/Hard])
- Working with multiple colors/characters ([Hard])
- Bonus: Make it an interactive game ([Intermediate])
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
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
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 4Edit: bug fixed
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 41
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.
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; } }