Cleaned up the tests

abhin4v · abhin4v · commit 7377f525071d · 2013-12-29T15:30:09.000+05:30
diff --git a/A_Star_Search/Haskell/abhin4v/AStarSearch_test.hs b/A_Star_Search/Haskell/abhin4v/AStarSearch_test.hs
@@ -1,10 +1,11 @@
-{-# LANGUAGE TemplateHaskell #-}
+{-# LANGUAGE TemplateHaskell, GeneralizedNewtypeDeriving #-}
 
 module AStarSearchTest where
 
 import AStarSearch
+import Data.Hashable (Hashable)
 import Data.List (foldl')
-import Data.Maybe (fromJust)
+import Data.Maybe (fromJust, fromMaybe)
 import Data.Sequence ((|>))
 import Test.QuickCheck
 import Test.QuickCheck.All
@@ -14,24 +15,24 @@ import qualified Data.Sequence as Seq
 -- We use A* search to find the shortest path (path with least number of moves) of a knight
 -- from a start square to a goal square on a chess board.
 
-type Square = (Int, Int)
+newtype Square = Square (Int, Int) deriving (Eq, Hashable, Show)
 type Path = [Square]
 
 -- Finds the next squares a knight can move to from a given square
-nextKnightPos (x, y) =
-  filter isValidMove . map (\(dx, dy) -> (x + dx, y + dy)) $ moves
+nextKnightPos (Square (x, y)) =
+  map Square . filter isValidMove . map (\(dx, dy) -> (x + dx, y + dy)) $ moves
   where
     moves = [(1,2), (1,-2), (-1,2), (-1,-2), (2,1), (2,-1), (-2,1), (-2,-1)]
     isValidMove (x, y) = and [x > 0, x < 9, y > 0, y < 9]
 
 -- Creates the heuristic function given a goal square. The heuristic used is half of the max of
 -- the distance between x coordinates and the distance between y coordinates.
-mkHeuristic (gx, gy) (x, y) = max (abs (x-gx)) (abs (y-gy)) `div` 2
+mkHeuristic (Square (gx, gy)) (Square (x, y)) = max (abs (x-gx)) (abs (y-gy)) `div` 2
 
--- Finds the shortest path of the knight
+-- Finds the shortest path of the knight, returns empty path if the goal is invalid
 knightsShortestPath :: Square -> Square -> Path
 knightsShortestPath initSq goalSq =
-  snd . fromJust
+  snd . fromMaybe (0, [])
   $ astarSearch initSq (== goalSq) (flip zip (repeat 1) . nextKnightPos) (mkHeuristic goalSq)
 
 -- Finds the shortest path using breadth first search. Used for checking if the path returned by
@@ -40,7 +41,7 @@ bfs :: Square -> Square -> Path
 bfs startSq goalSq =
   bfs' goalSq (Map.singleton startSq noSuchSq) (Seq.singleton startSq)
   where
-    noSuchSq = (-1,-1)
+    noSuchSq = Square (-1, -1)
 
     bfs' goalSq tracks open = let
       (first, rest) = Seq.splitAt 1 open
@@ -58,30 +59,30 @@ bfs startSq goalSq =
           else []
 
 -- Setup to generate arbitrary squares for testing
-newtype TestSquare = TestSquare { sq :: Square } deriving (Show)
-
-instance Arbitrary TestSquare where
+instance Arbitrary Square where
   arbitrary = do
     x <- choose (1, 8)
     y <- choose (1, 8)
-    return $ TestSquare (x, y)
+    return $ Square (x, y)
 
 -- Properties to test
 prop_path_starts_with_start_square startSq goalSq =
-  head (knightsShortestPath (sq startSq) (sq goalSq)) == sq startSq
+  head (knightsShortestPath startSq goalSq) == startSq
 
 prop_path_ends_with_goal_square startSq goalSq =
-  last (knightsShortestPath (sq startSq) (sq goalSq)) == sq goalSq
+  last (knightsShortestPath startSq goalSq) == goalSq
 
 prop_path_consists_of_valid_knights_moves startSq goalSq =
-  let path = knightsShortestPath (sq startSq) (sq goalSq)
+  let path = knightsShortestPath startSq goalSq
   in all isValidKnightsMove $ zip path (tail path)
   where
     isValidKnightsMove (sqFrom, sqTo) = sqTo `elem` nextKnightPos sqFrom
 
+prop_no_path_for_invalid_goal startSq =
+  knightsShortestPath startSq (Square (-1, -1)) == []
+
 prop_path_is_shortest startSq goalSq =
-  let path = knightsShortestPath (sq startSq) (sq goalSq)
-  in length path == length (bfs (sq startSq) (sq goalSq))
+  length (knightsShortestPath startSq goalSq) == length (bfs startSq goalSq)
 
 -- Tests all the properties 1000 times each
 testAllProps = $forAllProperties $ quickCheckWithResult (stdArgs {maxSuccess = 1000})
