CodeEval Number Operations

Given five integers in the close interval [1 .. 52], determine if it is possible, just applying addition, subtraction, and multiplication, to get as result 42.
I spent some time thinking to a smarter way to solve codeeval problem #190, in the end I fell back to a brute force approach. After all, I thought, 42 must be an hint that the answer is easy, but the question is difficult to get.

Here is how I implemented a Python 3 solution for it.

These are the tests provided by CodeEval, that I put in a python unit test:
def test_provided_1(self):
    self.assertEqual('NO', solution('44 6 1 49 47'))

def test_provided_2(self):
    self.assertEqual('YES', solution('34 1 49 2 21'))

def test_provided_3(self):
    self.assertEqual('NO', solution('31 38 27 51 18'))
Assume that "data" is a list containing the five integers we have to deal with. I need to check all the possible permutations of them, after all they are only five, and 5! is just 120.
However, we have to check all the different combinations of +, -, * over them. That means that, for each permutation, examining all the items in the Cartesian product of three elements with four repetitions, that is 3**4, 81.
That's a total of 120 * 81 = 9720 tests.

Not terrible, however I can't expect this code to be blazingly fast. Good for us, the standard python library itertools gives us permutations() that generates all the possible permutations for a collection, and product() that generates all the elements in the Cartesian product for the passed collection and a given size of the result. Just what we need here.
for numbers in permutations(data):  # 1
    for operations in product('*+-', repeat=4):  # 2
        result, *values = numbers  # 3
        for value, op in zip(values, operations):  # 4
            if op == '+':
                result += value
            elif op == '-':
                result -= value
                result *= value
        if result == 42:  # 5
            return 'YES'
return 'NO'
1. Loop on all the data permutations.
2. Loop on all the combinations of the available operations, knowing that we need four of them.
3. Split the numbers, that is tuple, in two parts, result, the first number, on its own, and all the other values in a list. Notice the use of the star operator that here works as a gatherer, bringing together all the other elements besides the first one, taken by the variable before the comma.
4. Here you see why I did that weird thing in the line above (3). Now I can zip() values and operations. Each component with the same index are extracted together and associated to the loop variables value and op, so that I can happily apply the operation to the current result and the next value in list.
5. If the current permutation with the current operations result as required, I return success. Only if I won't find any match, after looping on all the elements, I will say that, no, I could not find a way to get 42 from those integers.

As I expected, CodeEval accepted the solution, but didn't was too large in giving points for it. Anyway, I pushed test case and python script to GitHub.

No comments:

Post a Comment