Problems

Description

This is a list of Ninety-Nine Haskell Problems.

Each problem is provided a skeleton where you can implement your own solutions. For example, the Problems.P11 module provides a skeleton in which you can provide your own implementation. Once implemented, you can run the existing tests to confirm it is indeed a correct solution, or at least one without obvious bugs. You can also run existing benchmarks against your solution, e.g., if you are curious how your amazingly clever but complicated solution performs compared to a simpler one.

Some solutions to these problems are in the Solutions module. The number of shruggies (🤷) indicate difficulty level. For a tutorial as to how one might solve problems, see the Problems.Tutorial module.

These are based on the Ninety-Nine Haskell Problems on the HaskellWiki. The source for this module is available at GitHub.

Synopsis

# List problems

## 🤷 Last element of a list

myLast :: [a] -> a Source #

Find the last element of a list.

### Examples

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

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


## 🤷 Penultimate element of a list

myButLast :: [a] -> a Source #

Find the last but one element of a list.

### Examples

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

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


## 🤷 Find element of a list at a given position

elementAt :: [a] -> Int -> a Source #

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

### Examples

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

>>> elementAt "haskell" 5
'e'


## 🤷 Length of a list

myLength :: [a] -> Int Source #

Find the number of elements of a list.

### Examples

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

>>> myLength "Hello, world!"
13


## 🤷 Reverse a list

myReverse :: [a] -> [a] Source #

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]


## 🤷 Palindromes

isPalindrome :: Eq a => [a] -> Bool Source #

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


## 🤷 Flatten a nested list structure

flatten :: NestedList a -> [a] Source #

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 [] []  data NestedList a Source # A list type with arbitrary nesting of lists. Constructors  Elem a A non-list element. List [NestedList a] Nested list. #### Instances Instances details  Source # Instance detailsDefined in Problems.Lists Associated Typestype Rep (NestedList a) :: Type -> Type # Methodsfrom :: NestedList a -> Rep (NestedList a) x #to :: Rep (NestedList a) x -> NestedList a # Show a => Show (NestedList a) Source # Instance detailsDefined in Problems.Lists MethodsshowsPrec :: Int -> NestedList a -> ShowS #show :: NestedList a -> String #showList :: [NestedList a] -> ShowS # Eq a => Eq (NestedList a) Source # Instance detailsDefined in Problems.Lists Methods(==) :: NestedList a -> NestedList a -> Bool #(/=) :: NestedList a -> NestedList a -> Bool # type Rep (NestedList a) Source # Instance detailsDefined in Problems.Lists type Rep (NestedList a) = D1 ('MetaData "NestedList" "Problems.Lists" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'False) (C1 ('MetaCons "Elem" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "List" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [NestedList a]))) ## Problem 8 ## 🤷 Eliminate duplicate elements in a list compress :: Eq a => [a] -> [a] Source # 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"  ## Problem 9 ## 🤷 🤷 Pack duplicates in a list pack :: Eq a => [a] -> [[a]] Source # 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"]  ## Problem 10 ## 🤷 Run-length encoding of a list encode :: Eq a => [a] -> [(Int, a)] Source # 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')]  ## Problem 11 ## 🤷 Modified run-length encoding encodeModified :: Eq a => [a] -> [Encoding a] Source # 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']  data Encoding a Source # Encodes one or more consecutively duplicate elements. Constructors  Single a Represents a single occurrence of an element. Multiple Int a Represents an element repeating consecutively a given number of times. #### Instances Instances details  Source # Instance detailsDefined in Problems.Lists Associated Typestype Rep (Encoding a) :: Type -> Type # Methodsfrom :: Encoding a -> Rep (Encoding a) x #to :: Rep (Encoding a) x -> Encoding a # Show a => Show (Encoding a) Source # Instance detailsDefined in Problems.Lists MethodsshowsPrec :: Int -> Encoding a -> ShowS #show :: Encoding a -> String #showList :: [Encoding a] -> ShowS # NFData a => NFData (Encoding a) Source # Instance detailsDefined in Problems.Lists Methodsrnf :: Encoding a -> () # Eq a => Eq (Encoding a) Source # Instance detailsDefined in Problems.Lists Methods(==) :: Encoding a -> Encoding a -> Bool #(/=) :: Encoding a -> Encoding a -> Bool # type Rep (Encoding a) Source # Instance detailsDefined in Problems.Lists type Rep (Encoding a) = D1 ('MetaData "Encoding" "Problems.Lists" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'False) (C1 ('MetaCons "Single" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "Multiple" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Int) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a))) ## Problem 12 ## 🤷 Decode a run-length encoded list decodeModified :: [Encoding a] -> [a] Source # 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"  ## Problem 13 ## 🤷 🤷 Run-length encoding of a list; direct solution encodeDirect :: Eq a => [a] -> [Encoding a] Source # 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']  ## Problem 14 ## 🤷 Duplicate elements in a list dupli :: [a] -> [a] Source # Duplicate the elements of a list. ### Examples >>> dupli [1, 2, 3] [1,1,2,2,3,3]  ## Problem 15 ## 🤷 Replicate elements of a list repli :: [a] -> Int -> [a] Source # Replicate the elements of a list a given number of times. ### Examples >>> repli "abc" 3 "aaabbbccc"  ## Problem 16 ## 🤷 🤷 Drop elements in a list dropEvery :: [a] -> Int -> [a] Source # Drop every nth element from a list. ### Examples >>> dropEvery "abcdefghik" 3 "abdeghk"  ## Problem 17 ## 🤷 Split a list split :: [a] -> Int -> ([a], [a]) Source # Split a list into two parts; the length of the first part is given. ### Examples >>> split "abcdefghik" 3 ("abc","defghik")  ## Problem 18 ## 🤷 🤷 Extract a slice from a list slice :: [a] -> Int -> Int -> [a] Source # 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"  ## Problem 19 ## 🤷 🤷 Rotate a list rotate :: [a] -> Int -> [a] Source # Rotate a list n places to the left. ### Examples >>> rotate "abcdefgh" 3 "defghabc"  >>> rotate "abcdefgh" (-2) "ghabcdef"  ## Problem 20 ## 🤷 Remove element from a list removeAt :: Int -> [a] -> (a, [a]) Source # Remove the kth element from a list. Return the element removed and the residue list. ### Examples >>> removeAt 2 "abcd" ('b',"acd")  ## Problem 21 ## 🤷 Insert element into a list insertAt :: a -> [a] -> Int -> [a] Source # Insert an element at a given position into a list. ### Examples >>> insertAt 'X' "abcd" 2 "aXbcd"  ## Problem 22 ## 🤷 Range of integers range :: Int -> Int -> [Int] Source # Create a list containing all integers within a given range. ### Examples >>> range 4 9 [4,5,6,7,8,9]  ## Problem 23 ## 🤷 🤷 Select random elements from a list randomSelect :: RandomGen g => [a] -> Int -> g -> ([a], g) Source # 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"


