• + 0 comments

    Haskell solution using Data.Matrix, passes all tests

    import qualified Data.Matrix as M
    import Data.Char (digitToInt)
    
    nOfCompairason pattern mat = (r !! ((M.nrows pattern) - 1),c !! ((M.ncols pattern) - 1))
      where r = reverse [1..(M.nrows mat)]
            c = reverse [1..(M.ncols mat)]
    
    -- this is nothing like a cross correlation but you get the idea
    -- submatrix is O(1)
    crossCorrelation :: (Eq a) => M.Matrix a -> M.Matrix a -> Bool
    crossCorrelation mat ptrn = or $ map (\ (a,aa,b,bb) -> ptrn == M.submatrix a aa b bb mat) compair
      where (cr,cc) = nOfCompairason ptrn mat
            pr = M.nrows ptrn - 1
            pc = M.ncols ptrn - 1
            compair = [(a,a+pr,b,b+pc) | a <- [1..cr], b <- [1..cc]]
    
    yesNo bool | bool      = "YES"
               | otherwise = "NO"
    
    -- typechecking seems to fail with a fold so i had to make this function
    strToIntList :: String -> [Int]
    strToIntList []     = []
    strToIntList (x:xs) = (digitToInt x) : (strToIntList xs)
    
    -- there's probably a cuter way to write I/O but that's not the important thing here
    action = do
      rc <- getLine
      mat <- sequence $ replicate (read $ head $ words rc) getLine
      prc <- getLine
      ptr <- sequence $ replicate (read $ head $ words prc) getLine
      let matrix = M.fromLists $ map strToIntList mat
          patter = M.fromLists $ map strToIntList ptr
          res = yesNo $ crossCorrelation matrix patter
      putStrLn res
    
    main = do
      times <-getLine
      sequence $ replicate (read times) action