Ninety-nine
The famous Ninety-Nine Prolog problems (by Werner Hett) transcended their original purpose and became a popular set of exercises for languages other than Prolog.
Solving these puzzles (and comparing your solutions with solutions of others) is a good way to “get a feel” for programing language and to explore idiomatic approaches to particular kind of problems.
Today we can easily find solutions to the problems in almost any wide-spread programming language. However most of the attempts use a single programing language and provide only one solution to each problem.
By providing multiple types of solutions we can enrich our programming “toolbox” and learn pros and cons of various methods. By using several programming languages simultaneously we can easily correlate different programming paradigms and explore limits of language expressive power.
Here goes my take on Ninety-Nine Problems in:
All the code is available as a GitHub repository.
See also:
Working with lists
Problem 1
(*) Find the last element of a list.
[1 2 3 7 5] -> 5
Scala | Java | Clojure | Haskell
Problem 2
(*) Find the last but one element of a list.
[1 2 3 7 5] -> 7
Scala | Java | Clojure | Haskell
Problem 3
(*) Find the K’th element of a list
The first element in the list is number 1.
[1 2 3 7 5] 4 -> 7
Scala | Java | Clojure | Haskell
Problem 4
(*) Find the number of elements of a list.
[1 2 3 5 7] -> 5
Scala | Java | Clojure | Haskell
Problem 5
(*) Reverse a list.
[1 2 3 7 5] -> [5 7 3 2 1]
Scala | Java | Clojure | Haskell
Problem 6
(*) Find out whether a list is a palindrome.
A palindrome can be read forward or backward.
[1 2 3 3 2 1] -> true
Scala | Java | Clojure | Haskell
Problem 7
(**) Flatten a nested list structure.
Transform a list, possibly holding lists as elements into a ‘flat’ list by replacing each list with its elements (recursively).
[1 [2 3 [5 7] 3] 1] -> [1 2 3 5 7 3 1]
Scala | Java | Clojure | Haskell
Problem 8
(**) 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.
[1 1 1 2 2 3 1 5 5 3 3] -> [1 2 3 1 5 3]
Scala | Java | Clojure | Haskell
Problem 9
(**) Pack consecutive duplicates of list elements into sublists.
If a list contains repeated elements they should be placed in separate sublists.
[1 1 1 2 2 3 1 5 5 3 3] -> [[1 1 1] [2 2] [3] [1] [5 5] [3 3]]
Scala | Java | Clojure | Haskell
Problem 10
(*) Run-length encoding of a list.
Use the result of problem 9 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as terms (N E) where N is the number of duplicates of the element E.
[1 1 1 2 2 3 1 5 5 3 3] -> [(3 1) (2 2) (1 3) (1 1) (2 5) (2 3)]
Scala | Java | Clojure | Haskell
Problem 11
(*) Modified run-length encoding.
Modify the result of problem 10 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 (N E) terms.
[1 1 1 2 2 3 1 5 5 3 3] -> [(3 1) (2 2) 3 1 (2 5) (2 3)]
Scala | Java | Clojure | Haskell
Problem 12
(**) Decode a run-length encoded list.
Given a run-length code list generated as specified in problem 11. Construct its uncompressed version.
[(3 1) (2 2) 3 1 (2 5) (2 3)] -> [1 1 1 2 2 3 1 5 5 3 3]
Scala | Java | Clojure | Haskell
Problem 13
(**) Run-length encoding of a list (direct solution).
Implement the so-called run-length encoding data compression method directly. I.e. don’t explicitly create the sublists containing the duplicates, as in problem 9, but only count them. As in problem 11, simplify the result list by replacing the singleton terms (1 X) by X.
[1 1 1 2 2 3 1 5 5 3 3] -> [(3 1) (2 2) 3 1 (2 5) (2 3)]
Scala | Java | Clojure | Haskell
Problem 14
(*) Duplicate the elements of a list.
[1 2 3 1] -> [1 1 2 2 3 3 1 1]
Scala | Java | Clojure | Haskell
Problem 15
(*) Replicate the elements of a list a given number of times.
[1 2 3 1] 3 -> [1 1 1 2 2 2 3 3 3 1 1 1]
Scala | Java | Clojure | Haskell
Problem 16
(**) Drop every N‘th element from a list.
[1 2 3 4 5 6 7 8] 3 -> [1 2 4 5 7 8]
Scala | Java | Clojure | Haskell
Problem 17
(*) Split a list into two parts; the length of the first part is given.
Do not use any predefined predicates.
[1 2 3 4 5 6 7 8] 3 -> ([1 2 3] [4 5 6 7 8])
Scala | Java | Clojure | Haskell
Problem 18
(**) 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 (both limits included). Start counting the elements with 1.
[1 2 3 4 5 6 7 8] 3 7 -> [3 4 5 6 7]
Scala | Java | Clojure | Haskell
Problem 19
(**) Rotate a list N places to the left.
[1 2 3 4 5 6 7 8] 3 -> [4 5 6 7 8 1 2 3]
Scala | Java | Clojure | Haskell
Problem 20
(*) Remove the K‘th element from a list.
[1 2 3 4] 2 -> (2, [1 3 4])
Scala | Java | Clojure | Haskell
Problem 21
(*) Insert an element at a given position into a list.
[1 2 3 4] 2 5 -> [1 5 2 3 4]
Scala | Java | Clojure | Haskell
Problem 22
(*) Create a list containing all integers within a given range.
(4 9) -> [4 5 6 7 8 9]
Scala | Java | Clojure | Haskell
Problem 23
(**) Extract a given number of randomly selected elements from a list.
[1 2 3 4 5 6 7 8] 3 -> [7 3 5]
Scala | Java | Clojure | Haskell
Problem 24
(*) Lotto: Draw N different random numbers from the set 1..M.
(1 8) 3 -> [7 3 5]
Scala | Java | Clojure | Haskell
Problem 25
(*) Generate a random permutation of the elements of a list.
[1 2 3 4 5] -> [2 5 1 3 4]
Scala | Java | Clojure | Haskell
To be continued…
[…] also: Scala for Project Euler and Ninety-nine for more advanced examples of Scala […]
problem 22
(4 9) -> [1 2 3 4 5 6 7 8 9]
should be
(4 9) -> [4 5 6 7 8 9]
or
(1 9) -> [1 2 3 4 5 6 7 8 9]
?
Oops… Of course it should be (4 9) -> [4 5 6 7 8 9] (it’s now fixed). Thank you for the notice!
problem 19
[1 2 3 4 5 6 7 8] 3 -> [3 4 5 6 7 8 1 2 3]
should be
[1 2 3 4 5 6 7 8] 3 -> [4 5 6 7 8 1 2 3]
Fixed. Thanks!