## 🤷 Lotto

randomDraw :: RandomGen g => Int -> Int -> g -> ([Int], g) Source #

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]  ## Problem 25 ## 🤷 Random permutation of a list randomPermute :: RandomGen g => [a] -> g -> ([a], g) Source # 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"


## 🤷 🤷 Combinations

combinations :: Int -> [a] -> [[a]] Source #

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",...]


## 🤷 🤷 Group the elements of a set into disjoint subsets

disjointGroups :: [Int] -> [a] -> [[[a]]] Source #

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


## 🤷 🤷 Sorting a list of lists according to length of sublists

lsort :: [[a]] -> [[a]] Source #

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"]


lfsort :: [[a]] -> [[a]] Source #

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"]


# Arithmetic problems

## 🤷 Fibonacci numbers

fibonacci :: Integral a => a -> a Source #

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]


## 🤷 🤷 Fibonacci numbers with matrix exponentiation

fibonacci' :: Integral a => a -> a Source #

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:

### Examples

>>> totient' 10
4


## 🤷 🤷 Highly totient numbers

highlyTotientNumbers :: Integral a => [a] Source #

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

Expand

Given a totient number $$n=\phi(x)$$, find an upper bound for $$x$$, which will bound the set of numbers from which to search for solutions. Compare the prime factorizations between $$\phi(x)$$ and $$x$$, and devise a modification of the former so that it must be larger than the latter.

## 🤷 List of prime numbers

primesR :: Integral a => a -> a -> [a] Source #

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]


primes :: Integral a => [a] Source #

Construct the list of all prime numbers.

### Examples

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


## 🤷 🤷 Goldbach's conjecture

goldbach :: Integral a => a -> (a, a) Source #

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)


## 🤷 🤷 List of Goldbach pairs

goldbachList :: Integral a => a -> a -> [(a, a)] Source #

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)]  ## Problem 42 ## 🤷 🤷 Modular multiplicative inverse multiplicativeInverse :: Integral a => a -> a -> Maybe a Source # 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


## 🤷 Gaussian integer divisibility

Arguments

 :: Complex Integer $$x$$ -> Complex Integer $$y$$ -> Bool $$y \mid x$$, i.e., whether $$x$$ is divisible by $$y$$

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

Expand

For $$y \neq 0$$, $$z = xy$$ means that $$x = \frac{z}{y}$$. If you multiply both the numerator and denominator by $$\overline{y}$$, the conjugate of $$y$$, then you can normalize the denominator to be a real number. You can then use this to check whether the real and imaginary parts are integers. Recall that $$\overline{a+bi} = a-bi$$ and $$(a+bi)(c+di) = (ac-bd) + (bc+ad)i$$ for real numbers $$a$$, $$b$$, $$c$$, and $$d$$.

## 🤷 🤷 Gaussian primes

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

Expand

Recall that $$|xy| = |x| \, |y|$$ for complex $$x$$ and $$y$$. This implies that for any proper divisor $$y$$ of a Gaussian integer $$x$$ where $$|x| > 1$$, it will be the case that $$|y| < |x|$$. In fact, it will be the case that there will be a non-unit divisor $$z$$ such that $$|z|^2 \leq |x|$$, if any non-unit proper divisor exists.

## 🤷 Gaussian primes using the two-square theorem

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  # Logic and code problems ## Problem 46 ## 🤷 Truth tables for logical expressions type BoolFunc = Bool -> Bool -> Bool Source # 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 Expand There is no technical reason to define the type synonym BoolFunc. However, it is a good place to explain the entire problem without talking about writing truth table functions first, especially for inclusion in the documentation for Problems. The original problem for Haskell required that the truth table be printed: "Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables." It was changed here to return a list of boolean tuples, because the requirement for I/O seemed uninteresting in the context of the rest of the problem. Documentation for the expected semantics for each boolean function was added, and the example for table was modified to avoid sensitivity to order. table :: BoolFunc -> [(Bool, Bool, Bool)] Source # 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


## 🤷 🤷 Universal logic gates

evaluateCircuit :: [(Int, Int)] -> Bool -> Bool -> Bool Source #

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


buildCircuit :: (Bool -> Bool -> Bool) -> [(Int, Int)] Source #

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

Expand

There are only 16 binary boolean functions, ignoring how they are actually computed, so it is feasible to devise logic circuits for all of them manually.

To have a computer construct them automatically, which may be more difficult, take advantage of the fact that a boolean function can be represented by its truth table. Consider what the inputs must be like for a NAND gate to output a desired truth table.

## 🤷 🤷 Truth tables for $$n$$-ary boolean functions

