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]

Solution:

  1. Haskell
  2. Lisp
  3. Prolog
  4. Python

, ,

About Author

about author

xathrya

A man who is obsessed to low level technology.

Leave a Reply

Your email address will not be published. Required fields are marked *

Social media & sharing icons powered by UltimatelySocial