# Programming Problem Set: 99 Problems Chapter 1

Home / Programming Problem Set: 99 Problems Chapter 1

### 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]```