HackerEarth Challenge Find Maximum Taste of Fruits

Question

Problem Statement:

Samu had got N fruits. Sweetness of ith fruit is given by A[i]. Now she wants to eat all the fruits , in such a way that total taste is maximised.

Total Taste is calculated as follow (Assume fruits sweetness array uses 1-based indexing) :

int taste=0;
for(int i=2;i<=N;i++){
    if (A[i]-A[i-1] >= 0){
       taste = taste + i*(A[i]-A[i-1]);
    }
    else{
       taste = taste + i*(A[i-1]-A[i]);   
    }
}

So, obviously the order in which she eat the fruits changes the Total taste. She can eat the fruits in any order. Also once she start eating a fruit she will finish that one before moving to some other fruit.

Now she got confused in deciding the order in which she should eat them so that her Total taste is maximized. So she ask for help from you. Help her find the maximum taste she can have , if she can eat the fruits in any order.

Input Format:

First line contain number of test cases T. First line of each test case contains N, denoting the number of fruits. Next line contain N space separated integers denoting the sweetness of each fruit.

Output Format:

For each test case you need to print the maximum taste Samu can have by eating the fruits in any order she want to.

Constraints:

\$1 \le T \le 10\$ \$1 \le N \le 15\$

Sweetness of each fruit, A[i] lies between 1 to 100 for 1 ≤ i ≤ N

Sample Input:

1
3
2 5 4

Sample Output:

13

Explanation:

[2,4,5] -> 2*(2) + 3*(1) = 7
[2,5,4] -> 2*(3) + 3*(1) = 9
[5,4,2] -> 2*(1) + 3*(2) = 8
[5,2,4] -> 2*(3) + 3*(2) = 12
[4,5,2] -> 2*(1) + 3*(3) = 11
[4,2,5] -> 2*(2) + 3*(3) = 13

The maximum is 13 that can be obtained by eating the fruits according to sweetness order [4,2,5].

---

from itertools import permutations
for _ in xrange(int(raw_input())):
    n=int(raw_input())
    val=map(int,raw_input().split())
    max_ = 0
    for A in permutations(val):
        taste=0;
        for i in xrange(1,len(A)):
            taste = taste + (i+1)*abs(A[i]-A[i-1])
        max_= max(max_,taste)
    print max_

Answer 1

You are searching over the full set of permutations, which leads to a time complexity of \$O(n!)\$, which is rarely a good thing. This seems like the type of problem that would benefit from a dynamic programming approach. I don't find it entirely satisfactory, as it uses a top-down approach, but it is much more efficient than your implementation, so here it goes:

The basic idea is that, if you take a subset \$A\$ of \$m\$ items, and compute the \$m\$ values \$t_{A,j}\$, being the "best taste using the items in \$A\$ and ending in the \$j\$-th item, you can compute \$t_{A^*, m+1}\$, where \$A^*\$ is the set \$A\$ augmented with an extra item not in that set, easily. This is kind of confusing, I know, but below I am indexing memoized solutions by (items_remaining_to_be_used, last_item_used), and building the total taste by adding one of the remaining items at a time. It may be easier to look at the code:

def top_down(seq):
    memo = {}
    for idx, item in enumerate(seq):
        key = (frozenset(seq[:idx] + seq[idx+1:]), item)
        memo[key] = 0
    mult = 1
    best_taste = None
    while best_taste is None:
        mult += 1
        new_memo = {}
        for (items, last), taste in memo.items():
            items = list(items)
            for idx, item in enumerate(items):
                new_taste = taste + mult * abs(item - last)
                new_set = frozenset(items[:idx] + items[idx+1:])
                if not new_set:
                    best_taste = max(new_taste,
                                     0 if best_taste is None else best_taste)
                else:
                    new_key = new_set, item
                    new_memo[new_key] = max(new_memo.get(new_key, 0),
                                            new_taste)
        memo = new_memo
    return best_taste

Comparing to a function implementing your naive approach:

def naive(seq):
    best_taste = 0
    for perm in permutations(seq):
        taste = 0
        for idx, (this, that) in enumerate(zip(perm[:-1], perm[1:])):
            taste += (idx + 2) * abs(this - that)
        best_taste = max(best_taste, taste)
    return best_taste

The timing differences start out small:

a = [random.randint(100) for _ in range(5)]
%timeit naive(a)
1000 loops, best of 3: 215 µs per loop
%timeit top_down(a)
1000 loops, best of 3: 262 µs per loop

But things soon favor the top_down implementation massively:

a = [random.randint(100) for _ in range(10)]
%timeit naive(a)
1 loops, best of 3: 10.4 s per loop
%timeit top_down(a)
10 loops, best of 3: 44.6 ms per loop

That's over a 200x improvement! And of course:

>>> naive(a) == top_down(a)
True

And even the largest problem in your challenge can be solved in a reasonable amount of time, not sure if it will be fast enough though:

a = [random.randint(100) for _ in range(15)]
%timeit top_down(a)
1 loops, best of 3: 3.76 s per loop