fundo

Nonogram , também conhecido como Picross ou Griddlers, é um quebra-cabeça em que o objetivo é determinar se cada célula na grade 2D deve ser colorida ou deixada em branco, usando o número de células coloridas consecutivas em cada linha.

A seguir, é apresentado um exemplo de quebra-cabeça Nonogram com solução.

O problema é que alguns jogos / aplicativos móveis Nonogram comerciais têm quebra-cabeças que não podem ser solucionados manualmente (por exemplo, possuem várias soluções ou exigem um retorno profundo). No entanto, eles também oferecem algumas vidas ao jogador, onde uma vida é perdida quando você tenta colorir uma célula cuja resposta correta está em branco . Então agora é hora de forçar com força esses "quebra-cabeças" desagradáveis!

Para simplificar a tarefa, imagine apenas uma linha com sua pista e nada mais:

3 7 | _ _ _ _ _  _ _ _ _ _  _ _ _ _ _

O [3,7]são as pistas, e o comprimento da linha é de 15 células. Como possui várias soluções possíveis, precisamos arriscar algumas vidas para resolver completamente essa linha (ou seja, determinar todas as células coloridas).

Desafio

Dada uma linha com pistas (uma lista de números inteiros positivos) e o comprimento da linha, encontre o número máximo de vidas que você perderá, assumindo que você força a linha com força, com uma estratégia ideal.

Observe que você sempre adivinha células coloridas . Em jogos reais, adivinhar células vazias (certas ou erradas) não afeta sua vida; portanto, você não pode "resolver" o quebra-cabeça dessa maneira.

Além disso, você pode assumir que a entrada sempre representa uma linha Nonogram válida, para que você não precise se preocupar com algo parecido [6], 5.

Explicação

Vejamos alguns exemplos mais simples primeiro.

[1,2], 5

Existem exatamente três possibilidades para essa linha ( Oé uma célula colorida, .é uma célula vazia):

O . O O .
O . . O O
. O . O O

Se tentarmos colorir a célula 0 (índice baseado em 0 da esquerda), acontece um dos seguintes:

• A célula está colorida corretamente. Agora, temos duas possibilidades e podemos escolher entre as células 2 e 4 para resolver completamente a linha. Em ambos os casos, perderemos uma vida no pior caso.
• A célula está vazia e perdemos uma vida. Nesse caso, já identificamos a solução exclusiva para essa linha, então terminamos com 1 vida perdida.

Portanto, a resposta para [1,2], 5é 1.

[5], 10

Pesquisa binária? Não.

A primeira escolha mais óbvia é 4 ou 5, o que revelará uma possibilidade se estiver em branco (a um custo de 1 ponto de vida). Digamos que escolhemos 4 primeiro. Se a célula 4 for realmente colorida, nós a estenderemos para a esquerda, ou seja, tente 3, 2, 1 e 0 até que uma vida seja perdida (ou a célula 0 seja colorida, acabamos sem passar nenhuma vida). Sempre que uma vida é perdida, podemos determinar exclusivamente a solução, por exemplo, se virmos algo assim:

_ _ X O O _ _ _ _ _

já sabemos que a resposta é esta:

. . . O O O O O . .

Portanto, a resposta para [5], 10também é 1.

[3,7], 15

Comece com a célula 11, que, se vazia, revelará a solução a seguir imediatamente.

O O O . O O O O O O O X . . .

Em seguida, tente 12, que, se vazio, oferece duas possibilidades que podem ser resolvidas ao custo de 1 vida útil extra.

O O O . . O O O O O O O X . .
. O O O . O O O O O O O X . .

Agora tente 2. Se vazio, ele leva a três possibilidades que podem ser resolvidas de maneira semelhante ao [1,2], 5exemplo.

. . X O O O . O O O O O O O .
. . X O O O . . O O O O O O O
. . X . O O O . O O O O O O O

Se você continuar minimizando o risco dessa maneira, poderá encontrar qualquer solução com no máx. 2 vidas gastas.

Casos de teste

[1,2] 5 => 1
[2] 5 => 2
[1] 5 => 4
[] 5 => 0
[5] 10 => 1
[2,1,5] 10 => 0
[2,4] 10 => 2
[6] 15 => 2
[5] 15 => 2
[4] 15 => 3
[3,7] 15 => 2
[3,4] 15 => 3
[2,2,4] 15 => 4
[1,1,1,1,1,1,1] 15 => 2

[2,1,1,3,1] 15 => 3
[1,1,1,2,1] 15 => 5

Nos dois últimos casos, a estratégia ideal não é passar pelos espaços em branco mínimos, mas simplesmente ir da esquerda para a direita (ou da direita para a esquerda). Obrigado a @crashoz por apontar isso.

Regras

Aplicam-se as regras de código-golfe padrão . O menor envio válido em bytes vence.

Recompensa

Se alguém criar um algoritmo de tempo polinomial (com a prova de correção), concederei +100 de recompensa a essa solução.

Ruby , 85 bytes

f=->l,n,s=n-l.sum-l.size+1{*a,b=l;b&&s>0?(a[0]?1+f[a,n-b-2,s-1]:(n.to_f/b).ceil-1):0}

Experimente online!

Explicação

$l=[l_1,l_2,...,l_x]$$x$$n$

$l_x$
$n-l_x$
$n-l_x$$1+f(l,n-l_x)$
$1+f(\tilde{l},n-l_x-2)$$\tilde{l}$$l$

