Copyright | Copyright (C) 2023 Yoo Chung |
---|---|

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

This is a list of 99 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. Unlike the set of problems on the HaskellWiki, problems have been added so that there actually are 99 problems. The source for this module is available at GitHub.

## Synopsis

- myLast :: [a] -> Maybe a
- myButLast :: [a] -> Maybe a
- elementAt :: [a] -> Int -> Maybe a
- myLength :: [a] -> Int
- myReverse :: [a] -> [a]
- isPalindrome :: Eq a => [a] -> Bool
- flatten :: NestedList a -> [a]
- data NestedList a
- = Elem a
- | List [NestedList a]

- compress :: Eq a => [a] -> [a]
- pack :: Eq a => [a] -> [[a]]
- encode :: Eq a => [a] -> [(Int, a)]
- encodeModified :: Eq a => [a] -> [Encoding a]
- data Encoding a
- decodeModified :: [Encoding a] -> [a]
- encodeDirect :: Eq a => [a] -> [Encoding a]
- dupli :: [a] -> [a]
- repli :: [a] -> Int -> [a]
- dropEvery :: [a] -> Int -> [a]
- split :: [a] -> Int -> ([a], [a])
- slice :: [a] -> Int -> Int -> [a]
- rotate :: [a] -> Int -> [a]
- removeAt :: Int -> [a] -> (a, [a])
- insertAt :: a -> [a] -> Int -> [a]
- range :: Int -> Int -> [Int]
- randomSelect :: RandomGen g => [a] -> Int -> g -> ([a], g)
- randomDraw :: RandomGen g => Int -> Int -> g -> ([Int], g)
- randomPermute :: RandomGen g => [a] -> g -> ([a], g)
- combinations :: Int -> [a] -> [[a]]
- disjointGroups :: [Int] -> [a] -> [[[a]]]
- lsort :: [[a]] -> [[a]]
- lfsort :: [[a]] -> [[a]]
- fibonacci :: Integral a => a -> a
- fibonacci' :: Integral a => a -> a
- isPrime :: Integral a => a -> Bool
- myGCD :: Integral a => a -> a -> a
- coprime :: Integral a => a -> a -> Bool
- totient :: Integral a => a -> a
- primeFactors :: Integral a => a -> [a]
- primeFactorsMultiplicity :: Integral a => a -> [(a, a)]
- totient' :: Integral a => a -> a
- highlyTotientNumbers :: Integral a => [a]
- primesR :: Integral a => a -> a -> [a]
- primes :: Integral a => [a]
- goldbach :: Integral a => a -> (a, a)
- goldbachList :: Integral a => a -> a -> [(a, a)]
- multiplicativeInverse :: Integral a => a -> a -> Maybe a
- gaussianDividesBy :: Complex Integer -> Complex Integer -> Bool
- isGaussianPrime :: Complex Integer -> Bool
- isGaussianPrime' :: Complex Integer -> Bool
- type BoolFunc = Bool -> Bool -> Bool
- table :: BoolFunc -> [(Bool, Bool, Bool)]
- evaluateCircuit :: [(Int, Int)] -> Bool -> Bool -> Bool
- buildCircuit :: (Bool -> Bool -> Bool) -> [(Int, Int)]
- tablen :: Int -> ([Bool] -> Bool) -> [[Bool]]
- gray :: Int -> [String]
- huffman :: [(Char, Int)] -> [(Char, String)]
- corrupt :: RandomGen g => g -> Int -> [Bool] -> [Bool]
- errorCorrectingEncode :: [Bool] -> [Bool]
- errorCorrectingDecode :: [Bool] -> [Bool]
- toConjunctiveNormalForm :: Formula -> Formula
- data Formula
- isTheorem :: [Formula] -> Formula -> Bool
- data Tree a
- leaf :: a -> Tree a
- tree1 :: Tree Char
- tree2 :: Tree Char
- tree3 :: Tree Char
- tree4 :: Tree Int
- completelyBalancedTrees :: Int -> [Tree ()]
- symmetric :: Tree a -> Bool
- construct :: Ord a => [a] -> Tree a
- addedTo :: Ord a => a -> Tree a -> Tree a
- symmetricBalancedTrees :: Int -> [Tree ()]
- heightBalancedTrees :: Int -> [Tree ()]
- heightBalancedTreesWithNodes :: Int -> [Tree ()]
- leaves :: Tree a -> [a]
- internals :: Tree a -> [a]
- atLevel :: Tree a -> Int -> [a]
- completeBinaryTree :: Int -> Tree ()
- isCompleteBinaryTree :: Tree a -> Bool
- layoutInorder :: Tree a -> Tree (a, (Int, Int))
- layoutLevelConstant :: Tree a -> Tree (a, (Int, Int))
- layoutCompact :: Tree a -> Tree (a, (Int, Int))
- treeToString :: Tree Char -> String
- stringToTree :: String -> Maybe (Tree Char)
- inorder :: Tree a -> [a]
- preorder :: Tree a -> [a]
- ordersToTree :: Eq a => [a] -> [a] -> Maybe (Tree a)
- dotstringToTree :: String -> Maybe (Tree Char)
- treeToDotstring :: Tree Char -> String
- data MultiwayTree a = MultiwayTree a [MultiwayTree a]
- multitree1 :: MultiwayTree Char
- multitree2 :: MultiwayTree Char
- multitree3 :: MultiwayTree Char
- multitree4 :: MultiwayTree Char
- multitree5 :: MultiwayTree Char
- stringToMultitree :: String -> Maybe (MultiwayTree Char)
- multitreeToString :: MultiwayTree Char -> String
- internalPathLength :: MultiwayTree a -> Int
- postOrderSequence :: MultiwayTree a -> [a]
- treeToSexp :: MultiwayTree Char -> String
- sexpToTree :: String -> Maybe (MultiwayTree Char)
- askGoldbach :: Handle -> Handle -> IO ()
- maybeGoldbach :: String -> Maybe (Integer, (Integer, Integer))
- eitherGoldbach :: String -> Either String (Integer, (Integer, Integer))
- randomWalkPaths :: Int -> [[Int]]
- collatz :: Integral a => a -> a
- calculatePostfix :: [Element] -> (Maybe Integer, [([Integer], Maybe Operator)])
- data Element
- data Operator
- class Graph g where
- type Vertex = Int
- newtype Edge = Edge (Vertex, Vertex)
- data Var a
- newtype Lists = Lists ([Vertex], [(Vertex, Vertex)])
- newtype Adjacency = Adjacency [(Vertex, [Vertex])]
- newtype Paths = Paths [[Vertex]]
- newtype G = G (Map Vertex (Set Vertex))
- neighbors :: Graph g => Vertex -> g -> Set Vertex
- adjacent :: Graph g => Vertex -> Vertex -> g -> Bool
- class (Graph g, ConvertibleGraph g) => ConvertibleGraph g
- toLists :: ConvertibleGraph g => g -> Lists
- toAdjacency :: ConvertibleGraph g => g -> Adjacency
- toPaths :: ConvertibleGraph g => g -> Paths
- toG :: ConvertibleGraph g => g -> G
- paths :: Vertex -> Vertex -> G -> [[Vertex]]
- cycles :: Vertex -> G -> [[Vertex]]
- spanningTrees :: G -> [G]
- isTree :: G -> Bool
- isConnected :: G -> Bool
- minimumSpanningTree :: G -> Map Edge Int -> G
- isomorphic :: G -> G -> Bool
- colorGraph :: G -> [(Vertex, Int)]
- depthFirst :: G -> Vertex -> [Vertex]
- connectedComponents :: G -> [[Vertex]]
- bipartite :: G -> Bool
- queens :: Int -> [[Int]]
- knightsTour :: Int -> (Int, Int) -> Maybe [(Int, Int)]
- closedKnightsTour :: Int -> Maybe [(Int, Int)]
- gracefulTree :: G -> Maybe (Map Vertex Int)
- arithmeticPuzzle :: [Integer] -> [String]
- regularGraphs :: Int -> Int -> [G]
- fullWords :: Integral a => a -> String
- isIdentifier :: String -> Bool
- sudoku :: [[Int]] -> Maybe [[Int]]
- nonogram :: [[Int]] -> [[Int]] -> Maybe [[Bool]]
- solveCrossword :: Crossword -> Maybe [[Maybe Char]]
- data Crossword = Crossword {}

