Contexte

Nonogram , également connu sous le nom de Picross ou Griddlers, est un casse-tête dont l'objectif est de déterminer si chaque cellule de la grille 2D doit être colorée ou laissée en blanc, en utilisant le nombre de cellules colorées consécutives sur chaque ligne.

Ce qui suit est un exemple de puzzle Nonogram avec solution.

Le problème est que certains jeux / applications mobiles Nonogram commerciaux ont des puzzles qui ne peuvent pas être résolus à la main (par exemple, ont plusieurs solutions ou nécessitent un retour en arrière profond). Cependant, ils offrent également des vies au joueur, où une vie est perdue lorsque vous essayez de colorer une cellule dont la bonne réponse est vide . Alors maintenant, il est temps de forcer ces "énigmes" méchantes!

Afin de simplifier la tâche, imaginez une seule ligne avec son indice et rien d'autre:

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

Le [3,7]sont les indices, et la longueur de ligne est de 15 cellules. Puisqu'il a plusieurs solutions possibles, nous devons risquer des vies afin de résoudre complètement cette ligne (c'est-à-dire déterminer toutes les cellules colorées).

Défi

Étant donné une ligne avec des indices (une liste d'entiers positifs) et la longueur de la ligne, trouvez le nombre maximum de vies que vous perdrez, en supposant que vous forcez la ligne avec une stratégie optimale.

Notez que vous devinez toujours les cellules colorées . Dans les jeux réels, deviner les cellules vides (bonnes ou mauvaises) n'a aucun effet sur votre vie, vous ne pouvez donc pas "résoudre" le puzzle de cette façon.

En outre, vous pouvez supposer que l'entrée représente toujours une ligne de Nonogram valide, vous n'avez donc pas à vous soucier de quelque chose comme [6], 5.

Explication

Voyons d'abord quelques exemples plus simples.

[1,2], 5

Il y a exactement trois possibilités pour cette ligne ( Oest une cellule colorée, .est une cellule vide):

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

Si nous essayons de colorer la cellule 0 (index basé sur 0 à partir de la gauche), l'une des situations suivantes se produit:

• La cellule est correctement colorée. Nous avons maintenant deux possibilités, et nous pouvons choisir entre la cellule 2 et la cellule 4 afin de résoudre complètement la ligne. Dans les deux cas, nous perdrons une vie dans le pire des cas.
• La cellule est vide et nous perdons une vie. Dans ce cas, nous avons déjà identifié la solution unique à cette ligne, nous avons donc terminé avec 1 vie perdue.

Par conséquent, la réponse [1,2], 5est 1.

[5], 10

Recherche binaire? Nan.

Le premier choix le plus évident est 4 ou 5, ce qui révélera une possibilité s'il est vide (au coût de 1 vie). Disons que nous avons choisi 4 en premier. Si la cellule 4 est en effet colorée, nous l'étendons vers la gauche, c'est-à-dire essayons 3, 2, 1 et 0 jusqu'à ce qu'une vie soit perdue (ou la cellule 0 est colorée, alors nous finissons par ne pas vivre du tout). Chaque fois qu'une vie est perdue, nous pouvons déterminer de manière unique la solution, par exemple si nous voyons quelque chose comme ceci:

_ _ X O O _ _ _ _ _

alors nous savons déjà que la réponse est la suivante:

. . . O O O O O . .

Par conséquent, la réponse pour [5], 10est également 1.

[3,7], 15

Commencez par la cellule 11 qui, si elle est vide, révélera immédiatement la solution suivante.

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

Essayez ensuite 12, ce qui, s'il est vide, donne deux possibilités qui peuvent être résolues au prix d'une vie supplémentaire.

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

Essayez maintenant 2. S'il est vide, cela conduit à trois possibilités qui peuvent être résolues de manière similaire à l' [1,2], 5exemple.

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

Si vous continuez à minimiser le risque de cette manière, vous pouvez atteindre n'importe quelle solution avec max. 2 vies passées.

Cas de test

[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

Pour les deux derniers cas, la stratégie optimale ne passe pas par les blancs minimum, mais simplement de gauche à droite (ou de droite à gauche). Merci à @crashoz de l'avoir signalé.

Règles

Les règles de code-golf standard s'appliquent. La soumission valide la plus courte en octets l'emporte.

Prime

Si quelqu'un propose un algorithme à temps polynomial (avec la preuve d'exactitude), j'accorderai une prime de +100 à une telle solution.

Rubis , 85 octets

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}

Essayez-le en ligne!

Explication

$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}$$

Voici un exemple _inconnu, Xun espace connu, Oune cellule colorée connue et une Lvie perdue

[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

$\mathcal{O}(2^n)$

Définissons une fonction de coût $h$

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

$h$

$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}$$

$$\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}$$

$$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}$$

$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}$$

$$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}$$

$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}$$

Chaque pas que nous diminuons $n$ d'au moins 3 et il y a maintenant un seul appel récursif, la complexité est $\mathcal{O}(n)$

Python, 303 289 octets

Premier golf depuis longtemps, donc il peut y avoir beaucoup d'excès de graisse. (Merci à Jo King d' avoir trouvé 14 octets.)

La fonction f génère tous les arrangements possibles (bien que toujours avec un blanc comme premier caractère, mais c'est bien tant que nous incrémentons la longueur de 1 avant de l'appeler). La fonction g sélectionne la position avec le moins de blancs et de répétitions. La fonction h les rassemble.

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)

Les exemples fonctionnent tous bien:

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