tablen :: Int -> ([Bool] -> Bool) -> [[Bool]] Source #

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  ## Problem 49 ## 🤷 🤷 Gray codes gray :: Int -> [String] Source # 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. ## Problem 50 ## 🤷 🤷 🤷 Huffman codes huffman :: [(Char, Int)] -> [(Char, String)] Source # 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  ## Problem 51 ## 🤷 Error correction codes corrupt :: RandomGen g => g -> Int -> [Bool] -> [Bool] Source # 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]  errorCorrectingEncode :: [Bool] -> [Bool] Source # 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. errorCorrectingDecode :: [Bool] -> [Bool] Source # 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]  ## Problem 52 ## 🤷 🤷 🤷 Conjunctive normal form 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 Expand Transform a boolean formula using De Morgan's law, the distributive law, and double negation elimination to reduce nesting. Alternatively, the conjunctive normal form can be obtained easily from the truth table, although this will always require a running time exponential to the number of variables. data Formula Source # Represents a boolean formula. Constructors  Value Bool A constant value. Variable String A variable with given name. Complement Formula Logical complement. I.e., it is true only if its clause is false. Disjoin [Formula] Disjunction. I.e., it is true if any of its clauses are true. Conjoin [Formula] Conjunction. I.e., it is true only if all of its clauses are true. #### Instances Instances details  Source # Instance detailsDefined in Problems.Logic Associated Typestype Rep Formula :: Type -> Type # Methodsto :: Rep Formula x -> Formula # Source # Instance detailsDefined in Problems.Logic MethodsshowList :: [Formula] -> ShowS # Source # Instance detailsDefined in Problems.Logic Methodsrnf :: Formula -> () # Source # Instance detailsDefined in Problems.Logic Methods(==) :: Formula -> Formula -> Bool #(/=) :: Formula -> Formula -> Bool # Source # Instance detailsDefined in Problems.Logic Methods(<) :: Formula -> Formula -> Bool #(<=) :: Formula -> Formula -> Bool #(>) :: Formula -> Formula -> Bool #(>=) :: Formula -> Formula -> Bool # type Rep Formula Source # Instance detailsDefined in Problems.Logic type Rep Formula = D1 ('MetaData "Formula" "Problems.Logic" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'False) ((C1 ('MetaCons "Value" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Bool)) :+: C1 ('MetaCons "Variable" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 String))) :+: (C1 ('MetaCons "Complement" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 Formula)) :+: (C1 ('MetaCons "Disjoin" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [Formula])) :+: C1 ('MetaCons "Conjoin" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [Formula]))))) ## Problem 53 ## 🤷 🤷 🤷 Resolution rule isTheorem :: [Formula] -> Formula -> Bool Source # 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  # Binary tree problems ## Problem 54 ## 🤷 Binary trees data Tree a Source # 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 Expand This is not the problem 54A from the original Ninety-Nine Haskell Problems. As it also mentions, there is nothing to do here except making sure code compiles correctly, thanks to Haskell's strict typing and the way Tree is defined. Instead, the problem was replaced by the simple problems of implementing given binary trees as Haskell values. I.e., turn the examples from the original problem into simple problems to solve. Constructors  Empty Branch a (Tree a) (Tree a) #### Instances Instances details  Generic (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Associated Typestype Rep (Tree a) :: Type -> Type # Methodsfrom :: Tree a -> Rep (Tree a) x #to :: Rep (Tree a) x -> Tree a # Show a => Show (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees MethodsshowsPrec :: Int -> Tree a -> ShowS #show :: Tree a -> String #showList :: [Tree a] -> ShowS # NFData a => NFData (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Methodsrnf :: Tree a -> () # Eq a => Eq (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Methods(==) :: Tree a -> Tree a -> Bool #(/=) :: Tree a -> Tree a -> Bool # Ord a => Ord (Tree a) Source # An arbitrary total ordering for Tree.Defines an order for a set of Trees. Not intended to support solving problems. Instance detailsDefined in Problems.BinaryTrees Methodscompare :: Tree a -> Tree a -> Ordering #(<) :: Tree a -> Tree a -> Bool #(<=) :: Tree a -> Tree a -> Bool #(>) :: Tree a -> Tree a -> Bool #(>=) :: Tree a -> Tree a -> Bool #max :: Tree a -> Tree a -> Tree a #min :: Tree a -> Tree a -> Tree a # type Rep (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees type Rep (Tree a) = D1 ('MetaData "Tree" "Problems.BinaryTrees" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'False) (C1 ('MetaCons "Empty" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Branch" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a))))) leaf :: a -> Tree a Source # 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. ## Problem 55 ## 🤷 🤷 Construct completely balanced binary trees 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) ]


## 🤷 🤷 Symmetric binary trees

symmetric :: Tree a -> Bool Source #

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

Expand

Write a function mirror first to check whether one tree is the mirror image of another.

## 🤷 🤷 Binary search trees

construct :: Ord a => [a] -> Tree a Source #

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

Expand

The original problem refers to a predicate which had not appeared in previous problems: Use the predicate add/3, developed in chapter 4 of the course, to write a predicate to construct a binary search tree from a list of integer numbers. This is presumably a reference to course material used at the time the problems were written. Given the different context, the problem was revised to also implement the function that would have taken the role that the add/3 predicate would have had in the original context.

For consistent examples, the condition to also use naive binary search tree insertion was imposed. For the same reason, the order for which elements in a list are added to the tree is also specified. Of course, anyone is free to implement whatever they want, although that could mean they would not pass the available tests.

addedTo :: Ord a => a -> Tree a -> Tree a Source #

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))


## 🤷 🤷 Symmetric and completely balanced binary trees

symmetricBalancedTrees :: Int -> [Tree ()] Source #

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

