Riddler Classic solution for 2021-08-13

riddler_dice.hs

{-# OPTIONS_GHC -Wno-tabs #-}
import Data.List
import Data.Ratio

-- https://fivethirtyeight.com/features/are-you-clever-enough/

-- calcEV n = expected value of playing the game, rolling n dice
calcEV :: Integer -> Rational
calcEV 0 = 0 -- base case
calcEV n = ev
	where
		-- consider every possible roll of n dice
		buildRolls :: Integer -> [[Rational]]
		buildRolls 0 = [[]]
		buildRolls n = [i:rest | i <- [1,2,3,4,5,6], rest <- buildRolls (n-1)]
		rolls :: [[Rational]]
		rolls = map (reverse.sort) $ buildRolls n
		-- calculate the value of each roll
		values :: [Rational]
		values = map calcValue rolls
		-- we have to keep the best die, and possibly keep more
		calcValue :: [Rational] -> Rational
		calcValue rolls = maximum $ map calcKeepValue [1..n]
			where calcKeepValue i = sum (genericTake i rolls) + getEV (n - i)
		-- average to get our EV
		ev = sum values / (6^n)

-- memoisation
evs = map calcEV [0..] :: [Rational]
getEV = genericIndex evs :: Integer -> Rational

main = mapM_ (putStrLn.outputLine) [0..10]
	where outputLine i = show i ++ ": " ++ show (getEV i) ++ " = " ++ show (fromRational (getEV i) :: Float)