16
1
Given a pattern representing a list of lengths, and a string representing those lengths, do they match?
For those interested, this is question equivalent to verifying if a row or column of a Nonogram may be correct. However, I have omitted all language relating to Nonograms to make the question less confusing for those unfamiliar with these puzzles.
Input
Two lines of data, separated by a newline.
The first line will be a space separated list of integers, example:
3 6 1 4 6
This line describes a pattern of filled spaces of size equal to the integer list, separated by empty spaces of unknown, positive length that the second line must match. There may also be empty spaces at the beginning and end of the matched string.
The second line will be a line that that may or may not match the pattern in line one. It consists entirely of
#
,x
, and_
. This line is guaranteed to be at least as long as the sum of the integers in the first line, plus the number of distinct integers, minus 1, and can be longer. So the second line in this case is guaranteed to be at least(3+6+1+4+6) + (5) - 1
, or 24 characters long. Here is an example 24 character line that matches the pattern in the first line:###_######_#_####_######
Meaning of symbols:
#
This represents a filled boxx
This represents a box marked as "guaranteed to be empty"_
This represents an unknown / unmarked box.
Goal
The idea is to:
- Validate that the second line could be a valid row that meets the pattern of the first line.
- You must print an unambiguous error message (how you choose to do this is up to you; the examples below write
ERROR
but it doesn't need to be those 5 characters) if the unknown spaces cannot be filled out with either#
orx
to match the first line.
- You must print an unambiguous error message (how you choose to do this is up to you; the examples below write
- Print the zero-indexed indices of the integers that have been completely placed in the row, space delimited. If there is ambiguity, do not print the index.
Examples:
Input: | Output: | Reason:
--------------------------------------------------------------------------
3 6 1 4 6 | 0 1 2 3 4 | This is a complete string that
###x######x#x####x###### | | matches perfectly.
--------------------------------------------------------------------------
1 2 1 | 0 1 2 | There is no ambiguity which filled cells
#____xx___##__x_# | | correspond to which parts of the pattern.
--------------------------------------------------------------------------
1 2 1 | | I don't know whether the filled block is
____#___x | | part of the 1, 2, or 1, so output nothing.
--------------------------------------------------------------------------
1 2 1 | ERROR | The first unknown cell will create a block that
#_#x_# | | matches either 1 1 or 3, but not 1 2.
--------------------------------------------------------------------------
1 2 1 | 0 2 | Even though we know where all the filled cells
#____# | | must be, only 0 and 2 are actually filled here.
--------------------------------------------------------------------------
1 1 1 1 | | There are so many possible ways to do fill this,
__#_______#____ | | we don't know which indices are actually matched.
--------------------------------------------------------------------------
4 4 | | Again, we don't know WHICH 4 is matched here,
______x####________ | | so output nothing.
--------------------------------------------------------------------------
4 4 | 0 | However, here, there's no room for a previous 4,
__x####________ | | so the displayed 4 must be index 0.
--------------------------------------------------------------------------
3 | ERROR | We can't fit a 3 into a space before or after
__x__ | | the x, so this is impossible to match.
--------------------------------------------------------------------------
5 1 3 | 0 | While we can match the 5, we don't know whether
x#####x____#____ | | the single block matches the 1 or the 3.
--------------------------------------------------------------------------
3 2 3 | 1 | The two has been completely placed,
____##x##____ | | even though we don't know which it is.
Rules:
You may write a program or function, which receives the input as a newline delimited String or from STDIN (or closest alternative), and returns the output as an space delimited String or printing it to STDOUT (or closest alternative). You may optionally include a single trailing newline in the output.
Additionally, standard loopholes which are no longer funny are banned.
1This is for solving nonograms, right? It might help to mention nongrams since that makes the challenge make immediate sense for those who solve them. – xnor – 2015-10-13T21:11:27.960
@jimmy23013 Edited in response. – durron597 – 2015-10-22T17:22:24.747