Kannst du die Punkte verbinden?

18

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.


Hier sind einige weitere Testprobleme:

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


Dies ist ein Codegolf und es gelten die Standardregeln.

Nathan Merrill
quelle
2
Muss eine Lösung "realistisch" oder nur theoretisch korrekt sein? Beispielsweise kann der Zustandsraum unterteilt werden, indem jeder leeren Zelle eine von 6 möglichen Eingabe-Eingabe-Konfigurationen zugewiesen wird. Die Lösbarkeit lässt sich leicht bestimmen, indem alle 6 ^ N-Kombinationen ausprobiert und zurückgegeben werden, 1wenn eine davon alle Zellen besucht und alle Terminals verbindet. Offensichtlich würde dieser Ansatz für nichts anderes als die kleinste N(Anzahl der leeren Zellen) in angemessener Zeit abgeschlossen sein , aber wir haben immer noch eine mathematische Garantie dafür, dass der Algorithmus schließlich den richtigen Wert zurückgibt.
COTO
1
Vielleicht, wenn Sie mit einem gemeinsamen Algorithmus zwei große Sätze von Spielgittern (ein öffentliches zum Testen, ein privates zur Validierung) erstellt haben und als Sieger die Einsendung angesehen haben, die in einigen Fällen die Lösbarkeit der meisten Gitter im privaten Satz korrekt identifizierte angemessene Zeit pro Raster, mit Programmgröße als Tiebreaker, wenn zwei Einreichungen den gleichen Nutzen hatten. Ich würde auf jeden Fall meine Hand versuchen.
COTO
1
@ NathanMerrill: Das Problem ist auf SAT und damit NP schwer zu reduzieren .
COTO
3
@NathanMerrill Reduzieren eines Problems auf SAT bedeutet, dass das Problem in NP vorliegt, nicht in NP-schwer. Es reduziert SAT auf ein Problem, das die NP-Härte des Problems anzeigt. Die Seite, auf die Sie verlinkt haben, enthält jedoch einen Link zum Nachweis der NP-Vollständigkeit.
cardboard_box
1
@VisualMelon Ziffernfarbe ist das falsche Wort. Jede Farbe wird durch eine andere Nummer dargestellt, nicht durch eine Ziffer.
Nathan Merrill

Antworten:

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

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)
Matt
quelle
2
Vielen Dank für die Einreichung und willkommen bei PPCG Stack Exchange. Dies ist eine Code-Golf-Herausforderung, das heißt, der Zweck ist, das kürzeste Programm zu schreiben, das die Herausforderung löst. Sie haben die Nase vorn, denn Sie haben die einzige Antwort, aber Sie sollten versuchen, Ihr Programm so weit wie möglich zu verkürzen.
isaacg
Ich bin ehrlich beeindruckt, dass Sie diese Frage nach all der Zeit beantwortet haben. Auch dieses Problem war eher eine Code-Herausforderung, aber ich verwendete Code-Golf, da es schwierig war, eine andere Bewertungsgrundlage zu finden.
Nathan Merrill
Ja, ich habe mich nicht zu sehr um den "Golf" -Aspekt gekümmert. Ich versuche Haskell zu lernen und es schien ein lustiges Problem zu sein :-)
Matt