Ninety-Nine Problems in Elixir

This list of problems is inspired by the original Ninety-Nine Prolog Problems post. Each entry is given a brief descriptor and, where applicable, a type spec you can use as a starting point. Solutions are left as an exercise, but you can follow along with mine here!

Working with lists

Find the last element of a list.
```
@spec last(list :: list()) :: any()
```

Find the last but one element of a list.

@spec penultimate(list :: list()) :: any()

Find the K’th element of a list (first element is number 1).

@spec element_at(list :: list(), k :: pos_integer()) :: any()

Find the number of elements of a list.

@spec length(list :: list()) :: non_neg_integer()

Reverse a list.

@spec reverse(list :: list()) :: list()

Find out whether a list is a palindrome.

@spec palindrome?(list :: list()) :: boolean()

Flatten a nested list structure.

@spec flatten(nested :: list()) :: list()

Eliminate consecutive duplicates of list elements.
```
@spec compress(list :: list()) :: list()
```
Pack consecutive duplicates of list elements into sublists.
```
@spec pack(list :: list()) :: list(list())
```

Run-length encoding of a list.

@spec encode(list :: list()) :: list({pos_integer(), any()})

Modified run-length encoding (singleton elements copied as-is).
```
@spec encode_modified(list :: list()) :: list()
```

Decode a run-length encoded list.

@spec decode(encoded :: list()) :: list()

Run-length encoding of a list (direct solution).

@spec encode_direct(list :: list()) :: list()

Duplicate the elements of a list.
```
@spec dupli(list :: list()) :: list()
```

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

@spec dupli(list :: list(), n :: pos_integer()) :: list()

Drop every N’th element from a list.

@spec drop(list :: list(), n :: pos_integer()) :: list()

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

@spec split(list :: list(), n :: non_neg_integer()) :: {list(), list()}

Extract a slice from a list (both indices inclusive, starting at 1).

@spec slice(list :: list(), i :: pos_integer(), k :: pos_integer()) :: list()

Rotate a list N places to the left (negative N rotates right).

@spec rotate(list :: list(), n :: integer()) :: list()

Remove the K’th element from a list.

@spec remove_at(list :: list(), k :: pos_integer()) :: {any(), list()}

Insert an element at a given position into a list.

@spec insert_at(list :: list(), x :: any(), k :: pos_integer()) :: list()

Create a list containing all integers within a given range.

@spec range(from :: integer(), to :: integer()) :: list(integer())

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

@spec rnd_select(list :: list(), n :: non_neg_integer()) :: list()

Lotto: draw N different random numbers from the set 1..M.

@spec lotto(n :: pos_integer(), m :: pos_integer()) :: list(pos_integer())

Generate a random permutation of the elements of a list.
```
@spec rnd_permu(list :: list()) :: list()
```
Generate the combinations of K distinct objects chosen from the N elements of a list.
```
@spec combination(list :: list(), k :: non_neg_integer()) :: list(list())
```

Group the elements of a set into disjoint subsets.

@spec group(list :: list(), sizes :: list(pos_integer())) :: list(list())

Sort a list of lists according to length of sublists.

# a) by sublist length
@spec lsort(list_of_lists :: list(list())) :: list(list())

# b) by length frequency
@spec lfsort(list_of_lists :: list(list())) :: list(list())

Arithmetic

Determine whether a given integer number is prime.

@spec prime?(n :: pos_integer()) :: boolean()

Determine the greatest common divisor of two positive integers (Euclid’s algorithm).
```
@spec gcd(a :: pos_integer(), b :: pos_integer()) :: pos_integer()
```

Determine whether two positive integer numbers are coprime.

@spec coprime?(a :: pos_integer(), b :: pos_integer()) :: boolean()

Calculate Euler’s totient function phi(m).

@spec totient_phi(m :: pos_integer()) :: non_neg_integer()

Determine the prime factors of a given positive integer.

@spec prime_factors(n :: pos_integer()) :: list(pos_integer())

Determine the prime factors of a given positive integer (with multiplicity).

@spec prime_factors_mult(n :: pos_integer()) :: list({pos_integer(), pos_integer()})

Calculate Euler’s totient function phi(m) (improved, using prime factors).
```
@spec phi(n :: pos_integer()) :: pos_integer()
```

Compare the two methods of calculating Euler’s totient function.

@spec compare_methods(n :: pos_integer()) :: {non_neg_integer(), non_neg_integer()}

A list of prime numbers in a given range.

@spec primes_in_range(from :: pos_integer(), to :: pos_integer()) :: list(pos_integer())

Goldbach’s conjecture: find two primes that sum to a given even integer.

@spec goldbach(n :: even_integer) :: {pos_integer(), pos_integer()}

A list of Goldbach compositions in a range of integers.

@spec goldbach_list(from :: pos_integer(), to :: pos_integer()) :: list({pos_integer(), {pos_integer(), pos_integer()}})

Logic and codes

Truth tables for logical expressions (two variables).

@spec table(a :: boolean(), b :: boolean(), expr :: (boolean(), boolean()) -> boolean()) :: list(map())

Truth tables for logical expressions using infix operators.
```
@spec table(expr :: any()) :: list(map())
```

Truth tables for logical expressions with any number of variables.

@spec table(vars :: list(atom()), expr :: any()) :: list(map())

Gray code: sequence of N-bit strings.

@spec gray(n :: pos_integer()) :: list(String.t())

Huffman code.

@spec huffman(frequencies :: list({any(), pos_integer()})) :: list({any(), String.t()})

Binary trees

A binary tree is represented as t(x, left, right) with nil for the empty tree.

@type tree() :: nil | {any(), tree(), tree()}

Check whether a term represents a binary tree.
```
@spec tree?(any()) :: boolean()
```
Construct completely balanced binary trees for a given number of nodes (generates all solutions).
```
@spec cbal_tree(pos_integer()) :: [tree()]
```
Check whether a binary tree is symmetric.
```
@spec symmetric?(tree()) :: boolean()
```
Construct a binary search tree from a list of integers.
```
@spec construct([integer()]) :: tree()
```
Generate all symmetric, completely balanced binary trees with a given number of nodes.
```
@spec sym_cbal_trees(pos_integer()) :: [tree()]
```
Construct height-balanced binary trees for a given height.
```
@spec hbal_tree(pos_integer()) :: [tree()]
```
Construct height-balanced binary trees with a given number of nodes.
```
@spec hbal_tree_nodes(pos_integer()) :: [tree()]
```

Count the leaves of a binary tree.

@spec count_leaves(tree()) :: non_neg_integer()

61a. Collect the leaves of a binary tree in a list.

```elixir
@spec leaves(tree()) :: [any()]
```

Collect the internal nodes of a binary tree in a list.
```
@spec internals(tree()) :: [any()]
```

62b. Collect the nodes at a given level in a list.

```elixir
@spec at_level(tree(), pos_integer()) :: [any()]
```

Construct a complete binary tree with N nodes.

@spec complete_binary_tree(pos_integer()) :: tree()

Layout a binary tree (1): positions determined by inorder and depth.
```
@spec layout(tree()) :: tree()
```
Layout a binary tree (2): constant horizontal distance between neighbors.
```
@spec layout(tree()) :: tree()
```
Layout a binary tree (3): compact layout with symmetry.
```
@spec layout(tree()) :: tree()
```

A string representation of binary trees (and back).

@spec tree_to_string(tree()) :: String.t()
@spec string_to_tree(String.t()) :: tree()

Preorder and inorder sequences of binary trees.

@spec preorder(tree()) :: [any()]
@spec inorder(tree()) :: [any()]
@spec pre_in_tree([any()], [any()]) :: tree()

Dotstring representation of binary trees.

@spec tree_to_dotstring(tree()) :: String.t()
@spec dotstring_to_tree(String.t()) :: tree()

Multiway trees

A multiway tree is represented as t(x, forest) where forest is a list of multiway trees.

@type multiway_tree() :: {any(), [multiway_tree()]}

Tree construction from a node string.

@spec string_to_mway(String.t()) :: multiway_tree()

Determine the internal path length of a multiway tree.
```
@spec ipl(multiway_tree()) :: non_neg_integer()
```
Construct the bottom-up order sequence of the tree nodes.
```
@spec bottom_up(multiway_tree()) :: [any()]
```

Lisp-like tree representation of a multiway tree.

@spec multiway_to_lisp(multiway_tree()) :: String.t()
@spec lisp_to_multiway(String.t()) :: multiway_tree()

Graphs

Convert between graph representations (edge-clause, graph-term, adjacency-list, human-friendly forms).
```
@spec conversion(graph :: any(), from :: atom(), to :: atom()) :: any()
```

Find an acyclic path from node A to node B in a graph.

@spec path(graph :: list(), a :: any(), b :: any()) :: list() | nil

Find a cycle (closed path) starting at node A.

@spec cycle(graph :: list(), a :: any()) :: list() | nil

Construct all spanning trees of a graph.

@spec spanning_trees(graph :: list()) :: list(list())

Construct the minimal spanning tree (Prim’s algorithm).
```
@spec mst(graph :: list()) :: list()
```

Graph isomorphism (bijection between two graphs).

@spec is_isomorphic?(g1 :: list(), g2 :: list()) :: boolean()

Node degree and graph coloration (Welch-Powell algorithm).

@spec color(graph :: list()) :: [{any(), non_neg_integer()}]

Depth-first order graph traversal.

@spec dfs(graph :: list(), start :: any()) :: list()

Split a graph into connected components.

@spec connected_components(graph :: list()) :: list(list())

Determine whether a graph is bipartite.

@spec bipartite?(graph :: list()) :: boolean()

Miscellaneous problems

Eight queens problem.

@spec queens(n :: pos_integer()) :: list(list())

Knight’s tour on an NxN chessboard.

@spec knights_tour(n :: pos_integer()) :: list({non_neg_integer(), non_neg_integer()}) | nil

Von Koch’s conjecture: enumerate nodes and edges 1..N such that each edge K differs by K.
```
@spec von_koch(tree :: list()) :: list() | nil
```

Arithmetic puzzle: insert operators into a list of numbers to form a valid equation.

@spec arithmetic(nums :: list(), target :: number()) :: String.t() | nil

Generate K-regular simple graphs with N nodes.

@spec k_regular(n :: pos_integer(), k :: non_neg_integer()) :: list(list())

English number words (e.g. 175 -> one seven five).

@spec number_words(n :: non_neg_integer()) :: String.t()

Syntax checker for Ada-style identifiers.

@spec valid_identifier?(s :: String.t()) :: boolean()

Sudoku solver.

@spec solve_sudoku(board :: list(list())) :: list(list()) | nil

Nonogram solver.

@spec solve_nonogram(rows :: list(), cols :: list()) :: list(list(0 | 1)) | nil

Crossword puzzle solver.

@spec solve_crossword(words :: list(), grid :: list()) :: list() | nil