Find the last element of a list.

Examples

>>> myLast [1,2,3,4]
Just 4

>>> myLast ['x','y','z']
Just 'z'

>>> myLast []
Nothing

Find the last but one element of a list.

Examples

>>> myButLast [1,2,3,4]
Just 3

>>> myButLast ['a'..'z']
Just 'y'

>>> myButLast ['a']
Nothing

Find the kth element of a list. The first element in the list is number 1.

Examples

>>> elementAt [1,2,3] 2
Just 2

>>> elementAt "haskell" 5
Just 'e'

>>> elementAt [1,2] 3
Nothing

Find the number of elements of a list.

Examples

>>> myLength [123, 456, 789]
3

>>> myLength "Hello, world!"
13

Reverse a list.

Examples

>>> myReverse "A man, a plan, a canal, panama!"
"!amanap ,lanac a ,nalp a ,nam A"

>>> myReverse [1,2,3,4]
[4,3,2,1]

Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. "xamax".

Examples

>>> isPalindrome [1,2,3]
False

>>> isPalindrome "madamimadam"
True

>>> isPalindrome [1,2,4,8,16,8,4,2,1]
True

Transform a list, possibly holding lists as elements, into a "flat" list by replacing each list with its elements recursively.

Examples

>>> flatten $ Elem 5
[5]

>>> flatten $ List [Elem 1, List [Elem 2, List [Elem 3, Elem 4], Elem 5]]
[1,2,3,4,5]

>>> flatten $ List []
[]

A list type with arbitrary nesting of lists.

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.

Examples

>>> compress "aaaabccaadeeee"
"abcade"

Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements, they should be placed in separate sublists.

Examples

>>> pack "aaaabccaadeeee"
["aaaa","b","cc","aa","d","eeee"]

Use the pack function to implement the so-called run-length encoding data compression method.

Consecutive duplicates of elements are encoded as tuples (n, e), where n is the number of duplicates of the element e.

Examples

>>> encode "aaaabccaadeeee"
[(4,'a'),(1,'b'),(2,'c'),(2,'a'),(1,'d'),(4,'e')]

Modify the encode function 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 (Multiple n x) values.

Examples

>>> encodeModified "aaaabccaadeeee"
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']

Encodes one or more consecutively duplicate elements.

Given a run-length code list generated by encodeModified, construct its uncompressed version.

Examples

>>> decodeModified [Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']
"aaaabccaadeeee"

Implement the so-called run-length encoding data compression method directly. I.e., do not explicitly create the sublists containing the duplicates, as with pack, but only count them.

As with encodeModified, simplify the result list by replacing the singletons (Multiple 1 x) by (Single x).

Examples

>>> encodeDirect "aaaabccaadeeee"
[Multiple 4 'a',Single 'b',Multiple 2 'c',Multiple 2 'a',Single 'd',Multiple 4 'e']

Duplicate the elements of a list.

Examples

>>> dupli [1, 2, 3]
[1,1,2,2,3,3]

Replicate the elements of a list a given number of times.

Examples

>>> repli "abc" 3
"aaabbbccc"

Drop every nth element from a list.

Examples

>>> dropEvery "abcdefghik" 3
"abdeghk"

Split a list into two parts; the length of the first part is given.

Examples

>>> split "abcdefghik" 3
("abc","defghik")

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, with both limits included. Start counting the elements with 1.

Examples

>>> slice "abcdefghijk" 3 7
"cdefg"

Rotate a list n places to the left.

Examples

>>> rotate "abcdefgh" 3
"defghabc"

>>> rotate "abcdefgh" (-2)
"ghabcdef"

Remove the kth element from a list. Return the element removed and the residue list.

Examples

>>> removeAt 2 "abcd"
('b',"acd")

Insert an element at a given position into a list.

Examples

>>> insertAt 'X' "abcd" 2
"aXbcd"

Create a list containing all integers within a given range.

Examples

>>> range 4 9
[4,5,6,7,8,9]

Extract a given number of randomly selected elements from a list.

Also return a new random number generator so that callers can avoid reusing a sequence of random numbers.

Examples

>>> fst $ randomSelect "abcdefgh" 3 $ mkStdGen 111
"chd"

>>> take 5 $ unfoldr (Just . randomSelect [1..100] 3) $ mkStdGen 111
[[11,19,76],[63,49,10],[75,42,12],[20,48,78],[40,94,86]]

>>> fst . randomSelect "abcdefgh" 3 <$> newStdGen
"ebf"

Draw \(n\) different random numbers from the set \( \{ k \,|\, 1 \leq k \leq m \} \).

Examples

>>> fst $ randomDraw 6 49 $ mkStdGen 111
[40,13,25,27,26,6]

>>> take 5 $ unfoldr (Just . randomDraw 3 100) $ mkStdGen 111
[[11,19,76],[63,49,10],[75,42,12],[20,48,78],[40,94,86]]

>>> fst . randomDraw 6 49 <$> newStdGen
[17,7,1,18,13,3]

Generate a random permutation of the elements of a list.

Examples

>>> fst $ randomPermute [1..10] $ mkStdGen 111
[8,4,7,9,3,5,10,2,1,6]

>>> take 5 $ unfoldr (Just . randomPermute ['a'..'d']) $ mkStdGen 111
["cbad","abdc","abdc","acdb","cdba"]

>>> fst . randomPermute "abcdef" <$> newStdGen
"dcaebf"

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 \({12 \choose 3} = 220\) possibilities, where \(n \choose k\) denotes the binomial coefficient. For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.

Examples

>>> length $ combinations 3 [1..12]
220

>>> sort $ combinations 3 "abcdef"
["abc","abd","abe",...]

In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3, and 4 persons? Given a list with the sizes of each group and list of items, write a function to return the list of disjoint groups.

Group sizes are larger than zero, and all items in the list to group are distinct. Note that we do not want permutations of the group members. E.g., [1,2] is the same group as [2,1]. However, different groups in the list are considered distinct. E.g., [[1,2],[3,4]] is considered a different list of groups from [[3,4],[1,2]].

You may find more about this combinatorial problem in a good book on discrete mathematics under the term multinomial coefficients.

Examples

>>> let names = ["aldo","beat","carla","david","evi","flip","gary","hugo","ida"]
>>> minimum $ map (map sort) $ disjointGroups [2,3,4] names
[["aldo","beat"],["carla","david","evi"],["flip","gary","hugo","ida"]]
>>> length $ disjointGroups [2,3,4] names
1260
>>> length $ disjointGroups [2,2,5] names
756

We suppose that a list contains elements that are lists themselves. Write a function to sort the elements of this list according to their length, i.e., short lists first and longer lists later.

Examples

>>> lsort ["xxx","xx","xxx","xx","xxxx","xx","x"]
["x","xx","xx","xx","xxx","xxx","xxxx"]

Again, we suppose that a list contains elements that are lists themselves. But this time, write a function to sort the elements of this list according to their length frequency, i.e., lists with rare lengths are placed first, others with a more frequent length come later.

Examples

>>> lfsort ["xxx", "xx", "xxx", "xx", "xxxx", "xx"]
["xxxx","xxx","xxx","xx","xx","xx"]

For \(n > 2\), the \(n\)th Fibonacci number \(F(n)\) is the sum of \(F(n-1)\) and \(F(n-2)\), and the first and second Fibonacci numbers are 1. I.e.,

\[ \begin{align} F(1) & = 1 \\ F(2) & = 1 \\ F(n) & = F(n-1) + F(n-2) \end{align} \]

Write a function to compute the \(n\)th Fibonacci number.

Examples

>>> map fibonacci [1..10]
[1,1,2,3,5,8,13,21,34,55]

Consider the following matrix equation, where \(F(n)\) is the \(n\)th Fibonacci number:

\[ \begin{pmatrix} x_2 \\ x_1 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix} \]

