module Exercise_12 where

import Control.Applicative ((<$>))
import Control.Arrow ((>>>))
import Control.Monad (ap, liftM2)
import Data.Bifoldable (biconcat)
import Data.List (elemIndex, genericIndex, partition, sortOn)
import Data.Maybe (fromJust)

isPrime :: Int -> Bool
isPrime n
  | n <= 1 = False
  | otherwise = primeAux (n-1)
  where
    primeAux 1 = True
    primeAux i = n `mod` i /= 0 && primeAux (i-1)

primes :: Int -> [Int]
primes n = [i | i <- [2..n], isPrime i]

{-WETT-}
encrypt :: String -> String
encrypt = liftM2 map genericIndex is

decrypt :: String -> String
decrypt = ap zip is >>> sortOn snd >>> map fst

is :: String -> [Int]
is = length >>> enumFromTo 1 >>> partition isPrime >>> biconcat >>> map pred

{-MCCOMMENT

  Please feel free to use the following 30-token alternative solution if unsafe
  imports are allowed:

    import GHC.Base (eqString)
    encrypt = liftM2 map genericIndex $ length >>> enumFromTo 1 >>> partition isPrime >>> biconcat >>> map pred
    decrypt = flip until encrypt =<< eqString >>> (encrypt >>>)

  This solution also passed the tests on the submission system without timeouts
  (tested using '(==)' instead of 'eqString').

  Less beautiful encrypt alternative (same number of tokens):

    encrypt xs = genericIndex xs . pred <$> biconcat (partition isPrime $ 1 `enumFromTo` length xs)

  Decipherable form of decrypt:

    decrypt xs = until ((xs ==) . encrypt) encrypt xs

  More about this decrypt algorithm (if you can't see the decrypt for the
  encrypt):

  A brief analysis of this beautiful encryption scheme with short messages led
  me to the assumption that applying the encryption algorithm to a message
  several times will always result in the original message in plain text again
  at some point, and that decrypting using this theorem is usually more
  efficient (and even better in terms of token counting) than checking all
  permutations (as proven by the submission system).

  How many iterations (worst-case)?

  Let I(n) denote the worst-case number of encrypt iterations until we get the
  plain text again, as a function of the message length n.
  Trivial cases: I(0) = 0, I(1) = 0.
  For all other numbers, quite obviously, I(n) = I(p), whereas p denotes the
  largest prime number <= n, as characters at a one-based index > p will by
  design never change their position, no matter how often we apply the
  encryption algorithm.
  Furthermore, for finding I(n), no characters can appear more than once in the
  message substring given by the characters at the indexes from 1 to p (both
  included), otherwise we may not get the worst-case number of iterations.

  Unfortunately, I did not have the time to investigate further, but I did
  compute I(n) for most of the first 200 prime numbers (timeout at 5×10^10
  iterations), which leads to the series of the so-called Kappelmann numbers
  (not to be confused with the much less important Catalan numbers):

  2, 3, 5, 12, 18, 13, 24, 88, 102, 40, 31, 300, 390, 43, 120, 592, 858, 450,
  3360, 330, 132, 2310, 1508, 1600, 630, 525, 861, 2850, 434682, 210, 117180,
  3948, 4650, 645, 414, 211068, 462, 37620, 17980, 2080, 4588, 127920, 104280,
  389340, 81696, 36195, 172050, 11026, 3376, 23256, 1269975, 32604, 17460, 251,
  3023280, 1027110, 24108, 46620, 9976, 41400, 210420, 107880, 2536872, 1228,
  3080, 112752, 1680, 33264, 3781050, 7644, 6632208, 275094, 2092440, 3960,
  27387360, 55944, 69048, 43419, 7602945, 705870, 3702888, 86955, 47878740,
  14630, 953724, 49902077576, 29064420, 6845652, 206040, 34650, 2590740, 56980,
  380688, 556920, 18520, 122032680, 9780, 869616, 2028, 15810, 372960, 231595,
  11994840, 1544382, 20254, 351204, 570353952, 657600, 2970, 388360, 514280,
  111264, 72629340, 73966620, 144604460, 11700, 2940, 335240, 264605352,
  13355370, 8674488900, 1844400, 506610, 2979900, 18956784, 24043740, 5922,
  19546580, 325520, 1497420, 6424236, 115960, 925572840, 8498599200, 41328,
  24990, 1543984650, 20524356, 130032, 83480880, 2635812900, 633228960,
  47723508, 34078548, 5414976, ???, 2596909392, 104932, 29751528, 71730108,
  27775440, 39009426414, 134371578,  ???, 294414120, 2386800, 6521788, 2797080,
  316008000, 152040, 98532, 3281653284, 1298009160, 85645560, 41694372720, ???,
  ???, 29010, 35799960, 267267, 7035, 115389474, 16484841750, 381420,
  11748241680, 3422193840, 12373218, 178080474, 1600556958, 4289010, ???,
  20165600, 109956132, 110258232, 214030440, 9810, 854856, 2370632550, 48231690,
  2485560, 31086146520, 66588930, 17340, 22354728, 2231439210, ???, 176280174,
  731816085, 688602, 54435480, ...

  This makes me hope that my initial assumption holds.
  OEIS request to be submitted.

  (The computations were performed in Java with arrays of unique ints instead of
  strings.)

  Summary:

  Let κ(n) denote the n-th Kappelmann number, Π(n) the index of the prime number
  n in the sequence of prime numbers, λ(n) the largest prime number <= n:

    I(0) = 0
    I(1) = 0
    I(n) = (κ ∘ Π ∘ λ) (n)

  The values of I(n), for reasonably small ns, are small enough to pass the
  decryption tests on the submission system without timeouts (which could, of
  course, partly also be due to the fact that individual characters may also
  occur more than just once).

  Cheers!

            "The time you enjoy wasting is not wasted time."
                                                              — Bertrand Russell

-}
{-TTEW-}