>>> 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) ]  ## Problem 59 ## 🤷 🤷 Construct height-balanced binary trees heightBalancedTrees :: Int -> [Tree ()] Source # 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  ## Problem 60 ## 🤷 🤷 Height-balanced binary trees with given number of nodes 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 Expand Consider a height-balanced binary tree of height $$h$$. What is the maximum number of nodes it can contain? Clearly, it is $$2^h-1$$. However, what is the minimum number of nodes it can contain? This question is more difficult. Try to find a recursive statement and turn it into a function that returns the minimum number of nodes in a height-balanced binary tree of height $$h$$. On the other hand, what is the maximum height $$h$$ a height-balanced binary tree with $$n$$ nodes can have? What about the minimum height? Try writing functions to compute these. ### Notes Expand The original problem asked to implement functions computing the minimum number of nodes for a given height and the maximum height for a given number of nodes. These are more of a hint as to how to implement the main function in question, so they were made hints instead of being part of the problem itself. ## Problem 61 ## 🤷 Collect nodes of a binary tree leaves :: Tree a -> [a] Source # 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

Expand

The original problem also included implementing a function which counts leaves. Instead, the internals function was moved from problem 62 to this one because it seemed a more natural grouping.

The examples sort the results to avoid order sensitivity. It is less of an issue for leaves, which has a sort of obvious natural order, but there is no single natural order for internals.

internals :: Tree a -> [a] Source #

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.

>>> sort $internals tree4 [1,2]  ## Problem 62 ## 🤷 Collect nodes at a given level atLevel :: Tree a -> Int -> [a] Source # 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 Expand In the original list, this was problem 62B, and internals was problem 62, but the latter was grouped with problem 61 because the grouping was more natural. ## Problem 63 ## 🤷 🤷 Construct a complete binary tree 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 Expand We can assign an address number to each node in a complete binary tree by enumerating the nodes in level-order, starting at the root with number 1. For every node $$x$$ with address $$a$$, the following property holds: The address of $$x$$'s left and right successors are $$2^a$$ and $$2^a + 1$$, respectively, if they exist. This fact can be used to elegantly construct a complete binary tree structure. 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  ## Problem 64 ## 🤷 🤷 Binary tree layout; in-order layoutInorder :: Tree a -> Tree (a, (Int, Int)) Source # 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 Expand In fact, the image was rendered to SVG using the return value of layoutInorder with writeSVG. The images for Problems.P65 and Problems.P66 were also rendered similarly. ## Problem 65 ## 🤷 🤷 Binary tree layout; constant distance at each level layoutLevelConstant :: Tree a -> Tree (a, (Int, Int)) Source # 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 Expand On a given level, the horizontal distance between neighboring nodes is constant. ## Problem 66 ## 🤷 🤷 🤷 Binary tree layout; compact layoutCompact :: Tree a -> Tree (a, (Int, Int)) Source # 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 Expand Consider the horizontal distance between a node and its successor nodes. How tight can you pack together two subtrees to construct the combined binary tree? ## Problem 67 ## 🤷 🤷 A string representation of binary trees 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))"
Branch 'x' (Branch 'y' Empty Empty) (Branch 'a' Empty (Branch 'b' Empty Empty))


## 🤷 🤷 In-order and pre-order sequences of binary trees

inorder :: Tree a -> [a] Source #

Return the in-order sequence of a binary tree.

### Examples

>>> inorder tree1
"dbeacgf"


preorder :: Tree a -> [a] Source #

Return the pre-order sequence of a binary tree.

### Examples

>>> preorder tree1
"abdecfg"


Arguments

 :: Eq a => [a] In-order sequence -> [a] Pre-order sequence -> Tree a Binary tree with the given in-order and pre-order sequences

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" == tree1
True


## 🤷 🤷 Dotstring representation of binary trees

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..."
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..."


# Multiway tree problems

data MultiwayTree a Source #

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.

Constructors

 MultiwayTree a [MultiwayTree a]

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.MultiwayTrees Associated Typestype Rep (MultiwayTree a) :: Type -> Type # Methodsfrom :: MultiwayTree a -> Rep (MultiwayTree a) x #to :: Rep (MultiwayTree a) x -> MultiwayTree a # Show a => Show (MultiwayTree a) Source # Instance detailsDefined in Problems.MultiwayTrees MethodsshowsPrec :: Int -> MultiwayTree a -> ShowS #show :: MultiwayTree a -> String #showList :: [MultiwayTree a] -> ShowS # NFData a => NFData (MultiwayTree a) Source # Instance detailsDefined in Problems.MultiwayTrees Methodsrnf :: MultiwayTree a -> () # Eq a => Eq (MultiwayTree a) Source # Instance detailsDefined in Problems.MultiwayTrees Methods(==) :: MultiwayTree a -> MultiwayTree a -> Bool #(/=) :: MultiwayTree a -> MultiwayTree a -> Bool # type Rep (MultiwayTree a) Source # Instance detailsDefined in Problems.MultiwayTrees type Rep (MultiwayTree a) = D1 ('MetaData "MultiwayTree" "Problems.MultiwayTrees" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'False) (C1 ('MetaCons "MultiwayTree" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [MultiwayTree a])))

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


## 🤷 🤷 Tree construction from a node string

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^^^" == multitree5
True


Construct the node string from a MultiwayTree.

### Examples

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


## 🤷 Internal path length of a tree

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


## 🤷 Post-order sequence of a tree

postOrderSequence :: MultiwayTree a -> [a] Source #

Construct the post-order sequence of the tree nodes.

### Examples

>>> postOrderSequence multitree5
"gfcdeba"


### Notes

Expand

The problem in the original list specifies a "bottom-up" order. There is no widespread common understanding of what this is (i.e., does this mean post-order, or all nodes at a level being sequenced before nodes at a higher level?), so post-order is specified instead.

## 🤷 🤷 Tree representation with s-expressions

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

Expand

This has been substantially rewritten from problem 73 in the original list, although it is still really the same problem. It made it sound like the representation outlined would be a natural one in Lisp, but it is hard to find multiway trees represented in this exact way with Lisp. All references I have found claiming this is a common representation are derived from the problem in the original list of 99 Prolog Problems.

I have tried to avoid giving an impression that this is the standard representation of trees in Lisp.

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))" == multitree5
True


