-- gps.hs: General Program Synthesis Benchmark Suite
--
-- Copyright (C) 2021 Rudy Matela
-- Distributed under the 3-Clause BSD licence (see the file LICENSE).
import Conjure
import System.Environment (getArgs)

import Data.Char (isLetter)                      -- GPS bench  #5
import Data.Char (isSpace)                       -- GPS bench  #7
import Data.Ratio ((%), numerator, denominator)  -- GPS bench #10


gps1p :: Int -> Float -> Float
gps1p 0 1.0  =  1.0
gps1p 1 0.0  =  1.0
gps1p 1 1.0  =  2.0
gps1p 1 1.5  =  2.5

gps1g :: Int -> Float -> Float
gps1g x f  =  fromIntegral x + f

gps1c :: IO ()
gps1c  =  conjure "gps1" gps1p
  [ prim "+" ((+) :: Float -> Float -> Float)
  , prim "fromIntegral" (fromIntegral :: Int -> Float)
  ]


gps2p :: Int -> Maybe String
gps2p    0  =  Just "small"
gps2p  500  =  Just "small"
gps2p 1000  =  Nothing
gps2p 1500  =  Nothing
gps2p 2000  =  Just "large"
gps2p 2500  =  Just "large"

gps2g :: Int -> Maybe String
gps2g n
  | n <  1000  =  Just "small"
  | 2000 <= n  =  Just "large"
  | otherwise  =  Nothing

gps2c :: IO ()
gps2c  =  conjureWith args{maxTests=5040, maxSize=30} "gps2" gps2p
  [ pr "small"
  , pr "large"
  , pr (1000 :: Int)
  , pr (2000 :: Int)
  , prim "Just" (Just :: String -> Maybe String)
  , prim "Nothing" (Nothing :: Maybe String)
  , prim "<=" ((<=) :: Int -> Int -> Bool)
  , prim "<" ((<) :: Int -> Int -> Bool)
  , prif (undefined :: Maybe String)
  ]


gps3p :: Int -> Int -> Int -> [Int]
gps3p 0 9 1  =  [0,1,2,3,4,5,6,7,8]
gps3p 2 9 2  =  [2,4,6,8]

gps3g1 :: Int -> Int -> Int -> [Int]
gps3g1 start end step  =  enumFromThenTo start (step+start) (end-1)

gps3g2 :: Int -> Int -> Int -> [Int]
gps3g2 start end step  =  if start < end
                          then start : gps3g2 (start+step) end step
                          else []

gps3c :: IO ()
gps3c  =  do
  conjure "gps3" gps3p
    [ pr (1 :: Int)
    , prim "enumFromThenTo" ((\x y z -> take 720 $ enumFromThenTo x y z) :: Int -> Int -> Int -> [Int])
    , prim "+" ((+) :: Int -> Int -> Int)
    , prim "-" ((-) :: Int -> Int -> Int)
    ]

  -- not possible, no recursive descent
  conjureWith args{maxSize=8} "gps3" gps3p
    [ pr ([] :: [Int])
    , prim ":" ((:) :: Int -> [Int] -> [Int])
    , prim "+" ((+) :: Int -> Int -> Int)
    , prim "<" ((<) :: Int -> Int -> Bool)
    , prif (undefined :: [Int])
    ]


gps4p :: String -> String -> String -> Bool
gps4p "" "a" "aa"  =  True
gps4p "aa" "a" ""  =  False
gps4p "a" "aa" ""  =  False
gps4p "a" "aa" "aaa"  =  True
gps4p "a" "aaa" "aa"  =  False
gps4p "aa" "a" "aaa"  =  False
gps4p "aa" "aaa" "a"  =  False
gps4p "aaa" "a" "aa"  =  False
gps4p "aaa" "aa" "a"  =  False

gps4g :: String -> String -> String -> Bool
gps4g s1 s2 s3  =  length s1 < length s2 && length s2 < length s3

gps4c :: IO ()
gps4c  =  do
  conjure "gps4" gps4p
    [ prim "length" (length :: String -> Int)
    , prim "<" ((<) :: Int -> Int -> Bool)
    , prim "&&" (&&)
    ]


