This is an adaptation of the Ninety-Nine Prolog Problems written by Werner Hett at the Berne University of Applied Sciences in Berne, Switzerland.
From the original source:
The purpose of this problem collection is to give you the opportunity to practice your skills in logic programming. Your goal should be to find the most elegant solution of the given problems. Efficiency is important, but logical clarity is even more crucial. Some of the (easy) problems can be trivially solved using built-in predicates. However, in these cases, you learn more if you try to find your own solution.
The problems have different levels of difficulty. Those marked with a single asterisk (*) are easy. If you have successfully solved the preceding 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 Haskell 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.
Lists are recursive type in Haskell.
P01 (*) Find the last element of a list
Prelude> last1 ["a","b","c","d"]
"d"We are using last1 because Haskell already has last function.
P02 (*) Find the last but one element of a list
Prelude> secondLast [1, 2, 11, 4, 5, 8, 10, 6]
10When list is empty you should get exception as shown below.
Prelude> secondLast []
*** Exception: Can't find secondLast element from a list with less than 2 elementsWhen list has one element
Prelude> secondLast [1]
*** Exception: Can't find secondLast element from a list with less than 2 elementsP03 (*) Find the K'th element of a list
Prelude> kth [1,2,3,4,5] 3
4P04 (*) Find the number of elements of a list
Prelude> length' [1..5]
5length' is a valid function name in Haskell.
P05 (*) Reverse a list
Prelude> reverse' [1..5]
[5,4,3,2,1]P06 (*) Find out whether a list is a palindrome
Prelude> isPalindrome ["x","a","m","a","x"]
True
Prelude> isPalindrome [1,2,3,4,5]
FalseP07 (**) Flatten a nested list structure
Prelude> flatten (List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]])
[1,2,3,4,5]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
Prelude> compress ["a", "a", "a", "a", "b", "c", "c", "a", "a", "d", "e", "e", "e", "e"]
["a","b","c","a","d","e"]P09 (**) Pack consecutive duplicates of list elements into sublists
If a list contains repeated elements they should be placed in separate sublists.
Prelude> 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 1.09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as terms [N,E] where N is the number of duplicates of the element E.
Prelude> 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")]
P11 (*) Modified run-length encoding
Modify the result of problem 1.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] terms.
Prelude> encode_modified ["a", "a", "a", "a", "b", "c", "c", "a", "a", "d", "e", "e", "e", "e"]
[Right (4,"a"),Left "b",Right (2,"c"),Right (2,"a"),Left "d",Right (4,"e")]P12 (*) Decode a run-length encoded list
Prelude> decode [Right (4,"a"),Left "b",Right (2,"c"),Right (2,"a"),Left "d",Right (4,"e")]
["a","a","a","a","b","c","c","a","a","d","e","e","e","e"]P13 (**) 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 P09, but only count them.
Prelude> encode_direct ["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")]
P14 (*) Duplicate the elements of a list
Prelude> duplicate ["a","b","c","d"]
["a","a","b","b","c","c","d","d"]P15 (**) Duplicate the elements of a list a given number of times
Prelude> duplicate ["a","b","c"] 3
["a","a","a","b","b","b","c","c","c"]P16 (**) Drop every N'th element from a list
Prelude> dropEveryNth ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k"] 3
["a","b","d","e","g","h","j","k"]P17 (*) Split a list into two parts; the length of the first part is given
Prelude> split ["a", "b", "c", "d", "e", "f", "g", "h", "i", "k"] 3
(["a","b","c"],["d","e","f","g","h","i","k"])P18 (**) Extract a slice from a list
Prelude> slice ["a", "b", "c", "d", "e", "f", "g", "h", "i", "k"] 3 7
["c","d","e","f"]P19 (**) Rotate a list N places to the left
Prelude> rotate ["a", "b", "c", "d", "e", "f", "g", "h"] 3
["d","e","f","g","h","a","b","c"]
Prelude> rotate ["a", "b", "c", "d", "e", "f", "g", "h"] (-2)
["g","h","a","b","c","d","e","f"]P20 (*) Remove the K'th element from a list
Prelude> removeAt ["a", "b", "c", "d"] 2
(["a","c","d"],"b")P21 (*) Insert an element at a given position into a list
Prelude> insertAt ["a", "b", "c", "d"] 2 "alfa"
["a","alfa","b","c","d"]P22 (*) Create a list containing all integers within a given range
Prelude> range 4 9
[4,5,6,7,8,9]P23 (**) Extract a given number of randomly selected elements from a list
Prelude> randomSelect ["a", "b", "c", "d", "e", "f", "g", "h"] 3P24 (*) Lotto: Draw N different random numbers from the set 1..M
Hint: Combine the solutions of problems P22 and P23
Prelude> randomSelect_lotto 6 (1,49)
[48,2,42,42,2,8]P25 (*) Generate a random permutation of the elements of a list
Hint: Use the solution of problem P23
Prelude> randomPermutation ["a", "b", "c", "d", "e", "f"]
["b","a","b","c","a","a"]P26 (**) Generate the combinations of K distinct objects chosen from the N elements of a list
Prelude> combinations ["a", "b", "c", "d", "e", "f"] 3
[["a","b","c"],["a","b","d"],["a","c","d"],["b","c","d"],["a","b","e"],["a","c","e"],["b","c","e"],["a","d","e"],["b","d","e"],["c","d","e"],["a","b","f"],["a","c","f"],["b","c","f"],["a","d","f"],["b","d","f"],["c","d","f"],["a","e","f"],["b","e","f"],["c","e","f"],["d","e","f"]]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 predicate that generates all the possibilities via backtracking
Prelude> length (group3 ["aldo", "beat", "carla", "david", "evi", "flip", "gary", "hugo", "ida"])
1260b) Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.
Prelude> length(group' ["aldo", "beat", "carla", "david", "evi", "flip", "gary", "hugo", "ida"] [2,2,5])
756P28 (**) Sorting a list of lists according to length of sublists
a) We suppose that a list (InList) contains elements that are lists themselves. The objective is to sort the elements of InList according to their length. E.g. short lists first, longer lists later, or vice versa.
Prelude> lsort [["a", "b", "c"], ["d", "e"], ["f", "g", "h"], ["d", "e"], ["i", "j", "k"], ["m", "n"], ["o"]]
[["o"],["d","e"],["d","e"],["m","n"],["a","b","c"],["f","g","h"],["i","j","k"]]b) Again, we suppose that a list (InList) contains elements that are lists themselves. But this time the objective is to sort the elements of InList according to their length frequency; i.e. in the default, where sorting is done in ascending order, lists with rare lengths are placed first, others with a more frequent length come later.
Prelude> lfsort [["a", "b", "c"], ["d", "e"], ["f", "g", "h"], ["d", "e"], ["i", "j", "k","l"], ["m", "n"], ["o"]]
[["o"],["i","j","k","l"],["a","b","c"],["f","g","h"],["d","e"],["d","e"],["m","n"]]P31 (**) Determine whether a given integer number is prime.
Prelude> isPrime 7
TrueP32 (**) Determine the prime factors of a given positive integer.
Prelude> primeFactors 315
[3,3,5,7]
Prelude> primeFactors 33
[3,11]P33 (**) Determine the prime factors of a given positive integer (2).
Prelude> primeFactorsMult 315
[[3,2],[5,1],[7,1]]P34 (*) A list of prime numbers
Prelude> primeNumbers [7..31]
[7,11,13,17,19,23,29,31]P35 (**) Goldbach's conjecture
Prelude> goldbach 28
[5,23]P36 (**) 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.
Prelude> goldbach_list [9..20]
[(10,[3,7]),(12,[5,7]),(14,[3,11]),(16,[3,13]),(18,[5,13]),(20,[3,17])]In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, the primes are both bigger than say 50. Try to find out how many such cases there are in the range 2..3000.
Prelude> goldbach_list1 50 [1..2000]
[(992,[73,919]),(1382,[61,1321]),(1856,[67,1789]),(1928,[61,1867])]P37 (**) Determine the greatest common divisor of two positive integer numbers.
Prelude> gcd' 36 63
9P38 (*) Determine whether two positive integer numbers are coprime.
Prelude> coprime 25 64
TrueP39 (**) Calculate Euler's totient function phi(m).
Prelude> totient_phi 10
4P40 (**) Calculate Euler's totient function phi(m) (2).
See problem P39 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 2.03 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.
Prelude> phi 10
4
Prelude> phi 99
60
Also you can import modules defined in 01-lists by starting ghci using the command
ghci -i../01-lists
P41 (*) Compare the two methods of calculating Euler's totient function.
Use the solutions of problems P39 and P40 to compare the algorithms. Take the number of logical inferences as a measure for efficiency. Try to calculate phi(10090) as an example.
P46 (**) Truth tables for logical expressions.
Define predicates and/2, or/2, nand/2, nor/2, xor/2, impl/2 and equ/2 (for logical equivalence) which succeed or fail according to the result of their respective operations; e.g. and(A,B) will succeed, if and only if both A and B succeed. Note that A and B can be Prolog goals (not only the constants true and fail).
A logical expression in two variables can then be written in prefix notation, as in the following example: and(or(A,B),nand(A,B)).
Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables.
table (\a b -> (and' a (or' a b)))
[(True,True,True),(True,False,True),(False,True,False),(False,False,False)]
P47 (*) Truth tables for logical expressions(2).
Skipping this problem for now.
P48 (**) Truth tables for logical expressions(3).
Skipping this problem for now.
P49 (**) Gray code.
An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,
n = 1: C(1) = ['0','1'].
n = 2: C(2) = ['00','01','11','10'].
n = 3: C(3) = ['000','001','011','010','110','111','101','100'].
Prelude> gray 3
["000","001","011","010","110","111","101","100"]