¿Puedes conectar los puntos?

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.

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

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)