gps5p :: String -> String
gps5p "a"  =  "aa"
gps5p "b"  =  "bb"
gps5p " "  =  " "
gps5p "!"  =  "!!!"
gps5p "aa"  =  "aaaa"

gps5g :: String -> String
gps5g []  =  []
gps5g (c:cs)
  | isLetter c  =  c:c:gps5g cs
  | c == '!'    =  c:c:c:gps5g cs
  | otherwise   =  c:gps5g cs

gps5c :: IO ()
gps5c  =  conjureWith args{maxSize=6} "gps5" gps5p -- can't find
  [ pr ""
  , prim ":" ((:) :: Char -> String -> String)
  , pr '!'
  , prim "==" ((==) :: Char -> Char -> Bool)
  , prim "isLetter" (isLetter :: Char -> Bool)
  , prif (undefined :: String -> String)
  ]


-- GPS Benchmark #6 -- Collatz/Hailstone numbers --

gps6p :: Int -> Int
gps6p 1  =  1
gps6p 2  =  2
gps6p 3  =  8
gps6p 4  =  3
gps6p 5  =  6
gps6p 6  =  9
gps6p 12  =  10
gps6p 60  =  20
gps6p 360  =  20

gps6g :: Int -> Int
gps6g  =  tnp1
  where
  tnp1 n | n <= 0  =  undefined
  tnp1 1  =  1                          --  1
  tnp1 n  =  1 + gps6g (if even n       --  7
                        then n `div` 2  -- 10
                        else 3*n + 1)   -- 15

-- This one is out of reach performance wise:
-- Speculate hangs with this background.
-- Removing three or setting maxEqSize to 4 makes it unhang.
-- But a size of 15 or 17 is simplyl out of our reach.
gps6c :: IO ()
gps6c  =  conjureWith args{maxSize=6,maxEquationSize=3} "gps6" gps6p
  [ pr (1 :: Int)
  , pr (2 :: Int)
  , pr (3 :: Int)
  , prim "+" ((+) :: Int -> Int -> Int)
  , prim "*" ((*) :: Int -> Int -> Int)
  , prim "`div`" (div :: Int -> Int -> Int)
  , prim "even" (even :: Int -> Bool)
  , prif (undefined :: Int)
  ]


-- GPS Benchmark #7 -- Replace Space with Newline (P 4.3)

gps7p :: String -> (String, Int)
gps7p "a"  =  ("a", 1)
gps7p "aa"  =  ("aa", 2)
gps7p "a a"  =  ("a\na", 2)
gps7p "a\na"  =  ("a\na", 2)

gps7g :: String -> (String, Int)
gps7g s  =  (init $ unlines $ words s, length (filter (not . isSpace) s))

gps7c :: IO ()
gps7c  =  conjure "gps7" gps7p
  [ prim "," ((,) :: String -> Int -> (String, Int))
  , prim "init" (init :: String -> String)
  , prim "unlines" unlines
  , prim "words" words
  , prim "length" (length :: String -> Int)
  , prim "filter" (filter :: (Char -> Bool) -> String -> String)
  , prim "not" not
  , prim "." ((.) :: (Bool -> Bool) -> (Char -> Bool) -> Char -> Bool) -- cheat?
  , prim "isSpace" (isSpace :: Char -> Bool)
  ]


-- GPS Benchmark #8 -- String Differences

gps8p :: String -> String -> [(Int, Char, Char)]
gps8p "a" "a"  =  []
gps8p "a" "b"  =  [(0,'a','b')]
gps8p "aa" "ab"  =  [(1,'a','b')]
gps8p "dealer" "dollar"  =  [(1,'e','o'), (2,'a','l'),(4,'e','a')]

gps8g :: String -> String -> [(Int, Char, Char)]
gps8g  =  diffs 0
  where
  diffs _ [] _  =  []
  diffs _ _ []  =  []
  diffs n (c:cs) (d:ds)  =  if c == d
                            then diffs (n+1) cs ds
                            else (n,c,d) : diffs (n+1) cs ds

-- out of reach as Conjure cannot invent helper functions
-- even if that would be solved,
-- I conjecture it would be out-of-reach performance-wise.
gps8c :: IO ()
gps8c  =  conjure "gps8" gps8p
  [
  ]


