CodeEval String List

In this CodeEval problem we are given a number n and a string. We have to return, as a comma separated list, the sorted collection of all the possible words sized n from the letters in the string.

I have converted the given samples in python tests:
def test_provided_1(self):
    self.assertEqual('a', solution('1,aa'))

def test_provided_2(self):
    self.assertEqual('aa,ab,ba,bb', solution('2,ab'))

def test_provided_3(self):
    self.assertEqual('ooo,oop,opo,opp,poo,pop,ppo,ppp', solution('3,pop'))
And then I spent some time thinking on them.

The first one remembers us that we need to keep only the unique letters in the string. So I would probably use a set to clean it up from repetitions.
The second one gives away a very important clue. The result is obviously the cartesian product between the first and the second letter. Since I am using Python as implementation language, I thought immediately to itertools product().
The third one tells me not to forget to sort the results. So set is useful as intermediate passage, but then I should put the items in a list, so that I can sort it. Besides, it shows me how I have to proceed, iterating on each partial solution applying each time the cartesian product between the previous result and the initial collection of letters.

Well. It looks quite easy now. It just a matter of writing the code.
def solution(line):
    n, data = line.split(',')
    letters = sorted(list(set(data)))  # 1
    result = letters  # 2
    for i in range(int(n)-1):  # 3
        result = ['{}{}'.format(x[0], x[1]) for x in product(result, letters)]  # 4
    return ','.join(result)
1. I use the set collection to remove duplicates, then I convert it to a list, and I sort it.
2. I need to keep the original letter collection aside, so that I can use it as a factor in the cartesian product, so I copy it in another list.
3. If n is 1, I don't have to do anything more, the plain list of single letters has been already generated. Otherwise have have to apply n-1 times the cartesian product.
4. The itertools product() function returns a tuple, I convert it to a plain string, and I push each result in a new list that overwrite the previous result.

There is not much left out to see, however the full code for the test case and python3 script is on GitHub.

No comments:

Post a Comment