# List problems

## Problem 1

## 🤷 Last element of a list

myLast :: [a] -> Maybe a Source #

Find the last element of a list.

### Examples

`>>>`

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

`>>>`

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

`>>>`

Nothing`myLast []`

## Problem 2

## 🤷 Penultimate element of a list

myButLast :: [a] -> Maybe a Source #

Find the last but one element of a list.

### Examples

`>>>`

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

`>>>`

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

`>>>`

Nothing`myButLast ['a']`

## Problem 3

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

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

Find the `k`

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

### Examples

`>>>`

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

`>>>`

Just 'e'`elementAt "haskell" 5`

`>>>`

Nothing`elementAt [1,2] 3`

## Problem 4

## 🤷 Length of a list

myLength :: [a] -> Int Source #

Find the number of elements of a list.

### Examples

`>>>`

3`myLength [123, 456, 789]`

`>>>`

13`myLength "Hello, world!"`

## Problem 5

## 🤷 Reverse a list

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

Reverse a list.

### Examples

`>>>`

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

`>>>`

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

## Problem 6

## 🤷 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

`>>>`

False`isPalindrome [1,2,3]`

`>>>`

True`isPalindrome "madamimadam"`

`>>>`

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

## Problem 7

## 🤷 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

`>>>`

[5]`flatten $ Elem 5`

