module Problem60 where

import qualified Data.IntSet as Set
import qualified Data.Map as Map
import Prime

main :: IO ()
main = print . sum $ concurrent 5 primes mp
  where
    primes = getPrimesUpto 10000
    mp     = Map.fromList
        [ (p, Set.fromList [ p' | p' <- primes, special p p', p' /= p ])
        | p <- primes
        ]

special :: Int -> Int -> Bool
special p q =
    (isPrimeNaive . read $ show p ++ show q) && (isPrimeNaive . read $ show q ++ show p)

concurrent :: Int -> [Int] -> Map.Map Int Set.IntSet -> [Int]
concurrent n primes mp =
    head
    -- find concurrent array with length n
        . filter (\xs -> length xs == n)
        $ [ concurrent' (n - 1) primes mp [p] | p <- primes ]

concurrent' :: Int -> [Int] -> Map.Map Int Set.IntSet -> [Int] -> [Int]
concurrent' k primes mp prev
    |
    -- we have k more integers to find, so we try all primes and recurse for k-1
    -- integers with choosing the current p as a different from prev and it is contained
    -- in all the other map-values (i.e. they are special), also if recurse doesn't find
    -- a solution it returns empty list which is returned all the way back up
      k > 0
    = let
          recurse =
            [ concurrent' (k - 1) primes mp (p : prev)
            | p <- primes
            , p `notElem` prev
            , all (\p' -> p `Set.member` (mp Map.! p')) prev
            ]
      in if null recurse then [] else head recurse
    | otherwise
    = prev
