Working with Lists

Problem 01

easy

Find the last element of a list.

Problem 02

easy

Find the last but one element of a list. (penúltimo, zweitletztes Element, l'avant-dernier élément)

Problem 03

easy

Find the $k$ 'th element of a list. The first element in the list is number $1$ .

Problem 04

easy

Find the number of elements of a list.

Problem 06

easy

Find out whether a list is a palindrome. A palindrome can be read forward or backward; e.g. [r, a, d, a, r].

Problem 07

intermediate

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).

Problem 08

intermediate

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.

Example

compress([a, a, a, a, b, c, c, a, a, d, e, e, e, e]) == [a, b, c, a, d, e]

Problem 09

intermediate

Pack consecutive duplicates of list elements into sublists. If a list contains repeated elements they should be placed in separate sublists.

Example

pack([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 ]
    ]

Problem 10

easy

Run-length encoding of a list. Use the result of problem P09 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.

Example

encode([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 ]
    ]

Problem 11

easy

Modified run-length encoding.

Modify the result of problem P10 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.

Example

encode_modified([a, a, a, a, b, c, c, a, a, d, e, e, e, e]) == 
    [
        [ 4, a ],
        b,
        [ 2, c ],
        [ 2, a ],
        d,
        [ 4, e ]
    ]

Problem 12

intermediate

Decode a run-length encoded list.

Given a run-length code list generated as specified in problem P11. Construct its uncompressed version.

Problem 13

intermediate

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 P09, but only count them. As in problem P11, simplify the result list by replacing the singleton terms [1, X] by X.

Example

encode_direct([a, a, a, a, b, c, c, a, a, d, e, e, e, e]) == 
    [
        [4, a], 
        b, 
        [2, c], 
        [2, a], 
        d, 
        [4, e]
    ]

Problem 14

easy

Duplicate the elements of a list.

Example

dupli([a, b, c, c, d]) == [a, a, b, b, c, c, c, c, d, d]

Problem 15

intermediate

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

Example

dupli([a, b, c], 3) == [a, a, a, b, b, b, c, c, c]

Problem 16

intermediate

Drop every $n$ 'th element from a list.

Example

drop([a, b, c, d, e, f, g, h, i, k], 3) == [a, b, d, e, g, h, k]

Problem 17

easy

Split a list into two parts; the length of the first part is given. Do not use any predefined functions.

Example

split([a, b, c, d, e, f, g, h, i, k], 3) == 
    [
        [a, b, c], 
        [d, e, f, g, h, i, k]
    ]

Problem 18

intermediate

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.

Example

slice([a, b, c, d, e, f, g, h, i, k], 3, 7) == [c, d, e, f, g]

Problem 19

intermediate

Rotate a list $n$ places to the left.

Examples

rotate([a, b, c, d, e, f, g, h], 3) == [d, e, f, g, h, a, b, c]
rotate([a, b, c, d, e, f, g, h], -2) == [g, h, a, b, c, d, e, f]

Hint: Use the result of problem P17.

Problem 20

easy

Remove the $k$ 'th element from a list.

Example

remove_at([a, b, c, d], 2) == [a, c, d]

Problem 21

easy

Insert an element at a given position into a list.

Example

insert_at(alfa, [a, b, c, d], 2) == [a, alfa, b, c, d]

Problem 22

easy

Create a list containing all integers within a given range.

Example

range(4, 9) == [4, 5, 6, 7, 8, 9]

Problem 23

intermediate

Extract a given number of randomly selected elements from a list. The selected items shall be put into a result list.

Example

rnd_select([a, b, c, d, e, f, g, h], 3) == [e, d, a]

Hint: Use the result of problem P20.

Problem 24

easy

Lotto: Draw $n$ different random numbers from the set $1, \dots, m$ . The selected numbers shall be put into a result list.

Example

rnd_select(6, 49) == [23, 1, 17, 33, 21, 37]

Hint: Combine the solutions of problems P22 and P23.

Problem 25

easy

Generate a random permutation of the elements of a list.

Example

rnd_permu([a, b, c, d, e, f]) == [b, a, d, c, e, f]

Hint: Use the solution of problem P23.

Problem 26

intermediate

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? We all know that there are $C_{3}^{12} = 220$ possibilities ( $C_{k}^{n}$ denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities.

Example

combination(3, [a, b, c, d, e, f]) ==
    [
        [a, b, c],
        [a, b, d],
        [a, b, e],
        ...
    ]

Problem 27

intermediate

Group the elements of a set into disjoint subsets.

In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities.

Example

group3([aldo, beat, carla, david, evi, flip, gary, hugo, ida]) == 
    [
        [aldo, beat], 
        [carla, david, evi], 
        [flip, gary, hugo, ida]
    ]

Generalize the above function in a way that we can specify a list of group sizes and the function will return a list of groups.

Example

group(  [aldo, beat, carla, david, evi, flip, gary, hugo, ida], 
        [2, 2, 5]) ==  
    [
        [aldo, beat], 
        [carla, david], 
        [evi, flip, gary, hugo, ida]
    ]

Note that we do not want permutations of the group members; i.e. [[aldo, beat], ...] is the same solution as [[beat, aldo], . ..].

However, we make a difference between [[aldo, beat], [carla, david], ...] and [[carla, david], [aldo, beat], ...].

You may find more about this combinatorial problem in a good book on discrete mathematics under the term "multinomial coefficients".

Problem 28

intermediate

Sort a list of lists according to length of sublist.

We 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( [
        [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]    
    ]

Again, we suppose that a list (InList) contains elements that are lists 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( [   [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 lists in the result have length 4 and 1, both lengths appear just once. The third and forth list have length 3 which appears, there are two list of this length. And finally, the last three lists have length 2. This is the most frequent length.

99 Problems

Working with Lists

Problem 01

Problem 02

Problem 03

Problem 04

Problem 05

Problem 06

Problem 07

Problem 08

Problem 09

Problem 10

Problem 11

Problem 12

Problem 13

Problem 14

Problem 15

Problem 16

Problem 17

Problem 18

Problem 19

Problem 20

Problem 21

Problem 22

Problem 23

Problem 24

Problem 25

Problem 26

Problem 27

Problem 28