¿Puedes conectar los puntos?

18

Este desafío se basa en Flow Free. Puede encontrar una versión en línea aquí: http://www.moh97.us/

Se le dará un rompecabezas, y debe regresar 1si el rompecabezas tiene solución, o 0si no lo es.

Para resolver un rompecabezas, el jugador debe crear una ruta para conectar cada par de números usando cada cuadrado vacío exactamente una vez.

Se te pasan las dimensiones del cuadrado y luego la x, y, c (donde c es un número que representa el color) de cada punto. Por ejemplo:

Si le 5,5 0,0,0 3,0,1 1,1,2 1,2,2 4,2,1 4,4,0fue pasado, representaría:

0..1.
.2...
.2..1
....0

Y debe devolver 1.


Aquí hay algunos problemas de prueba más:

5,2 2,0,1 0,1,2 4,1,2 representa:

..1..
2...2

y no es solucionable porque solo hay 1 1.

4,2 0,0,0 3,0,0 0,1,0 3,1,0 representa:

0..0
0..0

y no tiene solución porque incluye más de 2 0s.

8,6 0,0,1 7,5,1 representa:

1.......
........
........
........
........
.......1

y no tiene solución (ya que no puedes usar todos los cuadrados).

2,5 0,0,1 2,0,6 4,0,6 0,1,4 3,1,4 4,1,1 representa:

1.6.6
4..41

y no es solucionable porque no puede conectar los 1s.

6,3 1,0,4 5,0,1 0,1,4 1,1,3 5,1,3 0,2,2 3,2,2 5,2,1 representa:

.4...1
43...3
2..2.1

y no es solucionable porque no puede conectar los 1 (o los 3), ya que los dos caminos deben cruzarse necesariamente.

5,2 0,0,1 3,0,1 0,1,3 4,1,1 representa:

1..1.
3...3

y no se puede resolver porque no puedes usar todos los cuadrados para construir un camino.

2,2 0,0,0 1,1,0 representa:

1.
.1

y no es solucionable porque tampoco puedes usar todos los cuadrados aquí

Aquí hay algunas pruebas más:

5,5 0,3,0 0,4,1 1,2,2 1,3,1 2,0,0 3,0,4 3,1,2 3,3,5 3,4,4 4,4,5 debería devolver 1

13,13 1,1,0 9,1,1 10,1,2 11,1,3 1,2,4 2,2,5 5,2,6 7,2,7 3,3,0 5,4,6 6,4,1 9,6,3 4,7,8 5,8,9 12,8,8 11,9,10 2,10,4 4,10,2 9,10,5 11,10,7 1,11,9 12,12,10 debería devolver 1

7,7 0,0,0 0,1,1 1,1,2 2,1,3 4,2,4 0,3,1 5,3,3 0,4,4 2,4,5 5,4,2 0,5,0 1,5,5 3,5,6 3,7,6 debería devolver 0


Este es un código de golf, y se aplican las reglas estándar.

Nathan Merrill
fuente
2
¿Tiene que ser una solución "realista" correcta o teóricamente correcta? Por ejemplo, el espacio de estado se puede dividir en asignar una de las 6 posibles configuraciones de entrada a entrada a cada celda vacía. La solubilidad se determina fácilmente al intentar todas las combinaciones de 6 ^ N y regresar 1si alguna de ellas visita todas las celdas y conecta todas las terminales. Obviamente, este enfoque no se completaría en un período de tiempo razonable para nada más que el más pequeño N(número de celdas vacías), pero todavía tenemos una garantía matemática de que el algoritmo eventualmente devolverá el valor correcto.
COTO
1
Tal vez si se le ocurrieron dos grandes conjuntos de cuadrículas de juego (uno público para pruebas, otro privado para validación) utilizando un algoritmo común y consideró que el ganador fue la presentación que identificó correctamente la capacidad de solución de la mayoría de las cuadrículas en el conjunto privado en algunos cantidad de tiempo razonable por cuadrícula, con el tamaño del programa como un desempate si dos presentaciones tuvieron la misma utilidad. Definitivamente lo intentaría con eso.
COTO
1
@NathanMerrill: El problema es reducible a SAT y, por lo tanto, NP difícil.
COTO
3
@NathanMerrill reducir un problema a SAT significa que el problema está en NP, no que es NP-hard: está reduciendo SAT a un problema que muestra la dureza NP del problema. Sin embargo, la página a la que enlazó tiene un enlace a una prueba de integridad de NP.
cartón_
1
@VisualMelon El color del dígito es la palabra incorrecta. Cada color está representado por un número diferente, no por dígitos.
Nathan Merrill

Respuestas:

3

Haskell

import Data.List.Split
import qualified Data.Sequence as Q
import Data.List
import Control.Monad

data A a = S a | E a | P a | X deriving Eq

sc = foldr1 (Q.><)
sp b x y p = Q.update y (Q.update x p $ b `Q.index` y) b
dt b c | S c `elem` sc b = E c
       | otherwise = S c
ad b [x, y, c] = sp b x y (dt b c)

ep b [x, y, c] = do
  let nps = filter ob [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]
      ns = map gp nps
  [b | E c `elem` ns] ++ do
    (x', y') <- filter ((== X) . gp) nps
    ep (sp b x' y' (P c)) [x', y', c]
  where ob (u, v) = 0 <= u && u < length (b `Q.index` 0) && 0 <= v && v < length b
        gp (u, v) = b `Q.index` v `Q.index` u

rd i = let [c, r] : ps = (map read . splitOn ",") <$> words i :: [[Int]]
           e = Q.replicate r $ Q.replicate c X
           cs = map last ps
           ss = nubBy (\[_,_,c1] [_,_,c2] -> c1 == c2) ps
           b = foldl ad e ps
           bs = foldM ep b ss
       in if even (length cs) && length ss == length cs `div` 2 &&
             (all (\[j,k] -> j==k) . chunksOf 2 . sort $ cs) &&
             any (null . Q.elemIndicesL X . sc) bs
           then 1
           else 0

main = rd <$> getContents >>= print

Llave

  • sc: Seq concat
  • sp: posición establecida
  • dt: tipo de punto (es decir, inicio o final de línea)
  • anuncio: agregar punto
  • ep: extender el camino
  • rd: ejecutar puntos (algoritmo puro primario)
Mate
fuente
2
Gracias por el envío y bienvenido al intercambio de pila PPCG. Este es un desafío de código de golf, lo que significa que el propósito es escribir el programa más corto que resuelva el desafío. Usted está a la cabeza, porque tiene la única respuesta, pero debe intentar acortar su programa tanto como sea posible.
isaacg
Estoy sinceramente impresionado de que hayas respondido esta pregunta después de todo este tiempo. Además, este problema era más un desafío de código, pero usé código de golf, ya que era difícil encontrar una base de puntuación diferente.
Nathan Merrill
Sí, no me preocupé demasiado por el aspecto del "golf"; Estoy tratando de aprender Haskell y me pareció un problema divertido :-)
Matt