When written out as linear equations, this is equivalent to:

\[ \begin{align} x_2 & = F(n+1) + F(n) \\ x_1 & = F(n+1) \end{align} \]

So \(x_2 = F(n+2)\) and \(x_1 = F(n+1)\). Together with the associativity of matrix multiplication, this means:

\[ \begin{pmatrix} F(n+2) \\ F(n+1) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F(n+1) \\ F(n) \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2 \begin{pmatrix} F(n) \\ F(n-1) \end{pmatrix} = \cdots = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F(2) \\ F(1) \end{pmatrix} \]

Take advantage of this to write a function which computes the \(n\)th Fibonacci number with \(O(\log n)\) multiplications.

Compare with the solution for Problems.P29:

$ stack bench --benchmark-arguments="P29/fibonacci P30/fibonacci'"

Examples

>>> map fibonacci' [1..10]
[1,1,2,3,5,8,13,21,34,55]

>>> fibonacci' 1000000
19532821287077577316...

>>> length $ show $ fibonacci' 1000000
208988

Hint

Determine whether a given integer number is prime.

Examples

>>> isPrime 7
True

>>> isPrime 15
False

Determine the greatest common divisor of two positive integer numbers. Use Euclid's algorithm.

Examples

>>> myGCD 36 63
9

>>> myGCD 125 81
1

>>> myGCD 221 559
13

Determine whether two positive integer numbers are coprime. Two numbers are coprime if their greatest common divisor equals 1.

Examples

>>> coprime 35 64
True

>>> coprime 1173 1547
False

Calculate Euler's totient function \(\phi(m)\).

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

For example, with \(m = 10\), \(\{r \,|\, 1 \leq r \leq m, \textrm{coprime to $m$}\} = \{ 1, 3, 7, 9 \}\); thus \(\phi(m) = 4\). Note the special case of \(\phi(1) = 1\).

Examples

>>> totient 10
4

Determine the prime factors of a given positive integer. Construct a list containing the prime factors in ascending order.

Examples

>>> primeFactors 315
[3,3,5,7]

Determine the prime factors of a given positive integer. Construct a list containing the prime factors and their multiplicity.

Examples

>>> primeFactorsMultiplicity 315
[(3,2),(5,1),(7,1)]

Calculate Euler's totient function \(\phi(m)\). See totient for the definition of Euler's totient function.

Implement an improved version based on Euler's product formula. If the prime factors of \(m\) are known, i.e.,

\[ m = \prod_{i=1}^r {p_i}^{k_i} \]

where \(p_i\) is prime and \(k_i \geq 1\), then

\[ \phi(m) = \prod_{i=1}^r {p_i}^{k_i - 1} (p_i - 1) \]

Compare with the solution for Problems.P34:

$ stack bench --benchmark-arguments="P34/totient P37/totient'"

Examples

>>> totient' 10
4

It is possible for more than one number \(x\) to have the same totient number \(\phi(x)\). For example, \(\phi(77) = \phi(93) = 60\).

A highly totient number \(n\) has the most such \(x\) among the totient numbers less than or equal to \(n\). I.e., \(n\) is a highly totient number if \(|\{x \,|\, \phi(x)=n \}| > |\{x \,|\, \phi(x)=m \}|\) for \(m < n\).

Construct the list of highly totient numbers.

Examples

>>> take 10 highlyTotientNumbers
[1,2,4,8,12,24,48,72,144,240]

Hint

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

Examples

>>> primesR 10 20
[11,13,17,19]

Construct the list of all prime numbers.

Examples

>>> take 5 primes
[2,3,5,7,11]

Goldbach's conjecture says that every positive even number greater than 2 is the sum of two prime numbers. For example: \(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.

Write a function to find two prime numbers that sum up to a given even integer.

Examples

>>> goldbach 12
(5,7)

Given a range of integers by its lower and upper limit, return a list of all Goldbach compositions for the even numbers in the range.

In most cases, if an even number is written as the sum of two prime numbers, one of them is very small. Very rarely, it cannot be a sum of primes for which at least one is smaller than, say, 50. Try to find out how many such cases there are in the range \([2,3000]\).

Examples

>>> goldbachList 9 20
[(3,7),(5,7),(3,11),(3,13),(5,13),(3,17)]

>>> filter (\(m,n) -> m > 100 && n > 100) $ goldbachList 2 3000
[(103,2539)]

In modular arithmetic, integers \(a\) and \(b\) being congruent modulo an integer \(n\), also written as \(a \equiv b \pmod{n}\), means that \(a - b = kn\) for some integer \(k\). Many of the usual rules for addition, subtraction, and multiplication in ordinary arithmetic also hold for modular arithmetic.

A multiplicative inverse of an integer \(a\) modulo \(n\) is an integer \(x\) such that \(ax \equiv 1 \pmod{n}\). It exists if and only if \(a\) and \(n\) are coprime.

Write a function to compute the multiplicative inverse \(x\) of a given integer \(a\) and modulus \(n\) lying in the range \(0 \leq x < n\). Use the extended Euclidean algorithm and the fact that \(ax \equiv 1 \pmod{n}\) if \(ax+ny=1\).

Examples

>>> multiplicativeInverse 3 5
Just 2

>>> multiplicativeInverse 48 127
Just 45

>>> multiplicativeInverse 824 93
Just 50

>>> multiplicativeInverse 48 93
Nothing

