ninetynine-1.3.0: Ninety-Nine Haskell Problems
CopyrightCopyright (C) 2023 Yoo Chung
LicenseGPL-3.0-or-later
Maintainerdev@chungyc.org
Safe HaskellSafe-Inferred
LanguageGHC2021

Problems

Description

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

List problems

Problem 1

🤷 Last element of a list

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

Find the last element of a list.

Examples

>>> myLast [1,2,3,4]
Just 4
>>> myLast ['x','y','z']
Just 'z'
>>> myLast []
Nothing

Problem 2

🤷 Penultimate element of a list

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

Find the last but one element of a list.

Examples

>>> myButLast [1,2,3,4]
Just 3
>>> myButLast ['a'..'z']
Just 'y'
>>> myButLast ['a']
Nothing

Problem 3

🤷 Find element of a list at a given position

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

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

Examples

>>> elementAt [1,2,3] 2
Just 2
>>> elementAt "haskell" 5
Just 'e'
>>> elementAt [1,2] 3
Nothing

Problem 4

🤷 Length of a list

myLength :: [a] -> Int Source #

Find the number of elements of a list.

Examples

>>> myLength [123, 456, 789]
3
>>> myLength "Hello, world!"
13

Problem 5

🤷 Reverse a list

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

Reverse a list.

Examples

>>> myReverse "A man, a plan, a canal, panama!"
"!amanap ,lanac a ,nalp a ,nam A"
>>> myReverse [1,2,3,4]
[4,3,2,1]

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

>>> isPalindrome [1,2,3]
False
>>> isPalindrome "madamimadam"
True
>>> isPalindrome [1,2,4,8,16,8,4,2,1]
True

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

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

data NestedList a Source #

A list type with arbitrary nesting of lists.

Constructors

Elem a

A non-list element.

List [NestedList a]

Nested list.

Instances

Instances details
Generic (NestedList a) Source # 
Instance details

Defined in Problems.Lists

Associated Types

type Rep (NestedList a) :: Type -> Type #

Methods

from :: NestedList a -> Rep (NestedList a) x #

to :: Rep (NestedList a) x -> NestedList a #

Show a => Show (NestedList a) Source # 
Instance details

Defined in Problems.Lists

Eq a => Eq (NestedList a) Source # 
Instance details

Defined in Problems.Lists

Methods

(==) :: NestedList a -> NestedList a -> Bool #

(/=) :: NestedList a -> NestedList a -> Bool #

type Rep (NestedList a) Source # 
Instance details

Defined in Problems.Lists

type Rep (NestedList a) = D1 ('MetaData "NestedList" "Problems.Lists" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'False) (C1 ('MetaCons "Elem" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a)) :+: C1 ('MetaCons "List" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [NestedList a])))

Problem 8

🤷 Eliminate duplicate elements in a list

compress :: Eq a => [a] -> [a] Source #

Eliminate consecutive duplicates of list elements.

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

Examples

>>> compress "aaaabccaadeeee"
"abcade"

Problem 9

🤷 🤷 Pack duplicates in a list

pack :: Eq a => [a] -> [[a]] Source #

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

Examples

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

Problem 10

🤷 Run-length encoding of a list

encode :: Eq a => [a] -> [(Int, a)] Source #

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

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

Examples

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

Problem 11

🤷 Modified run-length encoding

encodeModified :: Eq a => [a] -> [Encoding a] Source #

Modify the encode function in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as (Multiple n x) values.

Examples

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

data Encoding a Source #

Encodes one or more consecutively duplicate elements.

Constructors

Single a

Represents a single occurrence of an element.

Multiple Int a

Represents an element repeating consecutively a given number of times.

Instances

Instances details
Generic (Encoding a) Source # 
Instance details

Defined in Problems.Lists

Associated Types

type Rep (Encoding a) :: Type -> Type #

Methods

from :: Encoding a -> Rep (Encoding a) x #

to :: Rep (Encoding a) x -> Encoding a #

Show a => Show (Encoding a) Source # 
Instance details

Defined in Problems.Lists

Methods

showsPrec :: Int -> Encoding a -> ShowS #

show :: Encoding a -> String #

showList :: [Encoding a] -> ShowS #

NFData a => NFData (Encoding a) Source # 
Instance details

Defined in Problems.Lists

Methods

rnf :: Encoding a -> () #

Eq a => Eq (Encoding a) Source # 
Instance details

Defined in Problems.Lists

Methods

(==) :: Encoding a -> Encoding a -> Bool #

(/=) :: Encoding a -> Encoding a -> Bool #

type Rep (Encoding a) Source # 
Instance details

Defined in Problems.Lists

Problem 12

🤷 Decode a run-length encoded list

decodeModified :: [Encoding a] -> [a] Source #

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

Examples

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

Problem 13

🤷 🤷 Run-length encoding of a list; direct solution

encodeDirect :: Eq a => [a] -> [Encoding a] Source #

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

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

