Solutions

Description

These are some solutions for Ninety-Nine Haskell Problems. A problem may have more than one solution included.

Synopsis

# List problems

## Problem 1

myLast :: [a] -> a Source #

Find the last element of a list.

## Problem 2

myButLast :: [a] -> a Source #

Find the last but one element of a list.

## Problem 3

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

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

## Problem 4

myLength :: [a] -> Int Source #

Find the number of elements of a list.

Add 1 for each element by induction.

myLength' :: [a] -> Int Source #

Find the number of elements of a list.

Cheat by using length.

myLength'' :: [a] -> Int Source #

Find the number of elements of a list.

Map elements to 1 and return their sum.

myLength''' :: [a] -> Int Source #

Find the number of elements of a list.

Add 1 for each element by induction, but tail recursively.

## Problem 5

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

Reverse a list.

## Problem 6

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

## Problem 7

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.

Recursively flatten lists and concatenate them together.

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.

Build the list starting from the last one, prepending each element one at a time.

## Problem 8

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.

## Problem 9

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.

Extract consecutive duplicates from the list, and repeat.

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.

Cheat by using group.

## Problem 10

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.

## Problem 11

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.

## Problem 12

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

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

Duplicates each element as appropriate and concatenates them together.

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

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

Prepend each element as many times as required, starting from the last element prepended to an empty list, and all the way to the first element.

## Problem 13

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

## Problem 14

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

Duplicate the elements of a list.

## Problem 15

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

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

## Problem 16

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

Drop every nth element from a list.

## Problem 17

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

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

## Problem 18

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.

Go through individual elements in the list, dropping them and then keeping some of the rest.

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.

drop and then take.

## Problem 19

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

Rotate a list n places to the left.

## Problem 20

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

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

## Problem 21

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

Insert an element at a given position into a list.

## Problem 22

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

Create a list containing all integers within a given range.

## Problem 23

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.

## Problem 24

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

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

## Problem 25

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

Generate a random permutation of the elements of a list.

## Problem 26

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

Generate the combinations of $$k$$ distinct objects chosen from the $$n$$ elements of a list.

## Problem 27

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

Given a list with the sizes of each group and list of items, write a function to return the list of disjoint groups.

## Problem 28

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.

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.

# Arithmetic problems

## Problem 29

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

Write a function to compute the $$n$$th Fibonacci number.

## Problem 30

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

Computes the $$n$$th Fibonacci number with $$O(\log n)$$ multiplications. Takes advantage of matrix multiplication and exponentiation.

## Problem 31

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

Determine whether a given integer number is prime.

Checks whether the integer is even or if there is a divisor among odd integers not greater than its square root.

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

Determine whether a given integer number is prime.

Uses an Erastothenes sieve to construct a list of primes up to at least the square root of the integer, and searches for a divisor among them.

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

Determine whether a given integer number is prime.

From a list of all prime numbers, search for a divisor.

## Problem 32

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

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

## Problem 33

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.

## Problem 34

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

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

Accumulates count of numbers that are coprime.

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

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

Filters through numbers that are coprime and count them.

## Problem 35

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.

## Problem 36

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.

## Problem 37

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

Calculate Euler's totient function $$\phi(m)$$ using Euler's product formula.

## Problem 38

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

Construct the list of highly totient numbers.

## Problem 39

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.

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

Construct the list of all prime numbers.

## Problem 40

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

Find two prime numbers that sum up to a given even integer.

## Problem 41

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.

## Problem 42

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

Compute the multiplicative inverse $$x$$ of a given integer $$a$$ and modulus $$n$$ lying in the range $$0 \leq x < n$$.

Uses the extended Euclidean algorithm and the fact that $$ax \equiv 1 \pmod{n}$$ if $$ax+ny=1$$.

## Problem 43

Arguments

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

Determine whether a Gaussian integer is divisible by another.

## Problem 44

Determine whether a Gaussian integer is a Gaussian prime.

## Problem 45

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.

# Logic and code problems

## Problem 46

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

Truth tables for logical expressions with two operands.

## Problem 47

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

Evaluates a logic circuit.

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

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

## Problem 48

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

Generalizes table in a way that the logical expression may contain any number of logical variables.

## Problem 49

gray :: Int -> [String] Source #

Returns the n-bit Gray code.

## Problem 50

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

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

The characters '0' and '1' will represent the 0 and 1 bits in the encoding.

## Problem 51

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

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

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

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

Uses a reptition code of length 3.

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

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

## Problem 52

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

## Problem 53

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

Determines whether the formula is valid given the axioms.

# Binary tree problems

## Problem 54

data Tree a Source #

A binary tree.

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

### Notes

Expand

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

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

Constructors

 Empty Branch a (Tree a) (Tree a)

#### Instances

Instances details
 Generic (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Associated Typestype Rep (Tree a) :: Type -> Type # Methodsfrom :: Tree a -> Rep (Tree a) x #to :: Rep (Tree a) x -> Tree a # Show a => Show (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees MethodsshowsPrec :: Int -> Tree a -> ShowS #show :: Tree a -> String #showList :: [Tree a] -> ShowS # NFData a => NFData (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Methodsrnf :: Tree a -> () # Eq a => Eq (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees Methods(==) :: Tree a -> Tree a -> Bool #(/=) :: Tree a -> Tree a -> Bool # Ord a => Ord (Tree a) Source # An arbitrary total ordering for Tree.Defines an order for a set of Trees. Not intended to support solving problems. Instance detailsDefined in Problems.BinaryTrees Methodscompare :: Tree a -> Tree a -> Ordering #(<) :: Tree a -> Tree a -> Bool #(<=) :: Tree a -> Tree a -> Bool #(>) :: Tree a -> Tree a -> Bool #(>=) :: Tree a -> Tree a -> Bool #max :: Tree a -> Tree a -> Tree a #min :: Tree a -> Tree a -> Tree a # type Rep (Tree a) Source # Instance detailsDefined in Problems.BinaryTrees type Rep (Tree a) = D1 ('MetaData "Tree" "Problems.BinaryTrees" "ninetynine-1.1.0-KhbacJ3ihVC6IHhZVwmJyl" 'False) (C1 ('MetaCons "Empty" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Branch" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a)))))

leaf :: a -> Tree a Source #

Define a shorthand function for constructing a leaf node.

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

Define as the tree as shown in the following.

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

Define as an empty binary tree.

Define as the following tree with integer values.

## Problem 55

Constructs completely balanced binary trees for a given number of nodes.

## Problem 56

symmetric :: Tree a -> Bool Source #

Check whether a given binary tree is symmetric.

## Problem 57

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

Construct a binary search tree from a list of ordered elements.

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

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

## Problem 58

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

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

## Problem 59

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

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

## Problem 60

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

## Problem 61

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

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

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

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

## Problem 62

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

Collect the nodes at a given level in a list

## Problem 63

Construct a complete binary tree with the given number of nodes.

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

## Problem 64

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

Lay out a binary tree using in-order positions.

## Problem 65

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

Lay out a binary tree with constance distance at each level.

## Problem 66

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

Lay out a binary tree compactly.

## Problem 67

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.

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

## Problem 68

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

Return the in-order sequence of a binary tree.

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

Return the pre-order sequence of a binary tree.

Arguments

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

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

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

## Problem 69

Convert a dotstring representation into its corresponding binary tree.

Convert a binary tree to its dotstring representation.

# Multiway tree problems

## Problem 70

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.

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

Construct the node string from a MultiwayTree.

## Problem 71

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.

## Problem 72

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

Construct the post-order sequence of the tree nodes.

## Problem 73

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.

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

## Problem 74

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

Implementation of askGoldbach' without do notation.

## Problem 75

Implementation of maybeGoldbach' with do notation.

## Problem 76

Rewrite of maybeGoldbach to return an Either value.

## Problem 77

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

Returns all the one-dimensional random walk paths with $$n$$ steps starting from position 0.

## Problem 78

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

## Problem 79

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

Use monad transformers to evaluate postfix notation.

Returns Nothing when there is an error. Also returns the history of the evaluation.

# Graph problems

## Problem 80

class Graph g => ConvertibleGraph g Source #

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

#### Instances

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

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

Convert graph to the Lists representation.

Convert graph to the Adjacency representation.

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

Convert graph to the Paths representation.

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

Convert graph to the G representation.

## Problem 81

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.

## Problem 82

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

Finds all cycles in the graph which include the given vertex.

## Problem 83

spanningTrees :: G -> [G] Source #

Construct all spanning trees of a given graph.

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

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

## Problem 84

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.

## Problem 85

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

Determine whether two graphs are isomorphic.

Builds up a bijection from a starting vertex to its neighbors, expanding until it encounters an inconsistency or until there are no more vertexes to expand to.

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

Determine whether two graphs are isomorphic.

This tests all bijections of vertexes from one graph to another to see if any are identical.

Determine whether two graphs are isomorphic.

Tests bijections which are limited to matching vertexes with the same degree, and looks for any which results in one graph becoming identical to the other.

## Problem 86

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

Color a graph using Welch-Powell's algorithm. Uses distinct integers to represent distinct colors, and returns the association list between vertexes and their colors.

## Problem 87

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.

## Problem 88

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

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

## Problem 89

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

# Miscellaenous problems

## Problem 90

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

Solve the extended eight queens problem for arbitrary $$n$$.

Represent the positions of the queens as a list of numbers from 1 to $$n$$.

## Problem 91

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

Returns a knight's tour ending at a particular square. Represents 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$$.

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. Starts the tour from $$(1,1)$$.

## Problem 92

Gracefully label a tree graph.

This implementation builds up a partial graceful labeling, adding one vertex at a time. It gives up and tries another if a partial labeling cannot be extended.

Gracefully label a tree graph.

This implementation tries all permutations of vertex labels and checks if any are a graceful labeling.

## Problem 93

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

Given a list of integer numbers, find a correct way of inserting the arithmetic signs such that the result is a correct equation.

## Problem 94

Arguments

 :: Int $$n$$ -> Int $$k$$ -> [G] non-isomorphic $$k$$-regular graphs with $$n$$ vertexes

Generate $$k$$-regular graphs with $$n$$ vertexes.

## Problem 95

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

Return non-negative integers in full words.

## Problem 96

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.

## Problem 97

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

Returns a solution for a given 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.

## Problem 98

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

Solve a nonogram.

## Problem 99

Solve a crossword puzzle.