$$f(l,n)=\begin{cases} 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\ \lceil \frac{n}{l_x} \rceil - 1 & \text{if } x= 1\\ 1+\max\begin{cases} f(l,n-l_x)\\ f(\tilde{l},n-l_x-2) \end{cases}, & \text{otherwise} \end{cases}$$

Aqui está um exemplo _são desconhecidos, Xé um espaço conhecido, Oé uma célula colorida conhecida e Lsua vida é perdida

[2,2,4] 15                  _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
(1) -> [2,2,4] 11           _ _ _ _ _ _ _ _ _ _ _ L X X X
    (1) -> [2,2,4] 7        _ _ _ _ _ _ _ L X X X L X X X
        0                   X X X L X X X L X X X L X X X
    (2) -> [2,2] 5          _ _ _ _ _ X O O O O L L X X X
        0                   O O X O O X O O O O L L X X X 
(2) -> [2,2] 9              _ _ _ _ _ _ _ _ _ X O O O O L
    (1) -> [2,2] 7          _ _ _ _ _ _ _ L X X O O O O L
        (1) -> [2,2] 5      _ _ _ _ _ L X L X X O O O O L
            0               O O X O O L X L X X O O O O L
        (2) -> [2] 3        _ _ _ X O O L L X X O O O O L
            1               O O L X O O L L X X O O O O L               
    (2) -> [2] 5            _ _ _ _ _ X O O L X O O O O L
        2                   O O L L X X O O L X O O O O L

Faz uma árvore binária, para obter o número de vidas perdidas, precisamos apenas contar a altura máxima da árvore. No entanto, isso o torna porque avaliamos todos os ramos. Nós podemos fazer melhor.$\mathcal{O}(2^n)$

Vamos definir uma função de custo que nos ajude a "escolher" o ramo certo em cada etapa.$h$

$$h(l,n)=n - \sum_1^xl_i-x+1$$

$h$ conta o número de espaços superficiais que temos se agruparmos todas as pistas com um espaço no meio. Portanto, é essencialmente um indicador de quantas vidas precisaremos resolver a instância, quanto maior, mais vidas serão necessárias. A idéia é aplicar esse indicador em nossa fórmula recursiva.

Por definição de , temos, $h$

$$\begin{align} h(l,n-l_x) &= n - l_x - \sum_1^xl_i-x+1\\ & =(n - \sum_1^xl_i-x+1) - l_x\\ & = h(l,n) - l_x \end{align}$$

E,

$$\begin{align} h(\tilde{l},n-l_x-2) &= n - l_x - 2 - \sum_1^{x-1}l_i-(x-1)+1\\ & =(n - \sum_1^xl_i-x+1) - 1\\ & = h(l,n) - 1 \end{align}$$

Então,

$$h(l,n)=\begin{cases} \leq 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\ n - l_x, & \text{if } x=1\\ \max\begin{cases} h(l,n-l_x)+l_x\\ h(\tilde{l},n-l_x-2)+1 \end{cases}, & \text{otherwise} \end{cases}$$

Queremos maximizar em cada etapa para obter o pior caso, então vamos verificar a diferença entre as duas expressões na recorrência$h$

$$[h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1]\\ \begin{align} &= n-l_x-n - \sum_1^xl_i-x+1 + l_x - [n-l_x-2 -\sum_1^{x-1}l_i-(x-1)+1+1]\\ &=-2 \end{align}$$

$$\begin{align} [h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1] &=-2\\ [h(l,n-l_x)+l_x] - [h(\tilde{l},n-l_x-2)+1] &< 0\\ [h(l,n-l_x)+l_x] &< [h(\tilde{l},n-l_x-2)+1] \end{align}$$ Portanto, a segunda expressão é sempre o máximo, podemos remover a primeira

$$h(l,n)=\begin{cases} \leq 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\ n - l_x, & \text{if } x=1\\ h(\tilde{l},n-l_x-2)+1 & \text{otherwise} \end{cases}$$

Finalmente, essa definição recursiva de mostra que a opção (2) na função é sempre o pior caso (fornecendo o número máximo de possibilidades, ou seja, maximizando )$h$$f$$h$

$$f(l,n)=\begin{cases} 0, & \text{if } \sum_1^xl_i+x-1 \geq n\\ \lceil \frac{n}{l_x} \rceil - 1 & \text{if } x= 1\\ 1+ f(\tilde{l},n-l_x-2), & \text{otherwise} \end{cases}$$

A cada passo, diminuímos em pelo menos 3 e agora há uma única chamada recursiva, a complexidade éO ( n $n$$\mathcal{O}(n)$

Python, 303 289 bytes

Primeiro golfe há muito tempo, portanto pode haver muito excesso de gordura. (Obrigado Jo King por encontrar 14 bytes de valor.)

A função f gera todos os arranjos possíveis (embora sempre com um espaço em branco como o primeiro caractere, mas tudo bem, desde que incrementemos o comprimento em 1 antes de chamá-lo). A função g seleciona a posição com o menor número de espaços em branco e se repete. A função h os une.

f=lambda l,n:["."*i+"X"*l[0]+c for i in range(1,n-l[0]+1)for c in f(l[1:],n-i-l[0])]if l else["."*n]
def g(q,n):O,X=min([[[p[:i]+p[i+1:]for p in q if p[i]==u]for u in".X"]for i in range(n)],key=lambda x:len(x[0]));return(len(q)>1)*1and max(1+g(O,n-1),g(X,n-1))
h=lambda l,n:g(f(l,n+1),n+1)

Todos os exemplos funcionam bem:

>>> h([3,7],15)
2
>>> h([3,4],15)
3
>>> h([1,1,1,2,1],15)
6