palindrome world

palakata.fs

module Tests

(*
    problem statement:
        a palindrome is a string that reads same forward and backward,
            e.g. 121 or tacocat. 
        A substring is a contiguous subset of characters in a string. 
        Given a string s, how many distinct substrings of s are palindromes?
        
    for example:   (initial test list)
    
        x    zero "" -> 0  (not possible)
        
        x  one "a" -> 1
        
        x  many "aa" -> 2
    
        aabaa -> 5  // de-dup
        
        abcddcbabcdcdaadcdcbabcdddcb -> 27
    
    TDD.
        red.                write just enough of a test to get a fail, where fail to compile is a fail.
        green.              make it pass, quickly: hacker gene on.
        refactor.           clean up the mess above.
        
    DoD.  all tests pass?     reveals intention?       no duplication?      fewest elements?
*)

open FsUnit.Xunit
open Xunit


let allSubstringsOf (big:string) =
    let ofLength n = [for i in 0..big.Length-n -> big[i..i+n-1]]
    let rec allSubstringsOf n =
        match n with
        | 0 -> []
        | n -> allSubstringsOf (n-1) |> List.append (ofLength n)
    allSubstringsOf big.Length


let rec isPalindrome (s:string) =
    match s.Length with
    | 0 -> true
    | n -> s.[0] = s.[n-1] && isPalindrome s[1..n-2]
       

let palindrome' s =
    let distinct x = Set.ofSeq x |> Set.toList
    allSubstringsOf s |> Seq.filter isPalindrome |> distinct
    
let palindrome s = palindrome' s |> Seq.length

module palindromes = 
    [<Fact>]
    let ``0 empty string`` () =
        let result = palindrome ""
        result |> should equal 0
            
    [<Fact>]
    let ``1 letter string`` () =
        let result = palindrome "a"
        result |> should equal 1


    [<Fact>]
    let ``2 letter string`` () =
        let result = palindrome "ab"
        result |> should equal 2
         
    [<Fact>]
    let ``2 letter string, distinct `` () =
        let result = palindrome "aa"
        result |> should equal 2

    [<Fact>]
    let ``distinct substrings`` () =
        let result = palindrome "aabaa" 
        result |> should equal 5 

    [<Fact>]
    let ``pretty big string`` () =
        let result = palindrome "abcddcbabcdcdaadcdcbabcdddcb" 
        result |> should equal 27

module ``all substrings of`` =
    [<Fact>]
    let ``empty`` () =
        let result = allSubstringsOf ""
        result |> should be Empty
        
    [<Fact>]
    let ``one `` () =
        let result = allSubstringsOf "a"
        result |> should equal ["a"]
        
    [<Fact>]
    let ``two `` () =
        let result = allSubstringsOf "ab"
        result |> should matchList ["a";"ab";"b"]    

    [<Fact>]
    let ``three `` () =
        let result = allSubstringsOf "abc"
        result |> should matchList ["a";"b";"c";"ab";"bc";"abc"]

module ``is palindrome?`` =
    [<Fact>]
    let ``zero`` () =
        let result = isPalindrome ""
        result |> should be True

    [<Fact>]
    let ``one`` () =
        let result = isPalindrome "a"
        result |> should be True

    [<Fact>]
    let ``two when not`` () =
        let result = isPalindrome "ab"
        result |> should be False

    [<Fact>]
    let ``two`` () =
        let result = isPalindrome "aa"
        result |> should be True


    [<Fact>]
    let ``many`` () =
        let result = isPalindrome "aba"
        result |> should be True
        
    [<Fact>]
    let ``many when not`` () =
        let result = isPalindrome "abza"
        result |> should be False
       
   
    [<Fact>]
    let ``many, five`` () =
        let result = isPalindrome "abcba"
        result |> should be True

    [<Fact>]
    let ``many, tacocat`` () =
        let result = isPalindrome "tacocat"
        result |> should be True