Examples

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

Problem 14

🤷 Duplicate elements in a list

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

Duplicate the elements of a list.

Examples

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

Problem 15

🤷 Replicate elements of a list

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

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

Examples

>>> repli "abc" 3
"aaabbbccc"

Problem 16

🤷 🤷 Drop elements in a list

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

Drop every nth element from a list.

Examples

>>> dropEvery "abcdefghik" 3
"abdeghk"

Problem 17

🤷 Split a list

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

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

Examples

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

Problem 18

🤷 🤷 Extract a slice from a list

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

Extract a slice from a list.

Given two indices, i and k, the slice is the list containing the elements between the i'th and k'th element of the original list, with both limits included. Start counting the elements with 1.

Examples

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

Problem 19

🤷 🤷 Rotate a list

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

Rotate a list n places to the left.

Examples

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

Problem 20

🤷 Remove element from a list

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

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

Examples

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

Problem 21

🤷 Insert element into a list

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

Insert an element at a given position into a list.

Examples

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

Problem 22

🤷 Range of integers

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

Create a list containing all integers within a given range.

Examples

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

Problem 23

🤷 🤷 Select random elements from a list

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

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

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

Examples

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

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

>>> fst $ randomDraw 6 49 $ mkStdGen 111
[40,13,25,27,26,6]
>>> take 5 $ unfoldr (Just . randomDraw 3 100) $ mkStdGen 111
[[11,19,76],[63,49,10],[75,42,12],[20,48,78],[40,94,86]]
>>> fst . randomDraw 6 49 <$> newStdGen
[17,7,1,18,13,3]

Problem 25

🤷 Random permutation of a list

randomPermute :: RandomGen g => [a] -> g -> ([a], g) Source #

Generate a random permutation of the elements of a list.

Examples

>>> fst $ randomPermute [1..10] $ mkStdGen 111
[8,4,7,9,3,5,10,2,1,6]
>>> take 5 $ unfoldr (Just . randomPermute ['a'..'d']) $ mkStdGen 111
["cbad","abdc","abdc","acdb","cdba"]
>>> fst . randomPermute "abcdef" <$> newStdGen
"dcaebf"

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

>>> length $ combinations 3 [1..12]
220
>>> sort $ combinations 3 "abcdef"
["abc","abd","abe",...]

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"]
>>> minimum $ map (map sort) $ disjointGroups [2,3,4] names
[["aldo","beat"],["carla","david","evi"],["flip","gary","hugo","ida"]]
>>> length $ disjointGroups [2,3,4] names
1260
>>> length $ disjointGroups [2,2,5] names
756

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

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

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

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

Examples

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

Arithmetic problems

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

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

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

>>> map fibonacci' [1..10]
[1,1,2,3,5,8,13,21,34,55]
>>> fibonacci' 1000000
19532821287077577316...
>>> length $ show $ fibonacci' 1000000
208988

Hint

Expand

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

>>> isPrime 7
True
>>> isPrime 15
False

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

>>> myGCD 36 63
9
>>> myGCD 125 81
1
>>> myGCD 221 559
13

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

>>> coprime 35 64
True
>>> coprime 1173 1547
False

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

>>> totient 10
4

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

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

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

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

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

>>> totient' 10
4

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

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

Hint

Expand

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

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

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

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

Construct the list of all prime numbers.

Examples

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

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

>>> goldbach 12
(5,7)

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

>>> goldbachList 9 20
[(3,7),(5,7),(3,11),(3,13),(5,13),(3,17)]
>>> filter (\(m,n) -> m > 100 && n > 100) $ goldbachList 2 3000
[(103,2539)]

Problem 42

🤷 🤷 Modular multiplicative inverse

multiplicativeInverse :: Integral a => a -> a -> Maybe a Source #

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

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

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

Examples

>>> multiplicativeInverse 3 5
Just 2
>>> multiplicativeInverse 48 127
Just 45
>>> multiplicativeInverse 824 93
Just 50
>>> multiplicativeInverse 48 93
Nothing

Problem 43

🤷 Gaussian integer divisibility

gaussianDividesBy Source #

Arguments

:: Complex Integer

\(x\)

-> Complex Integer

\(y\)

-> Bool

\(y \mid x\), i.e., whether \(x\) is divisible by \(y\)

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

Determine whether a Gaussian integer is divisible by another.

Examples

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

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

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

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

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

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

Hint

Expand

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

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

>>> isGaussianPrime (0 :+ 5)
False

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

>>> isGaussianPrime (17 :+ 0)
False

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

>>> isGaussianPrime (5 :+ 2)
True

Hint

Expand

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

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

>>> isGaussianPrime' (0 :+ 5)
False
>>> isGaussianPrime' (17 :+ 0)
False
>>> isGaussianPrime' (5 :+ 2)
True

Logic and code problems

Problem 46

🤷 Truth tables for logical expressions

