18
\$\begingroup\$

This challenge is based off of Flow Free. An online version can be found here: http://www.moh97.us/

You will be given a puzzle, and you must return 1 if the puzzle is solvable, or 0 if it is not.

To solve a puzzle, the player must create a path to connect each pair of numbers using every empty square exactly once.

You are passed in the dimensions of the square, and then the x,y,c (where c is a number representing the color) of each dot. For example:

If 5,5 0,0,0 3,0,1 1,1,2 1,2,2 4,2,1 4,4,0 was passed to you, it would represent:

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

And should return 1.


Here are some more test problems:

5,2 2,0,1 0,1,2 4,1,2 represents:

..1..
2...2

and is not solvable because there is only 1 1.

4,2 0,0,0 3,0,0 0,1,0 3,1,0 represents:

0..0
0..0

and is not solvable because it includes more than 2 0s.

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

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

and is not solvable (as you can't use every square).

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

1.6.6
4..41

and is not solvable because you cannot connect the 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 represents:

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

and is not solvable because you cannot connect the 1s (or the 3s), as the two paths must necessarily cross.

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

1..1.
3...3

and is not solvable because you cannot use all of the squares in building a path.

2,2 0,0,0 1,1,0 represents:

1.
.1

and is not solvable because you can't use all of the squares here either

Here are some more 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 should return 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 should return 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 should return 0


This is a code golf, and the standard rules apply.

\$\endgroup\$
  • 2
    \$\begingroup\$ Does a solution have to be "realistically" correct or just theoretically correct? For instance, the state space can be broken down into assigning one of 6 possible input-to-input configurations to each empty cell. Solvability is easily determined by attempting all 6^N combinations and returning 1 if any one of them visits all cells and connects all terminals. Obviously this approach wouldn't complete in a reasonable amount of time for anything but the smallest N (number of empty cells), but we still have a mathematical guarantee that the algorithm would eventually return the correct value. \$\endgroup\$ – COTO Sep 30 '14 at 17:46
  • 1
    \$\begingroup\$ Perhaps if you came up with two huge sets of playing grids (one public for testing, one private for validation) using a common algorithm and deemed the winner to be the submission that correctly identified the solvability of the most grids in the private set in some reasonable amount of time per grid, with program size as a tiebreaker if two submissions had equal utility. I'd definitely try my hand at that. \$\endgroup\$ – COTO Oct 1 '14 at 13:33
  • 1
    \$\begingroup\$ @NathanMerrill: The problem is reducible to SAT and thus NP hard. \$\endgroup\$ – COTO Oct 1 '14 at 17:13
  • 3
    \$\begingroup\$ @NathanMerrill reducing a problem to SAT means that the problem is in NP, not that it is NP-hard -- it's reducing SAT to a problem that shows NP-hardness of the problem. The page you linked to does have a link to a proof of NP-completeness though. \$\endgroup\$ – cardboard_box Oct 2 '14 at 14:47
  • 1
    \$\begingroup\$ @VisualMelon Digit color is the wrong word. Each color is represented by a different number, not digit. \$\endgroup\$ – Nathan Merrill Apr 16 '15 at 16:03
3
\$\begingroup\$

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

Key

  • sc: Seq concat
  • sp: set position
  • dt: dot type (ie, start or end of line)
  • ad: add dot
  • ep: extend path
  • rd: run dots (primary pure algorithm)
\$\endgroup\$
  • 2
    \$\begingroup\$ Thanks for the submission, and welcome to PPCG stack exchange. This is a code golf challenge, meaning the purpose is to write the shortest program which solves the challenge. You're in the lead, because you have the only answer, but you should try to shorten your program as much as possible. \$\endgroup\$ – isaacg May 25 '15 at 1:13
  • \$\begingroup\$ I'm honestly impressed that you answered this question after all this time. Also, this problem was more of a code-challenge, but I used code-golf, as it was hard to come up with a different scoring basis. \$\endgroup\$ – Nathan Merrill May 25 '15 at 14:03
  • \$\begingroup\$ Yes, I didn't worry too much about the "golf" aspect; I'm trying to learn Haskell and it seemed like a fun problem :-) \$\endgroup\$ – Matt May 26 '15 at 15:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.