-- Calculates the required number of encrypt iterations until we get the plain
-- text again for word lengths < 839 (the 146th prime number), as we have just
-- the first 145 Kappelmann numbers here.
iterations :: Int -> Integer
iterations 0 = 0
iterations 1 = 0
iterations x = (kappa . pi . lambda) x
  where
    kappa n = ks !! n
    pi n = fromJust $ elemIndex n (primes n)
    lambda = last . primes
    ks = [2, 3, 5, 12, 18, 13, 24, 88, 102, 40, 31, 300, 390, 43, 120, 592, 858, 450, 3360, 330, 132, 2310, 1508, 1600, 630, 525, 861, 2850, 434682, 210, 117180, 3948, 4650, 645, 414, 211068, 462, 37620, 17980, 2080, 4588, 127920, 104280, 389340, 81696, 36195, 172050, 11026, 3376, 23256, 1269975, 32604, 17460, 251, 3023280, 1027110, 24108, 46620, 9976, 41400, 210420, 107880, 2536872, 1228, 3080, 112752, 1680, 33264, 3781050, 7644, 6632208, 275094, 2092440, 3960, 27387360, 55944, 69048, 43419, 7602945, 705870, 3702888, 86955, 47878740, 14630, 953724, 49902077576, 29064420, 6845652, 206040, 34650, 2590740, 56980, 380688, 556920, 18520, 122032680, 9780, 869616, 2028, 15810, 372960, 231595, 11994840, 1544382, 20254, 351204, 570353952, 657600, 2970, 388360, 514280, 111264, 72629340, 73966620, 144604460, 11700, 2940, 335240, 264605352, 13355370, 8674488900, 1844400, 506610, 2979900, 18956784, 24043740, 5922, 19546580, 325520, 1497420, 6424236, 115960, 925572840, 8498599200, 41328, 24990, 1543984650, 20524356, 130032, 83480880, 2635812900, 633228960, 47723508, 34078548, 5414976]