2
\$\begingroup\$

Recently I appeared for an job challenge organised on HackerEarth.

Question:

There are two teams T1 and T2. Power of each player is represented in array. The rules of game are as follow.

There are only N fights.

  • No player from any team can fight twice.
  • At any instance, only one fight can occur.
  • For each fight score is calculated as (P1+P2)%N where P1, P2 is the power of player from T1 and T2 respectively and % is modulo operator.

Task in Hand is to arrange T2 players in such a way so that score is minimum. We have to print the score of the match after every fight. T2 is aware of the sequence of T1 players.

Input format is first line contains T denoting the number of test cases. It also denotes the number of times we have to run our function.

Second line contains N i.e. the number of fights

Third line contains the power of players from Team T1. The sequence in which T1 player power is shown is the sequence in which T1 players would fight.

Fourth line contains the power of players from Team T2.

Constraints:

1<=T<=10^5
1<=N<=10^5
0<=T1[i],T2[i]<= N for all i's.

I wrote the following code:

def solve (N, T1, T2):
    # Write your code here
    final_list=''
    for each in T1:
        temp_list=[]
        flag=True
        for i in range(0,len(T2)):
            if (each + T2[i])%N==0:
                T2.pop(i)
                final_list+='0'
                flag=False
                break
            else:
                temp_list.append((each + T2[i])%N)
        if flag:
            j=temp_list.index(min(temp_list))
            final_list+=str(min(temp_list))
            T2.pop(j)
    
    return final_list

T = int(input())
for _ in range(T):
    N = int(input())
    T1 = list(map(int, input().split()))
    T2 = list(map(int, input().split()))

    out_ = solve(N, T1, T2)
    print (' '.join(map(str, out_)))

It took 0.1 seconds for few test cases and more than 10.2 seconds for few test cases(so basically the test case failed for taking too much time).

Looking for optimal code

\$\endgroup\$
5
  • \$\begingroup\$ if possible, can you share the link to original question on the source platform (unless its visibility is private) \$\endgroup\$ – hjpotter92 Dec 21 '20 at 6:21
  • \$\begingroup\$ It is one of the job challenges on hackerearth for jobs in India. Test time is over so can't really share it. \$\endgroup\$ – Tanmey Rawal Dec 21 '20 at 6:37
  • 3
    \$\begingroup\$ I don't see why this is down-voted. There's working code, and the OP posted what constraints he could provide. \$\endgroup\$ – Reinderien Dec 21 '20 at 16:00
  • \$\begingroup\$ The current question title, which states your concerns about the code, applies to too many questions on this site to be useful. The site standard is for the title to simply state the task accomplished by the code. Please see How to Ask for examples, and revise the title accordingly. \$\endgroup\$ – Toby Speight Jan 4 at 15:10
  • \$\begingroup\$ If all that's wrong with it is the title, then just fix the title. \$\endgroup\$ – ShapeOfMatter Jan 4 at 15:37
1
\$\begingroup\$

Style:

This is the exact same algorithm, with the code-format, variable-names, and the use of strings cleaned up. I'm not actually sure this is the exact same function as yours, because the way you were using strings was probably wrong (because of the ' '.join(...) in the surrounding use-code).

def original_solve(N, T1, T2):
    final_list = []
    for item_1 in T1:
        temp_list = []
        already_appended = False
        for i in range(0, len(T2)):
            if (item_1 + T2[i]) % N == 0:
                T2.pop(i)
                final_list.append(0)
                already_appended = True
                break
            else:
                temp_list.append((item_1 + T2[i]) % N)
        if not already_appended:
            best_index = temp_list.index(min(temp_list))
            final_list.append(min(temp_list))
            T2.pop(best_index)
    
    return final_list

Benchmarking:

We should have a quick way to test out any improvements we make.

from random import randint  # insecure RNG is fine for this task.
from time import time

def make_test(N, t_len):
    return (N,
            [randint(0, N) for _ in range(t_len)],
            [randint(0, N) for _ in range(t_len)],
            None)

def time_function(f, *args):
    start = time()
    retval = f(*args)
    end = time()
    return retval, end - start

def main():
    candidates = {
        "Original": original_solve
    }
    tests = [
        (3, [1, 2, 3], [1, 2, 3], [0, 0, 0]),
        (4, [1, 2, 3], [1, 2, 3], [0, 0, 0]),
        (3, [1, 1, 3], [1, 2, 3], [0, 1, 1]),
        make_test(100, 100),
        make_test(100, 100),
        make_test(100, 100),
        make_test(10000, 10000),
        make_test(10000, 10000),
        make_test(10000, 10000),
    ]
    print('   T   ' + ''.join(f'{k:>10} (s)' for k in candidates.keys()) + '    Answer')
    for N, T1, T2, known in tests:
        results = [time_function(f, N, list(T1), list(T2))  # Copy these lists, since these algorithms modify T2. 
                   for f in candidates.values()]

        assert 1 == len(set(
            tuple(answer)
            for answer in [known, *(r[0] for r in results)]
            if answer is not None
        ))
        print(f'{len(T1):^7}'
              + ''.join(f'{r[1]:>14.9f}' for r in results)
              + f'  {results[0][0][:4]}')

if __name__ == '__main__':
    main()

Improvements to the existing algorithm:

Your current code is O(n^2). I suspect we can do better than that, but first lets consider some simplifications.

  • Checking separately for (item_1 + T2[i]) % N == 0 and short-circuiting is unlikely to save us much time, and it clutters up the function. Let's get rid of all of that.
  • Finding the min of temp_list, and then searching again to get its index, is stinky. One option would be to build temp_list as a list of t2_index, computed_value tuples, but I think re-doing one of the modulo-sum computations is cheap enough to not worry about. So we can just ask for the minimum index using a key-function.