## 🤷 🤷 Monads without do notation

askGoldbach :: Handle -> Handle -> IO () Source #

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 ()
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

Expand

In do notation,

do
a
b

is a shorthand for

(>>) a b

or equivalently,

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

Also,

do
x <- a
b

is a shorthand for

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

For those not familiar with monads, using these functions directly in prefix style will make it more apparent that these are not just sequenced statements as in imperative languages, but really a series of function applications. The distinction may be minor in the context of IO monads, but it will make it easier to understand other kinds of monads such as Maybe.

While not relevant to this problem, also note that return is not a return statement as in most languages, but a function that injects a value into the monad. For example,

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

does not return (1,2), but instead returns a monad with (2,3).

The naming of return can make the function body similar to what one would expect from imperative languages. For example,

f :: IO String
f = do
s <- getLine
return $"Got string: " ++ s But one should be careful to remember that it is not a return statement as such. ## Problem 75 ## 🤷 Maybe monad 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 "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


## Problem 76

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"


## Problem 77

randomWalkPaths :: Int -> [[Int]] Source #

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]]

:}
[10,12,15,18]


## 🤷 Collatz conjecture

collatz :: Integral a => a -> a Source #

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

Expand

The outputs produced by tell with the Writer monad are combined with mappend. In the Sum monoid, mappend is addition.

## 🤷 🤷 Postfix notation

calculatePostfix :: [Element] -> (Maybe Integer, [([Integer], Maybe Operator)]) Source #

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

Expand

The monad transformers for the State, Maybe, and Writer monads are StateT, MaybeT, and WriterT, respectively.

data Element Source #

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

Constructors

 Operator Operator Operand Integer

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Monads MethodsshowList :: [Element] -> ShowS # Source # Instance detailsDefined in Problems.Monads Methods(==) :: Element -> Element -> Bool #(/=) :: Element -> Element -> Bool #

data Operator Source #

Encodes an operator for a mathematical expression.

Constructors

 Negate Encodes negation. Equivalent to an unary minus. Unary operator. Add Encodes duplication. Makes another copy of its operand. Unary operator. Subtract Encodes subtraction. Binary operator. Multiply Encodes multiplication. Binary operator. Divide Encodes division. Equivalent to div. Binary operator. Modulo Encodes a modulo operator. Equivalent to mod. Binary operator.

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Monads Methods Source # Instance detailsDefined in Problems.Monads MethodsenumFrom :: Operator -> [Operator] #enumFromTo :: Operator -> Operator -> [Operator] # Source # Instance detailsDefined in Problems.Monads MethodsshowList :: [Operator] -> ShowS # Source # Instance detailsDefined in Problems.Monads Methods

# Graph problems

class Graph g where Source #

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

Expand

This introduction to graphs is substantially different from the one in the original list of Ninety-Nine Haskell Problems. The original introduction would serve as an introduction to graphs in the context of Prolog, but apparently was not updated to be more appropriate for other languages as the problems were ported for Lisp and then Haskell.

This is a rewrite targeted to be more useful towards practicing Haskell. Most of the graph problems themselves remain substantially the same.

Minimal complete definition

Methods

vertexes :: g -> Set Vertex Source #

The set of vertexes.

edges :: g -> Set Edge Source #

The set of edges.

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Methods Source # Instance detailsDefined in Problems.Graphs Methodssets :: G -> (Set Vertex, Set Edge) Source #adjacent :: Vertex -> Vertex -> G -> Bool Source #toGraph :: (Set Vertex, Set Edge) -> Maybe G Source # Source # Instance detailsDefined in Problems.Graphs Methodssets :: Lists -> (Set Vertex, Set Edge) Source # Source # Instance detailsDefined in Problems.Graphs Methodssets :: Paths -> (Set Vertex, Set Edge) Source #

type Vertex = Int Source #

A vertex in a graph.

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

newtype Edge Source #

An edge in a graph.

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

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

Constructors

 Edge (Vertex, Vertex)

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> Edge -> ShowS #show :: Edge -> String #showList :: [Edge] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methods(==) :: Edge -> Edge -> Bool #(/=) :: Edge -> Edge -> Bool # Source # Instance detailsDefined in Problems.Graphs Methodscompare :: Edge -> Edge -> Ordering #(<) :: Edge -> Edge -> Bool #(<=) :: Edge -> Edge -> Bool #(>) :: Edge -> Edge -> Bool #(>=) :: Edge -> Edge -> Bool #max :: Edge -> Edge -> Edge #min :: Edge -> Edge -> Edge #

## Graph representations

data Var a Source #

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

Expand

While many languages can repesent cycles in graphs with objects pointing or referencing each other, most of them cannot do so by value if there are any cycles. This is possible in Haskell thanks to lazy evaluation, and this technique is called "tying the knot".

However, tying the knot to represent graphs with cycles can be problematic. It is equivalent to and indistinguishable from an infinite multiway tree. This can be resolved by assuming that values with the same label are the same vertex. Unfortunately, this allows for an inconsistent graph representation, and there is no general way to confirm that a graph representation is consistent.

For example, there are no graphs consistent with the following representation:

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


On the other hand, the following is a consistent representation of a graph. Unfortunately, it cannot be proven that it is consistent using just the values.

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


If there are no cycles in the graph, there is no need to tie the knot, so this is not an issue. In fact, trees are graphs which are often represented this way.

#### Instances

Instances details
 Show a => Show (Var a) Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> Var a -> ShowS #show :: Var a -> String #showList :: [Var a] -> ShowS # Eq a => Eq (Var a) Source # Instance detailsDefined in Problems.Graphs Methods(==) :: Var a -> Var a -> Bool #(/=) :: Var a -> Var a -> Bool #

newtype Lists Source #

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 ...