A Gaussian integer is a complex number where both the real and imaginary parts are integers. If \(x\) and \(y\) are Gaussian integers where \(y \neq 0\), then \(x\) is said to be divisible by \(y\) if there is a Guassian integer \(z\) such that \(x=yz\).

Determine whether a Gaussian integer is divisible by another.

Examples

\(10 = 2 \times 5\), so

>>> (10 :+ 0) `gaussianDividesBy` (2 :+ 0)
True

\(10 = -2i \times 5i\), so

>>> (10 :+ 0) `gaussianDividesBy` (0 :+ 2)
True

However, there is no Gaussian integer \(x\) such that \(5+2i = (2-i)x\), so

>>> (5 :+ 2) `gaussianDividesBy` (2 :+ (-1))
False

Hint

A Gaussian integer \(x\) is said to be a Gaussian prime when it has no divisors except for the units and associates of \(x\). The units are \(1\), \(i\), \(-1\), and \(-i\). The associates are defined by the numbers obtained when \(x\) is multiplied by each unit.

Determine whether a Gaussian integer is a Gaussian prime.

Examples

Since \(5i = (2+i)(1+2i)\),

>>> isGaussianPrime (0 :+ 5)
False

Since \(17 = (4+i)(4-i)\),

>>> isGaussianPrime (17 :+ 0)
False

No non-unit proper divisors divide \(5+2i\), so

>>> isGaussianPrime (5 :+ 2)
True

Hint

Using Fermat's two-square theorem, it can be shown that a Gaussian integer \(a+bi\) is prime if and only if it falls into one of the following categories:

• |a| is prime and \(|a| \equiv 3 \mod 4\), if \(b=0\).
• |b| is prime and \(|b| \equiv 3 \mod 4\), if \(a=0\).
• \( a^2 + b^2 \) is prime, if \( a \neq 0 \) and \( b \neq 0 \).

Use this property to determine whether a Gaussian integer is a Gaussian prime.

Compare with the solution for Problems.P44:

$ stack bench --benchmark-arguments="P44/isGaussianPrime P45/isGaussianPrime'"

Examples

>>> isGaussianPrime' (0 :+ 5)
False

>>> isGaussianPrime' (17 :+ 0)
False

>>> isGaussianPrime' (5 :+ 2)
True

Define boolean functions and', or', nand', nor', xor', impl', and equ', which succeed or fail according to the result of their respective operations; e.g., (and' a b) is true if and only if both a and b are true. Do not use the builtin boolean operators.

A logical expression in two variables can then be written as in the following example:

\a b -> and' (or' a b) (nand' a b)

Write a function table which returns the truth table of a given logical expression in two variables.

Notes

Truth tables for logical expressions with two operands.

The truth table will be a list of (Bool, Bool, Bool) tuples. If f is the logical expression, a tuple (a, b, c) in the list will mean that (f a b == c). The list will include all possible distinct combinations of the tuples.

Examples

>>> printTable $ table (\a b -> (and' a (or' a b)))
False False False
False True  False
True  False True
True  True  True

Consider a logic circuit composed of NAND gates with binary input, specified as follows.

• A list of pairs of numbers for each NAND gate.

• A pair (i,j) in the list denotes that the inputs for the NAND gate are the outputs for the ith and jth gates in the list, respectively, with the first element starting at index 1.

  • As a special case, -1 and -2 denote the first and second boolean variables fed into the circuit, respectively.
  • An input to a NAND gate can only use output from a NAND gate which appears earlier in the list.
• The output of the last gate in the list is the output of the logic circuit.

Write a function to evaluate a given logic circuit as specified above.

Examples

>>> evaluateCircuit [(-1,-2)] True True
False

>>> evaluateCircuit [(-1,-2)] True False
True

>>> evaluateCircuit [(-1,-2), (1,1)] True True
True

>>> evaluateCircuit [(-1,-2), (1,1)] True False
False

>>> evaluateCircuit [(-1,-1),(-2,-2),(1,2)] True False
True

>>> evaluateCircuit [(-1,-1),(-2,-2),(1,2)] False False
False

Any boolean function can be computed with logic circuits composed solely of NAND gates. I.e., NAND is a universal logic gate.

Write a function to return a logic circuit composed of NAND gates which computes a given a binary boolean function. The logic circuit should be in a form which evaluateCircuit can evaluate.

Examples

>>> evaluateCircuit (buildCircuit (&&)) False False
False

>>> evaluateCircuit (buildCircuit (&&)) False True
False

>>> evaluateCircuit (buildCircuit (&&)) True False
False

>>> evaluateCircuit (buildCircuit (&&)) True True
True

Hint

Truth tables for logical expressions with an arbitrary number of variables.

Generalize table in a way that the logical expression may contain any number of logical variables. Define tablen such that tablen n f prints the truth table for the expression f, which contains n logical variables.

Examples

>>> printTablen $ tablen 3 (\[a,b,c] -> a `and'` (b `or'` c) `equ'` a `and'` b `or'` a `and'` c)
False False False False
False False True  False
False True  False False
False True  True  True
True  False False False
True  False True  True
True  True  False False
True  True  True  True

An n-bit Gray code is a sequence of n-bit strings constructed according to certain rules. For example,

>>> gray 1  -- 1-bit gray code
["0","1"]

>>> gray 2  -- 2-bit gray code
["00","01","11","10"]

>>> gray 3  -- 3-bit gray code
["000","001","011","010","110","111","101","100"]

Infer the construction rules and write a function returning the n-bit Gray code.

Given a list of characters and their number of occurrences, construct a list of the characters and their Huffman encoding.

In the encoding, '0' and '1' will denote the 0 and 1 bits.

Examples

>>> huffman [('a',45),('b',13),('c',12),('d',16),('e',9),('f',5)]
[('a',"0"),('b',"101"),('c',"100"),('d',"111"),('e',"1101"),('f',"1100")]

The encoding table computed by huffman can be used to compress data:

>>> length $ encodeHuffman (huffman $ countCharacters text) text
3552

Compare this to the length of a fixed-length 5-bit encoding:

>>> length $ encodeHuffman loweralpha text
4375

or the length of the more standard ASCII encoding with 8 bits:

>>> length $ encodeHuffman ascii text
7000

Huffman coding is unambiguous, so we can get back the original text:

>>> let table = huffman $ countCharacters text
>>> let encodedText = encodeHuffman table text
>>> let decodedText = decodeHuffman table encodedText
>>> decodedText == text
True

Flip a given number of boolean values in the boolean list randomly.

Examples

>>> corrupt (mkStdGen 111) 2 [False, True, True, False, True]
[False,False,True,True,False]

Construct an error-correcting encoding of the given Boolean list.

The encoding must be able to correct at least one error. Consider using a repetition code of length 3.