`>>>`

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

`>>>`

[]`flatten $ List []`

data NestedList a Source #

A list type with arbitrary nesting of lists.

Elem a | A non-list element. |

List [NestedList a] | Nested list. |

#### Instances

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

`>>>`

"abcade"`compress "aaaabccaadeeee"`

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

`>>>`

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

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

`>>>`

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

## 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 `(`

values.`Multiple`

n x)

### Examples

`>>>`

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

Encodes one or more consecutively duplicate elements.

Single a | Represents a single occurrence of an element. |

Multiple Int a | Represents an element repeating consecutively a given number of times. |

#### Instances

Generic (Encoding a) Source # | |

Show a => Show (Encoding a) Source # | |

NFData a => NFData (Encoding a) Source # | |

Defined in Problems.Lists | |

Eq a => Eq (Encoding a) Source # | |

type Rep (Encoding a) Source # | |

Defined in Problems.Lists type Rep (Encoding a) = D1 ('MetaData "Encoding" "Problems.Lists" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" '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

`>>>`

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

## 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 `(`

by `Multiple`

1 x)`(`

.`Single`

x)

### Examples

`>>>`

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

## Problem 14

## 🤷 Duplicate elements in a list

Duplicate the elements of a list.

### Examples

`>>>`

[1,1,2,2,3,3]`dupli [1, 2, 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

`>>>`

"aaabbbccc"`repli "abc" 3`

## Problem 16

## 🤷 🤷 Drop elements in a list

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

Drop every `n`

th element from a list.

### Examples

`>>>`

"abdeghk"`dropEvery "abcdefghik" 3`

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

`>>>`

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

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

`>>>`

"cdefg"`slice "abcdefghijk" 3 7`

## Problem 19

## 🤷 🤷 Rotate a list

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

Rotate a list `n`

places to the left.

### Examples

`>>>`

"defghabc"`rotate "abcdefgh" 3`

`>>>`

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

## Problem 20

## 🤷 Remove element from a list

removeAt :: Int -> [a] -> (a, [a]) Source #

Remove the `k`

th element from a list.
Return the element removed and the residue list.

### Examples

`>>>`

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

## Problem 21

## 🤷 Insert element into a list

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

Insert an element at a given position into a list.

### Examples

`>>>`

"aXbcd"`insertAt 'X' "abcd" 2`

## Problem 22

## 🤷 Range of integers

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

Create a list containing all integers within a given range.

### Examples

`>>>`

[4,5,6,7,8,9]`range 4 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

`>>>`

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

`>>>`

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

`>>>`

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

## Problem 24

## 🤷 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

`>>>`

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

`>>>`

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

`>>>`

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

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

`>>>`

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

`>>>`

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

`>>>`

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

## Problem 26

## 🤷 🤷 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

`>>>`

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

`>>>`

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

## Problem 27

## 🤷 🤷 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"]`

`>>>`

[["aldo","beat"],["carla","david","evi"],["flip","gary","hugo","ida"]]`minimum $ map (map sort) $ disjointGroups [2,3,4] names`

`>>>`

1260`length $ disjointGroups [2,3,4] names`

`>>>`

756`length $ disjointGroups [2,2,5] names`

## Problem 28

## 🤷 🤷 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

`>>>`

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

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

`>>>`

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

# Arithmetic problems

## Problem 29

## 🤷 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

`>>>`

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

## Problem 30

## 🤷 🤷 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:

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

### Examples

`>>>`

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

`>>>`

19532821287077577316...`fibonacci' 1000000`

`>>>`

208988`length $ show $ fibonacci' 1000000`

### Hint

With exponentiation by squaring, \(x^n\) can be computed with \(O(\log n)\) multiplications. E.g., since \(x^{39} = (((((((x^2 )^2 )^2) x)^2) x)^2 ) x\), \(x^{39}\) can be computed with 8 multiplications instead of 38.

## Problem 31

## 🤷 🤷 Primality checking

isPrime :: Integral a => a -> Bool Source #

Determine whether a given integer number is prime.

### Examples

`>>>`

True`isPrime 7`

`>>>`

False`isPrime 15`

## Problem 32

## 🤷 🤷 Greatest common divisor

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

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

### Examples

`>>>`

9`myGCD 36 63`

`>>>`

1`myGCD 125 81`

`>>>`

13`myGCD 221 559`

## Problem 33

## 🤷 Coprimality

coprime :: Integral a => a -> a -> Bool Source #

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

### Examples

`>>>`

True`coprime 35 64`

`>>>`

False`coprime 1173 1547`

## Problem 34

## 🤷 🤷 Euler's totient function

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

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

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

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

### Examples

`>>>`

4`totient 10`

## Problem 35

## 🤷 🤷 List of prime factors

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

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

### Examples

`>>>`

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

## Problem 36

## 🤷 🤷 List of prime factors and their multiplicities

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

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

### Examples

`>>>`

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

## Problem 37

## 🤷 🤷 Euler's totient function with Euler's product formula

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

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

for the definition of Euler's totient function.

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

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

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

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

Compare with the solution for Problems.P34:

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

### Examples

`>>>`

4`totient' 10`

## Problem 38

## 🤷 🤷 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

`>>>`

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

### Hint

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.

## Problem 39

## 🤷 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

`>>>`

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

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

Construct the list of all prime numbers.

### Examples

`>>>`

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

## Problem 40

## 🤷 🤷 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

`>>>`

(5,7)`goldbach 12`

## Problem 41

## 🤷 🤷 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

`>>>`

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

`>>>`

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

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

`>>>`

Just 2`multiplicativeInverse 3 5`

`>>>`

Just 45`multiplicativeInverse 48 127`

`>>>`

Just 50`multiplicativeInverse 824 93`

`>>>`

Nothing`multiplicativeInverse 48 93`

## Problem 43

## 🤷 Gaussian integer divisibility

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

`>>>`

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

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

`>>>`

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

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

`>>>`

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

### Hint

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

## Problem 44

## 🤷 🤷 Gaussian primes

isGaussianPrime :: Complex Integer -> Bool Source #

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

`>>>`

False`isGaussianPrime (0 :+ 5)`

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

`>>>`

False`isGaussianPrime (17 :+ 0)`

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

`>>>`

True`isGaussianPrime (5 :+ 2)`

### Hint

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.

## Problem 45

## 🤷 Gaussian primes using the two-square theorem

isGaussianPrime' :: Complex Integer -> Bool Source #

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

`>>>`

False`isGaussianPrime' (0 :+ 5)`

`>>>`

False`isGaussianPrime' (17 :+ 0)`

`>>>`

True`isGaussianPrime' (5 :+ 2)`

# 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

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

tuples.
If `Bool`

, `Bool`

, `Bool`

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

`>>>`

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

## Problem 47

## 🤷 🤷 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`i`

th and`j`

th 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

`>>>`

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

`>>>`

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

`>>>`

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

`>>>`

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

`>>>`

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

`>>>`

False`evaluateCircuit [(-1,-1),(-2,-2),(1,2)] 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

`>>>`

False`evaluateCircuit (buildCircuit (&&)) False False`

`>>>`

False`evaluateCircuit (buildCircuit (&&)) False True`

`>>>`

False`evaluateCircuit (buildCircuit (&&)) True False`

`>>>`

True`evaluateCircuit (buildCircuit (&&)) True True`

### Hint

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.

## Problem 48

## 🤷 🤷 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

`>>>`

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`printTablen $ tablen 3 (\[a,b,c] -> a `and'` (b `or'` c) `equ'` a `and'` b `or'` a `and'` c)`

## 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,

`>>>`

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

`>>>`

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

`>>>`

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

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

`>>>`

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

The encoding table computed by `huffman`

can be used to compress data:

`>>>`

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

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

`>>>`

4375`length $ encodeHuffman loweralpha text`

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

`>>>`

7000`length $ encodeHuffman ascii text`

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`

`>>>`

True`decodedText == text`

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

`>>>`

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

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

`>>>`

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

`>>>`

`let e = errorCorrectingEncode [True, False, False, True, False]`

`>>>`

`let e' = corrupt (mkStdGen 111) 1 e`

`>>>`

[True,False,False,True,False]`errorCorrectingDecode e'`

## Problem 52

## 🤷 🤷 🤷 Conjunctive normal form

toConjunctiveNormalForm :: Formula -> Formula Source #

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

`>>>`

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

`>>>`

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

`>>>`

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

### Hint

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.

Represents a boolean formula.

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

## 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:

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.

- Convert \(Y\) into conjunctive normal form; see Problems.P52.
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

`>>>`

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

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

`>>>`

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

# Binary tree problems

## Problem 54

## 🤷 Binary trees

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

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.

#### Instances

Generic (Tree a) Source # | |

Show a => Show (Tree a) Source # | |

NFData a => NFData (Tree a) Source # | |

Defined in Problems.BinaryTrees | |

Eq a => Eq (Tree a) Source # | |

Ord a => Ord (Tree a) Source # | An arbitrary total ordering for Defines an order for a set of |

type Rep (Tree a) Source # | |

Defined in Problems.BinaryTrees type Rep (Tree a) = D1 ('MetaData "Tree" "Problems.BinaryTrees" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" '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))))) |

Define a shorthand function for constructing a leaf node.

A leaf node in `Tree`

is a branch with two empty subtrees.

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

.

## Problem 55

## 🤷 🤷 Construct completely balanced binary trees

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

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

`>>>`

[ 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) ]`printTreeList $ completelyBalancedTrees 4`

## Problem 56

## 🤷 🤷 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

`>>>`

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

`>>>`

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

### Hint

Write a function `mirror`

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

## Problem 57

## 🤷 🤷 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

`>>>`

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

`>>>`

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

`>>>`

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

### Notes

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

`>>>`

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

## Problem 58

## 🤷 🤷 Symmetric and completely balanced binary trees

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

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

### Examples

`>>>`

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

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

`>>>`

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

`>>>`

315`length $ heightBalancedTrees 4`

## Problem 60

## 🤷 🤷 Height-balanced binary trees with given number of nodes

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

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

### Examples

`>>>`

1553`length $ heightBalancedTreesWithNodes 15`

`>>>`

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

### Hint

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

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

`>>>`

[2,4]`sort $ leaves tree4`

### Notes

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.

### Examples

`>>>`

[1,2]`sort $ internals tree4`

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

`>>>`

[2,2]`atLevel tree4 2`

### Notes

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

completeBinaryTree :: Int -> Tree () Source #

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
`Empty`

s, 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

`>>>`

Branch () (Branch () (Branch () Empty Empty) Empty) (Branch () Empty Empty)`completeBinaryTree 4`

### Hint

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.

isCompleteBinaryTree :: Tree a -> Bool Source #

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

### Examples

`>>>`

True`isCompleteBinaryTree $ Branch () (Branch () Empty Empty) Empty`

`>>>`

False`isCompleteBinaryTree $ Branch () Empty (Branch () Empty Empty)`

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

`>>>`

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

### Notes

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

`>>>`

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

### Hint

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

`>>>`

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