Constructors

 Lists ([Vertex], [(Vertex, Vertex)])

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Associated Typestype Rep Lists :: Type -> Type # Methodsfrom :: Lists -> Rep Lists x #to :: Rep Lists x -> Lists # Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> Lists -> ShowS #show :: Lists -> String #showList :: [Lists] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methodsrnf :: Lists -> () # Source # Instance detailsDefined in Problems.Graphs Methods(==) :: Lists -> Lists -> Bool #(/=) :: Lists -> Lists -> Bool # Source # Instance detailsDefined in Problems.Graphs Methodssets :: Lists -> (Set Vertex, Set Edge) Source # Source # Instance detailsDefined in Problems.P80 MethodstoG :: Lists -> G Source # Source # Instance detailsDefined in Solutions.P80 MethodstoG :: Lists -> G Source # type Rep Lists Source # Instance detailsDefined in Problems.Graphs type Rep Lists = D1 ('MetaData "Lists" "Problems.Graphs" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'True) (C1 ('MetaCons "Lists" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 ([Vertex], [(Vertex, Vertex)]))))

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 ...


Constructors

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Associated Typestype Rep Adjacency :: Type -> Type # Methodsto :: Rep Adjacency x -> Adjacency # Source # Instance detailsDefined in Problems.Graphs MethodsshowList :: [Adjacency] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methodsrnf :: Adjacency -> () # Source # Instance detailsDefined in Problems.Graphs Methods Source # Instance detailsDefined in Problems.Graphs Methods Source # Instance detailsDefined in Problems.P80 Methods Source # Instance detailsDefined in Solutions.P80 Methods type Rep Adjacency Source # Instance detailsDefined in Problems.Graphs type Rep Adjacency = D1 ('MetaData "Adjacency" "Problems.Graphs" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'True) (C1 ('MetaCons "Adjacency" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [(Vertex, [Vertex])])))

newtype Paths Source #

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

Expand

This is similar to the approach used by DOT graphs, which are commonly used to generate visualizations of graphs. E.g., the example graph can be written in DOT as:

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

Constructors

 Paths [[Vertex]]

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Associated Typestype Rep Paths :: Type -> Type # Methodsfrom :: Paths -> Rep Paths x #to :: Rep Paths x -> Paths # Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> Paths -> ShowS #show :: Paths -> String #showList :: [Paths] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methodsrnf :: Paths -> () # Source # Instance detailsDefined in Problems.Graphs Methods(==) :: Paths -> Paths -> Bool #(/=) :: Paths -> Paths -> Bool # Source # Instance detailsDefined in Problems.Graphs Methodssets :: Paths -> (Set Vertex, Set Edge) Source # Source # Instance detailsDefined in Problems.P80 MethodstoG :: Paths -> G Source # Source # Instance detailsDefined in Solutions.P80 MethodstoG :: Paths -> G Source # type Rep Paths Source # Instance detailsDefined in Problems.Graphs type Rep Paths = D1 ('MetaData "Paths" "Problems.Graphs" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'True) (C1 ('MetaCons "Paths" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [[Vertex]])))

newtype G Source #

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 ...


Constructors

 G (Map Vertex (Set Vertex))

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Graphs Associated Typestype Rep G :: Type -> Type # Methodsfrom :: G -> Rep G x #to :: Rep G x -> G # Source # Instance detailsDefined in Problems.Graphs MethodsshowsPrec :: Int -> G -> ShowS #show :: G -> String #showList :: [G] -> ShowS # Source # Instance detailsDefined in Problems.Graphs Methodsrnf :: G -> () # Source # Instance detailsDefined in Problems.Graphs Methods(==) :: G -> G -> Bool #(/=) :: G -> G -> Bool # Source # Instance detailsDefined in Problems.Graphs Methodssets :: G -> (Set Vertex, Set Edge) Source #adjacent :: Vertex -> Vertex -> G -> Bool Source #toGraph :: (Set Vertex, Set Edge) -> Maybe G Source # Source # Instance detailsDefined in Problems.P80 MethodstoG :: G -> G Source # Source # Instance detailsDefined in Solutions.P80 MethodstoG :: G -> G Source # type Rep G Source # Instance detailsDefined in Problems.Graphs type Rep G = D1 ('MetaData "G" "Problems.Graphs" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'True) (C1 ('MetaCons "G" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map Vertex (Set Vertex)))))

## Useful graph functions

These may be useful when implementing functions on graphs.

neighbors :: Graph g => Vertex -> g -> Set Vertex Source #

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

adjacent :: Graph g => Vertex -> Vertex -> g -> Bool Source #

Whether the given vertexes are adjacent in the graph.

## 🤷 🤷 🤷 Converting between graph representations

class (Graph g, ConvertibleGraph g) => ConvertibleGraph g Source #

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.

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.P80 Methods Source # Instance detailsDefined in Problems.P80 MethodstoG :: G -> G Source # Source # Instance detailsDefined in Problems.P80 MethodstoG :: Lists -> G Source # Source # Instance detailsDefined in Problems.P80 MethodstoG :: Paths -> G Source #

toLists :: ConvertibleGraph g => g -> Lists Source #

Convert graph to the Lists representation.

Convert graph to the Adjacency representation.

toPaths :: ConvertibleGraph g => g -> Paths Source #

Convert graph to the Paths representation.

toG :: ConvertibleGraph g => g -> G Source #

Convert graph to the G representation.

## 🤷 🤷 Paths between vertexes

paths :: Vertex -> Vertex -> G -> [[Vertex]] Source #

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

>>> 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]] []  ## Problem 82 ## 🤷 🤷 Cycles with a given vertex cycles :: Vertex -> G -> [[Vertex]] Source # 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]]


## 🤷 🤷 Construct spanning trees

spanningTrees :: G -> [G] Source #

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.

>>> 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  ## Problem 84 ## 🤷 🤷 Construct minimum spanning tree 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

Expand

The minimum spanning tree of a graph can be constructed using Prim's algorithm or Kruskal's algorithm.

## 🤷 🤷 Graph isomorphism