-- GPS Benchmark #9 -- Even Squares
-- given an integer _n_, print all of the positive even perfect squares less
-- than _n_ on separate lines.

gps9p :: Int -> [Int]
gps9p 10  =  [4]
gps9p 100  =  [4,16,36,64]
gps9p 1000  =  [4,16,36,64,100,144,196,256,324,400,484,576,676,784,900]

-- non-optimal performance, but does the job
-- gps9g :: Int -> [Int]
-- gps9g n  =  [x*x | x <- [1..n], x*x < n, even (x*x)]
gps9g :: Int -> [Int]
gps9g n  =  filter (n >) (filter even (map sq [1..n]))
  where
  sq  =  (^2)

gps9c :: IO ()
gps9c  =  conjureWith args{maxTests=60} "gps9" gps9p
  [ pr (1 :: Int)
  , prim "map" (map :: (Int -> Int) -> [Int] -> [Int])
  , prim "filter" (filter :: (Int -> Bool) -> [Int] -> [Int])
  , prim ".." (enumFromTo :: Int -> Int -> [Int])
  , prim ">" ((>) :: Int -> Int -> Bool)
  , prim "even" (even :: Int -> Bool)
  , prim "sq" ((^2) :: Int -> Int)  -- invented separately
  ]


-- GPS Benchmark #10 -- Wallis Pi
-- (quarter pi approximation)
-- 2   4   4   6   6   8   8
-- - x - x - x - x - x - x - x ...
-- 3   3   5   5   7   7   9

gps10p :: Int -> Rational
gps10p 1  =     2/3
gps10p 2  =     8/9
gps10p 3  =    32/45
gps10p 4  =    64/75
gps10p 5  =   128/175
gps10p 6  =  1024/1225

gps10g :: Int -> Rational
gps10g n  =  product $ take n $ iterate wallisNext (2/3)

wallisNextP :: Rational -> Rational
wallisNextP q
  | q == 2/3  =  4/3
  | q == 4/3  =  4/5
  | q == 4/5  =  6/5
  | q == 6/5  =  6/7
  | q == 6/7  =  8/7
  | q == 8/7  =  8/9

wallisNext :: Rational -> Rational
wallisNext q  =  if n < d
                 then (n+2) % d
                 else n % (d+2)
  where
  n  =  numerator q
  d  =  denominator q
-- wallisNext (x % y)  =  (y + (y + 2)) % (x + (x + 2)) -- which simplifies to...
-- wallisNext (x % y)  =  (x + x * y) % (x + x * x)     -- which simplifies to...
-- wallisNext (x % y)  =  (y + 1) % (x + 1)             -- this correct version


gps10c :: IO ()
gps10c  =  do
  conjureWith args{maxSize=14} "wallisNext" wallisNextP
    [ pr (1 :: Integer)
    , pr (2 :: Integer)
    , prim "+" ((+) :: Integer -> Integer -> Integer)
    , prim "*" ((*) :: Integer -> Integer -> Integer)
    , prim "%" ((%) :: Integer -> Integer -> Rational)
    , prim "<" ((<) :: Integer -> Integer -> Bool)
--  , prim "numerator" (numerator :: Rational -> Integer)
--  , prim "denominator" (denominator :: Rational -> Integer)
    , prif (undefined :: Rational)
    ]

  conjure "gps10" gps10p
    [ pr (2 :: Integer)
    , pr (3 :: Integer)
    , prim "%" ((%) :: Integer -> Integer -> Rational)
--  , pr (2/3 :: Rational)
    , prim "product"    (product :: [Rational] -> Rational)
    , prim "take"       (take :: Int -> [Rational] -> [Rational])
    , prim "iterate"    ((\f -> take 720 . iterate f) :: (Rational -> Rational) -> Rational -> [Rational])
    , prim "wallisNext" wallisNext
    ]

main :: IO ()
main  =  do
  as <- getArgs
  case as of
    [] -> sequence_ gpss
    (n:_) -> gpss !! (read n - 1)


gpss :: [IO ()]
gpss  =  [ gps1c
         , gps2c
         , gps3c
         , gps4c
         , gps5c
         , gps6c
         , gps7c
         , gps8c
         , gps9c
         , gps10c
         ]