### Hint

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

treeToString :: Tree Char -> String Source #

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

`>>>`

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

stringToTree :: String -> Maybe (Tree Char) Source #

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

### Examples

`>>>`

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

## Problem 68

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

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

Return the in-order sequence of a binary tree.

### Examples

`>>>`

"dbeacgf"`inorder tree1`

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

Return the pre-order sequence of a binary tree.

### Examples

`>>>`

"abdecfg"`preorder tree1`

:: Eq a | |

=> [a] | In-order sequence |

-> [a] | Pre-order sequence |

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

`>>>`

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

## Problem 69

## 🤷 🤷 Dotstring representation of binary trees

dotstringToTree :: String -> Maybe (Tree Char) Source #

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

`>>>`

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

treeToDotstring :: Tree Char -> String Source #

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

### Examples

`>>>`

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

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

MultiwayTree a [MultiwayTree a] |

#### Instances

multitree1 :: MultiwayTree Char Source #

Example of the following multiway tree.

`>>>`

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

multitree2 :: MultiwayTree Char Source #

Example of the following multiway tree.

`>>>`

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

multitree3 :: MultiwayTree Char Source #

Example of the following multiway tree.

`>>>`

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

multitree4 :: MultiwayTree Char Source #

Example of the following multiway tree.

`>>>`

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

multitree5 :: MultiwayTree Char Source #

Example of the following multiway tree.

`>>>`

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

## Problem 70

## 🤷 🤷 Tree construction from a node string

stringToMultitree :: String -> Maybe (MultiwayTree Char) Source #

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

`>>>`

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

multitreeToString :: MultiwayTree Char -> String Source #

Construct the node string from a `MultiwayTree`

.

### Examples

`>>>`

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

## Problem 71

## 🤷 Internal path length of a tree

internalPathLength :: MultiwayTree a -> Int Source #

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

`>>>`

9`internalPathLength multitree5`

`>>>`

2`internalPathLength multitree4`

## Problem 72

## 🤷 Post-order sequence of a tree

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

Construct the post-order sequence of the tree nodes.

### Examples

`>>>`

"gfcdeba"`postOrderSequence multitree5`

### Notes

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.

## Problem 73

## 🤷 🤷 Tree representation with s-expressions

treeToSexp :: MultiwayTree Char -> String Source #

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

`>>>`

"a"`treeToSexp multitree1`

`>>>`

"(a b)"`treeToSexp multitree2`

`>>>`

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

`>>>`

"(b d e)"`treeToSexp multitree4`

`>>>`

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

### Notes

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.

sexpToTree :: String -> Maybe (MultiwayTree Char) Source #

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

, into a `MultiwayTree`

.

### Examples

`>>>`

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

# Monad problems

## Problem 74

## 🤷 🤷 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 () askGoldbach hIn hOut = do s <- hGetLine hIn let n = read s :: Int let (a,b) = goldbach n hPutStr hOut $ show n hPutStr hOut "=" hPutStr hOut $ show a hPutStr hOut "+" hPrint hOut b

Implement the function without do notation.
In other words, use `>>=`

or `>>`

directly, instead of using them implicitly through do notation.
Try to use these functions with prefix style instead of infix style.

### Examples

`>>>`

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

### Hint

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

maybeGoldbach :: String -> Maybe (Integer, (Integer, Integer)) Source #

In Problems.P75, `askGoldbach`

could not output an error if the input was not a number
or it was not an even number greater than 2. We could implement a function which returned `Nothing`

when the input is not valid, such as in the following.

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

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

`>>>`

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

However, the implementation of `maybeGoldbach`

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

value.

Take advantage of the fact that `Maybe`

is a monad
and rewrite `maybeGoldbach`

more succintly using do notation.
The `guard`

function, which in the `Maybe`

monad
returns `Just ()`

when its argument is true
and `Nothing`

when its argument is false,
would be useful for making it even more succinct.

### Examples

`>>>`

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

`>>>`

Nothing`maybeGoldbach "not a number"`

`>>>`

Nothing`maybeGoldbach "1"`

`>>>`

Nothing`maybeGoldbach "101"`

## Problem 76

## 🤷 Either monad