type BoolFunc = Bool -> Bool -> Bool Source #

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

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

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

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

Notes

Expand

There is no technical reason to define the type synonym BoolFunc. However, it is a good place to explain the entire problem without talking about writing truth table functions first, especially for inclusion in the documentation for Problems.

The original problem for Haskell required that the truth table be printed: "Now, write a predicate table/3 which prints the truth table of a given logical expression in two variables." It was changed here to return a list of boolean tuples, because the requirement for I/O seemed uninteresting in the context of the rest of the problem.

Documentation for the expected semantics for each boolean function was added, and the example for table was modified to avoid sensitivity to order.

table :: BoolFunc -> [(Bool, Bool, Bool)] Source #

Truth tables for logical expressions with two operands.

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

Examples

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

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 ith and jth gates in the list, respectively, with the first element starting at index 1.

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

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

Examples

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

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

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

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

Examples

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

Hint

Expand

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

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

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

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

Problem 49

🤷 🤷 Gray codes

gray :: Int -> [String] Source #

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

>>> gray 1  -- 1-bit gray code
["0","1"]
>>> gray 2  -- 2-bit gray code
["00","01","11","10"]
>>> gray 3  -- 3-bit gray code
["000","001","011","010","110","111","101","100"]

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

Problem 50

🤷 🤷 🤷 Huffman codes

huffman :: [(Char, Int)] -> [(Char, String)] Source #

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

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

Examples

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

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

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

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

>>> length $ encodeHuffman loweralpha text
4375

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

>>> length $ encodeHuffman ascii text
7000

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

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

Problem 51

🤷 Error correction codes

corrupt :: RandomGen g => g -> Int -> [Bool] -> [Bool] Source #

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

Examples

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

errorCorrectingEncode :: [Bool] -> [Bool] Source #

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

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

errorCorrectingDecode :: [Bool] -> [Bool] Source #

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

Examples

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

Problem 52

🤷 🤷 🤷 Conjunctive normal form

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

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

Hint

Expand

Transform a boolean formula using De Morgan's law, the distributive law, and double negation elimination to reduce nesting. Alternatively, the conjunctive normal form can be obtained easily from the truth table, although this will always require a running time exponential to the number of variables.

data Formula Source #

Represents a boolean formula.

Constructors

Value Bool

A constant value.

Variable String

A variable with given name.

Complement Formula

Logical complement. I.e., it is true only if its clause is false.

Disjoin [Formula]

Disjunction. I.e., it is true if any of its clauses are true.

Conjoin [Formula]

Conjunction. I.e., it is true only if all of its clauses are true.

Instances

Instances details
Generic Formula Source # 
Instance details

Defined in Problems.Logic

Associated Types

type Rep Formula :: Type -> Type #

Methods

from :: Formula -> Rep Formula x #

to :: Rep Formula x -> Formula #

Show Formula Source # 
Instance details

Defined in Problems.Logic

NFData Formula Source # 
Instance details

Defined in Problems.Logic

Methods

rnf :: Formula -> () #

Eq Formula Source # 
Instance details

Defined in Problems.Logic

Methods

(==) :: Formula -> Formula -> Bool #

(/=) :: Formula -> Formula -> Bool #

Ord Formula Source # 
Instance details

Defined in Problems.Logic

type Rep Formula Source # 
Instance details

Defined in Problems.Logic

Problem 53

🤷 🤷 🤷 Resolution rule

isTheorem :: [Formula] -> Formula -> Bool Source #

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

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

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

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

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

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

    • Do not apply the resolution rule to the values of true and false. If \(Y\) contains raw true or false values, transform \(Y\) into a form which contains none.
  2. Convert \(Y\) into conjunctive normal form; see Problems.P52.
  3. If there are two clauses for which the resolution rule can be applied, add the new clause to \(Y\) and repeat until an empty clause is inferred or if no new clauses can be added. Filter out tautologies, i.e., clauses which will always be true because it contains both a variable and its logical complement.

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

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

Examples

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

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

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

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

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

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

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

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

Binary tree problems

Problem 54

🤷 Binary trees

data Tree a Source #

A binary tree.

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

Notes

Expand

This is not the problem 54A from the original Ninety-Nine Haskell Problems. As it also mentions, there is nothing to do here except making sure code compiles correctly, thanks to Haskell's strict typing and the way Tree is defined.

Instead, the problem was replaced by the simple problems of implementing given binary trees as Haskell values. I.e., turn the examples from the original problem into simple problems to solve.

Constructors

Empty 
Branch a (Tree a) (Tree a) 

Instances

Instances details
Generic (Tree a) Source # 
Instance details

Defined in Problems.BinaryTrees

Associated Types

type Rep (Tree a) :: Type -> Type #

Methods

from :: Tree a -> Rep (Tree a) x #

to :: Rep (Tree a) x -> Tree a #

Show a => Show (Tree a) Source # 
Instance details

Defined in Problems.BinaryTrees

Methods

