Given a list of lengths, and a string representing those lengths, do they match?

Question

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.

1. 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.

2. 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 box
• x This represents a box marked as "guaranteed to be empty"
• _ This represents an unknown / unmarked box.

Goal

The idea is to:

1. 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 # or x to match the first line.
2. 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.

• xnor: This is for solving nonograms, right? It might help to mention nongrams since that makes the challenge make immediate sense for those who solve them.
• durron597: @jimmy23013 Edited in response.

Answer 1

Perl, 134 bytes

(includes 1 switch)

perl -pe '$p.="([#_]{$_})[x_]+"for@l=split;chop$p,$_=<>;/^[x_]*$p*$(?{$h[$_-1].=$$_ for 1..@l})(?!)/;$_=@h?join$",grep{$h[$_]!~/_/}0..$#l:ERROR'

Takes two lines of input from STDIN. Must be re-executed for every input.

The idea is to first extract all possible patterns that match the given lengths. For example, if we have the lengths 1 2 and the pattern #_x_#_, then the matching patterns are (#, _#) and (#, #_). Then, concatenate the matched patterns for every index - for the example the result is the list (##, _##_). Now, print the indices of all the strings in the list which have only '#' characters.

I got the method to extract all possible matches from a regex in Perl here.

• Ungolfed and extended explanation
• ideone.com

• durron597: Cool. Could you add an ungolfed version and an ideone link please?
• svsd: Sure, I have added the link at the end of my answer.
• Arjun: True example of how horrible a golfed code snippet can look! At least to me.
• svsd: @Arjun Golfing tends to obfuscate code. There's beauty in golfed code, but only if you know the language it is written in.
• durron597: I added a new example because one scenario was still ambiguous in the problem description. Fortunately, your program still works correctly in that case too.