eitherGoldbach :: String -> Either String (Integer, (Integer, Integer)) Source #

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

`>>>`

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

`>>>`

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

`>>>`

Left "not greater than 2"`eitherGoldbach "2"`

`>>>`

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

## Problem 77

## 🤷 List monad

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

`>>>`

[[0]]`randomWalkPaths 0`

`>>>`

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

### Hint

The list monad can be a simple way to model non-deterministic computations. For example, if we have one number that may be either 2 or 3, and we want to multiply it by another number that may be either 5 or 6, we can get the possible results as follows:

`>>>`

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

## Problem 78

## 🤷 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

`>>>`

0`collatz 1`

`>>>`

1`collatz 2`

`>>>`

106`collatz 31`

### Hint

## Problem 79

## 🤷 🤷 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:

`>>>`

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

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

`>>>`

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

Negation applies to a single number:

`>>>`

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

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

`>>>`

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

The `parsePostfix`

function can be used to conveniently create an expression:

`>>>`

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

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

`>>>`

([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)`mapM_ print $ snd $ calculatePostfix $ parsePostfix "8 5 4 10 + - 3 * negate +"`

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:

`>>>`

Nothing`fst $ calculatePostfix $ parsePostfix "1 2 * +"`

`>>>`

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

### Hint

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

Encodes an operator for a mathematical expression.

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 |

Modulo | Encodes a modulo operator. Equivalent to |

#### Instances

Bounded Operator Source # | |

Enum Operator Source # | |

Show Operator Source # | |

Eq Operator Source # | |

# Graph problems

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

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.

vertexes :: g -> Set Vertex Source #

The set of vertexes.

edges :: g -> Set Edge Source #

The set of edges.

#### Instances

A vertex in a graph.

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

An edge in a graph.

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

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

## Graph representations

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

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.

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 ...`Lists ([1, 2, 3, 4, 5], [(1, 2), (1, 4), (2, 3), (2, 4), (3, 4), (4, 5)])`

#### Instances

Generic Lists Source # | |

Show Lists Source # | |

NFData Lists Source # | |

Defined in Problems.Graphs | |

Eq Lists Source # | |

Graph Lists Source # | |

Defined in Problems.Graphs vertexes :: Lists -> Set Vertex Source # edges :: Lists -> Set Edge Source # sets :: Lists -> (Set Vertex, Set Edge) Source # neighbors :: Vertex -> Lists -> Set Vertex Source # adjacent :: Vertex -> Vertex -> Lists -> Bool Source # toGraph :: (Set Vertex, Set Edge) -> Maybe Lists Source # isValidGraph :: Lists -> Bool Source # | |

ConvertibleGraph Lists Source # | |

ConvertibleGraph Lists Source # | |

type Rep Lists Source # | |

Defined in Problems.Graphs |

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 ...`Adjacency [(1, [2, 4]), (2, [1, 3, 4]), (3, [2, 4]), (4, [1, 2, 3, 5]), (5, [4])]`

#### Instances

Generic Adjacency Source # | |

Show Adjacency Source # | |

NFData Adjacency Source # | |

Defined in Problems.Graphs | |

Eq Adjacency Source # | |

Graph Adjacency Source # | |

Defined in Problems.Graphs vertexes :: Adjacency -> Set Vertex Source # edges :: Adjacency -> Set Edge Source # sets :: Adjacency -> (Set Vertex, Set Edge) Source # neighbors :: Vertex -> Adjacency -> Set Vertex Source # adjacent :: Vertex -> Vertex -> Adjacency -> Bool Source # toGraph :: (Set Vertex, Set Edge) -> Maybe Adjacency Source # isValidGraph :: Adjacency -> Bool Source # | |

ConvertibleGraph Adjacency Source # | |

ConvertibleGraph Adjacency Source # | |

type Rep Adjacency Source # | |

Defined in Problems.Graphs |

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 ...`Paths [[1, 2, 3, 4, 5], [1, 4], [2, 4]]`

### DOT graphs

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 }

#### Instances

Generic Paths Source # | |

Show Paths Source # | |

NFData Paths Source # | |

Defined in Problems.Graphs | |

Eq Paths Source # | |

Graph Paths Source # | |

