Kannst du die Punkte verbinden?

Diese Herausforderung basiert auf Flow Free. Eine Online-Version finden Sie hier: http://www.moh97.us/

Sie erhalten ein Puzzle und müssen zurückkehren, 1wenn das Puzzle lösbar ist oder 0nicht.

Um ein Rätsel zu lösen, muss der Spieler einen Pfad erstellen, um jedes Zahlenpaar mit jedem leeren Quadrat genau einmal zu verbinden.

Sie werden in den Dimensionen des Quadrats übergeben und dann die x, y, c (wobei c eine Zahl ist, die die Farbe darstellt) jedes Punkts. Beispielsweise:

Wenn 5,5 0,0,0 3,0,1 1,1,2 1,2,2 4,2,1 4,4,0an Sie übergeben wurde, würde dies Folgendes darstellen:

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

Und sollte 1 zurückgeben.

5,2 2,0,1 0,1,2 4,1,2 repräsentiert:

..1..
2...2

und ist nicht lösbar, weil es nur 1 gibt 1.

4,2 0,0,0 3,0,0 0,1,0 3,1,0 repräsentiert:

0..0
0..0

und ist nicht lösbar, da es mehr als 2 0s umfasst.

8,6 0,0,1 7,5,1 repräsentiert:

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

und ist nicht lösbar (da Sie nicht jedes Quadrat verwenden können).

2,5 0,0,1 2,0,6 4,0,6 0,1,4 3,1,4 4,1,1 repräsentiert:

1.6.6
4..41

und ist nicht lösbar, weil Sie die 1s nicht verbinden können.

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 repräsentiert:

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

und ist nicht lösbar, weil Sie die 1 (oder die 3) nicht verbinden können, da sich die beiden Pfade unbedingt kreuzen müssen.

5,2 0,0,1 3,0,1 0,1,3 4,1,1 repräsentiert:

1..1.
3...3

und ist nicht lösbar, da Sie nicht alle Quadrate zum Erstellen eines Pfades verwenden können.

2,2 0,0,0 1,1,0 repräsentiert:

1.
.1

und ist nicht lösbar, weil Sie auch hier nicht alle Quadrate verwenden können

Hier sind einige weitere Tests:

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 sollte 1 zurückgeben

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 sollte 1 zurückgeben

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 sollte 0 zurückgeben

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

Schlüssel

• sc: Seq concat
• sp: Position einstellen
• dt: Punkttyp (dh Anfang oder Ende der Linie)
• Anzeige: Punkt hinzufügen
• ep: Pfad verlängern
• rd: run dots (primärer reiner Algorithmus)