Czy potrafisz połączyć kropki?

To wyzwanie jest oparte na Flow Free. Wersja online znajduje się tutaj: http://www.moh97.us/

Dostaniesz układankę i musisz wrócić, 1jeśli układanka jest rozwiązana lub 0nie.

Aby rozwiązać zagadkę, gracz musi utworzyć ścieżkę, aby połączyć każdą parę liczb za pomocą każdego pustego kwadratu dokładnie raz.

Przechodzisz do wymiarów kwadratu, a następnie x, y, c (gdzie c jest liczbą reprezentującą kolor) każdej kropki. Na przykład:

Gdyby 5,5 0,0,0 3,0,1 1,1,2 1,2,2 4,2,1 4,4,0został ci przekazany, reprezentowałby:

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

I powinien zwrócić 1.

5,2 2,0,1 0,1,2 4,1,2 reprezentuje:

..1..
2...2

i nie można go rozwiązać, ponieważ jest tylko 1 1.

4,2 0,0,0 3,0,0 0,1,0 3,1,0 reprezentuje:

0..0
0..0

i nie można go rozwiązać, ponieważ obejmuje więcej niż 2 0sekundy.

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

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

i nie jest do rozwiązania (ponieważ nie można użyć każdego kwadratu).

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

1.6.6
4..41

i nie można go rozwiązać, ponieważ nie można połączyć 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 reprezentuje:

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

i nie można go rozwiązać, ponieważ nie można połączyć 1 (lub 3), ponieważ dwie ścieżki muszą koniecznie się przeciąć.

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

1..1.
3...3

i nie można go rozwiązać, ponieważ nie można użyć wszystkich kwadratów do zbudowania ścieżki.

2,2 0,0,0 1,1,0 reprezentuje:

1.
.1

i nie można go rozwiązać, ponieważ nie można tutaj użyć wszystkich kwadratów

Oto kilka innych testów:

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 powinien zwrócić 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 powinien zwrócić 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 powinien zwrócić 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

Klucz

• sc: Seq concat
• sp: ustaw pozycję
• dt: typ kropki (tj. początek lub koniec linii)
• ad: dodaj kropkę
• ep: przedłużyć ścieżkę
• rd: uruchom kropki (podstawowy czysty algorytm)