Defined in Problems.Graphs vertexes :: Paths -> Set Vertex Source # edges :: Paths -> Set Edge Source # sets :: Paths -> (Set Vertex, Set Edge) Source # neighbors :: Vertex -> Paths -> Set Vertex Source # adjacent :: Vertex -> Vertex -> Paths -> Bool Source # toGraph :: (Set Vertex, Set Edge) -> Maybe Paths Source # isValidGraph :: Paths -> Bool Source # | |

ConvertibleGraph Paths Source # | |

ConvertibleGraph Paths Source # | |

type Rep Paths Source # | |

Defined in Problems.Graphs |

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 ...`:{`

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

## Problem 80

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

toAdjacency :: ConvertibleGraph g => g -> Adjacency Source #

Convert graph to the `Adjacency`

representation.

## Problem 81

## 🤷 🤷 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`

.

### Examples

`>>>`

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

`>>>`

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

`>>>`

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

## Problem 83

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

### Examples

`>>>`

173`length $ spanningTrees graph83`

`>>>`

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

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

.

### Examples

`>>>`

False`isTree graph83`

`>>>`

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

isConnected :: G -> Bool Source #

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

.

### Examples

`>>>`

True`isConnected graph83`

`>>>`

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

## Problem 84

## 🤷 🤷 Construct minimum spanning tree

minimumSpanningTree :: G -> Map Edge Int -> G Source #

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`

`>>>`

33`Set.foldr (\e w -> w + weights84 ! e) 0 $ edges t`

### Hint

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

## Problem 85

## 🤷 🤷 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

`>>>`

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

`>>>`

True`isomorphic graph85 graph85'`

## Problem 86

## 🤷 🤷 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

`>>>`

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

#### Visualization with real colors

### Hint

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.

## Problem 87

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

### Examples

`>>>`

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

`>>>`

True`xs `elem` [[1,2,3,4,5], [1,2,4,5,3], [1,2,4,3,5]]`

## Problem 88

## 🤷 🤷 Connected components

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

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

### Examples

`>>>`

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

## Problem 89

## 🤷 🤷 Bipartite graphs

bipartite :: G -> Bool Source #

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

### Examples

`>>>`

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

`>>>`

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

# 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

`>>>`

92`length $ queens 8`

`>>>`

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

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

`>>>`

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`printKnightsTour $ knightsTour 6 (3,5)`

### Hint

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.

closedKnightsTour :: Int -> Maybe [(Int, Int)] Source #

The same as `knightsTour`

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

### Examples

`>>>`

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`printKnightsTour $ closedKnightsTour 6`

## Problem 92

## 🤷 🤷 🤷 Graceful tree labeling

gracefulTree :: G -> Maybe (Map Vertex Int) Source #

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

`>>>`

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),...`gracefulTree tree92'`

### Notes

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

`>>>`

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`mapM_ putStrLn $ sort $ arithmeticPuzzle [2,3,5,7,11]`

## Problem 94

## 🤷 🤷 🤷 Regular graphs

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

`>>>`

2`length $ regularGraphs 6 3`

## Problem 95

## 🤷 🤷 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

`>>>`

"one-seven-five"`fullWords 175`

## Problem 96

## 🤷 🤷 Syntax checking

isIdentifier :: String -> Bool Source #

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

`>>>`

True`isIdentifier "this_is_a_long_identifier"`

`>>>`

False`isIdentifier "This_ends_in_an_underscore_"`

`>>>`

False`isIdentifier "This__has__two__consecutive__underscores"`

`>>>`

False`isIdentifier "1234"`

`>>>`

False`isIdentifier "_legal_in_many_other_languages"`

`>>>`

True`isIdentifier "Fibonacci_sequence_is_1_1_2_3_5_8_13_21_ad_infinitum"`

### Hint

Translate the syntax diagram into a recursive grammar.

## Problem 97

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

### Examples

`>>>`

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`printSudoku $ sudoku sudokuPuzzle`

## Problem 98

## 🤷 🤷 🤷 Nonograms

:: [[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

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?

## Problem 99

## 🤷 🤷 🤷 Crossword puzzles

solveCrossword :: Crossword -> Maybe [[Maybe Char]] Source #

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`:{`

`>>>`

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

`>>>`

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

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: