Dado um padrão que representa uma lista de comprimentos e uma string que representa esses comprimentos, eles correspondem?

_{Para os interessados, essa é uma pergunta equivalente a verificar se uma linha ou coluna de um Nonograma pode estar correta. No entanto, omiti todo o idioma relacionado aos nonogramas para tornar a pergunta menos confusa para aqueles que não estão familiarizados com esses quebra-cabeças.}

Entrada

Duas linhas de dados, separadas por uma nova linha.

1. A primeira linha será uma lista de números inteiros separados por espaço, por exemplo:

   3 6 1 4 6
   

   Esta linha descreve um padrão de espaços preenchidos de tamanho igual à lista inteira, separados por espaços vazios de comprimento positivo desconhecido que a segunda linha deve corresponder. Também pode haver espaços vazios no início e no final da sequência correspondente.

2. A segunda linha será uma linha que pode ou não corresponder ao padrão na linha um. Ele consiste inteiramente de #, xe _. É garantido que esta linha seja pelo menos enquanto a soma dos números inteiros na primeira linha, mais o número de números inteiros distintos, menos 1, e puder ser maior. Portanto, a segunda linha neste caso é garantida para ter pelo menos (3+6+1+4+6) + (5) - 124 caracteres. Aqui está um exemplo de linha de 24 caracteres que corresponde ao padrão na primeira linha:

   ###_######_#_####_######
   

Significado dos símbolos:

• # Isso representa uma caixa cheia
• x Isso representa uma caixa marcada como "garantia de estar vazia"
• _ Isso representa uma caixa desconhecida / não marcada.

Objetivo

A ideia é:

1. Valide que a segunda linha pode ser uma linha válida que atenda ao padrão da primeira linha.
   • Você deve imprimir uma mensagem de erro inequívoca (como você decide fazer isso; os exemplos abaixo escrevem, ERRORmas não precisam ser esses 5 caracteres) se os espaços desconhecidos não puderem ser preenchidos com #ou xpara corresponder ao primeiro linha.
2. Imprima os índices indexados a zero dos números inteiros que foram completamente colocados na linha, delimitado por espaço. Se houver ambiguidade, não imprima o índice .

Exemplos:

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.

Regras:

Você pode escrever um programa ou função que receba a entrada como uma String delimitada por nova linha ou a partir de STDIN (ou alternativa mais próxima) e retorne a saída como uma String delimitada por espaço ou imprima-a em STDOUT (ou alternativa mais próxima). Opcionalmente, você pode incluir uma única nova linha à direita na saída.

Além disso, as brechas padrão que não são mais engraçadas são proibidas .

Perl, 134 bytes

(inclui 1 opção)

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

Toma duas linhas de entrada de STDIN. Deve ser reexecutado para cada entrada.

A idéia é primeiro extrair todos os padrões possíveis que correspondam aos comprimentos especificados. Por exemplo, se tivermos os comprimentos 1 2e o padrão #_x_#_, os padrões correspondentes serão (#, _#)e (#, #_). Em seguida, concatene os padrões correspondentes para cada índice - por exemplo, o resultado é a lista (##, _##_). Agora, imprima os índices de todas as seqüências na lista que possuem apenas caracteres '#'.

Eu peguei o método para extrair todas as correspondências possíveis de uma regex em Perl aqui .

• Explicação ungolfed e estendida
• ideone.com