isomorphic :: G -> G -> Bool Source #

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

colorGraph :: G -> [(Vertex, Int)] Source #

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)]


Expand

### Hint

Expand

Write a function to sort vertexes in decreasing order of degree, i.e., the number of neighbors. The function sortOn may be useful for this.

## 🤷 🤷 Depth-first graph traversal

depthFirst :: G -> Vertex -> [Vertex] Source #

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.

>>> 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  ## Problem 88 ## 🤷 🤷 Connected components connectedComponents :: G -> [[Vertex]] Source # 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]]  ## Problem 89 ## 🤷 🤷 Bipartite graphs 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  # Miscellaenous problems ## Problem 90 ## 🤷 🤷 Find all solutions to the $$n$$ queens problem queens :: Int -> [[Int]] Source # 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]  ## Problem 91 ## 🤷 🤷 Knight's tour knightsTour :: Int -> (Int, Int) -> Maybe [(Int, Int)] Source # 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

Expand

A straightforward backtracking algorithm can be very slow even for moderately sized boards such as $$8 \times 8$$. Consider using Warnsdorff's rule. Alternatively, consider using a divide-and conquer algorithm which finds knight's tours for smaller boards and patching them together.

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)$$.

>>> 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  ## Problem 92 ## 🤷 🤷 🤷 Graceful tree labeling 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: Write a function which will gracefully label a tree graph. If there is no graceful labeling for a particular tree, return Nothing, and write up the counterexample for publication. ### Examples >>> gracefulTree tree92 Just (fromList [(1,5),(2,2),(3,1),(4,7),(5,3),(6,6),(7,4)])  >>> gracefulTree tree92' Just (fromList [(1,1),(2,10),(3,7),(4,3),(5,5),(6,6),(7,14),(8,13),(9,12),...  ### Notes Expand Problem 92 in the original list referred to this conjecture as "Von Koch's conjecture". However, I could not find any reference confirming that von Koch actually made this conjecture. From the style the problem was written in, it seems likely this was an imaginary scenario to make the problem feel more personal and fun, rather than something which actually happened. It is too unbelievable for me to have met the mathematician in question, so this was rewritten to a more dry presentation. ## Problem 93 ## 🤷 🤷 🤷 An arithmetic puzzle arithmeticPuzzle :: [Integer] -> [String] Source # Given a list of positive integer numbers, find a correct way of inserting the arithmetic signs such that the result is a correct equation. For example, with the list of numbers [2,3,5,7,11], we can form the equations 2-3+5+7=11 or 2=(3*5+7)/11. The arithmetic signs to insert are: • + : addition • - : subtraction • * : multiplication • / : division • = : equality • (, ) : parentheses Arithmetic operations are only binary, e.g., -4 should not be included. Division should be interpreted as operating on rationals, e.g., $$3/5 = 6/10$$ but $$3/5 \neq 0$$, and division by zero should be avoided. Parentheses should be inserted only when the default precedence rules need to be overridden. Equality should be inserted exactly once. ### Examples >>> mapM_ putStrLn$ sort $arithmeticPuzzle [2,3,5,7,11] 2 = (3*5+7)/11 2 = 3-(5+7)+11 2 = 3-(5+7-11) 2 = 3-5-(7-11) 2 = 3-5-7+11 2*(3-5) = 7-11 2-(3-(5+7)) = 11 2-(3-5)+7 = 11 2-(3-5-7) = 11 2-3+5+7 = 11  ## Problem 94 ## 🤷 🤷 🤷 Regular graphs Arguments  :: Int $$n$$ -> Int $$k$$ -> [G] non-isomorphic $$k$$-regular graphs with $$n$$ vertexes Generate $$k$$-regular graphs with $$n$$ vertexes. In a $$k$$-regular graph, all vertexes have a degree of $$k$$. I.e., the number of edges incident in each vertex is $$k$$. How many non-isomorphic 3-regular graphs with 6 vertexes are there? See Problems.P94.Examples for examples of $$k$$-regular graphs. ### Examples >>> length$ regularGraphs 6 3
2


## 🤷 🤷 English number words

fullWords :: Integral a => a -> String Source #

On financial documents such as checks, numbers must sometimes be written in full words. For example, 175 must be written as "one-seven-five". Write a function to return non-negative integers in full words.

### Examples

>>> fullWords 175
"one-seven-five"


## 🤷 🤷 Syntax checking

Identifiers in the Ada programming language have the syntax described by the diagram below.

Write a function which checks whether a given string is a legal identifier.

### Examples

>>> isIdentifier "this_is_a_long_identifier"
True

>>> isIdentifier "This_ends_in_an_underscore_"
False

>>> isIdentifier "This__has__two__consecutive__underscores"
False

>>> isIdentifier "1234"
False

>>> isIdentifier "_legal_in_many_other_languages"
False

>>> isIdentifier "Fibonacci_sequence_is_1_1_2_3_5_8_13_21_ad_infinitum"
True


### Hint

Expand

Translate the syntax diagram into a recursive grammar.

## 🤷 🤷 Sudoku

sudoku :: [[Int]] -> Maybe [[Int]] Source #

A Sudoku puzzle looks like this:

$\begin{array}{|ccc|ccc|ccc|} \hline . & . & 4 & 8 & . & . & . & 1 & 7 \\ 6 & 7 & . & 9 & . & . & . & . & . \\ 5 & . & 8 & . & 3 & . & . & 2 & 4 \\ \hline 3 & . & . & 7 & 4 & . & 1 & . & . \\ . & 6 & 9 & . & . & . & 7 & 8 & . \\ . & . & 1 & . & 6 & 9 & . & . & 5 \\ \hline 1 & . & . & . & 8 & . & 3 & . & . \\ . & . & . & . & . & 6 & . & 9 & 1 \\ 2 & 4 & . & . & . & 1 & 5 & . & . \\ \hline \end{array}$

The solution for the above is:

