175.hs

module Main where

import System.Environment (getArgs, getProgName)
import System.Random
import Data.List (permutations)

-- | Randomly permutes a list
shuffle :: [a] -> StdGen -> ([a], StdGen)
shuffle xs gen = (ys !! randIndex, gen')
  where
    (randIndex, gen') = randomR (0, length ys - 1) gen
    ys = permutations xs
  

-- | Counts random permutations required to permute into goal string
bogo :: Eq a => [a] -> [a] -> StdGen -> Int
bogo xs goal g = go g xs 0 
  where
    go g xs acc = if xs == goal
      then acc
      else let (xs', g') = shuffle xs g
           in go g' xs' (acc+1)


main = do
  args <- getArgs
  case args of
    [str, goal] -> do
      gen <- newStdGen
      let ans = bogo str goal gen
      putStrLn $ unwords ["Sorted in", show ans, "iterations."]
    _ -> do
      prog <- getProgName
      putStrLn $ unwords ["Usage:", prog, "string", "goalstring"]