4
\$\begingroup\$

You are given two arbitrary integer lists, e.g. [-10, 99, -6, 43], [100, 32, 44]. You are to pick one integer from each list and sum them up, then sort the best pairs ordered by the absolute distance to 100 in ascending order. Paired up integers from each list shall not be repeated in the output.

For instance, we have

(-10, 100): |100 - (-10 + 100)| = 10
(-10, 32) : |100 - (-10 + 32 )| = 78
(-10, 44) : |100 - (-10 + 44 )| = 66
(99, 100) : |100 - (99 + 100 )| = 99
(99, 32 ) : |100 - (99 + 32  )| = 31
(99, 44 ) : |100 - (99 + 44  )| = 43
(-6, 100) : |100 - (-6 + 100 )| = 6
(-6, 32 ) : |100 - (-6 + 32  )| = 74
(-6, 44 ) : |100 - (-6 + 44  )| = 62
(43, 100) : |100 - (43 + 100 )| = 43
(43, 32 ) : |100 - (43 + 32  )| = 25
(43, 44 ) : |100 - (43 + 44  )| = 13

After pairing with the first item -10, it is tempted to pick the pair (-10, 100) as the best pair as it has the least distance to 100. But further checking down the list, (-6, 100) in fact has a lesser distance to 100, hence it should be the best pair picked. After picking the pair, they are removed from their lists, leaving us

(-10, 32) : |100 - (-10 + 32)| = 78
(-10, 44) : |100 - (-10 + 44)| = 66
(99, 32 ) : |100 - (99 + 32 )| = 31
(99, 44 ) : |100 - (99 + 44 )| = 43
(43, 32 ) : |100 - (43 + 32 )| = 25
(43, 44 ) : |100 - (43 + 44 )| = 13

Then next pair to pick will be (43, 44). Notice that the distance to 100 is 13 for this pair, which is higher than the pair (-10, 100), but only because 100 has been paired with -6 and hence the pair (-10, 100) is gone. Moving on, we have these remaining

(-10, 32) : |100 - (-10 + 32)| = 78
(99, 32 ) : |100 - (99 + 32 )| = 31

And finally (99, 32) is picked. Hence the output (-6, 100), (43, 44), (99, 32). Ignore the rest that have nothing to pair up.

Note: when there is a tie, just pick any pair, without worrying the consequence to the remaining candidates.

The challenge here is to complete the task with the least number of comparisons operating on the inputs. i.e. if all comparison result has to come from a function comp(a, b), then the least number of call to this function wins. Looping control etc. are not included. Three way comparison is essentially 2 operations. General purpose code only and no special purpose optimisation is required. Favour code that can verify the number of comparison calls, however, when using build in functions, please explain their complexity for us to examine.

\$\endgroup\$
  • 1
    \$\begingroup\$ Welcome to PPCG! / Can you clarify if 3-way comparison is counted as 1 or 2 steps? \$\endgroup\$ – user202729 Jun 14 '18 at 10:13
  • \$\begingroup\$ I assume that the only operation that you can do on the numbers are comparing them (instead of, say, use them to index into arrays, or hash them? Is addition or multiplication allowed?) \$\endgroup\$ – user202729 Jun 14 '18 at 10:14
  • 4
    \$\begingroup\$ In summary: This is a nice challenge idea, but in the current form it's too unclear. You can sandbox the challenge before posting to main. \$\endgroup\$ – user202729 Jun 14 '18 at 10:39
  • \$\begingroup\$ @user202729 haha thanks. First time poster, tried my best. Points noted and updated in the question. Cheers. Enjoy! \$\endgroup\$ – user1589188 Jun 14 '18 at 11:33
  • 2
    \$\begingroup\$ The least number of comparisons over what space of possible inputs? That is, I could write a function that gives correct answers for all inputs, does a provably minimum number of comparisons on this example input, but does way more comparisons than necessary on other inputs. \$\endgroup\$ – aschepler Jun 14 '18 at 11:52
3
\$\begingroup\$

Python O(mn log mn)

The best pairs can be found computing the distances of all the possible pairs, and iteratively choosing the best pair among those remaining after filtering out the already chosen items.

A simple implementation is shown in the following code:

def find_nearest_pairs_to_100(l, m):
    pair_list = sorted([((i, j), abs(100 - i - j)) for i in l for j in m], key=lambda x: x[1])
    chosen_pairs = []
    while pair_list:
        best_pair = pair_list[0][0]
        chosen_pairs.append(best_pair)
        pair_list = [(p, s) for (p, s) in pair_list if p[0] != best_pair[0] and p[1] != best_pair[1]]
    return chosen_pairs

The find_nearest_pairs_to_100 function takes the two lists in input and returns an ordered list with the chosen pairs.

The sorted function in Python is based on Timsort algorithm, that requires O(n log n) comparisons in the worst case (where n is the length of the list).

In this case the length of the list is the cardinality of the Cartesian product of the two input lists, i.e. mn (with n > m). Therefore, the total cost of this implementation is of O(mn log mn) comparisons, excluding the other comparison operations needed for filtering.

Including comparisons for filtering, at each iteration, in the worst case, all the items of the list are checked against the elements of the chosen pair; the length the pair_list is mn at the first iteration, (n-1)(m-1) at the second, (n-2)(m-2) at the third, and n-m+1 at the last step. So the total number of comparisons for filtering is O(n^3).

If you like golfing, it is a golfed version (163 bytes) of the previous one (a little bit different):

f=lambda l,m:l and m and[[k]+f(l.remove(k[0])or l,m.remove(k[1])or m)for k in sorted([[[[i,j]],abs(100-i-j)]for i in l for j in m],key=lambda x:x[1])[0][0]][0]or[]
\$\endgroup\$
  • \$\begingroup\$ Thank you! Really nice submission and good explanation, I have learnt a lot here. Just that for the selection part, you may want to update that a little bit as the current code will exclude potential pairs with same integer value of picked pairs but from a different input list. i.e. when the two input lists both contain some equal integers. \$\endgroup\$ – user1589188 Jun 15 '18 at 0:57
  • \$\begingroup\$ @user1589188 You're right, I've updated the code. \$\endgroup\$ – PieCot Jun 15 '18 at 5:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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