We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Functional Programming
  3. Memoization and DP
  4. Dice Path
  5. Discussions

Dice Path

  • adeeb_hs1
     + 0 comments

    This is my haskell solution, but this doesn't work for test case 5 and 6 Time Complexity - O(t.m.n), Space Complexity - O(m.n) Please suggest some edits to get my program to pass all the test cases.

    import Data.Array

find :: Int -> Int -> Int 
find m n = findPaths (1, 1, 1, 3, 2)
    where
        dp = array ((1,1,1,1,1), (m, n, 6, 6, 6))
             [(c , findPaths c) | c <- (,,,,) <$> [1..m] <*> [1..n] <*> [1..6]  <*> [1..6] <*> [1..6]]
             
        get c
            | inRange (bounds dp) c = dp ! c
            | otherwise = -1
    
        findPaths (i,j,t,l,f)
            | i == m && j == n = t
            | otherwise = t + max path1 path2
                where
                    path1 = get (i, j+1, l, 7-t, f)
                    path2 = get (i+1, j, 7-f, l, t)
     
main :: IO()
main = do
    raw <- getContents
    mapM_ print $ map helper $ (map . map) (read :: String -> Int) $ map words $ tail $ lines raw
    where helper (m : n : _) = find m n