Skip to content
Tags

I’ve got 99 problems (but a list ain’t one)

21 August 2011

So I stumbled upon this: 99 Scala problems. Considering (oh, the shame) I never touched Scala, I thought I’d tackle the proposed list problems with Python and see how much I’m missing. So here we go:

1. Find the last element of a list.

Example:
scala> last(List(1, 1, 2, 3, 5, 8))
res0: Int = 8

Solution in Python:

>>> l = [1, 1, 2, 3, 5, 8]
>>> l[-1]
8

2. Find the last but one element of a list.

Example:
scala> penultimate(List(1, 1, 2, 3, 5, 8))
res0: Int = 5

Solution in Python:

>>> l = [1, 1, 2, 3, 5, 8]
>>> l[-2]
5

3. Find the Kth element of a list.
By convention, the first element in the list is element 0.

Example:
scala> nth(2, List(1, 1, 2, 3, 5, 8))
res0: Int = 2

Solution in Python:

>>> l = [1, 1, 2, 3, 5, 8]
>>> k = 2
>>> l[k]
2

4. Find the number of elements of a list.

Example:
scala> length(List(1, 1, 2, 3, 5, 8))
res0: Int = 6

Solution in Python:

>>> l = [1, 1, 2, 3, 5, 8]
>>> len(l)
6

5. Reverse a list.

Example:
scala> reverse(List(1, 1, 2, 3, 5, 8))
res0: List[Int] = List(8, 5, 3, 2, 1, 1)

Solution in Python:

>>> l = [1, 1, 2, 3, 5, 8]
>>> l[::-1]
[8, 5, 3, 2, 1, 1]

6. Find out whether a list is a palindrome.

Example:
scala> isPalindrome(List(1, 2, 3, 2, 1))
res0: Boolean = true

Solution in Python:

>>> l = [1, 2, 3, 2, 1]
>>> l == l[::-1]
True

7. Flatten a nested list structure.

Example:
scala> flatten(List(List(1, 1), 2, List(3, List(5, 8))))
res0: List[Any] = List(1, 1, 2, 3, 5, 8 )

Solution in Python:

>>> l = [[1, 1], 2, [3, [5, 8]]]
>>> def flat(l, r=[]):
...     for i in l: r = r + flat(i) if isinstance(i, list) else r + [i]
...     return r
...
>>> flat(l)
[1, 1, 2, 3, 5, 8]

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.

Example:
scala> compress(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Symbol] = List('a, 'b, 'c, 'a, 'd, 'e)

Solution in Python:

>>> l = ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
>>> from itertools import groupby
>>> [i[0] for i in groupby(l)]
['a', 'b', 'c', 'a', 'd', 'e']

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

Example:
scala> pack(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[List[Symbol]] = List(List('a, 'a, 'a, 'a), List('b), List('c, 'c), List('a, 'a), List('d), List('e, 'e, 'e, 'e))

Solution in Python:

>>> l = ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
>>> from itertools import groupby
>>> [list(j) for i, j in groupby(l)]
[['a', 'a', 'a', 'a'], ['b'], ['c', 'c'], ['a', 'a'], ['d'], ['e', 'e', 'e', 'e']]

10. 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 tuples (N, E) where N is the number of duplicates of the element E.

Example:
scala> encode(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))

Solution in Python:

>>> l = ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
>>> from itertools import groupby
>>> [(sum(1 for _ in j), i) for i, j in groupby(l)]
[(4, 'a'), (1, 'b'), (2, 'c'), (2, 'a'), (1, 'd'), (4, 'e')]

11. 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:
scala> encodeModified(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[Any] = List((4,'a), 'b, (2,'c), (2,'a), 'd, (4,'e))

Solution in Python:

>>> l = ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
>>> from itertools import groupby
>>> r = []
>>> for i, j in groupby(l):
...     s = sum(1 for _ in j)
...     r.append((s, i) if s > 1 else i)
...
>>> r
[(4, 'a'), 'b', (2, 'c'), (2, 'a'), 'd', (4, 'e')]

12. Decode a run-length encoded list.
Given a run-length code list generated as specified in problem P10, construct its uncompressed version.

Example:
scala> decode(List((4, 'a), (1, 'b), (2, 'c), (2, 'a), (1, 'd), (4, 'e)))
res0: List[Symbol] = List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e)

Solution in Python:

>>> l = [(4, 'a'), (1, 'b'), (2, 'c'), (2, 'a'), (1, 'd'), (4, 'e')]
>>> [j for i in l for j in i[0] * i[1]]
['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. I.e. don’t use other methods you’ve written (like P09’s pack); do all the work directly.

Example:
scala> encodeDirect(List('a, 'a, 'a, 'a, 'b, 'c, 'c, 'a, 'a, 'd, 'e, 'e, 'e, 'e))
res0: List[(Int, Symbol)] = List((4,'a), (1,'b), (2,'c), (2,'a), (1,'d), (4,'e))

Solution in Python:

>>> l = ['a', 'a', 'a', 'a', 'b', 'c', 'c', 'a', 'a', 'd', 'e', 'e', 'e', 'e']
>>> r = [(1, l[0])]
>>> for i in l[1:]:
...     if i == r[-1][1]:
...         r[-1] = (r[-1][0] + 1, r[-1][1])
...     else:
...         r.append((1, i))
...
>>> r
[(4, 'a'), (1, 'b'), (2, 'c'), (2, 'a'), (1, 'd'), (4, 'e')]

14. Duplicate the elements of a list.

Example:
scala> duplicate(List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'b, 'b, 'c, 'c, 'c, 'c, 'd, 'd)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd']
>>> [j for i in l for j in i * 2]
['a', 'a', 'b', 'b', 'c', 'c', 'd', 'd']

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

Example:
scala> duplicateN(3, List('a, 'b, 'c, 'c, 'd))
res0: List[Symbol] = List('a, 'a, 'a, 'b, 'b, 'b, 'c, 'c, 'c, 'c, 'c, 'c, 'd, 'd, 'd)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd']
>>> n = 3
>>> [j for i in l for j in i * n]
['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c', 'c', 'd', 'd', 'd']

16. Drop every Nth element from a list.

Example:
scala> drop(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('a, 'b, 'd, 'e, 'g, 'h, 'j, 'k)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
>>> [l[i] for i in range(len(l)) if (i+1) % 3 != 0]
['a', 'b', 'd', 'e', 'g', 'h', 'j', 'k']

17. Split a list into two parts.
The length of the first part is given. Use a Tuple for your result.

Example:
scala> split(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: (List[Symbol], List[Symbol]) = (List('a, 'b, 'c),List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k))

Solution in Python:

>>> l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
>>> n = 3
>>> (l[:n], l[n:])
(['a', 'b', 'c'], ['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k'])

18. Extract a slice from a list.
Given two indices, I and K, the slice is the list containing the elements from and including the Ith element up to but not including the Kth element of the original list. Start counting the elements with 0.

Example:
scala> slice(3, 7, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
>>> i, k = 3, 7
>>> l[i:k]
['d', 'e', 'f', 'g']

19. Rotate a list N places to the left.

Examples:
scala> rotate(3, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res0: List[Symbol] = List('d, 'e, 'f, 'g, 'h, 'i, 'j, 'k, 'a, 'b, 'c)

scala> rotate(-2, List('a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i, 'j, 'k))
res1: List[Symbol] = List('j, 'k, 'a, 'b, 'c, 'd, 'e, 'f, 'g, 'h, 'i)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k']
>>> n = 3
>>> l[n:] + l[:n]
['d', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'a', 'b', 'c']
>>> n = -2
>>> l[n:] + l[:n]
['j', 'k', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']

20. Remove the Kth element from a list.
Return the list and the removed element in a Tuple. Elements are numbered from 0.

Example:
scala> removeAt(1, List('a, 'b, 'c, 'd))
res0: (List[Symbol], Symbol) = (List('a, 'c, 'd),'b)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd']
>>> n = 1
>>> (l[:n] + l[n+1:], l[n])
(['a', 'c', 'd'], 'b')

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

Example:
scala> insertAt('new, 1, List('a, 'b, 'c, 'd))
res0: List[Symbol] = List('a, 'new, 'b, 'c, 'd)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd']
>>> elem, n = 'new', 1
>>> l[:n] + [elem] + l[n:]
['a', 'new', 'b', 'c', 'd']

22. Create a list containing all integers within a given range.

Example:
scala> range(4, 9)
res0: List[Int] = List(4, 5, 6, 7, 8, 9)

Solution in Python:

>>> start, end = 4, 9
>>> [i for i in range(start, end+1)]
[4, 5, 6, 7, 8, 9]

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

Example:
scala> randomSelect(3, List('a, 'b, 'c, 'd, 'f, 'g, 'h))
res0: List[Symbol] = List('e, 'd, 'a)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> n = 3
>>> import random
>>> random.shuffle(l)
>>> l[:n]
['a', 'b', 'h']

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

Example:
scala> lotto(6, 49)
res0: List[Int] = List(23, 1, 17, 33, 21, 37)

Solution in Python:

>>> n, m = 6, 49
>>> l = [i for i in range(1, m+1)]
>>> import random
>>> random.shuffle(l)
>>> l[:n]
[20, 9, 16, 21, 42, 48]

25. Generate a random permutation of the elements of a list.

Example:
scala> randomPermute(List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[Symbol] = List('b, 'a, 'd, 'c, 'e, 'f)

Solution in Python:

>>> l = ['a', 'b', 'c', 'd', 'e', 'f']
>>> import random
>>> random.shuffle(l)
>>> l
['e', 'c', 'd', 'a', 'b', '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? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficient). For pure mathematicians, this result may be great. But we want to really generate all the possibilities.

Example:
scala> combinations(3, List('a, 'b, 'c, 'd, 'e, 'f))
res0: List[List[Symbol]] = List(List('a, 'b, 'c), List('a, 'b, 'd), List('a, 'b, 'e), ...

Solution in Python:

>>> l = ['a', 'b', 'c', 'd', 'e', 'f']
>>> k = 3
>>> from itertools import combinations
>>> [i for i in combinations(l, k)]
[('a', 'b', 'c'), ('a', 'b', 'd'), ('a', 'b', 'e'), ('a', 'b', 'f'), ('a', 'c','d'), ('a', 'c', 'e'), ('a', 'c', 'f'), ('a', 'd', 'e'), ('a', 'd', 'f'), ('a','e', 'f'), ('b', 'c', 'd'), ('b', 'c', 'e'), ('b', 'c', 'f'), ('b', 'd', 'e'), ('b', 'd', 'f'), ('b', 'e', 'f'), ('c', 'd', 'e'), ('c', 'd', 'f'), ('c', 'e', 'f'), ('d', 'e', 'f')]

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? Write a function that generates all the possibilities.

Example:
scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), List(Flip, Gary, Hugo, Ida)), ...

Solution in Python:

>>> l = ['Aldo', 'Beat', 'Carla', 'David', 'Evi', 'Flip', 'Gary', 'Hugo', 'Ida']
>>> from itertools import combinations
>>> l = set(l)
>>> [[list(i), list(j), list(l - set(i).union(set(j)))] for i in combinations(l, 2) for j in combinations(l - set(i), 3)]
...

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

Example:
scala> group(List(2, 2, 5), List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida"))
res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David), List(Evi, Flip, Gary, Hugo, Ida)), ...

Solution in Python:

>>> l = ['Aldo', 'Beat', 'Carla', 'David', 'Evi', 'Flip', 'Gary', 'Hugo', 'Ida']

>>> n = [2, 2, 4]
>>> from itertools import combinations
>>> l = set(l)
>>> def group(l, n, i=0):
...     if i < len(n):
...         for a in [[j] + k for j in combinations(l, n[i]) for k in group(l -set(j), n, i+1)]:
...             yield a
...     else:
...         yield []
...
>>> [i for i in group(l, n)]
...

28. Sorting a list of lists according to length of sublists.
a) We suppose that a list contains elements that are lists themselves. The objective is to sort the elements of the list according to their length. E.g. short lists first, longer lists later, or vice versa.

Example:
scala> lsort(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res0: List[List[Symbol]] = List(List('o), List('d, 'e), List('d, 'e), List('m, 'n), List('a, 'b, 'c), List('f, 'g, 'h), List('i, 'j, 'k, 'l))

Solution in Python:

>>> l = [['a', 'b', 'c'], ['d', 'e'], ['f', 'g', 'h'], ['d', 'e'], ['i', 'j', 'k', 'l'], ['m', 'n'], ['o']]
>>> sorted(l, key=len)
[['o'], ['d', 'e'], ['d', 'e'], ['m', 'n'], ['a', 'b', 'c'], ['f', 'g', 'h'], ['i', 'j', 'k', 'l']]

b) Again, we suppose that a list contains elements that are lists themselves. But this time the objective is to sort the elements according to their length frequency; i.e. in the default, sorting is done ascendingly, lists with rare lengths are placed, others with a more frequent length come later.

Example:
scala> lsortFreq(List(List('a, 'b, 'c), List('d, 'e), List('f, 'g, 'h), List('d, 'e), List('i, 'j, 'k, 'l), List('m, 'n), List('o)))
res1: List[List[Symbol]] = List(List('i, 'j, 'k, 'l), List('o), List('a, 'b, 'c), List('f, 'g, 'h), List('d, 'e), List('d, 'e), List('m, 'n))

Solution in Python:

>>> l = [['a', 'b', 'c'], ['d', 'e'], ['f', 'g', 'h'], ['d', 'e'], ['i', 'j', 'k', 'l'], ['m', 'n'], ['o']]
>>> from itertools import groupby
>>> sorted([list(j) for i, j in groupby(sorted(l, key=len), key=len)], key=len)
[[['o']], [['i', 'j', 'k', 'l']], [['a', 'b', 'c'], ['f', 'g', 'h']], [['d', 'e'], ['d', 'e'], ['m', 'n']]]

From → code complete

Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: