F-99: Ninety-Nine F# Problems

Adapting from S-99: Ninety-Nine Scala Problems. Also worth seeing: http://fssnip.net/an and https://github.com/paks/99-FSharp-Problems/, and of course http://www.ic.unicamp.br/~meidanis/courses/mc336/2006s2/funcional/L-99_Ninety-Nine_Lisp_Problems.html.

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. The difficulties were all assigned for the Prolog problems, but the F# versions seem to be of roughly similar difficulty.

Working with lists

P01 (*) Find the last element of a list.

Example:
* (my-last '(a b c d))
(D)

	
> let my_last(L) = List.toSeq L |> Seq.last;;

val my_last : L:'a list -> 'a

> my_last [1; 1; 2; 3; 5; 8;];;
val it : int = 8
	
      

P02 (*) Find the last but one element of a list.

Example:
* (my-but-last '(a b c d))
(C D)

        
> let my_but_last L = List.toSeq L |> Seq.skip (List.length L - 2) ;;

val my_but_last : L:'a list -> seq<'a>

> my_but_last ['a' .. 'd'];;
val it : seq = seq ['c'; 'd']
        
      

P03 (*) Find the Kth element of a list.

The first element in the list is number 1.
Example:
* (element-at '(a b c d e) 3)
C

        
> let element_at (L, n) = List.nth L (n-1) ;;

val element_at : L:'a list * n:int -> 'a

> element_at (['a'..'e'], 3);;               
val it : char = 'c'
        
      

P04 (*) Find the number of elements of a list.

        
> List.length L;;
val it : int = 6
        
      

P05 (*) Reverse a list.

        
> List.rev L;;  
val it : int list = [8; 5; 3; 2; 1; 1]
        
      

P06 (*) Find out whether a list is a palindrome.

A palindrome can be read forward or backward; e.g. (x a m a x).

        
> L;;
val it : int list = [1; 1; 2; 3; 5; 8]
> L = List.rev L;;
val it : bool = false
> let L3 = [1; 2; 3; 4; 3; 2; 1;];;

val L3 : int list = [1; 2; 3; 4; 3; 2; 1]

> L3 = List.rev L3;;
val it : bool = true
        
      

P07 (**) Flatten a nested list structure.

Transform a list, possibly holding lists as elements into a `flat' list by replacing each list with its elements (recursively).

Example:
* (my-flatten '(a (b (c d) e)))
(A B C D E)

Hint: Use the predefined functions list and append.

P08 (**) Eliminate consecutive duplicates of list elements.

If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.

Example:
* (compress '(a a a a b c c a a d e e e e))
(A B C A D E)

        
> L ;;
val it : char list =
  ['a'; 'a'; 'a'; 'a'; 'a'; 'b'; 'b'; 'c'; 'd'; 'd'; 'd'; 'a'; 'a']
> List.foldBack (fun x res -> if List.isEmpty res then [ x ] else if List.head res = x then res else x::res) L [];;
val it : char list = ['a'; 'b'; 'c'; 'd'; 'a']
        
      

P09 (**) Pack consecutive duplicates of list elements into sublists.

If a list contains repeated elements they should be placed in separate sublists.

Example:
* (pack '(a a a a b c c a a d e e e e))
((A A A A) (B) (C C) (A A) (D) (E E E E))

P10 (*) Run-length encoding of a list.

Use the result of problem P09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as lists (N E) where N is the number of duplicates of the element E.

Example:
* (encode '(a a a a b c c a a d e e e e))
((4 A) (1 B) (2 C) (2 A) (1 D)(4 E))

        
> let pack xs = 
-     let collect x = function
-         | (y::xs)::xss when x = y -> (x::y::xs)::xss
-         | xss -> [x]::xss
-     List.foldBack collect xs []
- (* stolen from https://github.com/paks/99-FSharp-Problems/blob/master/P01to10/Solutions.fs ... :( *)
- ;;

val pack : xs:'a list -> 'a list list when 'a : equality

> L |> pack ;;
val it : char list list =
  [['a'; 'a'; 'a'; 'a']; ['b']; ['c'; 'c']; ['a'; 'a']; ['d'];
   ['e'; 'e'; 'e'; 'e']]
        
      

P11 (*) Modified run-length encoding.

Modify the result of problem P10 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) terms.

        
> L |> pack |> List.map ( fun x -> List.length x, List.head x ) ;;
val it : (int * char) list =
  [(4, 'a'); (1, 'b'); (2, 'c'); (2, 'a'); (1, 'd'); (4, 'e')]
        
      

P12 (**) Decode a run-length encoded list.

Given a run-length code list generated as specified in problem P10, construct its uncompressed version.

P13 (**) Run-length encoding of a list (direct solution).

Implement the so-called run-length encoding data compression method directly. I.e. don't use other methods you've written (like P09's pack); do all the work directly.

P14 (*) Duplicate the elements of a list.

        
> let L = ['a';'b';'c';'c';'d';];;

val L : char list = ['a'; 'b'; 'c'; 'c'; 'd']

> let duplicate L = List.foldBack (fun x res -> x::x::res) L [] ;;

val duplicate : L:'a list -> 'a list

> duplicate(L);;
val it : char list = ['a'; 'a'; 'b'; 'b'; 'c'; 'c'; 'c'; 'c'; 'd'; 'd']
        
      

P15 (**) Duplicate the elements of a list a given number of times.

        
> let duplicateN(n, L) = List.foldBack(fun x res -> Seq.append (List.replicate n x) res) L Seq.empty |> Seq.toList;;

val duplicateN : n:int * L:'a list -> 'a list

> duplicateN(3, L);;
val it : char list =
  ['a'; 'a'; 'a'; 'b'; 'b'; 'b'; 'c'; 'c'; 'c'; 'c'; 'c'; 'c'; 'd'; 'd'; 'd']
        
      

P16 (**) Drop every Nth element from a list.

        
> let drop(n, L) =
-   L |> List.mapi ( fun i x -> (i+1, x)) |> List.filter (fun (i, x) -> i % n <> 0) |> List.map (fun (_, x) -> x) ;;

val drop : n:int * L:'a list -> 'a list

> drop(3, L);;
val it : char list = ['a'; 'b'; 'd'; 'e'; 'g'; 'h'; 'j'; 'k']
        
      

P17 (*) Split a list into two parts.

The length of the first part is given. Use a Tuple for your result.

        
> let split(n, L) =                     
-     ((Seq.take n L), (Seq.skip n L))  
- ;;

val split : n:int * L:seq<'a> -> seq<'a> * seq<'a>

> split(2, L);;
val it : seq<char> * seq<char> =
  (seq ['a'; 'b'], seq ['c'; 'd'; 'e'; 'f'; ...])
        
      

P18 (**) Extract a slice from a list.

Given two indices, I and K, the slice is the list containing the elements from and including the Ith element up to but not including the Kth element of the original list. Start counting the elements with 0.

        
> let slice (n, m, L) = Seq.skip n L |> Seq.take m;;

val slice : n:int * m:int * L:seq<'a> -> seq<'a>

> slice(3, 7, L4);;
val it : seq<char> = seq ['d'; 'e'; 'f'; 'g'; ...]
        
      

P19 (**) Rotate a list N places to the left.

        
> let rotate (n, L) = 
-     Seq.append (Seq.skip n L) (Seq.take n L)
- ;;
> let L = [ 'a'..'f' ];;
> rotate(3,L);;
val it : seq<char> = seq ['d'; 'e'; 'f'; 'a'; ...]
        
      

P20 (*) Remove the Kth element from a list.

Return the list and the removed element in a Tuple. Elements are numbered from 0.

        
> let remove(n, L) =                            
-     Seq.append (Seq.take (n-1) L) (Seq.skip n L);;

val remove : n:int * L:seq<'a> -> seq<'a>

> remove(3, L);;
val it : seq = seq ['a'; 'b'; 'd'; 'e'; ...]
        
      

P21 (*) Insert an element at a given position into a list.

        
> let insert(E, n, L) =                       
-     let LL = Seq.append (Seq.take n L) [ E ]
-     Seq.append LL (Seq.skip n L)            
- ;;

val insert : E:'a * n:int * L:seq<'a> -> seq<'a>

> insert('Z', 2, L);;                         
val it : seq<char> = seq ['a'; 'b'; 'Z'; 'c'; ...]
        
      

P22 (*) Create a list containing all integers within a given range.

        
> [ 4..9 ];;
val it : int list = [4; 5; 6; 7; 8; 9]
        
      

P23 (**) Extract a given number of randomly selected elements from a list.

        
> let randomSelect(n, L) =
-     let rnd = new Random()
-     List.foldBack (fun x res -> Seq.append [(Seq.nth (rnd.Next(List.length L)) L)] res)  [ 1..n ] Seq.empty  
- ;;

val randomSelect : n:int * L:'a list -> seq<'a>

> randomSelect(4, L);;
val it : seq = seq ['g'; 'f'; 'h'; 'j']
        
      

P24 (*) Lotto: Draw N different random numbers from the set 1..M.

        
> let lotto(n, M) =
-     let rnd = new Random()                                                                                 
-     let L = [ 1..M]
-     List.foldBack (fun x res -> Seq.append [(Seq.nth (rnd.Next(List.length L)) L)] res)  [ 1..n ] Seq.empty |> Seq.to List
- ;;

val lotto : n:int * M:int -> int list

> lotto(6, 49);;
val it : int list = [3; 25; 12; 42; 39; 9]
        
      

P25 (*) Generate a random permutation of the elements of a list.

        
> let shuffle L =
-     let rnd = new Random()
-     L |> List.map (fun x -> (rnd.Next(), x)) |> List.sortBy fst |> List.map (fun (x,y) -> y)
- ;;

val shuffle : L:'a list -> 'a list

> shuffle L ;;
val it : char list = ['f'; 'd'; 'j'; 'h'; 'e'; 'b'; 'c'; 'g'; 'k'; 'a'; 'i']
> shuffle L ;;
val it : char list = ['d'; 'i'; 'b'; 'h'; 'j'; 'a'; 'f'; 'k'; 'e'; 'c'; 'g']
        
      

P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list.

In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). For pure mathematicians, this result may be great. But we want to really generate all the possibilities.

P27 (**) Group the elements of a set into disjoint subsets.

a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities.

P28 (**) Sorting a list of lists according to length of sublists.

a) We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of the list according to their length. E.g. short lists first, longer lists later, or vice versa.

        
> [ [ 1..5]; [ 2..4]; [ 1..2]; [1..10]; ] |> List.map (fun x -> (List.length x, x)) |> List.sortBy fst |> List.map (fun (_, x) -> x) ;;
val it : int list list =
  [[1; 2]; [2; 3; 4]; [1; 2; 3; 4; 5]; [1; 2; 3; 4; 5; 6; 7; 8; 9; 10]]
        
      

Arithmetic

For the next section, we're going to take a different tack with the solutions. We'll declare a new class, S99Int, and an implicit conversion from regular Ints. The arithmetic1 file contains the starting definitions for this section. Each individual solution will show the relevant additions to the S99Int class. The full class will be given at the end of the section.

P31 (**) Determine whether a given integer number is prime.

        
> let isprime (n:bigint) =
-     let rec check i =
-         i > n/2I || (n % i <> 0I && check (i + 1I))
-     check 2I
- ;;

> isprime 7I;;
val it : bool = true
        
      

P32 (**) Determine the greatest common divisor of two positive integer numbers.

Use Euclid's algorithm.

        
> let rec gcd a b =
-     if b = 0 then a else gcd b (a%b)
- ;;

val gcd : a:int -> b:int -> int

> gcd 25 49
- ;;
val it : int = 1
> gcd 25 48;;
val it : int = 1
> gcd 25 45;;
val it : int = 5
        
      

P33 (*) Determine whether two positive integer numbers are coprime.

Two numbers are coprime if their greatest common divisor equals 1.

        
> let coprime a b =
-     match gcd a b with
-     | 1 -> true
-     | _ -> false
- ;;

val coprime : a:int -> b:int -> bool

> coprime 35 64 ;;
val it : bool = true
> coprime 35 65 ;;
val it : bool = false
        
      

P34 (**) Calculate Euler's totient function phi(m).

Euler's so-called totient function phi(m) is defined as the number of positive integers r (1 <= r <= m) that are coprime to m.

        
> let phi m =
-     [ 1..m ] |> List.mapi (fun i x -> (i, coprime x m)) |> List.filter (fun (_,x) -> x = true) |> List.length
- ;;

val phi : m:int -> int

> phi 10;;
val it : int = 4
> phi 100;;
val it : int = 40
> phi 109900;;
val it : int = 37440
> phi 1090;;  
val it : int = 432
        
      

P35 (**) Determine the prime factors of a given positive integer.

Construct a flat list containing the prime factors in ascending order.

        
> let primeFactors n =  
-     let L = [ 2..n/2 ] |> List.filter (fun x -> isprime(bigint(x))) |> List.filter (fun x -> n%x = 0) 
-     (n/(List.reduce (fun x r -> r*x) L))::L |> List.sort
- ;;

val primeFactors : n:int -> int list

> primeFactors 315;;   
val it : int list = [3; 3; 5; 7]
        
      

P36 (**) Determine the prime factors of a given positive integer (2).

Construct a list containing the prime factors and their multiplicity.

        
> primeFactors 99 |> List.map ( fun x -> (x, 1) ) |> Seq.countBy fst ;;           
val it : seq = seq [(3, 2); (11, 1)]
        
      

P37 (**) Calculate Euler's totient function phi(m) (improved).

See problem P34 for the definition of Euler's totient function. If the list of the prime factors of a number m is known in the form of problem P36 then the function phi(m>) can be efficiently calculated as follows: Let [[p1, m1], [p2, m2], [p3, m3], ...] be the list of prime factors (and their multiplicities) of a given number m. Then phi(m) can be calculated with the following formula:

phi(m) = (p1 - 1) * p1 ** (m1 - 1) + (p2 - 1) * p2 ** (m2 - 1) + (p3 - 1) * p3 ** (m3 - 1) + ...

Note that a ** b stands for the b'th power of a.

P38 (*) Compare the two methods of calculating Euler's totient function.

Use the solutions of problems P34 and P37 to compare the algorithms. Try to calculate phi(10090) as an example.

P39 (*) A list of prime numbers.

Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.

        
> let primes n m =
-     [ n..m ] |> List.filter (fun x -> isprime x) 
- ;;

val primes : n:bigint -> m:bigint -> bigint list

> primes 100I 9000I |> List.map (fun x -> int(x));;
val it : int list =
  [101; 103; 107; 109; 113; 127; 131; 137; 139; 149; 151; 157; 163; 167; 173;
   179; 181; 191; 193; 197; 199; 211; 223; 227; 229; 233; 239; 241; 251; 257;
   263; 269; 271; 277; 281; 283; 293; 307; 311; 313; 317; 331; 337; 347; 349;
   353; 359; 367; 373; 379; 383; 389; 397; 401; 409; 419; 421; 431; 433; 439;
   443; 449; 457; 461; 463; 467; 479; 487; 491; 499; 503; 509; 521; 523; 541;
   547; 557; 563; 569; 571; 577; 587; 593; 599; 601; 607; 613; 617; 619; 631;
   641; 643; 647; 653; 659; 661; 673; 677; 683; 691; ...]
        
      

P40 (**) Goldbach's conjecture.

Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. E.g. 28 = 5 + 23. It is one of the most famous facts in number theory that has not been proved to be correct in the general case. It has been numerically confirmed up to very large numbers (much larger than Scala's Int can represent). Write a function to find the two prime numbers that sum up to a given even integer.

        
> let goldbach (n:bigint) =
-   let nn = List.filter (fun x -> isprime(n - x)) (List.filter (fun x -> isprime(x)) [ 2I..n ]) |> List.head
-   (nn, n-nn);;                                                          

val goldbach : n:bigint -> Numerics.BigInteger * Numerics.BigInteger

> goldbach 28I;;
val it : Numerics.BigInteger * Numerics.BigInteger =
  (5 {IsEven = false;
      IsOne = false;
      IsPowerOfTwo = false;
      IsZero = false;
      Sign = 1;}, 23 {IsEven = false;
                      IsOne = false;
                      IsPowerOfTwo = false;
                      IsZero = false;
                      Sign = 1;})
        
      

P41 (**) A list of Goldbach compositions.

Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.

        
> let goldbach2 (n:bigint, m:bigint) =
-    List.filter (fun x -> x%2I = 0I) [ n..m ] |> List.map (fun x -> (int(x), goldbach x) );;        

val goldbach2 : n:bigint * m:bigint -> (int * (int * int)) list

> goldbach2 (100I, 200I) ;;
val it : (int * (int * int)) list =
  [(100, (3, 97)); (102, (5, 97)); (104, (3, 101)); (106, (3, 103));
   (108, (5, 103)); (110, (3, 107)); (112, (3, 109)); (114, (5, 109));
   (116, (3, 113)); (118, (5, 113)); (120, (7, 113)); (122, (13, 109));
   (124, (11, 113)); (126, (13, 113)); (128, (19, 109)); (130, (3, 127));
   (132, (5, 127)); (134, (3, 131)); (136, (5, 131)); (138, (7, 131));
   (140, (3, 137)); (142, (3, 139)); (144, (5, 139)); (146, (7, 139));
   (148, (11, 137)); (150, (11, 139)); (152, (3, 149)); (154, (3, 151));
   (156, (5, 151)); (158, (7, 151)); (160, (3, 157)); (162, (5, 157));
   (164, (7, 157)); (166, (3, 163)); (168, (5, 163)); (170, (3, 167));
   (172, (5, 167)); (174, (7, 167)); (176, (3, 173)); (178, (5, 173));
   (180, (7, 173)); (182, (3, 179)); (184, (3, 181)); (186, (5, 181));
   (188, (7, 181)); (190, (11, 179)); (192, (11, 181)); (194, (3, 191));
   (196, (3, 193)); (198, (5, 193)); (200, (3, 197))]
        
      

Logic and Codes

Links and notes

• http://msdn.microsoft.com/en-us/library/ee370256.aspx
• http://stackoverflow.com/questions/7051531/random-generation-into-fsharp-list