Improving the algorithm:

The modulo operator in the scoring function is what makes this problem non-trivial, but it doesn't really change the fact that numbers are easy to sort, and sorting is usually O(n log(n)). If our list (T2) were already sorted, could we do the rest of the problem in better-than O(n^2) complexity?

  • Sort T2, and give it a structure to keep track of what's already been used. This is bank in the bellow code. Using ints/flags to track what's already been used is (probably) better than just dropping elements from the structure, because python's list's pop-intermediate is O(n).
  • For each item in T1:
    • Calculate the ideal paring: N - item (mod N)
    • Use a binary search (O(log(n)) to find where that value is or should be in the bank-structure.
    • Search upward from there for a value that hasn't been used yet. In the worst-case this is O(n), but for randomly generated data the rate of collisions will be "low" (I haven't looked up the formula)

So yes, we can write a sub-quadratic algorithm, in fact it's O(n log(n)), which is pretty good for most purposes. Further refinement may be possibly, but I suspect there's not an algorithm better than log-linear.

Results:

from itertools import count, groupby
from random import randint  # insecure RNG is fine for this task.
from time import time

def original_solve(N, T1, T2):
    final_list = []
    for item_1 in T1:
        temp_list = []
        already_appended = False
        for i in range(0, len(T2)):
            if (item_1 + T2[i]) % N == 0:
                T2.pop(i)
                final_list.append(0)
                already_appended = True
                break
            else:
                temp_list.append((item_1 + T2[i]) % N)
        if not already_appended:
            best_index = temp_list.index(min(temp_list))
            final_list.append(min(temp_list))
            T2.pop(best_index)
    
    return final_list

def clean_solve(N, T1, T2):
    final_list = []
    for item_1 in T1:
        def key_function(index):
            return (item_1 + T2[index]) % N
        best_index = min(range(len(T2)), key=key_function)
        final_list.append(key_function(best_index))
        T2.pop(best_index)
    
    return final_list

def sub_quadratic_solve(N, T1, T2):
    # Cases of `% length` are wrapping indexes back to the start of the list.
    # Cases of `% N` are wrapping any exact N values back to 0.
    bank = tuple([t2_item, len(list(copies))]  # using list as an easily-mutable object.
            for t2_item, copies
            in groupby(sorted(t % N for t in T2)))
    length = len(bank)

    def binary_search_index(value):  # https://www.codementor.io/@info658/the-binary-search-algorithm-in-python-19jvyrt5ly
        lower_bound = 0
        upper_bound = length - 1
        while lower_bound < upper_bound:
            midpoint = (lower_bound + upper_bound) // 2
            if bank[midpoint][0] == value:
                return midpoint
            elif bank[midpoint][0] < value:
                lower_bound = midpoint + 1
            else:
                upper_bound = midpoint - 1
        return lower_bound if bank[lower_bound][0] >= value else lower_bound + 1

    def find_best(value):
        ideal_index = binary_search_index(value % N)
        useable_index = next(i % length
                             for i in count(ideal_index)
                             if bank[i % length][1])
        bank[useable_index][1] -= 1
        return bank[useable_index][0]

    return [(t1_item + find_best(N - t1_item)) % N
            for t1_item in T1]


def make_test(N, t_len):
    return (N,
            [randint(0, N) for _ in range(t_len)],
            [randint(0, N) for _ in range(t_len)],
            None)

def time_function(f, *args):
    start = time()
    retval = f(*args)
    end = time()
    return retval, end - start

def main():
    candidates = {
        "Original": original_solve,
        "Cleaned": clean_solve,
        "Sub-Quad": sub_quadratic_solve,
    }
    tests = [
        (3, [1, 2, 3], [1, 2, 3], [0, 0, 0]),
        (4, [1, 2, 3], [1, 2, 3], [0, 0, 0]),
        (3, [1, 1, 3], [1, 2, 3], [0, 1, 1]),
        make_test(100, 100),
        make_test(100, 100),
        make_test(100, 100),
        make_test(10000, 10000),
        make_test(10000, 10000),
        make_test(10000, 10000),
    ]
    print('   T   ' + ''.join(f'{k:>10} (s)' for k in candidates.keys()) + '    Answer')
    for N, T1, T2, known in tests:
        results = [time_function(f, N, list(T1), list(T2))  # Copy these lists, since these algorithms modify T2. 
                   for f in candidates.values()]
        assert 1 == len(set(
            tuple(answer)
            for answer in [known, *(r[0] for r in results)]
            if answer is not None
        ))
        print(f'{len(T1):^7}'
              + ''.join(f'{r[1]:>14.9f}' for r in results)
              + f'  {results[0][0][:4]}')

if __name__ == '__main__':
    main()
Prints:
   T     Original (s)   Cleaned (s)  Sub-Quad (s)    Answer
   3      0.000027657   0.000033140   0.000041246  [0, 0, 0]
   3      0.000026226   0.000004768   0.000029802  [0, 0, 0]
   3      0.000004292   0.000024319   0.000008106  [0, 1, 1]
  100     0.000726700   0.000534534   0.000247002  [0, 2, 0, 0]
  100     0.000698566   0.000530243   0.000190973  [0, 0, 4, 0]
  100     0.000658035   0.000528812   0.000208855  [0, 5, 0, 2]
 10000    7.761836529   5.691253662   0.064605951  [0, 0, 1, 0]
 10000    7.386102200   5.667595863   0.067104578  [0, 1, 0, 2]
 10000    7.601329803   5.666092873   0.056614161  [0, 0, 0, 0]
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.