You are viewing a single comment's thread. Return to all comments →
Had to cheat a bit: I couldn't find a great way to clear Test 20 without prioritizing multiplication on the descent :-/
Haskell:
module Main where {- Building the string from the end of the list to the beginning, the solution will be at least one of the following: 1. (n_0 op_0 n_1 op_1 ... n_(n-2) ) + n_(n-1) = 0 mod 101 2. (n_0 op_0 n_1 op_1 ... n_(n-2) ) - n_(n-1) = 0 mod 101 3. (n_0 op_0 n_1 op_1 ... n_(n-2) ) * n_(n-1) = 0 mod 101 For each of the three operations, we can calculate the what the shorter sequence must evaluate to mod 101. Recurse on the shorter sequence. Memoize the inverses (Operation, last digit, result mod 101) as you go. Cheat: Prioritzie the * operation on the descent, else Test 20 will timeout :-/ Don't know a better way yet. -} import Data.Array (Array, Ix, array, (!)) import Data.List (find) import Data.Maybe (catMaybes, fromMaybe, listToMaybe) data Operation = Plus | Minus | Times deriving (Eq, Ord, Ix) -- the show was only for testing instance Show Operation where show Plus = "+" show Minus = "-" show Times = "*" -- memoizing the left sequence inverses (Operation, last digit, result mod 101) type IdxOpTackMod = (Operation, Int, Int) inverseOM :: Array IdxOpTackMod Int inverseOM = array ((Plus, 1, 0), (Times, 100, 100)) [((op, i, j), inv op i j) | op <- [Plus, Minus, Times], i <- [1 .. 100], j <- [0 .. 100]] where inv :: Operation -> Int -> Int -> Int inv Plus i j = mod (j - i) 101 inv Minus i j = mod (j + i) 101 inv Times i j = fromMaybe 0 $ find (\k -> mod (k * i) 101 == j) [0 .. 100] solve :: [Int] -> String solve [] = "" solve ns = fromMaybe "" $ go rs subMod accStr where rs = reverse ns accStr = "" subMod = 0 -- go RemainingDigits valueMod101ForRemainingDigits AccumulatedString -> PathResult go :: [Int] -> Int -> String -> Maybe String go [] subMod accStr = Just accStr -- should not occur go [r] subMod accStr = if r == subMod then Just (show r ++ accStr) else Nothing -- stopping go (r : rs) subMod accStr = listToMaybe . catMaybes $ [ go rs (inverseOM ! (Times, r, subMod)) ("*" ++ show r ++ accStr) , go rs (inverseOM ! (Plus, r, subMod)) ("+" ++ show r ++ accStr) , go rs (inverseOM ! (Minus, r, subMod)) ("-" ++ show r ++ accStr) ] -- descent main :: IO () main = do numLine <- getLine let num = read numLine :: Int nsLine <- getLine let ns = map read $ words nsLine :: [Int] putStrLn $ solve ns return () -- https://www.hackerrank.com/challenges/expressions/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=24-hour-campaign
Seems like cookies are disabled on this browser, please enable them to open this website
Expressions
You are viewing a single comment's thread. Return to all comments →
Had to cheat a bit: I couldn't find a great way to clear Test 20 without prioritizing multiplication on the descent :-/
Haskell: