Resolución de fuerza bruta de línea no monográfica

25

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

Bubbler
fuente
¿Para qué es la salida prevista [6], 5?
Leaky Nun
Cuando adivina, ¿tiene que adivinar que la celda es negra o puede adivinar si es negra o blanca?
feersum
@LeakyNun Es una línea no válida. Puede suponer que la entrada siempre es una línea de Nonograma válida.
Bubbler
@feersum Siempre adivinas celdas de colores. En los juegos reales, adivinar una celda vacía (correcta o incorrecta) no tiene ningún efecto en sus vidas, por lo que no puede obtener ningún comentario al respecto.
Bubbler
Fantástico desafío
Enrico Borba

Respuestas:

19

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=[l1,l2,...,lx]xn

lx
nlx
nlx1+f(l,nlx)
1+f(l~,nlx2)l~l

f(l,n)={0,if 1xli+x1nnlx1if x=11+max{f(l,nlx)f(l~,nlx2),otherwise

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.O(2n)

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

h(l,n)=n1xlix+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

h(l,nlx)=nlx1xlix+1=(n1xlix+1)lx=h(l,n)lx

Y,

h(l~,nlx2)=nlx21x1li(x1)+1=(n1xlix+1)1=h(l,n)1

Entonces,

h(l,n)={0,if 1xli+x1nnlx,if x=1max{h(l,nlx)+lxh(l~,nlx2)+1,otherwise

Queremos maximizar en cada paso para obtener el peor de los casos, así que verifiquemos la diferencia entre las dos expresiones en la recurrenciah

[h(l,nlx)+lx][h(l~,nlx2)+1]=nlxn1xlix+1+lx[nlx21x1li(x1)+1+1]=2

[h(l,nlx)+lx][h(l~,nlx2)+1]=2[h(l,nlx)+lx][h(l~,nlx2)+1]<0[h(l,nlx)+lx]<[h(l~,nlx2)+1]
Entonces la segunda expresión es siempre el máximo, podemos eliminar la primera

h(l,n)={0,if 1xli+x1nnlx,if x=1h(l~,nlx2)+1otherwise

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 )hfh

f(l,n)={0,if 1xli+x1nnlx1if x=11+f(l~,nlx2),otherwise

Cada paso disminuimos en al menos 3 y ahora hay una sola llamada recursiva, la complejidad esnO(n)

crashoz
fuente
2
¡Bienvenido a PPCG, increíble primer post!
cole
1
@cole No es su primera publicación, ¡pero seguramente es increíble! Enfoque muy inteligente +1
Sr. Xcoder
1
Impresionante trabajo. Otorgaré la recompensa 2 días después, si nadie encuentra algún defecto lógico serio hasta entonces.
Bubbler
2

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
Uri Granta
fuente
1
¿Se le permite volver Falsea 0? Si es así, puede cambiar (len(q)>1)*1anda len(q)>1and. Si no se le permite regresar Falsepara 0, a continuación, hacer eso, pero el cambio g(f(l,n+1),n+1)a 1*g(f(l,n+1),n+1)y aún ahorrará un byte
Zachary
1
Aún mejor: en el caso Falseno está permitido para 0, en lugar de cambiar g(f(l,n+1),n+1)a 1*g(f(l,n+1),n+1), cambie a+g(f(l,n+1),n+1)
Zachary
2
Además, no es necesario que cuente h=en el recuento de bytes
Zacharý
1
288 bytes .
Jonathan Frech