Fondo

Nonogram , también conocido como Picross o Griddlers, es un rompecabezas en el que el objetivo es determinar si cada celda de la cuadrícula 2D debe colorearse o dejarse en blanco, utilizando los números de celdas coloreadas consecutivas en cada línea.

El siguiente es un ejemplo de rompecabezas de Nonogram con solución.

El problema es que algunos juegos comerciales de Nonogram / aplicaciones móviles tienen rompecabezas que no se pueden resolver a mano (por ejemplo, tienen múltiples soluciones o requieren un seguimiento profundo). Sin embargo, también ofrecen algunas vidas al jugador, donde se pierde una vida cuando intentas colorear una celda cuya respuesta correcta está en blanco . ¡Así que ahora es el momento de imponer esos desagradables "rompecabezas"!

Para simplificar la tarea, imagine solo una línea con su pista y nada más:

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

El [3,7]son las pistas, y la longitud de línea es de 15 células. Dado que tiene múltiples soluciones posibles, necesitamos arriesgar algunas vidas para resolver completamente esta línea (es decir, determinar todas las celdas coloreadas).

Reto

Dada una línea con pistas (una lista de enteros positivos) y la longitud de la línea, encuentre el número máximo de vidas que perderá, suponiendo que fuerza la línea con la estrategia óptima.

Tenga en cuenta que siempre adivina las celdas de colores . En los juegos reales, adivinar celdas vacías (correctas o incorrectas) no tiene ningún efecto en sus vidas, por lo que no puede "resolver" el rompecabezas de esa manera.

Además, puede suponer que la entrada siempre representa una línea válida de Nonogram, por lo que no necesita preocuparse por algo así [6], 5.

Explicación

Veamos primero algunos ejemplos más simples.

[1,2], 5

Hay exactamente tres posibilidades para esta línea ( Oes una celda de color, .está vacía):

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

Si intentamos colorear la celda 0 (índice basado en 0 desde la izquierda), sucede uno de los siguientes:

• La celda está correctamente coloreada. Ahora tenemos dos posibilidades, y podemos elegir entre la celda 2 y la celda 4 para resolver completamente la línea. En cualquier caso, perderemos una vida en el peor de los casos.
• La celda está vacía y perdemos una vida. En este caso, ya hemos identificado la solución única para esta línea, por lo que hemos terminado con 1 vida perdida.

Por lo tanto, la respuesta para [1,2], 5es 1.

[5], 10

¿Búsqueda binaria? No

La primera opción más obvia es 4 o 5, lo que revelará una posibilidad si está en blanco (a un costo de 1 vida). Digamos que elegimos 4 primero. Si la celda 4 está coloreada, la extendemos a la izquierda, es decir, intente 3, 2, 1 y 0 hasta que se pierda una vida (o la celda 0 esté coloreada, entonces terminamos sin gastar ninguna vida). Cada vez que se pierde una vida, podemos determinar de manera única la solución, por ejemplo, si vemos algo como esto:

_ _ X O O _ _ _ _ _

entonces ya sabemos que la respuesta es esta:

. . . O O O O O . .

Por lo tanto, la respuesta para [5], 10es también 1.

[3,7], 15

Comience con la celda 11, que, si está vacía, revelará la siguiente solución de inmediato.

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

Luego pruebe 12, que, si está vacío, ofrece dos posibilidades que pueden resolverse a costa de 1 vida extra.

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

Ahora intente 2. Si está vacío, da lugar a tres posibilidades que pueden resolverse de manera similar al [1,2], 5ejemplo.

. . 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 sigue minimizando el riesgo de esta manera, puede alcanzar cualquier solución con un máx. 2 vidas gastadas.

Casos de prueba

[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

Para los últimos dos casos, la estrategia óptima no es pasar por los espacios en blanco mínimos, sino simplemente ir de izquierda a derecha (o de derecha a izquierda). Gracias a @crashoz por señalarlo.

Reglas

Se aplican reglas estándar de código de golf . El envío válido más corto en bytes gana.

Generosidad

Si a alguien se le ocurre un algoritmo de tiempo polinómico (con la prueba de corrección), otorgaré una recompensa de +100 a dicha solución.

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}

Pruébalo en línea!

Explicación

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

Aquí hay un ejemplo _desconocido, Xes un espacio conocido, Oes una celda de color conocida y Lse pierde la vida

[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

Hace un árbol binario, para obtener la cantidad de vidas perdidas, solo necesitamos contar la altura máxima del árbol. Sin embargo, esto lo hace porque evaluamos todas las ramas. Podemos hacerlo mejor.$\mathcal{O}(2^n)$

Definamos una función de costo que nos ayudará a "elegir" la rama correcta en cada paso.$h$

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

$h$ cuenta el número de espacios superfugos que tenemos si empaquetamos todas las pistas con un espacio en el medio. Por lo tanto, es esencialmente un indicador de cuántas vidas necesitaremos para resolver la instancia, cuanto más alta sea, más vidas serán necesarias. La idea es aplicar este indicador en nuestra fórmula recursiva.

Por definición de tenemos, $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}$$

Y,

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

Entonces,

$$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 en cada paso para obtener el peor de los casos, así que verifiquemos la diferencia entre las dos expresiones en la recurrencia$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}$$ Entonces la segunda expresión es siempre el máximo, podemos eliminar la primera

$$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, esta definición recursiva de nos muestra que la opción (2) en la función es siempre el peor de los casos (dando el número máximo de posibilidades, es decir, 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}$$

Cada paso disminuimos en al menos 3 y ahora hay una sola llamada recursiva, la complejidad es$n$$\mathcal{O}(n)$

Python, 303 289 bytes

Primer golf en mucho tiempo, por lo que puede haber mucho exceso de grasa. (Gracias, Jo King, por encontrar 14 bytes).

La función f genera todos los arreglos posibles (aunque siempre con un espacio en blanco como primer carácter, pero está bien siempre que incrementemos la longitud en 1 antes de llamarlo). La función g selecciona la posición con el menor número de espacios en blanco y recursivos. La función h los pone juntos.

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 los ejemplos funcionan bien:

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