H-99

Ninety-Nine Haskell Problems

The problems

Questions 1 to 10: Lists

• 1. Find the last element of a list.
• 2. Find the last but one element of a list.
• 3. Find the K'th element of a list.
• 4. Find the number of elements of a list.
• 5. Reverse a list.
• 6. Find out whether a list is a palindrome.
• 7. Flatten a nested list structure.
• 8. Eliminate consecutive duplicates of list elements.
• 9. Pack consecutive duplicates of list elements into sublists.
• 10. Run-length encoding of a list.

Questions 11 to 20: Lists, continued

• 11. Modified run-length encoding.
• 12. Decode a run-length encoded list.
• 13. Run-length encoding of a list (direct solution).
• 14. Duplicate the elements of a list.
• 15. Replicate the elements of a list a given number of times.
• 16. Drop every N'th element from a list.
• 17. Split a list into two parts; the length of the first part is given.
• 18. Extract a slice from a list.
• 19. Rotate a list N places to the left.
• 20. Remove the K'th element from a list.

Questions 21 to 28: Lists again

• 21. Insert an element at a given position into a list.
• 22. Create a list containing all integers within a given range.
• 23. Extract a given number of randomly selected elements from a list.
• 24. Lotto: Draw N different random numbers from the set 1..M.
• 25. Generate a random permutation of the elements of a list.
• 26. Generate the combinations of K distinct objects chosen from the N elements of a list.
• 27. Group the elements of a set into disjoint subsets.
• 27A. Generate all the possibilities and returns them in a list.
• 27B. Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.
• 28. Sorting a list of lists according to length of sublists
• 28A. Sort the elements of this list according to their length.
• 28B. Sort the elements of this list according to their length frequency.

Skipped

• 29. Skipped
• 30. Skipped

Questions 31 to 41: Arithmetic

• 31. Determine whether a given integer number is prime.
• 32. Determine the greatest common divisor of two positive integer numbers. Use Euclid's algorithm.
• 33. Determine whether two positive integer numbers are coprime.
• 34. Calculate Euler's totient function phi(m).
• 35. Determine the prime factors of a given positive integer. Construct a flat list containing the prime factors in ascending order.
• 36. Determine the prime factors of a given positive integer. Construct a list containing the prime factors and their multiplicity.
• 37. Calculate Euler's totient function phi(m) (improved).
• 38. Compare the two methods of calculating Euler's totient function.
• 39. A list of prime numbers. Given a range of integers by its lower and upper limit, construct a list of all prime numbers in that range.
• 40. Goldbach's conjecture.
• 41. Given a range of integers by its lower and upper limit, print a list of all even numbers and their Goldbach composition.

Skipped

• 42. Skipped
• 43. Skipped
• 44. Skipped
• 45. Skipped

Questions 46 to 50: Logic and codes

• 46. Write a predicate table/3 which prints the truth table of a given logical expression in two variables.
• 47. Truth tables for logical expressions (2).
• 48. Truth tables for logical expressions (3).
• 49. Gray codes.
• 50. Huffman codes.

Skipped

• 51. Skipped
• 52. Skipped
• 53. Skipped

Questions 54A to 60: Binary trees

• 54A. Check whether a given term represents a binary tree. (non-solution)
• 55. Construct completely balanced binary trees
• 56. Symmetric binary trees
• 57. Binary search trees (dictionaries)
• 58. Generate-and-test paradigm
• 59. Construct height-balanced binary trees
• 60. Construct height-balanced binary trees with a given number of nodes

Questions 61 to 69: Binary trees, continued

• 61. Count the leaves of a binary tree
• 61A. Collect the leaves of a binary tree in a list
• 62. Collect the internal nodes of a binary tree in a list
• 62B. Collect the nodes at a given level in a list
• 63. Construct a complete binary tree
• 64. Annotate each node of the tree with a position
• 65. Annotate each node of the tree with a position (alternative layout method)
• 66. Annotate each node of the tree with a position (Yet another layout strategy)
• 67. A string representation of binary trees
• 68. Preorder and inorder sequences of binary trees.
• 68A. Write predicates preorder/2 and inorder/2 that construct the preorder and inorder sequence of a given binary tree, respectively.
• 68B. Use preorder/2 from problem part a) in the reverse direction.
• 68C. If both the preorder sequence and the inorder sequence of the nodes of a binary tree are given, then the tree is determined unambiguously. Write a predicate pre_in_tree/3 that does the job.
• 69. Dotstring representation of binary trees.

Skipped

• 70A. Skipped

Questions 70B to 73: Multiway trees

• 70B. Check whether a given term represents a multiway tree.
• 70C. Count the nodes of a multiway tree.
• 70. Tree construction from a node string.
• 71. Determine the internal path length of a tree.
• 72. Construct the bottom-up order sequence of the tree nodes.
• 73. Lisp-like tree representation.

Skipped

• 74. Skipped
• 75. Skipped
• 76. Skipped
• 77. Skipped
• 78. Skipped
• 79. Skipped

Questions 80 to 89: Graphs

• 80. Conversions
• 81. Path from one node to another one
• 82. Cycle from a given node
• 83. Construct all spanning trees
• 84. Construct the minimal spanning tree
• 85. Graph isomorphism
• 86. Node degree and graph coloration
• 87. Depth-first order graph traversal (alternative solution)
• 88. Connected components (alternative solution)
• 89. Bipartite graphs

Questions 90 to 94: Miscellaneous problems

• 90. Eight queens problem
• 91. Knight's tour
• 92. Von Koch's conjecture
• 93. An arithmetic puzzle
• 94. Generate K-regular simple graphs with N nodes

Questions 95 to 99: Miscellaneous problems, continued

• 95. English number words
• 96. Syntax checker
• 97. Sudoku
• 98. Nonograms
• 99. Crossword puzzle