The inverse of errorCorrectingEncode. Recover the original Boolean list from its encoding. There could be a single error in the encoding.

Examples

>>> errorCorrectingDecode . errorCorrectingEncode $ [False, False, True, False]
[False,False,True,False]

>>> let e = errorCorrectingEncode [True, False, False, True, False]
>>> let e' = corrupt (mkStdGen 111) 1 e
>>> errorCorrectingDecode e'
[True,False,False,True,False]

It is known that any boolean function can be represented in conjunctive normal form. These are conjunctions of disjunctions of literals, where literals are one of boolean values, variables, or the complement of values or variables. For example, the boolean formula \(\neg(x \wedge \neg y) \wedge (z \vee w)\) is equivalent to the conjunctive normal form \( (\neg x \vee y) \wedge (z \vee w) \).

Return the conjunctive normal form of a boolean formula. The value returned should always be a conjunction of disjunctions.

Examples

>>> toConjunctiveNormalForm $ Value True
Conjoin [Disjoin [Value True]]

>>> toConjunctiveNormalForm $ Complement $ Disjoin [Variable "X", Variable "Y"]
Conjoin [Disjoin [Complement (Variable "X")],Disjoin [Complement (Variable "Y")]]

>>> :{
toConjunctiveNormalForm $ Disjoin [ Variable "X"
                                  , Conjoin [ Complement $ Variable "Y"
                                            , Variable "Z"
                                            ]
                                  ]
:}
Conjoin [Disjoin [Variable "X",Complement (Variable "Y")],Disjoin ...

Hint

Represents a boolean formula.

In propositional logic, if a formula \(X\) is always true when a set of axioms \(\mathrm{S}\) are true, then \(X\) is said to be valid given \(\mathrm{S}\).

The resolution rule is an inference rule in propositional logic where two clauses with complementary literals can be merged to produce another clause. Specifically, if clauses \(x \vee a_1 \vee \ldots \vee a_m\) and \(\neg x \vee b_1 \vee \ldots \vee b_n\) are true, then the clause \(a_1 \vee \ldots \vee a_m \vee b_1 \vee \ldots \vee b_n\) must also be true. This is commonly expressed as

\[ x \vee a_1 \vee \ldots \vee a_m \hspace{2em} \neg x \vee b_1 \vee \ldots \vee b_n \above 1pt a_1 \vee \ldots \vee a_m \vee b_1 \vee \ldots \vee b_n \]

The resolution rule can be used with conjunctive normal forms to prove whether or not a given formula \(X\) is valid given a set of axioms \(\mathrm{S}\). It is a proof by contradiction, and the procedure is as follows:

1. Conjunctively connect the formulas in \(\mathrm{S}\) and the negation of \(X\) into a single formula \(Y\).

   For example, if the axioms are \(x\) and \(y\), and the given formula is \(z\), then \(Y\) would be \(x \wedge y \wedge \neg z\).

   • Do not apply the resolution rule to the values of true and false. If \(Y\) contains raw true or false values, transform \(Y\) into a form which contains none.
2. Convert \(Y\) into conjunctive normal form; see Problems.P52.

3. If there are two clauses for which the resolution rule can be applied, add the new clause to \(Y\) and repeat until an empty clause is inferred or if no new clauses can be added. Filter out tautologies, i.e., clauses which will always be true because it contains both a variable and its logical complement.

   • If the empty clause has been inferred, then false has been inferred from \(Y\). I.e., there is a contradiction, so \(X\) must have been valid given the axioms \(\mathrm{S}\).
   • If no more clauses can be inferred, then \(X\) cannot be inferred to be valid.

Given a list of axioms and a formula, use the resolution rule to determine whether the formula is valid given the axioms.

Examples

When \(x \wedge y \wedge z\) is true, then obviously \(x \vee y\) is true, so

>>> :{
isTheorem
  [ Variable "X", Variable "Y", Variable "Z" ] $
  Disjoin [ Variable "X", Variable "Y" ]
:}
True

When \(x \to y\) and \(y \to z\), or equivalently \(\neg x \vee y\) and \(\neg y \vee z\), then it is also the case that \(x \to z\), so

>>> :{
    isTheorem
      [ Disjoin [ Complement $ Variable "X", Variable "Y" ]
      , Disjoin [ Complement $ Variable "Y", Variable "Z" ]
      ] $
      Disjoin [ Complement $ Variable "X", Variable "Z" ]
:}
True

Just because \(x\) is true does not mean that \(y\) is true, so

>>> isTheorem [ Variable "X" ] $ Variable "Y"
False

If there is a contradiction, then everything is both true and false, so

>>> isTheorem [ Variable "X", Complement $ Variable "X" ] $ Value False
True

A binary tree.

A Tree of type a consists of either an Empty node, or a Branch containing one value of type a with exactly two subtrees of type a.

Notes

Define a shorthand function for constructing a leaf node.

A leaf node in Tree is a branch with two empty subtrees.

Define as the tree as shown in the following.

Define as a binary tree consisting of only a single root node with value 'a'.

Define as an empty binary tree.

Define as the following tree with integer values.

In a completely balanced binary tree, the following property holds for every node: The number of nodes in its left subtree and the number of nodes in its right subtree are almost equal, which means their difference is not greater than one.

Write a function to construct completely balanced binary trees for a given number of nodes.

Examples

>>> printTreeList $ completelyBalancedTrees 4
[ Branch () (Branch () (Branch () Empty Empty) Empty) (Branch () Empty Empty)
, Branch () (Branch () Empty Empty) (Branch () (Branch () Empty Empty) Empty)
, Branch () (Branch () Empty Empty) (Branch () Empty (Branch () Empty Empty))
, Branch () (Branch () Empty (Branch () Empty Empty)) (Branch () Empty Empty) ]

Let us call a binary tree symmetric if you can draw a vertical line through the root node and then the right subtree is the mirror image of the left subtree. Write a function symmetric to check whether a given binary tree is symmetric. We are only interested in the structure, not in the contents of the nodes.

Examples

>>> symmetric (Branch 'x' (Branch 'x' Empty Empty) Empty)
False

>>> symmetric (Branch 'x' (Branch 'x' Empty Empty) (Branch 'x' Empty Empty))
True

Hint

Write an addedTo function which adds an element to a binary search tree to obtain another binary search tree. Use this function to construct a binary search tree from a list of ordered elements. Each element should be added from the front to the back of the list.

Examples

>>> construct [3, 2, 5, 7, 1]
Branch 3 (Branch 2 (Branch 1 Empty Empty) Empty) (Branch 5 Empty (Branch 7 Empty Empty))

>>> symmetric . construct $ [5, 3, 18, 1, 4, 12, 21]
True

>>> symmetric . construct $ [3, 2, 5, 7, 1]
True

Notes

Return a binary search tree with an element added to another binary search tree.

Use a simple insertion algorithm which leaves the tree mostly the same except for the new element in a leaf node. In particular, no balancing should be done.

Examples

>>> 8 `addedTo` Branch 5 Empty (Branch 7 Empty (Branch 9 Empty Empty))
Branch 5 Empty (Branch 7 Empty (Branch 9 (Branch 8 Empty Empty) Empty))

Construct all symmetric, completely balanced binary trees with a given number of nodes.

Examples

>>> printTreeList $ symmetricBalancedTrees 5
[ Branch () (Branch () (Branch () Empty Empty) Empty) (Branch () Empty (Branch () Empty Empty))
, Branch () (Branch () Empty (Branch () Empty Empty)) (Branch () (Branch () Empty Empty) Empty) ]

In a height-balanced binary tree, the following property holds for every node: The height of its left subtree and the height of its right subtree are almost equal, which means their difference is not greater than one.

Construct a list of all height-balanced binary trees with the given maximum height.

Examples

>>> printTreeList $ heightBalancedTrees 2
[ Branch () (Branch () Empty Empty) Empty
, Branch () (Branch () Empty Empty) (Branch () Empty Empty)
, Branch () Empty (Branch () Empty Empty) ]

>>> length $ heightBalancedTrees 4
315

Construct all the height-balanced binary trees with a given number of nodes.

Examples

>>> length $ heightBalancedTreesWithNodes 15
1553

>>> mapM_ printTreeList $ map heightBalancedTreesWithNodes [0..3]
[ Empty ]
[ Branch () Empty Empty ]
[ Branch () (Branch () Empty Empty) Empty
, Branch () Empty (Branch () Empty Empty) ]
[ Branch () (Branch () Empty Empty) (Branch () Empty Empty) ]

Hint

Notes

Collect the leaves of a binary tree in a list. A leaf is a node with no successors.

Examples

>>> sort $ leaves tree4
[2,4]

Notes

Collect the internal nodes of a binary tree in a list.

An internal node of a binary tree has either one or two non-empty successors.

Examples

>>> sort $ internals tree4
[1,2]

Collect the nodes at a given level in a list

A node of a binary tree is at level \(n\) if the path from the root to the node has length \(n-1\). The root node is at level 1.

Examples

>>> atLevel tree4 2
[2,2]

Notes

A complete binary tree with height \(h\) is defined as follows:

• The levels 1, 2, 3, ..., \(h-1\) contain the maximum number of nodes, i.e., \(2^{i-1}\) at level \(i\).
• On level \(h\), which may contain less than the maximum possible number of nodes, all the nodes are "left-adjusted". This means that in a level-order tree traversal all internal nodes come first, the leaves come second, and empty successors (the Emptys, which are not really nodes of the tree) come last.

In particular, complete binary trees are used as data structures or addressing schemes for heaps.

Write a function to construct a complete binary tree with the given number of nodes.

Examples

>>> completeBinaryTree 4
Branch () (Branch () (Branch () Empty Empty) Empty) (Branch () Empty Empty)

Hint

Write a function to return whether a tree is a complete binary tree.

Examples

>>> isCompleteBinaryTree $ Branch () (Branch () Empty Empty) Empty
True

>>> isCompleteBinaryTree $ Branch () Empty (Branch () Empty Empty)
False

Let's say we want to draw a binary tree. In preparation, a layout algorithm is required to determine the position of each node in a rectangular grid. Several layout methods are conceivable. One of them is shown in the illustration below:

In this layout strategy, the position of a node \(v\) is obtained by the following two rules:

• \(x(v)\) is equal to the position of the node \(v\) in the in-order sequence.
• \(y(v)\) is equal to the depth of the node \(v\) in the tree.

Write a function to annotate each node of the tree with a position, where \((1,1)\) is the top left corner of the rectangle bounding the drawn tree.

Examples

>>> layoutInorder tree64
Branch ('n',(8,1)) (Branch ('k',(6,2)) (Branch ('c',(2,3)) ...

Notes

An alternative layout method is depicted in the illustration below:

Find out the rules and write the corresponding function. Use the same conventions as in Problems.P64.

Examples

>>> layoutLevelConstant tree65
Branch ('n',(15,1)) (Branch ('k',(7,2)) (Branch ('c',(3,3)) ...

Hint

Yet another layout strategy is shown in the illustration below:

The method yields a very compact layout while maintaining a certain symmetry in every node. Find out the rules and write the corresponding function. Use the same conventions as in Problems.P64 and Problems.P65.

Examples

>>> layoutCompact tree65
Branch ('n',(5,1)) (Branch ('k',(3,2)) (Branch ('c',(2,3)) ...

Hint

Somebody represents binary trees as strings of the following form:

a(b(d,e),c(,f(g,)))

Write a function to generate this string representation from a binary tree.

Examples

>>> treeToString $ Branch 'x' (Branch 'y' Empty Empty) (Branch 'a' Empty (Branch 'b' Empty Empty))
"x(y,a(,b))"

Write a function to construct a tree from the string representation.

Examples

>>> stringToTree "x(y,a(,b))"
Just (Branch 'x' (Branch 'y' Empty Empty) (Branch 'a' Empty (Branch 'b' Empty Empty)))

Return the in-order sequence of a binary tree.

Examples

>>> inorder tree1
"dbeacgf"

Return the pre-order sequence of a binary tree.

Examples

>>> preorder tree1
"abdecfg"

Given the in-order and pre-order sequences of a binary tree, return the original binary tree.

The values in each node of the binary tree will be distinct, in which case the tree is determined unambiguously.

Examples

>>> ordersToTree "dbeacgf" "abdecfg" == Just tree1
True

Consider binary trees with nodes that are identified by single characters. Such a tree can be represented by the preorder sequence of its nodes in which dots (.) are inserted where an empty subtree is encountered during the tree traversal.

Write a function to convert a dotstring representation into its corresponding binary tree.

Examples

>>> dotstringToTree "xy..z0..."
Just (Branch 'x' (Branch 'y' Empty Empty) (Branch 'z' (Branch '0' Empty Empty) Empty))

Write a function to convert a binary tree to its dotstring representation.

Examples

>>> treeToDotstring tree1
"abd..e..c.fg..."

A multiway tree is composed of a root element and a (possibly empty) set of successors which are multiway trees themselves. A multiway tree is never empty. The set of successor trees is sometimes called a forest.

Example of the following multiway tree.

>>> multitree1 == MultiwayTree 'a' []
True

Example of the following multiway tree.

>>> multitree2 == MultiwayTree 'a' [MultiwayTree 'b' []]
True

Example of the following multiway tree.

>>> multitree3 == MultiwayTree 'a' [MultiwayTree 'b' [MultiwayTree 'c' []]]
True

Example of the following multiway tree.

>>> multitree4 == MultiwayTree 'b' [MultiwayTree 'd' [], MultiwayTree 'e' []]
True

Example of the following multiway tree.

>>> :{
multitree5 == MultiwayTree 'a'
  [ MultiwayTree 'f' [MultiwayTree 'g' []]
  , MultiwayTree 'c' []
  , MultiwayTree 'b' [MultiwayTree 'd' [], MultiwayTree 'e' []]
  ]
:}
True

We suppose that the nodes of a multiway tree contain single characters. The characters in the node string are in depth-first order of the tree. The special character ^ is inserted whenever the move is a backtrack to the previous level during tree traversal. Note that the tree traversal will also backtrack from the root node of the tree.

For example, multitree5 is represented by the string "afg^^c^bd^e^^^".

Write a function to construct the MultiwayTree when the string is given.

Examples

>>> stringToMultitree "afg^^c^bd^e^^^" == Just multitree5
True

Construct the node string from a MultiwayTree.

Examples

>>> multitreeToString multitree5
"afg^^c^bd^e^^^"

Determine the internal path length of a tree.

We define the internal path length of a multiway tree as the total sum of the path lengths from the root to all nodes of the tree. By this definition, multitree5 has an internal path length of 9.

Examples

>>> internalPathLength multitree5
9

>>> internalPathLength multitree4
2

Construct the post-order sequence of the tree nodes.

Examples

>>> postOrderSequence multitree5
"gfcdeba"

Notes

An s-expression is commonly represented as a list of items between parentheses. In particular, s-expressions can be nested, e.g., (a b (c d) e (f g)). It is used by programming languages such as Lisp and Scheme.

A possible way to represent a multiway tree with an s-expression is for the first element in a list to represent the root of the tree, and the rest of the elements in the list would be its children. As a special case, a multiway tree with no children is represented without parentheses.

Write a function which will return this s-expression representation of a multiway tree as a string.

Examples

>>> treeToSexp multitree1
"a"

>>> treeToSexp multitree2
"(a b)"

>>> treeToSexp multitree3
"(a (b c))"

>>> treeToSexp multitree4
"(b d e)"

>>> treeToSexp multitree5
"(a (f g) c (b d e))"

Notes

Write a function which will convert an s-expression, representing a multiway tree as in treeToSexp, into a MultiwayTree.

Examples

>>> sexpToTree "(a (f g) c (b d e))" == Just multitree5
True

We would like to implement a function which reads an even number from standard input, finds two prime numbers which add up to the number (see goldbach), and prints out the equation to standard output.

Given the use of input and ouput, this could be written with the IO monad in do notation:

askGoldbach :: Handle -> Handle -> IO ()
askGoldbach hIn hOut = do
  s <- hGetLine hIn
  let n = read s :: Int
  let (a,b) = goldbach n
  hPutStr hOut $ show n
  hPutStr hOut "="
  hPutStr hOut $ show a
  hPutStr hOut "+"
  hPrint hOut b

Implement the function without do notation. In other words, use >>= or >> directly, instead of using them implicitly through do notation. Try to use these functions with prefix style instead of infix style.

Examples

>>> withFixedInput "104" stdout askGoldbach
104=3+101

Hint

do
  a
  b

(>>) a b

(>>=) a (\_ -> b)

do
  x <- a
  b

(>>=) a (\x -> b)

f :: SomeMonad (Int,Int)
f = do
  (a,b) <- return (1,2)
  return (a+1,b+1)

f :: IO String
f = do
  s <- getLine
  return $ "Got string: " ++ s

In Problems.P75, askGoldbach could not output an error if the input was not a number or it was not an even number greater than 2. We could implement a function which returned Nothing when the input is not valid, such as in the following.

maybeGoldbach :: String -> Maybe (Int, (Int,Int))
maybeGoldbach s =
  case readMaybe s of
    Nothing -> Nothing
    Just n -> if n < 2 then Nothing else
                if odd n then Nothing else
                  Just (n, goldbach n)

Then we could take advantage of this function to print out an error if the input is not valid.

>>> :{
let format (n, (a,b)) = (show n) ++ "=" ++ (show a) ++ "+" ++ (show b)
    maybeAskGoldbach hIn hOut = do
      s <- hGetLine hIn
      case maybeGoldbach s of
        Nothing -> hPutStrLn hOut "error"
        Just x  -> hPutStrLn hOut $ format x
in do
  withFixedInput "104" stdout maybeAskGoldbach
  withFixedInput "not a number" stdout maybeAskGoldbach
:}
104=3+101
error

However, the implementation of maybeGoldbach above is a chain of conditional expressions. It is not problematic in this particular case, but can make things awkward when there are many conditions and successful operations that need to happen for a function to return a Maybe value.

Take advantage of the fact that Maybe is a monad and rewrite maybeGoldbach more succintly using do notation. The guard function, which in the Maybe monad returns Just () when its argument is true and Nothing when its argument is false, would be useful for making it even more succinct.

Examples

>>> maybeGoldbach "104"
Just (104,(3,101))

>>> maybeGoldbach "not a number"
Nothing

>>> maybeGoldbach "1"
Nothing

>>> maybeGoldbach "101"
Nothing

In Problems.P75, maybeGoldbach returned Nothing when there is an error. However, this revealed nothing about why there is an error.

Either is a data type which can hold either of two data types, which can be used to store either an error or a correct value when there is no error. By convention when Either is used this way, the Left constructor is used for errors and the Right constructor is used for correct values. Either is also a monad.

Rewrite maybeGoldbach to return an Either value, using one of the following strings when there is an error with their obvious meanings:

• "not a number"

• "not greater than 2"

• "not an even number"

Examples

>>> eitherGoldbach "104"
Right (104,(3,101))

>>> eitherGoldbach "this is not a number"
Left "not a number"

>>> eitherGoldbach "2"
Left "not greater than 2"

>>> eitherGoldbach "101"
Left "not an even number"

A list is also a monad.

For example, dupli in P14 could have been implemented with the list monad:

>>> :{
let dupli xs = do
                 x <- xs
                 [x, x]
in dupli [1, 2, 3]
:}
[1,1,2,2,3,3]

Using the list monad, implement a function which returns all the one-dimensional random walk paths with \(n\) steps. Starting from position 0, each step can change positions by -1, 0, or 1. Each path will be a list of positions starting from 0.

Examples

>>> randomWalkPaths 0
[[0]]

>>> sort $ randomWalkPaths 2
[[0,-1,-2],[0,-1,-1],[0,-1,0],[0,0,-1],[0,0,0],[0,0,1],[0,1,0],[0,1,1],[0,1,2]]

Hint

>>> :{
do
  x <- [2,3] :: [Int]
  y <- [5,6] :: [Int]
  return $ x*y
:}
[10,12,15,18]

Starting from a positive integer \(n\), we can have a sequence of numbers such that at each step, the next number is \(3n+1\) if \(n\) is odd, or \(\frac{n}{2}\) if \(n\) is even. The Collatz conjecture states that this sequence will always end at 1 after a finite number of steps.

Using the Writer monad, count the number of these steps for a given positive integer \(n\).

Examples

>>> collatz 1
0

>>> collatz 2
1

>>> collatz 31
106

Hint

Postfix notation, also known as reverse Polish notation, has operators come after their operands in mathematical expressions. It has no need for operator precedence or parentheses to specify evaluation order.

Evaluation is typically done using a stack. Numbers are pushed onto the stack, and operators pop out numbers and pushes back the result. The State monad would be useful for maintaining such a stack.

There may be errors with some expressions. For example, an expression may be ill-formed, or there may be a division by zero. It would be useful to use the Maybe monad so that we can return Nothing if there is an error.

Finally for this problem, we would like to keep track of changes to the stack and which operators are applied to which numbers. The function should also return a list, with each entry showing the state of the stack after an operand has been pushed or an operator has been applied. Logging each entry can be done with the Writer monad.

Unfortunately, it would be very cumbersome to use these monads directly together. Monad transformers are a way to make it substantially easier to use more than one monad at the same time. Use monad transformers to compose the State, Maybe, and Writer monads into a single monad to implement a function which evaluates an expression in postfix notation. It should also return the history of the calculation.

Examples

The result of applying subtraction to 8 and 5 should be 3:

>>> fst $ calculatePostfix [Operand 8, Operand 5, Operator Subtract]
Just 3

It should be an error if no operator is applied to two or more numbers:

>>> fst $ calculatePostfix [Operand 8, Operand 6]
Nothing

Negation applies to a single number:

>>> fst $ calculatePostfix [Operand 8, Operator Negate]
Just (-8)

But it is an error if there is only one number for a binary operator:

>>> fst $ calculatePostfix [Operand 8, Operator Add]
Nothing

The parsePostfix function can be used to conveniently create an expression:

>>> fst $ calculatePostfix $ parsePostfix "8 5 4 10 + - 3 * negate +"
Just 35

The second element in the return value should show the history of the calculation:

>>> mapM_ print $ snd $ calculatePostfix $ parsePostfix "8 5 4 10 + - 3 * negate +"
([8],Nothing)
([5,8],Nothing)
([4,5,8],Nothing)
([10,4,5,8],Nothing)
([14,5,8],Just Add)
([-9,8],Just Subtract)
([3,-9,8],Nothing)
([-27,8],Just Multiply)
([27,8],Just Negate)
([35],Just Add)

Even if the expression is invalid, the second element should still show the history of the calculation until the point at which there is an error:

>>> fst $ calculatePostfix $ parsePostfix "1 2 * +"
Nothing
>>> mapM_ print $ snd $ calculatePostfix $ parsePostfix "1 2 * +"
([1],Nothing)
([2,1],Nothing)
([2],Just Multiply)

Hint

A single element within a mathematical expression. A list of these elements comprises an expression in postfix notation.

Encodes an operator for a mathematical expression.

A graph is mathematically defined as a set of vertexes and a set of edges, where an edge is a set of two elements from the set of vertexes. I.e., if \(G = (V, E)\), where \(E \subseteq \{ \{v_1, v_2\} \,|\, v_1 \in V, v_2 \in V\}\), then \(G\) is a graph.

The following is an example of a graph, with vertexes represented as circles and edges represented as lines.

Notes

A vertex in a graph.

In general, vertexes can be anything. For these problems, vertexes will be integers.

An edge in a graph.

We will only deal with undirected graphs. I.e.,

Edge (u, v) == Edge (v, u)

There are many ways to represent graphs in Haskell. For example, the example graph can be represented by variables including their adjacent vertexes as values:

>>> :{
let v1 = Var () [v2, v4]
    v2 = Var () [v1, v3, v4]
    v3 = Var () [v2, v4]
    v4 = Var () [v1, v2, v3, v5]
    v5 = Var () [v4]
:}

We will not be using this representation of graphs further.

Tying the knot

>>> :{
let v1  = Var 1 [v2]
    v2  = Var 2 [v3]
    v3  = Var 3 [v1']
    v1' = Var 1 [v3]
:}

>>> :{
let v1 = Var 1 [v2]
    v2 = Var 2 [v1]
:}

Graphs can also be represented by the lists of its vertexes and edges. This is close to the standard mathematical definition of a graph.

For example, the example graph can be represented as:

>>> Lists ([1, 2, 3, 4, 5], [(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5)])
Lists ...

A common approach to representing graphs are with adjacency lists. As the name implies, for each vertex it lists its adjacent vertexes

For example, the example graph can be represented as:

>>> Adjacency [(1, [2, 4]), (2, [1, 3, 4]), (3, [2, 4]), (4, [1, 2, 3, 5]), (5, [4])]
Adjacency ...

The previous approaches can be verbose and error-prone for humans to use.

An easier way for humans is to use paths of vertexes to represent both the vertexes and edges. Within a path is implicitly an edge between consecutive vertexes. E.g., a path [a, b, c, ...] means there are vertexes a, b, c, ... and edges (a, b), (b, c), ... There will be as many paths as required to represent all edges in the graph.

For example, the example graph can be represented as:

>>> Paths [[1, 2, 3, 4, 5], [1, 4], [2, 4]]
Paths ...

DOT graphs

graph {
  1 -- 2 -- 3 -- 4 -- 5
  1 -- 4
  2 -- 4
}

Represents a graph with a map where a vertex is a key and the set of its neighbors is the value.

This is basically an indexed version of adjacency lists. This representation may be the easiest for graph functions to use, and we will use it as the default representation of graphs.

For example, the example graph can be represented as:

>>> :{
G $ Map.map Set.fromList $ Map.fromList
  [ (1, [2, 4])
  , (2, [1, 3, 4])
  , (3, [2, 4])
  , (4, [1, 2, 3, 5])
  , (5, [4])
  ]
:}
G ...

The neighbors of a vertex in a graph. I.e., the set of vertexes adjacent to the given vertex.

Whether the given vertexes are adjacent in the graph.

Write functions to convert between the different graph representations Lists, Adjacency, Paths, and G.

The types can already be easily converted between each other using the sets and toGraph functions available to the Graph type class. Unlike the other graph problems, this problem should be solved without using the functions available to the Graph type class for it to not be trivial.

Convert graph to the Lists representation.

Convert graph to the Adjacency representation.

Convert graph to the Paths representation.

Convert graph to the G representation.

Write a function that, given two vertexes a and b in a graph, returns all the acyclic paths from a to b.

Examples

>>> sort $ paths 1 4 $ toG $ Paths [[1,2,3], [1,3,4,2], [5,6]]
[[1,2,3,4],[1,2,4],[1,3,2,4],[1,3,4]]

>>> paths 2 6 $ toG $ Paths [[1,2,3], [1,3,4,2], [5,6]]
[]

A cycle is a path in a graph whose first and last vertexes are the same vertex. No edges and no other vertexes repeat in the path.

Write a function which finds all cycles in the graph which include the given vertex.

Examples

>>> sort $ cycles 1 $ toG $ Paths [[1,2,3], [1,3,4,2], [5,6]]
[[1,2,3],[1,2,4,3],[1,3,2],[1,3,4,2]]

Mathematically, a tree is a graph with exactly one path between any two vertexes. A spanning tree of a graph is a tree which includes all vertexes of the graph.

Write a function to construct all spanning trees of a given graph.

You can use graph83 as an example graph to construct spanning trees from.

Examples

>>> length $ spanningTrees graph83
173

>>> toG (Paths [[1,2,4,5,6,7,8],[1,3],[5,10],[7,9]]) `elem` spanningTrees graph83
True

Write a function which returns whether a graph is a tree using spanningTrees.

Examples

>>> isTree graph83
False

>>> isTree $ toG $ Paths [[1,2,3],[1,4,5]]
True

Write a function which returns whether a graph is connected using spanningTrees.

Examples

>>> isConnected graph83
True

>>> isConnected $ toG $ Lists ([1,2,3], [])
False

Write a function which constructs the minimum spanning tree of a given weighted graph. While the weight of an edge could be encoded in the graph represention itself, here we will specify the weight of each edge in a separate map.

Examples

>>> let t = minimumSpanningTree graph83 weights84
>>> Set.foldr (\e w -> w + weights84 ! e) 0 $ edges t
33

Hint

Two graphs \(G_1 = (V_1,E_1)\) and \(G_2 = (V_2,E_2)\) are isomorphic if there is a bijection \(f: V_1 -> V_2\) such that for any vertexes \(x\), \(y\) in \(V_1\), \(x\) and \(y\) are adjacent if and only if \(f(x)\) and \(f(y)\) are adjacent.

Write a function that determines whether two graphs are isomorphic.

Examples

>>> isomorphic (toG $ Paths [[1,2,3], [2,4]]) (toG $ Paths [[1,2,3],[1,4]])
False

>>> isomorphic graph85 graph85'
True

Graph coloring assigns colors to each vertex in a way such that no adjacent vertexes have the same color.

Write a function to color a graph using Welch-Powell's algorithm. Use distinct integers to represent distinct colors, and return the association list between vertexes and their colors.

Examples

>>> colorGraph $ toG $ Paths [[1,2,3,4,5,10,8,6,9,7,2], [1,5], [1,6], [3,8], [4,9], [7,10]]
[(1,1),(2,2),(3,1),(4,2),(5,3),(6,2),(7,1),(8,3),(9,3),(10,2)]

Visualization with real colors

Hint

Write a function that generates a depth-first order graph traversal sequence. The starting point should be specified, and the output should be a list of nodes that are reachable from this starting point in depth-first order.

Examples

>>> let xs = depthFirst (toG $ Paths [[1,2,3,4,5], [2,4], [6,7]]) 1
>>> xs `elem` [[1,2,3,4,5], [1,2,4,5,3], [1,2,4,3,5]]
True

Write a function that splits a graph into its connected components.

Examples

>>> sort $ map sort $ connectedComponents $ toG $ Paths [[1,2,3,4,5], [2,4], [6,7]]
[[1,2,3,4,5],[6,7]]

Write a function that finds out whether a given graph is bipartite.

Examples

>>> bipartite $ toG $ Paths [[1,2,3,4],[1,4,5,2]]
True

>>> bipartite $ toG $ Paths [[1,2,3,4],[1,4,5,2],[1,3]]
False

The eight queens problem is a classical problem in computer science. The objective is to place eight queens on a chessboard so that no two queens are attacking each other. I.e., no two queens are in the same row, the same column, or on the same diagonal. Solve the extended problem for arbitrary \(n\).

Represent the positions of the queens as a list of numbers from 1 to \(n\). For example, [4,2,7,3,6,8,5,1] means that the queen in the first column is in row 4, the queen in the second column is in row 2, etc.

Examples

>>> length $ queens 8
92

>>> minimum $ queens 8
[1,5,8,6,3,7,2,4]

Another famous problem is this one: How can a knight jump on an \(N \times N\) chessboard in such a way that it visits every square exactly once?

Write a function which returns a knight's tour ending at a particular square. Represent the squares by their coordinates with the tuple \((x,y)\), where \(1 \leq x \leq N\) and \(1 \leq y \leq N\). A tour will be a list of these tuples of length \(N \times N\).

Examples

>>> printKnightsTour $ knightsTour 6 (3,5)
24  7 32 17 22  5
33 16 23  6 31 18
 8 25 10 19  4 21
15 34  1 28 11 30
26  9 36 13 20  3
35 14 27  2 29 12

Hint

The same as knightsTour, except return a circular tour. I.e., the knight must be able to jump from the last position in the tour to the first position in the tour. Start the tour from \((1,1)\).

Examples

>>> printKnightsTour $ closedKnightsTour 6
 1 14 31 20  3  8
32 21  2  7 30 19
13 36 15  4  9  6
22 33 24 27 18 29
25 12 35 16  5 10
34 23 26 11 28 17

It has been conjectured that if graph \(G=(V,E)\) is a tree with \(n\) vertexes, which necessarily means that it has \(n-1\) edges, then there is a graceful labeling of the tree. This means that there is a way to label each vertex with integers from 1 to \(n\) such that for every integer \(m\) from 1 to \(n-1\), there is an edge whose difference in vertex labels is \(m\). I.e., there is a bijection \(l : V \rightarrow \{ k \,|\, 1 \leq k \leq n \}\) such that \(\{ |l(v)-l(v')| \,|\, \{v,v'\} \in E \} = \{ k \,|\, 1 \leq k \leq n-1 \}\). There is no known counterexample, but neither is it proven that this is true for all trees.

For example, the following is a graceful labeling of the tree graph tree92: