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

License | GPL-3.0-or-later |

Maintainer | dev@chungyc.org |

Safe Haskell | Safe-Inferred |

Language | GHC2021 |

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

## Synopsis

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

# List problems

## Problem 1

## Problem 2

## Problem 3

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

Find the `k`

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

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

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

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

by `Multiple`

1 x)`(`

.`Single`

x)

## Problem 14

## Problem 15

## Problem 16

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

## Problem 19

## Problem 20

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

Remove the `k`

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

## Problem 21

## Problem 22

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

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

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

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

isGaussianPrime :: Complex Integer -> Bool Source #

Determine whether a Gaussian integer is a Gaussian prime.

## Problem 45

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.

# Logic and code problems

## Problem 46

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

Truth tables for logical expressions with two operands.

## Problem 47

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

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

toConjunctiveNormalForm :: Formula -> Formula Source #

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

A binary tree.

A `Tree`

of type `a`

consists of either an `Empty`

node,
or a `Branch`

containing one value of type `a`

with exactly two subtrees of type `a`

.

### Notes

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

is defined.

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

#### Instances

Generic (Tree a) Source # | |

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

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

Defined in Problems.BinaryTrees | |

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

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

type Rep (Tree a) Source # | |

Defined in Problems.BinaryTrees type Rep (Tree a) = D1 ('MetaData "Tree" "Problems.BinaryTrees" "ninetynine-1.3.0-4Xxr3hBGtJH9Ff8qb2Invo" 'False) (C1 ('MetaCons "Empty" 'PrefixI 'False) (U1 :: Type -> Type) :+: C1 ('MetaCons "Branch" 'PrefixI 'False) (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 a) :*: (S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a)) :*: S1 ('MetaSel ('Nothing :: Maybe Symbol) 'NoSourceUnpackedness 'NoSourceStrictness 'DecidedLazy) (Rec0 (Tree a))))) |

Define a shorthand function for constructing a leaf node.

A leaf node in `Tree`

is a branch with two empty subtrees.

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

.

## Problem 55

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

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

## Problem 56

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

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

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.

## Problem 62

## Problem 63

completeBinaryTree :: Int -> Tree () Source #

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

isCompleteBinaryTree :: Tree a -> Bool Source #

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

## Problem 67

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.

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

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

## Problem 68

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

## Problem 69

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

Convert a dotstring representation into its corresponding binary tree.

treeToDotstring :: Tree Char -> String Source #

Convert a binary tree to its dotstring representation.

# Multiway tree problems

## Problem 70

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.

Write a function to construct the `MultiwayTree`

when the string is given.

multitreeToString :: MultiwayTree Char -> String Source #

Construct the node string from a `MultiwayTree`

.

## Problem 71

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.

## Problem 72

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

Construct the post-order sequence of the tree nodes.

## Problem 73

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.

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`

.

# Monad problems

## Problem 74

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

Implementation of `askGoldbach'`

without do notation.

## Problem 75

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

Implementation of `maybeGoldbach'`

with do notation.

## Problem 76

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

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 #

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

Convert graph to the `Adjacency`

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`

.

isConnected :: G -> Bool Source #

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

.

## Problem 84

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.

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

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

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

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

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

## Problem 92

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

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.

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

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

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

## Problem 95

## Problem 96

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.

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

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