showsPrec :: Int -> Tree a -> ShowS #

show :: Tree a -> String #

showList :: [Tree a] -> ShowS #

NFData a => NFData (Tree a) Source # 
Instance details

Defined in Problems.BinaryTrees

Methods

rnf :: Tree a -> () #

Eq a => Eq (Tree a) Source # 
Instance details

Defined in Problems.BinaryTrees

Methods

(==) :: Tree a -> Tree a -> Bool #

(/=) :: Tree a -> Tree a -> Bool #

Ord a => Ord (Tree a) Source #

An arbitrary total ordering for Tree.

Defines an order for a set of Trees. Not intended to support solving problems.

Instance details

Defined in Problems.BinaryTrees

Methods

compare :: Tree a -> Tree a -> Ordering #

(<) :: Tree a -> Tree a -> Bool #

(<=) :: Tree a -> Tree a -> Bool #

(>) :: Tree a -> Tree a -> Bool #

(>=) :: Tree a -> Tree a -> Bool #

max :: Tree a -> Tree a -> Tree a #

min :: Tree a -> Tree a -> Tree a #

type Rep (Tree a) Source # 
Instance details

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

leaf :: a -> Tree a Source #

Define a shorthand function for constructing a leaf node.

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

tree1 :: Tree Char Source #

Define as the tree as shown in the following.

tree2 :: Tree Char Source #

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

tree3 :: Tree Char Source #

Define as an empty binary tree.

tree4 :: Tree Int Source #

Define as the following tree with integer values.

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

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

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

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

Hint

Expand

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

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

>>> construct [3, 2, 5, 7, 1]
Branch 3 (Branch 2 (Branch 1 Empty Empty) Empty) (Branch 5 Empty (Branch 7 Empty Empty))
>>> symmetric . construct $ [5, 3, 18, 1, 4, 12, 21]
True
>>> symmetric . construct $ [3, 2, 5, 7, 1]
True

Notes

Expand

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

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

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

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

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

Examples

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

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

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

Problem 59

🤷 🤷 Construct height-balanced binary trees

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

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

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

Examples

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

Problem 60

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

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

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

Examples

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

Hint

Expand

Consider a height-balanced binary tree of height \(h\). What is the maximum number of nodes it can contain? Clearly, it is \(2^h-1\).

However, what is the minimum number of nodes it can contain? This question is more difficult. Try to find a recursive statement and turn it into a function that returns the minimum number of nodes in a height-balanced binary tree of height \(h\).

On the other hand, what is the maximum height \(h\) a height-balanced binary tree with \(n\) nodes can have? What about the minimum height? Try writing functions to compute these.

Notes

Expand

The original problem asked to implement functions computing the minimum number of nodes for a given height and the maximum height for a given number of nodes. These are more of a hint as to how to implement the main function in question, so they were made hints instead of being part of the problem itself.

Problem 61

🤷 Collect nodes of a binary tree

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

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

Examples

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

Notes

Expand

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

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

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

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

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

Examples

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

Problem 62

🤷 Collect nodes at a given level

atLevel :: Tree a -> Int -> [a] Source #

Collect the nodes at a given level in a list

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

Examples

>>> atLevel tree4 2
[2,2]

Notes

Expand

In the original list, this was problem 62B, and internals was problem 62, but the latter was grouped with problem 61 because the grouping was more natural.

Problem 63

🤷 🤷 Construct a complete binary tree

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 Emptys, which are not really nodes of the tree) come last.

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

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

Examples

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

Hint

Expand

We can assign an address number to each node in a complete binary tree by enumerating the nodes in level-order, starting at the root with number 1. For every node \(x\) with address \(a\), the following property holds: The address of \(x\)'s left and right successors are \(2^a\) and \(2^a + 1\), respectively, if they exist. This fact can be used to elegantly construct a complete binary tree structure.

isCompleteBinaryTree :: Tree a -> Bool Source #

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

Examples

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

Problem 64

🤷 🤷 Binary tree layout; in-order

layoutInorder :: Tree a -> Tree (a, (Int, Int)) Source #

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

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

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

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

Examples

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

Notes

Expand

In fact, the image was rendered to SVG using the return value of layoutInorder with writeSVG. The images for Problems.P65 and Problems.P66 were also rendered similarly.

Problem 65

🤷 🤷 Binary tree layout; constant distance at each level

layoutLevelConstant :: Tree a -> Tree (a, (Int, Int)) Source #

An alternative layout method is depicted in the illustration below:

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

Examples

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

Hint

Expand

On a given level, the horizontal distance between neighboring nodes is constant.

Problem 66

🤷 🤷 🤷 Binary tree layout; compact

layoutCompact :: Tree a -> Tree (a, (Int, Int)) Source #

Yet another layout strategy is shown in the illustration below:

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

Examples

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

Hint

Expand

Consider the horizontal distance between a node and its successor nodes. How tight can you pack together two subtrees to construct the combined binary tree?

