module Euler.Problems.Problem68
( answer
) where
import Euler.Prelude
import Euler.Util.Foldable (allEqual)
import Data.List (filter, (!!))
import qualified Data.Foldable as Foldable
import qualified Data.List as List
type Group = [Int]
type Ring = [Group]
answer :: String
answer =
Foldable.maximum $ foldMap (foldMap show) <$> magicRings
magicRings :: [Ring]
magicRings =
filter isMagic rings
isMagic :: Ring -> Bool
isMagic =
allEqual . fmap Foldable.sum
rings :: [Ring]
rings =
(10:) <$> permutations [1..9] <&> \p ->
indices & fmap (fmap (p !!)) & cycleToMin
indices :: Ring
indices =
[ [ 0, 5, 6 ]
, [ 1, 6, 7 ]
, [ 2, 7, 8 ]
, [ 3, 8, 9 ]
, [ 4, 9, 5 ]
]
cycleToMin :: Ord a => [a] -> [a]
cycleToMin xs =
let i = indexOfMin xs
in List.drop i xs <> List.take i xs
indexOfMin :: Ord a => [a] -> Int
indexOfMin xs =
List.zip xs [0..] & Foldable.minimum & snd