### Programming Problem Set: 99 Problems Chapter 1

December 9, 2015 | Labs | No Comments

Ninety-nine Problems is generalized version to famous P-99: Ninety-Nine Prolog Problems collection used for teaching programming. The problems initially set for prolog but later many solutions come from various programming language. The purpose of this problem is to give us opportunity to practice our skills in logic programming. The goal is to find the most elegant solution of the given problem. Efficiency is important, but logical clarity is even more crucial.

The problem set are divided into seven categories / chapters: Lists, Arithmetic, Logic and Codes, Binary Trees, Multiway Trees, Graphs, and Miscellaneous.

In this chapter you will be only given a problem set. The solution might come however it would be on different page.

This chapter will cover about **Lists**. A list is either empty or it is composed of a first element (head) and a tail, which is a list itself.

#### 01. Find the last element of a list

Example: last_p( [a, b, c, d] ) -> d

#### 02. Find the last but one element of a list

Example: last_one_p( [a, b, c, d] ) -> c

#### 03. Find the n’th element of a list

The index is started from 1. Example: at_p( [a, b, c, d], 3) -> c

#### 04. Find the number of elements of a list

Example: length_p( [a, b, c, d] ) -> 4

#### 05. Reverse a list

Example: reverse_p( [a, b, c, d] ) -> [d, c, b, a]

#### 06. Find out whether a list is a palindrome

A palindrome ca be read forward of backward. Example: palindrom_p( [a, b, c, b, a] ) -> true

#### 07. Flatten a nested list structure

Transform a lists as elements into a 'flat' list by replacing each list with its element (recursively) Example: flatten_p( [a, [b, [c, d], e]] ) -> [a, b, c, d, e]

#### 08. 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 elements should not be changed. Example: compress_p( [a, a, a, a, b, c, c, a, a, d, e, e, e, e] ) -> [a, b, c, a, d, e]

#### 09. Pack consecutive duplicates of list elements into sublists

If a list contains repeated elements, they should be placed in separate sublist. Example: pack_p( [a, a, a, a, b, c, c, a, a, d, e, e, e, e]) -> [ [a, a, a, a], [b], [c, c], [a, a], [d], [e, e, e, e,] ]

#### 10. Run-length encoding of a list

Consecutive duplicates of elements are encoded as terms [N, E] where N is the number of duplicates of the element E. Example: encode_p1( [a, a, a, a, b, c, c, a, a, d, e, e, e, e] ) -> [ [4,a], [1,b], [2,c], [2,a], [1,d], [4,e]]

#### 11. Modified run-length encoding

Consecutive duplicates of elements are encoded as terms [N, E] where N is the number of duplicates of the element E. If an element has no duplicates, it is simply copied into the result list Only duplicates are transferred as [N, E] terms. Example: encode_p2( [a, a, a, a, b, c, c, a, a, d, e, e, e, e] ) -> [ [4,a], b, [2,c], [2,a], d, [4,e] ]

#### 12. Decode a run-length encoding list

Given a run-length code list generated, construct its uncompressed version. Example: encode_p3( [4,a], [1,b], [2,c], [2,a], [1,d], [4,e]) -> [a, a, a, a, b, c, c, a, a, d, e, e, e, e] ]

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

Implement the so-called run-length encoding data compression method directly. Don't explicitly create the sublists containing the duplicates but only count them. Simplify the result list by replacing the singleton terms [1,X] by X. Example: encode_p4([a, a, a, a, b, c, c, a, a, d, e, e, e, e]) -> [ [4,a], b, [2,c], [2,a], d, [4,e]]

#### 14. Duplicate the elements of a list

Example: duplicate_p([a, b, c, d, e]) -> [a, a, b, b, c, c, d, d, e, e]

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

Example: duplicate_px([a, b, c, d, e], 3) -> [a, a, a, b, b, b], c, c, c, d, d, d, e, e, e]

#### 16. Drop everh N’th element from a list

Example: drop_p([a, b, c, d, e, f, g, h, i, k], 3) -> [a, b, d, e, g, h, k]

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

Do not use any predefined predicates / function. Example: split_p([a, b, c, d, e, f, g, h, i, k], 3, L1, L2) -> L1 = [a, b, c] ; L2 = [d, e, f, g, h, i, k]

#### 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 element with 1. Example: slice_p([a, b, c, d, e, f, g, h, i, k], 3, 7) -> [c, d, e, f, g]

#### 19. Rotate a list N places to the left

Example: rotate_p([a, b, c, d, e, f, g, h], 3) -> [d, e, f, g, h, a, b, c] rotate_p([a, b, c, d, e, f, g, h],-2) -> [g, h, a, b, c, d, e, f]

#### 20. Remove the K’th element from a list

Example: remove_p([a, b, c, d], 2) -> [a, c, d]

#### 21. Insert an element at a given position into a list

Example: insert_p(x, [a, b, c, d], 2) -> [a, x, b, c, d]

#### 22. Create a list containing all integers withing a given range.

Example: range_p(4, 9) -> [4, 5, 6, 7, 8, 9]

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

The selected items shall be put into a result list. Example: rnd_select_p1([a, b, c, d, e, f, g, h], 3) -> [g, a, c]

#### 24. Draw N different random numbers from the set 1..M.

The selected numbers shall be put into a result list. Example: rnd_select_p2(6, 49) -> [23, 1, 33, 21, 37, 17]

#### 25. Generate a random permutation of the elemnts of a list.

Example: rnd_permut_p([a, b, c, d, e]) -> [b, a, d, c, e, f]

#### 26. Generate the combinations of K distinct objects chosen from the N elements of a list.

In how many ways can a committee of 3 be chosen from a group of 12 people? There are C(12,3) = 220 possibilities denotes the well-known binomial coefficients. Example: combination_p([a, b, c, d, e, f]) [a, b, c] [a, b, d] [a, b, e] ...

#### 27. Group the elements of a set into disjoint subsets.

(a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3, and 4 persons? Example: group3_p([aldo,beat, carla, david, evi, flip, gary, hugo, ida]) G1 = [aldo, beat], G2 = [carla, david, evi], G3 = [flip, gary, hugo, ida] (b) Generalize the above function in a way that we can specify a list of group sizes and the predicate will return a list of groups Example: group_p([aldo, beat, arla, david, evi, flip, gary, hugo, ida],[2, 2, 5]) -> [[aldo,beat],[carla,david],[evi,flip,gary,hugo, ida]] [/sourcecode]

#### 28. Sorting a list of lists according to length of sublists

(a) Suppose that a list (InList) contains elements that are lists themselves. The objective is to sort the elements of InList according to their length. E.g. short lists first, longer lists later, or vice versa. Example: lsort_p([[a, b, c], [d,e],[f,g,h], [d,e], [i,j,k,l], [m,n],[o]]) -> [[o],[d, e],[d, e],[m, n],[a, b, c],[f, g, h],[i, j, k, l]] (b) Suppose a list (InList) contains elements that are list themselves. But this time the objective is to sort the elements of InList according to their length frequency. i.e. in the default, where sorting is done ascendingly, lists with rare lengths are placed first, others with a more frequent length come later. Example: lfsort_p([[a, b, c], [d,e],[f,g,h], [d,e], [i,j,k,l], [m,n],[o]]) -> [[i, j, k, l],[o],[a, b, c],[f, g, h],[d, e],[d, e],[m, n]] Note that in the above example, the first two list in the result have length 4 and 1, both lengths appear just one. The third and forth list have length 3, there are two list of this length. And finally the last three lists have length 2. This is the most frequent length [/sourcecode]

## Solution:

- Haskell
- Lisp
- Prolog
- Python