Problem 67

🤷 🤷 A string representation of binary trees

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

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

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

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

Examples

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

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

>>> inorder tree1
"dbeacgf"

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

Return the pre-order sequence of a binary tree.

Examples

>>> preorder tree1
"abdecfg"

ordersToTree Source #

Arguments

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

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

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

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

treeToDotstring :: Tree Char -> String Source #

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

Examples

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

Multiway tree problems

data MultiwayTree a Source #

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

Constructors

MultiwayTree a [MultiwayTree a] 

Instances

Instances details
Generic (MultiwayTree a) Source # 
Instance details

Defined in Problems.MultiwayTrees

Associated Types

type Rep (MultiwayTree a) :: Type -> Type #

Methods

from :: MultiwayTree a -> Rep (MultiwayTree a) x #

to :: Rep (MultiwayTree a) x -> MultiwayTree a #

Show a => Show (MultiwayTree a) Source # 
Instance details

Defined in Problems.MultiwayTrees

NFData a => NFData (MultiwayTree a) Source # 
Instance details

Defined in Problems.MultiwayTrees

Methods

rnf :: MultiwayTree a -> () #

Eq a => Eq (MultiwayTree a) Source # 
Instance details

Defined in Problems.MultiwayTrees

type Rep (MultiwayTree a) Source # 
Instance details

Defined in Problems.MultiwayTrees

