// [snippet: Ninety-Nine F# Problems - Problems 11 - 20 - List, continued]
/// These are F# solutions of Ninety-Nine Haskell Problems 
/// (http://www.haskell.org/haskellwiki/H-99:_Ninety-Nine_Haskell_Problems), 
/// which are themselves translations of Ninety-Nine Lisp Problems
/// (http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html)
/// and Ninety-Nine Prolog Problems
/// (https://sites.google.com/site/prologsite/prolog-problems).
///
/// If you would like to contribute a solution or fix any bugs, send 
/// an email to paks at kitiara dot org with the subject "99 F# problems". 
/// I'll try to update the problem as soon as possible.
///
/// The problems have different levels of difficulty. Those marked with a single asterisk (*) 
/// are easy. If you have successfully solved the preceeding problems you should be able to 
/// solve them within a few (say 15) minutes. Problems marked with two asterisks (**) are of 
/// intermediate difficulty. If you are a skilled F# programmer it shouldn't take you more than 
/// 30-90 minutes to solve them. Problems marked with three asterisks (***) are more difficult. 
/// You may need more time (i.e. a few hours or more) to find a good solution
///
/// Though the problems number from 1 to 99, there are some gaps and some additions marked with 
/// letters. There are actually only 88 problems.
// [/snippet]

// [snippet: (*) Problem 11 :  Modified run-length encoding.]
/// Modify the result of problem 10 in such a way that if an element has no duplicates it 
/// is simply copied into the result list. Only elements with duplicates are transferred as
/// (N E) lists.
///  
/// Example: 
/// * (encode-modified '(a a a a b c c a a d e e e e))
/// ((4 A) B (2 C) (2 A) D (4 E))
///  
/// Example in F#: 
/// 
/// > encodeModified <| List.ofSeq "aaaabccaadeeee"
/// val it : char Encoding list =
///   [Multiple (4,'a'); Single 'b'; Multiple (2,'c'); Multiple (2,'a');
///    Single 'd'; Multiple (4,'e')]

type 'a Encoding = Multiple of int * 'a | Single of 'a

(*[omit:(Solution)]*)
/// From problem 9 
let pack xs = 
    let collect x = function
        | [] -> failwith "empty list you fool!"
        | []::xss -> [x]::xss
        | (y::xs)::xss as acc -> 
            if x = y then
                (x::y::xs)::xss
            else
                [x]::acc
    List.foldBack collect xs [[]]

let encodeModified xs = xs |> pack |> List.map (Seq.countBy id >> Seq.head >> fun(x,n)-> if n = 1 then Single x else Multiple (n,x))
(*[/omit]*)
// [/snippet]


// [snippet: (**) Problem 12 : Decode a run-length encoded list.]
/// Given a run-length code list generated as specified in problem 11. Construct its 
/// uncompressed version.
///  
/// Example in F#: 
/// 
/// > decodeModified 
///     [Multiple (4,'a');Single 'b';Multiple (2,'c');
///      Multiple (2,'a');Single 'd';Multiple (4,'e')];;
/// val it : char list =
///   ['a'; 'a'; 'a'; 'a'; 'b'; 'c'; 'c'; 'a'; 'a'; 'd'; 'e'; 'e'; 'e'; 'e']

(*[omit:(Solution)]*)
let decodeModified xs = 
    let expand = function
        | Single x -> [x]
        | Multiple (n,x) -> List.replicate n x
    xs |> List.collect expand
(*[/omit]*)
// [/snippet]

// [snippet: (**) Problem 13 : Run-length encoding of a list (direct solution).]
/// Implement the so-called run-length encoding data compression method directly. I.e. 
/// don't explicitly create the sublists containing the duplicates, as in problem 9, 
/// but only count them. As in problem P11, simplify the result list by replacing the 
/// singleton lists (1 X) by X.
///  
/// Example: 
/// * (encode-direct '(a a a a b c c a a d e e e e))
/// ((4 A) B (2 C) (2 A) D (4 E))
///  
/// Example in F#: 
/// 
/// > encodeDirect <| List.ofSeq "aaaabccaadeeee"
/// val it : char Encoding list =
///   [Multiple (4,'a'); Single 'b'; Multiple (2,'c'); Multiple (2,'a');
///    Single 'd'; Multiple (4,'e')]

