Re: Haskel

Voilà la solution, j’ai changé les Int en Ratio Int, enlevé les vérifications de la division et de la soustraction (mais là, je n’en vois pas l’intérêt ;-) )

À chaque modification, j’ai laissé l’ancienne ligne en commentaire pour voir les différences.

import Data.List
-- new line
import Data.Ratio
-- A value is an Int or an operation with two arguments and a result.
--data Value = V Int | Op Operation Value Value Int
data Value = V (Ratio Int) | Op Operation Value Value (Ratio Int)
data Operation = Plus | Min | Mult | Div | Error
-- Instance of Show class to be able to display Operation type
instance Show Operation where
 show Plus = "+"
 show Min = "-"
 show Mult = "×ばつ"
 show Div = "÷"
 show _ = "Error"
-- Instance of Show class for Value.
instance Show Value where
-- show (V a) = show a
 show (V a) = show $ numerator a -- The value is a % 1
 show (Op o a b _) = " (" ++ (show a) ++ (show o) ++ (show b) ++ ") "
-- Take an Operation and a list of 2 minimal Values. Generate a new value with the first two terms.
doOp :: Operation -> [Value] -> [Value]
doOp Plus (a:b:xs) = (Op Plus a b (va+vb):xs)
 where va = getV a
 vb = getV b
-- We don't want to have negative values, so check if a >= b
-- We work in Q
doOp Min (a:b:xs) = (Op Min a b ((getV a)-(getV b)):xs)
-- | otherwise = (Op Error a b (-1)):xs
doOp Mult (a:b:xs) = (Op Mult a b (va*vb)):xs
 where va = getV a
 vb = getV b
-- First check that divisor is not 0, then check if b can divide a without rest.
doOp Div (a:b:xs) | vb == 0 = (Op Error a b (-1)):xs
-- | va `mod` vb == 0 = (Op Div a b (va `div` vb)):xs
-- | otherwise = (Op Error a b (-1)):xs
 | otherwise = (Op Div a b (va / vb)):xs
 where va = getV a
 vb = getV b
-- Create a Ratio
--setV a = V a
setV a = V (a % 1)
getV (V a) = a
getV (Op _ _ _ a) = a
-- Do operations, take a list of Values and do all operations, drop error if a computation is not possible
doOps :: [Value] -> [[Value]]
doOps a = filter (dropError.head) $ map (\x -> doOp x a) [Plus, Min, Mult, Div] 
-- Check for error filter, return True if it's valid.
dropError :: Value -> Bool
dropError (Op Error _ _ _) = False
dropError _ = True
-- En entrée une liste de values, en sortie une liste d'opérations filtrée.
-- Check we have 4 numbers.
-- From right to left
-- - map setV x => generate a Value list with only V values.
-- - compute all permutations
-- - For each list of values apply all operations on first two values, we get list of list of list so concat to obtain list of list Values
-- - We have 3 elements
-- - For each element, we perform permutations and concat to get a list of list of Values.
-- - loop twice to get list of list of Value with length == 1.
-- - Then filter to check if result is 24.
get24 :: [Int] -> [[Value]]
get24 x | length x == 4 = filter (\x -> (getV (head x))==24) $ concat.map doOps $ concat.map permutations $ concat.map doOps $ concat.map permutations $ concat.map doOps $ permutations $ map setV x
 | otherwise = []

Et le résultat :

*Main Data.Ratio> get24 [7,7,2,1]
[[ ( ( (7×ばつ7) -1) ÷2) ],[ ( ( (7×ばつ7) -1) ÷2) ],[ ( ( (7×ばつ7) -1) ÷2) ],[ ( ( (7×ばつ7) -1) ÷2) ]]
*Main Data.Ratio> get24 [ 1,4,5,6]
[[ (6÷ ( (5÷4) -1) ) ],[ (4÷ (1- (5÷6) ) ) ],[ (6÷ ( (5÷4) -1) ) ],[ (4÷ (1- (5÷6) ) ) ]]
*Main Data.Ratio> get24 [7,7,2,1]
[[ ( ( (7×ばつ7) -1) ÷2) ],[ ( ( (7×ばつ7) -1) ÷2) ],[ ( ( (7×ばつ7) -1) ÷2) ],[ ( ( (7×ばつ7) -1) ÷2) ]]
*Main Data.Ratio> get24 [ 1,4,5,6]
[[ (6÷ ( (5÷4) -1) ) ],[ (4÷ (1- (5÷6) ) ) ],[ (6÷ ( (5÷4) -1) ) ],[ (4÷ (1- (5÷6) ) ) ]]