$\begin{array}{|ccc|ccc|ccc|} \hline 9 & 3 & 4 & 8 & 2 & 5 & 6 & 1 & 7 \\ 6 & 7 & 2 & 9 & 1 & 4 & 8 & 5 & 3 \\ 5 & 1 & 8 & 6 & 3 & 7 & 9 & 2 & 4 \\ \hline 3 & 2 & 5 & 7 & 4 & 8 & 1 & 6 & 9 \\ 4 & 6 & 9 & 1 & 5 & 3 & 7 & 8 & 2 \\ 7 & 8 & 1 & 2 & 6 & 9 & 4 & 3 & 5 \\ \hline 1 & 9 & 7 & 5 & 8 & 2 & 3 & 4 & 6 \\ 8 & 5 & 3 & 4 & 7 & 6 & 2 & 9 & 1 \\ 2 & 4 & 6 & 3 & 9 & 1 & 5 & 7 & 8 \\ \hline \end{array}$

Every spot in the puzzle on a $$9 \times 9$$ board belongs to a row and a column, as well as to one single $$3 \times 3$$ square, which we will simply call "square" for short. At the beginning, some of the spots carry a single-digit number from 1 to 9. The problem is to fill the missing spots with digits in such a way that every number between 1 and 9 appears exactly once in each row, in each column, and in each square.

Write a function which returns a solution given a Sudoku puzzle. Both will be expressed as a list of 9 rows. Each row will be a list of 9 numbers from 0 to 9, where 0 signifies a blank spot.

>>> printSudoku $sudoku sudokuPuzzle 9 3 4 8 2 5 6 1 7 6 7 2 9 1 4 8 5 3 5 1 8 6 3 7 9 2 4 3 2 5 7 4 8 1 6 9 4 6 9 1 5 3 7 8 2 7 8 1 2 6 9 4 3 5 1 9 7 5 8 2 3 4 6 8 5 3 4 7 6 2 9 1 2 4 6 3 9 1 5 7 8  ## Problem 98 ## 🤷 🤷 🤷 Nonograms Arguments  :: [[Int]] Lengths of occupied cells in each row -> [[Int]] Lengths of occupied cells in each column -> Maybe [[Bool]] Solution to the puzzle, if it exists Nonograms are picture logic puzzles invented in 1987, spreading from Japan to across the world. They look like this:  □ □ □ □ □ □ □ □ 3 □ □ □ □ □ □ □ □ 2 1 □ □ □ □ □ □ □ □ 3 2 □ □ □ □ □ □ □ □ 2 2 □ □ □ □ □ □ □ □ 6 □ □ □ □ □ □ □ □ 1 5 □ □ □ □ □ □ □ □ 6 □ □ □ □ □ □ □ □ 1 □ □ □ □ □ □ □ □ 2 1 3 1 7 5 3 4 3 2 1 5 1  Essentially, each row and column of a rectangular bitmap is annotated with the respective lengths of its distinct strings of occupied cells. The person who solves the puzzle must complete the bitmap given only these lengths. Published puzzles are larger than this example, e.g., $$25 \times 20$$, and apparently always have unique solutions. Try to solve the $$25 \times 25$$ puzzle in nonogramPuzzle. ### Examples >>> :{ printNonogramSolution$
nonogram [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]]
[[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]]
:}
■ ■ ■          3
■ ■   ■          2 1
■ ■ ■     ■ ■  3 2
■ ■     ■ ■  2 2
■ ■ ■ ■ ■ ■  6
■   ■ ■ ■ ■ ■    1 5
■ ■ ■ ■ ■ ■      6
■        1
■ ■        2

1 3 1 7 5 3 4 3

2 1 5 1


### Hint

Expand

If there is a string of occupied cells with length 9 in a row of 10 cells, can we infer which cells in the row must be occupied?

## 🤷 🤷 🤷 Crossword puzzles

Given an empty, or almost empty, crossword puzzle grid and a set of words, the problem is to place the words on the grid.

Words are strings of at least two characters. A horizontal or vertical sequence of spots in the crossword puzzle grid is called a site. Our problem is to find a compatible way of placing words onto sites. Each word should be placed at most once at a site.

Try to solve the $$25 \times 25$$ crossword puzzle in crosswordPuzzle'.

### Examples

>>> :{
crosswordPuzzle == Crossword
{ word = ["ALPHA", "ARES", "POPPY"]
, grid = [ [ Left False, Left False, Left True,  Left False, Left False ]
, [ Left False, Left False, Left True,  Left False, Left False ]
, [ Left True,  Left True,  Left True,  Left True,  Left True  ]
, [ Left False, Left False, Left True,  Left False, Left True  ]
, [ Left False, Left False, Left True,  Left False, Left True  ]
, [ Left False, Left False, Left False, Left False, Left True  ]
]
}
:}
True

>>> head $fromJust$ solveCrossword crosswordPuzzle
[Nothing,Nothing,Just 'P',Nothing,Nothing]

>>> printCrossword \$ solveCrossword crosswordPuzzle
■ ■ P ■ ■
■ ■ O ■ ■
A L P H A
■ ■ P ■ R
■ ■ Y ■ E
■ ■ ■ ■ S


data Crossword Source #

A crossword puzzle.

A list of words to fill the puzzle with is given along the grid to fill. The crossword puzzle grid is represented with a list of sublists. Each sublist denotes a row, and each value in the sublists denotes a spot. For each value in a spot:

• True denotes a blank spot that needs a character to be filled in.
• False denotes a spot that cannot be filled in.
• A character value denotes a spot pre-filled with the character.

Constructors

 Crossword Fieldsword :: [String]List of words to fill crossword puzzle withgrid :: [[Either Bool Char]]Grid for the crossword puzzle

#### Instances

Instances details
 Source # Instance detailsDefined in Problems.Crosswords MethodsshowList :: [Crossword] -> ShowS # Source # Instance detailsDefined in Problems.Crosswords Methods