(*[omit:(Solution)]*)
let encodeDirect xs = 
    let collect x = function
        | [] -> [Single x]
        | Single y::xs when x = y -> Multiple(2, x)::xs
        | Single _::_ as xs -> Single x::xs
        | Multiple(n,y)::xs when y = x -> Multiple(n + 1, x)::xs
        | xs -> Single x::xs
    List.foldBack collect xs []
(*[/omit]*)
// [/snippet]

// [snippet: (*) Problem 14 : Duplicate the elements of a list.]
/// Example: 
/// * (dupli '(a b c c d))
/// (A A B B C C C C D D)
///  
/// Example in F#: 
/// 
/// > dupli [1; 2; 3]
/// [1;1;2;2;3;3]

(*[omit:(Solution 1)]*)
let dupli xs = xs |> List.map (fun x -> [x; x]) |> List.concat
(*[/omit]*)

(*[omit:(Solution 2)]*)
let rec dupli' = function
    | [] -> []
    | x::xs -> x::x::dupli' xs
(*[/omit]*)

(*[omit:(Solution 3)]*)
let dupli'' xs = [ for x in xs do yield x; yield x ]
(*[/omit]*)

(*[omit:(Solution 4)]*)
let dupli''' xs = xs |> List.collect (fun x -> [x; x])
(*[/omit]*)

(*[omit:(Solution 5)]*)
let dupli'''' xs = (xs,[]) ||> List.foldBack(fun x xs -> x::x::xs) 
(*[/omit]*)

(*[omit:(Solution 6)]*)
let dupli''''' xs = ([], xs) ||> List.fold(fun xs x -> xs @ [x; x])
(*[/omit]*)

(*[omit:(Solution 7)]*)
let dupli'''''' xs = xs |> List.collect (List.replicate 2)
(*[/omit]*)
// [/snippet]

// [snippet: (**) Problem 15 : Replicate the elements of a list a given number of times.]
/// Example: 
/// * (repli '(a b c) 3)
/// (A A A B B B C C C)
///  
/// Example in F#: 
/// 
/// > repli (List.ofSeq "abc") 3
/// val it : char list = ['a'; 'a'; 'a'; 'b'; 'b'; 'b'; 'c'; 'c'; 'c']

(*[omit:(Solution 1)]*)
let repli xs n = xs |> List.collect (List.replicate n)
(*[/omit]*)

(*[omit:(Solution 2)]*)
let repli' xs n= 
    [ for x in xs do 
        for i=1 to n do
            yield x ]
(*[/omit]*)
// [/snippet]

// [snippet: (**) Problem 16 : Drop every N'th element from a list.]
/// Example: 
/// * (drop '(a b c d e f g h i k) 3)
/// (A B D E G H K)
///  
/// Example in F#: 
/// 
/// > dropEvery (List.ofSeq "abcdefghik") 3;;
/// val it : char list = ['a'; 'b'; 'd'; 'e'; 'g'; 'h'; 'k']

(*[omit:(Solution 1)]*)
let dropEvery xs n = xs |> List.mapi (fun i x -> (i + 1,x)) |> List.filter(fun (i,_) -> i % n <> 0) |> List.map snd
(*[/omit]*)

(*[omit:(Solution 2)]*)
let dropEvery' xs n =
    let rec drop xs count =
        match xs,count with
            | [], _ -> []
            | _::xs, 1 -> drop xs n
            | x::xs, _ -> x::drop xs (count - 1) 
    drop xs n
(*[/omit]*)
// [/snippet]

// [snippet: (*) Problem 17 : Split a list into two parts; the length of the first part is given.]
/// Do not use any predefined predicates. 
/// 
/// Example: 
/// * (split '(a b c d e f g h i k) 3)
/// ( (A B C) (D E F G H I K))
///  
/// Example in F#: 
/// 
/// > split (List.ofSeq "abcdefghik") 3
/// val it : char list * char list =
///   (['a'; 'b'; 'c'], ['d'; 'e'; 'f'; 'g'; 'h'; 'i'; 'k'])

(*[omit:(Solution)]*)
let split xs n = 
    let rec take n xs =
        match xs,n with
            | _,0 -> []
            | [],_ -> []
            | x::xs,n -> x::take (n-1) xs
    let rec drop n xs =
        match xs,n with
            | xs,0 -> xs
            | [],_ -> []
            | _::xs,n -> drop (n-1) xs
    take n xs, drop n xs
(*[/omit]*)
// [/snippet]

// [snippet: (**) Problem 18 : Extract a slice from a list.]
/// Given two indices, i and k, the slice is the list containing the elements between the 
/// i'th and k'th element of the original list (both limits included). Start counting the 
/// elements with 1.
///  
/// Example: 
/// * (slice '(a b c d e f g h i k) 3 7)
/// (C D E F G)
///  
/// Example in F#: 
/// 
/// > slice ['a';'b';'c';'d';'e';'f';'g';'h';'i';'k'] 3 7;;
/// val it : char list = ['c'; 'd'; 'e'; 'f'; 'g']

(*[omit:(Solution 1)]*)
let slice xs s e =
    let rec take n xs =
        match xs,n with
            | _,0 -> []
            | [],_ -> []
            | x::xs,n -> x::take (n-1) xs
    let rec drop n xs =
        match xs,n with
            | xs,0 -> xs
            | [],_ -> []
            | _::xs,n -> drop (n-1) xs
    let diff = e - s
    xs |> drop (s - 1) |> take (diff + 1)
(*[/omit]*)

(*[omit:(Solution 2)]*)
let slice' xs s e = [ for (x,j) in Seq.zip xs [1..e] do
                            if s <= j then
                                yield x ]
(*[/omit]*)

(*[omit:(Solution 3)]*)
let slice'' xs s e = xs |> Seq.zip (seq {1 .. e}) |> Seq.filter(fst >> (<=) s) |> Seq.map snd
(*[/omit]*)
// [/snippet]

// [snippet: (**) Problem 19 : Rotate a list N places to the left.]
/// Hint: Use the predefined functions length and (@) 
/// 
/// Examples: 
/// * (rotate '(a b c d e f g h) 3)
/// (D E F G H A B C)
/// 
/// * (rotate '(a b c d e f g h) -2)
/// (G H A B C D E F)
///  
/// Examples in F#: 
/// 
/// > rotate ['a';'b';'c';'d';'e';'f';'g';'h'] 3;;
/// val it : char list = ['d'; 'e'; 'f'; 'g'; 'h'; 'a'; 'b'; 'c']
///  
/// > rotate ['a';'b';'c';'d';'e';'f';'g';'h'] (-2);;
/// val it : char list = ['g'; 'h'; 'a'; 'b'; 'c'; 'd'; 'e'; 'f']

(*[omit:(Solution 1)]*)
// using problem 17
let rotate xs n =
    let at = let ln = List.length xs in abs <| (ln + n) % ln
    let st,nd = split xs at
    nd @ st
(*[/omit]*)

(*[omit:(Solution 2)]*)
let rec rotate' xs n =
    match xs, n with
        | [], _ -> []
        | xs, 0 -> xs
        | x::xs, n when n > 0 -> rotate' (xs @ [x]) (n - 1)
        | xs, n -> rotate' xs (List.length xs + n)
(*[/omit]*)
// [/snippet]

// [snippet: (*) Problem 20 : Remove the K'th element from a list.]
/// Example in Prolog: 
/// ?- remove_at(X,[a,b,c,d],2,R).
/// X = b
/// R = [a,c,d]
///  
/// Example in Lisp: 
/// * (remove-at '(a b c d) 2)
/// (A C D)
///  
/// (Note that this only returns the residue list, while the Prolog version also returns 
/// the deleted element.)
///  
/// Example in F#: 
/// 
/// > removeAt 1 <| List.ofSeq "abcd";;
/// val it : char * char list = ('b', ['a'; 'c'; 'd'])

(*[omit:(Solution 1)]*)
let removeAt n xs = 
    let rec rmAt acc xs n =
        match xs, n with
            | [], _ -> failwith "empty list you fool!"
            | x::xs, 0 -> (x, (List.rev acc) @ xs)
            | x::xs, n -> rmAt (x::acc) xs (n - 1)
    rmAt [] xs n
(*[/omit]*)

(*[omit:(Solution 2)]*)
// using problem 17
let removeAt' n xs = 
    let front,back = split xs n
    List.head back, front @ List.tail back
(*[/omit]*)
// [/snippet]