Você pode conectar os pontos?

18

Esse desafio é baseado no Flow Free. Uma versão online pode ser encontrada aqui: http://www.moh97.us/

Você receberá um quebra-cabeça e deverá retornar 1se o quebra-cabeça for solucionável ou 0não.

Para resolver um quebra-cabeça, o jogador deve criar um caminho para conectar cada par de números usando cada quadrado vazio exatamente uma vez.

Você passa nas dimensões do quadrado e depois x, y, c (onde c é um número que representa a cor) de cada ponto. Por exemplo:

Se 5,5 0,0,0 3,0,1 1,1,2 1,2,2 4,2,1 4,4,0foi passado para você, representaria:

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

E deve retornar 1.


Aqui estão mais alguns problemas de teste:

5,2 2,0,1 0,1,2 4,1,2 representa:

..1..
2...2

e não é solucionável porque existe apenas 1 1.

4,2 0,0,0 3,0,0 0,1,0 3,1,0 representa:

0..0
0..0

e não é solucionável porque inclui mais de 2 0s.

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

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

e não é solucionável (como você não pode usar todos os quadrados).

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

e não é solucionável porque você não pode conectar os 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

e não é solucionável porque você não pode conectar os 1s (ou os 3s), pois os dois caminhos devem necessariamente se cruzar.

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

1..1.
3...3

e não é solucionável porque você não pode usar todos os quadrados na construção de um caminho.

2,2 0,0,0 1,1,0 representa:

1.
.1

e não é solucionável porque você não pode usar todos os quadrados aqui também

Aqui estão mais alguns testes:

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 deve retornar 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 deve retornar 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 deve retornar 0


Este é um código de golfe e as regras padrão se aplicam.

Nathan Merrill
fonte
2
Uma solução precisa ser "realisticamente" correta ou apenas teoricamente correta? Por exemplo, o espaço de estado pode ser dividido em atribuir uma das 6 configurações possíveis de entrada a entrada para cada célula vazia. A resolubilidade é facilmente determinada tentando todas as combinações de 6 ^ N e retornando 1se alguma delas visitar todas as células e conectar todos os terminais. Obviamente, essa abordagem não seria concluída em um período de tempo razoável para nada além do menor N(número de células vazias), mas ainda temos uma garantia matemática de que o algoritmo retornaria o valor correto.
COTO 30/09
1
Talvez se você tivesse dois conjuntos enormes de grades de jogo (uma pública para teste e outra privada para validação) usando um algoritmo comum e considerasse o vencedor a submissão que identificou corretamente a resolubilidade da maioria das grades no conjunto privado em alguns quantidade razoável de tempo por grade, com o tamanho do programa como desempatador se dois envios tiverem a mesma utilidade. Eu definitivamente tentaria minha mão nisso.
COTO
1
@ NathanMerrill: O problema é redutível ao SAT e, portanto, ao NP.
COTO
3
@NathanMerrill reduzir um problema para SAT significa que o problema está no NP, não que seja difícil para o NP - está reduzindo o SAT para um problema que mostra a dureza do NP do problema. A página à qual você vinculou possui um link para uma prova de integridade do NP.
cardboard_box
1
@VisualMelon Digit color é a palavra errada. Cada cor é representada por um número diferente, não por dígito.
19415 Nathan Merrill

Respostas:

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

Chave

  • sc: Seq concat
  • sp: posição definida
  • dt: tipo de ponto (ou seja, início ou fim da linha)
  • anúncio: adicionar ponto
  • ep: estender o caminho
  • rd: pontos de execução (algoritmo puro primário)
Matt
fonte
2
Obrigado pela apresentação e bem-vindo à troca de pilhas do PPCG. Este é um desafio de código de golfe, o que significa que o objetivo é escrever o programa mais curto que resolve o desafio. Você está na liderança, porque tem a única resposta, mas deve tentar reduzir o seu programa o máximo possível.
Isaacg 25/05
Sinceramente, estou impressionado que você tenha respondido a essa pergunta depois de todo esse tempo. Além disso, esse problema foi mais um desafio para o código, mas eu usei o code-golf, pois era difícil criar uma base de pontuação diferente.
Nathan Merrill
Sim, não me preocupei muito com o aspecto "golfe"; Eu estou tentando aprender Haskell e parecia que um problema divertido :-)
Matt