Вы можете соединить точки?

18

Эта задача основана на Flow Free. Онлайн-версию можно найти здесь: http://www.moh97.us/

Вам дадут головоломку, и вы должны вернуться, 1если головоломка разрешима или 0если нет.

Чтобы решить головоломку, игрок должен создать путь, соединяющий каждую пару чисел, используя каждый пустой квадрат ровно один раз.

Вы передаете размеры квадрата, а затем x, y, c (где c - число, представляющее цвет) каждой точки. Например:

Если бы он 5,5 0,0,0 3,0,1 1,1,2 1,2,2 4,2,1 4,4,0был передан вам, он бы представлял:

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

И должен вернуть 1.


Вот еще несколько тестовых задач:

5,2 2,0,1 0,1,2 4,1,2 представляет:

..1..
2...2

и не разрешима, потому что есть только 1 1.

4,2 0,0,0 3,0,0 0,1,0 3,1,0 представляет:

0..0
0..0

и не разрешима, потому что включает в себя более 2 0с.

8,6 0,0,1 7,5,1 представляет:

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

и не решаемо (так как вы не можете использовать каждый квадрат).

2,5 0,0,1 2,0,6 4,0,6 0,1,4 3,1,4 4,1,1 представляет:

1.6.6
4..41

и не разрешим, потому что вы не можете подключить 1.

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 представляет:

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

и не разрешима, потому что вы не можете соединить 1 (или 3), так как два пути обязательно должны пересекаться.

5,2 0,0,1 3,0,1 0,1,3 4,1,1 представляет:

1..1.
3...3

и не разрешима, потому что вы не можете использовать все квадраты при построении пути.

2,2 0,0,0 1,1,0 представляет:

1.
.1

и не разрешим, потому что вы не можете использовать все квадраты здесь

Вот еще несколько тестов:

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 должен вернуть 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 должен вернуть 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 должен вернуть 0


Это код гольф, и применяются стандартные правила.

Натан Меррилл
источник
2
Должно ли решение быть «реалистичным» или просто теоретически правильным? Например, пространство состояний может быть разбито на назначение одной из 6 возможных конфигураций ввода-вывода для каждой пустой ячейки. Разрешимость легко определяется путем попытки всех 6 ^ N комбинаций и возврата, 1если какая-либо из них посещает все ячейки и соединяет все терминалы. Очевидно, что этот подход не будет завершен за разумное количество времени ни для чего, кроме самого маленького N(количество пустых ячеек), но у нас все еще есть математическая гарантия того, что алгоритм в конечном итоге вернет правильное значение.
COTO
1
Возможно, если вы придумали два огромных набора игровых сеток (одну общедоступную для тестирования, одну закрытую для проверки) с использованием общего алгоритма и посчитали, что победителем является представление, которое правильно определило разрешимость большинства сеток в частном наборе в некоторых разумное количество времени на сетку, с размером программы в качестве тай-брейка, если два представления имели одинаковую полезность. Я определенно попробую свои силы в этом.
COTO
1
@NathanMerrill: проблема сводится к SAT и, следовательно, NP трудна.
COTO
3
@NathanMerrill, сводящий проблему к SAT, означает, что проблема в NP, а не в том, что она NP-сложная - это сводит SAT к проблеме, которая показывает NP-сложность проблемы. Однако на странице, на которую вы ссылались, есть ссылка на доказательство полноты NP.
картонная
1
@VisualMelon Цвет цифры - неправильное слово. Каждый цвет представлен другим номером, а не цифрой.
Натан Меррилл

Ответы:

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

ключ

  • sc: Seq concat
  • sp: установить положение
  • dt: тип точки (т. е. начало или конец строки)
  • объявление: добавить точку
  • ep: расширить путь
  • rd: запустить точки (основной чистый алгоритм)
Matt
источник
2
Спасибо за отправку, и добро пожаловать в обмен стека PPCG. Это задача для игры в гольф, означающая, что цель - написать самую короткую программу, которая решает эту проблему. Вы лидируете, потому что у вас есть единственный ответ, но вы должны постараться максимально сократить свою программу.
Исаак
Я искренне впечатлен, что вы ответили на этот вопрос спустя столько времени. Кроме того, эта проблема была скорее проблемой кода, но я использовал код-гольф, поскольку было сложно придумать другую основу для подсчета очков.
Натан Меррилл
Да, я не слишком беспокоился об аспекте "гольфа"; Я пытаюсь изучить Haskell, и это кажется забавной проблемой :-)
Matt