Ninety-nine

"99" in digital rainThe 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: Scala for Project Euler.

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 -> [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) -> [1 2 3 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…

One Comment

  1. [...] also: Scala for Project Euler and Ninety-nine for more advanced examples of Scala [...]

Leave a Reply