Dada uma lista de comprimentos e uma string que representa esses comprimentos, eles correspondem?

16

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 .

durron597
fonte
11
Isso é para resolver nonogramas, certo? Pode ser útil mencionar os não-gramas, já que isso faz o desafio fazer sentido imediato para aqueles que os resolvem.
Xnor
@ jimmy23013 Editado em resposta.
durron597

Respostas:

5

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 .

svsd
fonte
Legal. Você poderia adicionar uma versão não-gasta e um link ideone, por favor?
precisa saber é o seguinte
Claro, eu adicionei o link no final da minha resposta.
DSVS
Verdadeiro exemplo de quão horrível pode ser um trecho de código de golfe! Pelo menos para mim.
Arjun
11
@Arjun Golfing tende a ofuscar o código. Há beleza em código golfed, mas só se você conhece a linguagem que está escrito no.
DSVS
11
Eu adicionei um novo exemplo porque um cenário ainda era ambíguo na descrição do problema. Felizmente, seu programa ainda funciona corretamente nesse caso também.
durron597