type Rep (MultiwayTree a) = D1 ('MetaData "MultiwayTree" "Problems.MultiwayTrees" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'False) (C1 ('MetaCons "MultiwayTree" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [MultiwayTree a])))

multitree1 :: MultiwayTree Char Source #

Example of the following multiway tree.

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

multitree2 :: MultiwayTree Char Source #

Example of the following multiway tree.

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

multitree3 :: MultiwayTree Char Source #

Example of the following multiway tree.

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

multitree4 :: MultiwayTree Char Source #

Example of the following multiway tree.

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

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

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

multitreeToString :: MultiwayTree Char -> String Source #

Construct the node string from a MultiwayTree.

Examples

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

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

>>> internalPathLength multitree5
9
>>> internalPathLength multitree4
2

Problem 72

🤷 Post-order sequence of a tree

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

Construct the post-order sequence of the tree nodes.

Examples

>>> postOrderSequence multitree5
"gfcdeba"

Notes

Expand

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

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

>>> treeToSexp multitree1
"a"
>>> treeToSexp multitree2
"(a b)"
>>> treeToSexp multitree3
"(a (b c))"
>>> treeToSexp multitree4
"(b d e)"
>>> treeToSexp multitree5
"(a (f g) c (b d e))"

Notes

Expand

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

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

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

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

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

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

Hint

Expand

In do notation,

do
  a
  b

is a shorthand for

(>>) a b

or equivalently,

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

Also,

do
  x <- a
  b

is a shorthand for

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

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

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

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

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

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

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

But one should be careful to remember that it is not a return statement as such.

Problem 75

🤷 Maybe monad

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

>>> maybeGoldbach "104"
Just (104,(3,101))
>>> maybeGoldbach "not a number"
Nothing
>>> maybeGoldbach "1"
Nothing
>>> maybeGoldbach "101"
Nothing

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

>>> eitherGoldbach "104"
Right (104,(3,101))
>>> eitherGoldbach "this is not a number"
Left "not a number"
>>> eitherGoldbach "2"
Left "not greater than 2"
>>> eitherGoldbach "101"
Left "not an even number"

Problem 77

🤷 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

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

Hint

Expand

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

>>> collatz 1
0
>>> collatz 2
1
>>> collatz 31
106

Hint

Expand

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

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:

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

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

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

Negation applies to a single number:

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

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

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

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

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

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

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

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

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

Hint

Expand

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

data Element Source #

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

Instances

Instances details
Show Element Source # 
Instance details

Defined in Problems.Monads

Eq Element Source # 
Instance details

Defined in Problems.Monads

Methods

(==) :: Element -> Element -> Bool #

(/=) :: Element -> Element -> Bool #

data Operator Source #

Encodes an operator for a mathematical expression.

Constructors

Negate

Encodes negation. Equivalent to an unary minus. Unary operator.

Add

Encodes duplication. Makes another copy of its operand. Unary operator.

Subtract

Encodes subtraction. Binary operator.

Multiply

Encodes multiplication. Binary operator.

Divide

Encodes division. Equivalent to div. Binary operator.

Modulo

Encodes a modulo operator. Equivalent to mod. Binary operator.

Instances

Instances details
Bounded Operator Source # 
Instance details

Defined in Problems.Monads

Enum Operator Source # 
Instance details

Defined in Problems.Monads

Show Operator Source # 
Instance details

Defined in Problems.Monads

Eq Operator Source # 
Instance details

Defined in Problems.Monads

Graph problems

class Graph g where Source #

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

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

Notes

Expand

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

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

Minimal complete definition

vertexes, edges, toGraph, isValidGraph

Methods

vertexes :: g -> Set Vertex Source #

The set of vertexes.

edges :: g -> Set Edge Source #

The set of edges.

Instances

Instances details
Graph Adjacency Source # 
Instance details

Defined in Problems.Graphs

Graph G Source # 
Instance details

Defined in Problems.Graphs

Graph Lists Source # 
Instance details

Defined in Problems.Graphs

Graph Paths Source # 
Instance details

Defined in Problems.Graphs

type Vertex = Int Source #

A vertex in a graph.

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

newtype Edge Source #

An edge in a graph.

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

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

Constructors

Edge (Vertex, Vertex) 

Instances

Instances details
Show Edge Source # 
Instance details

Defined in Problems.Graphs

Methods

showsPrec :: Int -> Edge -> ShowS #

show :: Edge -> String #

showList :: [Edge] -> ShowS #

Eq Edge Source # 
Instance details

Defined in Problems.Graphs

Methods

(==) :: Edge -> Edge -> Bool #

(/=) :: Edge -> Edge -> Bool #

Ord Edge Source # 
Instance details

Defined in Problems.Graphs

Methods

compare :: Edge -> Edge -> Ordering #

(<) :: Edge -> Edge -> Bool #

(<=) :: Edge -> Edge -> Bool #

(>) :: Edge -> Edge -> Bool #

(>=) :: Edge -> Edge -> Bool #

max :: Edge -> Edge -> Edge #

min :: Edge -> Edge -> Edge #

Graph representations

data Var a Source #

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

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

We will not be using this representation of graphs further.

Tying the knot

Expand

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

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

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

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

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

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

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

Instances

Instances details
Show a => Show (Var a) Source # 
Instance details

Defined in Problems.Graphs

Methods

showsPrec :: Int -> Var a -> ShowS #

show :: Var a -> String #

showList :: [Var a] -> ShowS #

Eq a => Eq (Var a) Source # 
Instance details

Defined in Problems.Graphs

Methods

(==) :: Var a -> Var a -> Bool #

(/=) :: Var a -> Var a -> Bool #

newtype Lists Source #

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

For example, the example graph can be represented as:

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

Constructors

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

Instances

Instances details
Generic Lists Source # 
Instance details

Defined in Problems.Graphs

Associated Types

type Rep Lists :: Type -> Type #

Methods

from :: Lists -> Rep Lists x #

to :: Rep Lists x -> Lists #

Show Lists Source # 
Instance details

Defined in Problems.Graphs

Methods

showsPrec :: Int -> Lists -> ShowS #

show :: Lists -> String #

showList :: [Lists] -> ShowS #

NFData Lists Source # 
Instance details

Defined in Problems.Graphs

Methods

rnf :: Lists -> () #

Eq Lists Source # 
Instance details

Defined in Problems.Graphs

Methods

(==) :: Lists -> Lists -> Bool #

(/=) :: Lists -> Lists -> Bool #

Graph Lists Source # 
Instance details

Defined in Problems.Graphs

ConvertibleGraph Lists Source # 
Instance details

Defined in Problems.P80

ConvertibleGraph Lists Source # 
Instance details

Defined in Solutions.P80

type Rep Lists Source # 
Instance details

Defined in Problems.Graphs

type Rep Lists = D1 ('MetaData "Lists" "Problems.Graphs" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'True) (C1 ('MetaCons "Lists" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 ([Vertex], [(Vertex, Vertex)]))))

newtype Adjacency Source #

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

For example, the example graph can be represented as:

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

Constructors

Adjacency [(Vertex, [Vertex])] 

Instances

Instances details
Generic Adjacency Source # 
Instance details

Defined in Problems.Graphs

Associated Types

type Rep Adjacency :: Type -> Type #

Show Adjacency Source # 
Instance details

Defined in Problems.Graphs

NFData Adjacency Source # 
Instance details

Defined in Problems.Graphs

Methods

rnf :: Adjacency -> () #

Eq Adjacency Source # 
Instance details

Defined in Problems.Graphs

Graph Adjacency Source # 
Instance details

Defined in Problems.Graphs

ConvertibleGraph Adjacency Source # 
Instance details

Defined in Problems.P80

ConvertibleGraph Adjacency Source # 
Instance details

Defined in Solutions.P80

type Rep Adjacency Source # 
Instance details

Defined in Problems.Graphs

type Rep Adjacency = D1 ('MetaData "Adjacency" "Problems.Graphs" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'True) (C1 ('MetaCons "Adjacency" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [(Vertex, [Vertex])])))

newtype Paths Source #

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

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

For example, the example graph can be represented as:

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

DOT graphs

Expand

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

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

Constructors

Paths [[Vertex]] 

Instances

Instances details
Generic Paths Source # 
Instance details

Defined in Problems.Graphs

Associated Types

type Rep Paths :: Type -> Type #

Methods

from :: Paths -> Rep Paths x #

to :: Rep Paths x -> Paths #

Show Paths Source # 
Instance details

Defined in Problems.Graphs

Methods

showsPrec :: Int -> Paths -> ShowS #

show :: Paths -> String #

showList :: [Paths] -> ShowS #

NFData Paths Source # 
Instance details

Defined in Problems.Graphs

Methods

rnf :: Paths -> () #

Eq Paths Source # 
Instance details

Defined in Problems.Graphs

Methods

(==) :: Paths -> Paths -> Bool #

(/=) :: Paths -> Paths -> Bool #

Graph Paths Source # 
Instance details

Defined in Problems.Graphs

ConvertibleGraph Paths Source # 
Instance details

Defined in Problems.P80

ConvertibleGraph Paths Source # 
Instance details

Defined in Solutions.P80

type Rep Paths Source # 
Instance details

Defined in Problems.Graphs

type Rep Paths = D1 ('MetaData "Paths" "Problems.Graphs" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'True) (C1 ('MetaCons "Paths" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 [[Vertex]])))

newtype G Source #

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

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

For example, the example graph can be represented as:

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

Constructors

G (Map Vertex (Set Vertex)) 

Instances

Instances details
Generic G Source # 
Instance details

Defined in Problems.Graphs

Associated Types

type Rep G :: Type -> Type #

Methods

from :: G -> Rep G x #

to :: Rep G x -> G #

Show G Source # 
Instance details

Defined in Problems.Graphs

Methods

showsPrec :: Int -> G -> ShowS #

show :: G -> String #

showList :: [G] -> ShowS #

NFData G Source # 
Instance details

Defined in Problems.Graphs

Methods

rnf :: G -> () #

Eq G Source # 
Instance details

Defined in Problems.Graphs

Methods

(==) :: G -> G -> Bool #

(/=) :: G -> G -> Bool #

Graph G Source # 
Instance details

Defined in Problems.Graphs

ConvertibleGraph G Source # 
Instance details

Defined in Problems.P80

ConvertibleGraph G Source # 
Instance details

Defined in Solutions.P80

type Rep G Source # 
Instance details

Defined in Problems.Graphs

type Rep G = D1 ('MetaData "G" "Problems.Graphs" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'True) (C1 ('MetaCons "G" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Map Vertex (Set Vertex)))))

Useful graph functions

These may be useful when implementing functions on graphs.

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

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

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

Whether the given vertexes are adjacent in the graph.

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.

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

Convert graph to the Lists representation.

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

Convert graph to the Adjacency representation.

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

Convert graph to the Paths representation.

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

Convert graph to the G representation.

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

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

Problem 82

🤷 🤷 Cycles with a given vertex

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

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

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

Examples

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

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

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

isTree :: G -> Bool Source #

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

Examples

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

isConnected :: G -> Bool Source #

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

Examples

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

Problem 84

🤷 🤷 Construct minimum spanning tree

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
>>> Set.foldr (\e w -> w + weights84 ! e) 0 $ edges t
33

Hint

Expand

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

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

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

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

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

Visualization with real colors

Expand

Hint

Expand

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

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
>>> xs `elem` [[1,2,3,4,5], [1,2,4,5,3], [1,2,4,3,5]]
True

Problem 88

🤷 🤷 Connected components

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

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

Examples

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

Problem 89

🤷 🤷 Bipartite graphs

bipartite :: G -> Bool Source #

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

Examples

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

Miscellaenous problems

Problem 90

🤷 🤷 Find all solutions to the \(n\) queens problem

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

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

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

Examples

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

Problem 91

🤷 🤷 Knight's tour

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

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

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

Examples

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

Hint

Expand

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

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

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

Problem 92

🤷 🤷 🤷 Graceful tree labeling

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

>>> gracefulTree tree92
Just (fromList [(1,5),(2,2),(3,1),(4,7),(5,3),(6,6),(7,4)])
>>> gracefulTree tree92'
Just (fromList [(1,1),(2,10),(3,7),(4,3),(5,5),(6,6),(7,14),(8,13),(9,12),...

Notes

Expand

Problem 92 in the original list referred to this conjecture as "Von Koch's conjecture". However, I could not find any reference confirming that von Koch actually made this conjecture. From the style the problem was written in, it seems likely this was an imaginary scenario to make the problem feel more personal and fun, rather than something which actually happened.

It is too unbelievable for me to have met the mathematician in question, so this was rewritten to a more dry presentation.

Problem 93

🤷 🤷 🤷 An arithmetic puzzle

arithmeticPuzzle :: [Integer] -> [String] Source #

Given a list of positive integer numbers, find a correct way of inserting the arithmetic signs such that the result is a correct equation. For example, with the list of numbers [2,3,5,7,11], we can form the equations 2-3+5+7=11 or 2=(3*5+7)/11.

The arithmetic signs to insert are:

  • + : addition
  • - : subtraction
  • * : multiplication
  • / : division
  • = : equality
  • (, ) : parentheses

Arithmetic operations are only binary, e.g., -4 should not be included. Division should be interpreted as operating on rationals, e.g., \(3/5 = 6/10\) but \(3/5 \neq 0\), and division by zero should be avoided. Parentheses should be inserted only when the default precedence rules need to be overridden. Equality should be inserted exactly once.

Examples

>>> mapM_ putStrLn $ sort $ arithmeticPuzzle [2,3,5,7,11]
2 = (3*5+7)/11
2 = 3-(5+7)+11
2 = 3-(5+7-11)
2 = 3-5-(7-11)
2 = 3-5-7+11
2*(3-5) = 7-11
2-(3-(5+7)) = 11
2-(3-5)+7 = 11
2-(3-5-7) = 11
2-3+5+7 = 11

Problem 94

🤷 🤷 🤷 Regular graphs

regularGraphs Source #

Arguments

:: Int

\(n\)

-> Int

\(k\)

-> [G]

non-isomorphic \(k\)-regular graphs with \(n\) vertexes

Generate \(k\)-regular graphs with \(n\) vertexes.

In a \(k\)-regular graph, all vertexes have a degree of \(k\). I.e., the number of edges incident in each vertex is \(k\). How many non-isomorphic 3-regular graphs with 6 vertexes are there? See Problems.P94.Examples for examples of \(k\)-regular graphs.

Examples

>>> length $ regularGraphs 6 3
2

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

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

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

>>> isIdentifier "this_is_a_long_identifier"
True
>>> isIdentifier "This_ends_in_an_underscore_"
False
>>> isIdentifier "This__has__two__consecutive__underscores"
False
>>> isIdentifier "1234"
False
>>> isIdentifier "_legal_in_many_other_languages"
False
>>> isIdentifier "Fibonacci_sequence_is_1_1_2_3_5_8_13_21_ad_infinitum"
True

Hint

Expand

Translate the syntax diagram into a recursive grammar.

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

>>> printSudoku $ sudoku sudokuPuzzle
9 3 4 8 2 5 6 1 7
6 7 2 9 1 4 8 5 3
5 1 8 6 3 7 9 2 4
3 2 5 7 4 8 1 6 9
4 6 9 1 5 3 7 8 2
7 8 1 2 6 9 4 3 5
1 9 7 5 8 2 3 4 6
8 5 3 4 7 6 2 9 1
2 4 6 3 9 1 5 7 8

Problem 98

🤷 🤷 🤷 Nonograms

nonogram Source #

Arguments

:: [[Int]]

Lengths of occupied cells in each row

-> [[Int]]

Lengths of occupied cells in each column

-> Maybe [[Bool]]

Solution to the puzzle, if it exists

Nonograms are picture logic puzzles invented in 1987, spreading from Japan to across the world. They look like this:

 □ □ □ □ □ □ □ □  3
 □ □ □ □ □ □ □ □  2 1
 □ □ □ □ □ □ □ □  3 2
 □ □ □ □ □ □ □ □  2 2
 □ □ □ □ □ □ □ □  6
 □ □ □ □ □ □ □ □  1 5
 □ □ □ □ □ □ □ □  6
 □ □ □ □ □ □ □ □  1
 □ □ □ □ □ □ □ □  2

 1 3 1 7 5 3 4 3

 2 1 5 1

Essentially, each row and column of a rectangular bitmap is annotated with the respective lengths of its distinct strings of occupied cells. The person who solves the puzzle must complete the bitmap given only these lengths. Published puzzles are larger than this example, e.g., \(25 \times 20\), and apparently always have unique solutions.

Try to solve the \(25 \times 25\) puzzle in nonogramPuzzle.

Examples

>>> :{
printNonogramSolution $
nonogram [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]]
         [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]]
:}
   ■ ■ ■          3
 ■ ■   ■          2 1
   ■ ■ ■     ■ ■  3 2
     ■ ■     ■ ■  2 2
     ■ ■ ■ ■ ■ ■  6
 ■   ■ ■ ■ ■ ■    1 5
 ■ ■ ■ ■ ■ ■      6
         ■        1
       ■ ■        2

 1 3 1 7 5 3 4 3

 2 1 5 1

Hint

Expand

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

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
>>> head $ fromJust $ solveCrossword crosswordPuzzle
[Nothing,Nothing,Just 'P',Nothing,Nothing]
>>> printCrossword $ solveCrossword crosswordPuzzle
■ ■ P ■ ■
■ ■ O ■ ■
A L P H A
■ ■ P ■ R
■ ■ Y ■ E
■ ■ ■ ■ S

data Crossword Source #

A crossword puzzle.

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

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

Constructors

Crossword 

Fields

Instances

Instances details
Show Crossword Source # 
Instance details

Defined in Problems.Crosswords

Eq Crossword Source # 
Instance details

Defined in Problems.Crosswords