7
\$\begingroup\$

Given a list of N lists, each containing M positive integers, and a separate list of M positive integers (target values), return a list of N scalars (integers with a value of 0 or more) that correspond to each list in the lists of lists, such that when each value in a list is multiplied by it's scalar, and the values at each index of each list are added together to make one final summed list, the sum of the absolute difference between each value in the summed list and the target list is minimized. If there are multiple possible outputs of equal absolute difference for a given input, output any single answer.

The solution with the fastest algorithm (by running time complexity) wins.

Examples:

Input: 
    Lists:  [[1,2], [2,1]]
    Target: [9,9]

Output:
    [3, 3]

---------- ---------- ----------


Input:
    Lists:  [[3,9,2,1], [7,1,2,3], [2,3,8,1]]
    Target: [60, 70, 50, 60]

Output:
    [6, 5, 4]

---------- ---------- ----------

Input:
    Lists:  [[9, 7, 8], [9, 4, 12]]
    Target: [176, 68, 143]

Output:
    [6, 8]

Example of Answer Corectness Checking:

Input:
        Lists:  [[9, 7, 8], [9, 4, 12]]
        Target: [176, 68, 143]
        
Output:
    [6, 8]

6 * [9, 7, 8]  = [54, 42, 48]
8 * [9, 4, 12] = [72, 32, 96]

[54, 42, 48] + [72, 42, 96] = [126, 84, 144]

summed difference:
    abs(176 - 126) + abs(68 - 84) + abs(143 - 144)
    = 50 + 16 + 1
    = 67 
    (minimize this number)
\$\endgroup\$
6
  • \$\begingroup\$ When there are multiple possible outputs, should the program output any one of them or all of them? For example Lists: [[2], [4]], Target: [12] \$\endgroup\$
    – tsh
    Mar 7, 2022 at 7:16
  • \$\begingroup\$ @tsh When there are multiple possible outputs of equal absolute difference, output any single answer. \$\endgroup\$
    – drmosley
    Mar 7, 2022 at 15:41
  • 4
    \$\begingroup\$ You have used both fastest-code and fastest-algorithm without specifying which one the challenge is scored by. Is it scored by the fastest asymptotic time complexity or the fastest runtime performance? \$\endgroup\$
    – Lecdi
    Mar 7, 2022 at 17:07
  • 1
    \$\begingroup\$ @Lecdi Updated prompt. It should be fastest time complexity. \$\endgroup\$
    – drmosley
    Mar 7, 2022 at 17:29
  • 1
    \$\begingroup\$ think 8 * [9, 4, 12] = [72, 32, 96] \$\endgroup\$
    – LHeng
    Apr 19, 2022 at 12:31

2 Answers 2

1
\$\begingroup\$

Python 3, Brute Force Solution

from itertools import product
import numpy as np


def abs_difference(totals, target):
    distance = sum(abs(totals - target))
    return distance


def best_combo(array, target):

    # setup, using numpy arrays for optimization
    array = np.array(array)
    target = np.array(target)
    low_difference = sum(target)
    low_combo = None
    n = len(array)

    # figure a limiting scalar for each list
    # aka, the scalar just before a scaled list gets further from the target
    individual_limits = []
    for row in array:
        row_low_difference = sum(target)
        i = 0
        while True:
            i += 1
            totals = i * row
            if abs_difference(totals, target) > row_low_difference:
                break
        individual_limits.append(i)

    # create a range for each limiting scalars
    # and create a generator function for all combinations of the value in these ranges
    # aka combinations of scalars to be multiplied by each row
    ranges = (range(i) for i in individual_limits)
    combos = product(*ranges)

    # iterate over these combos
    # figure out which combination of the rows gets closest to the target
    for combo in combos:
        totals = sum(array * np.array(combo).reshape(n, 1))
        difference = abs_difference(totals, target)
        if difference < low_difference:
            low_combo = combo
            low_difference = difference

    return low_combo


assert best_combo([[1, 2], [2, 1]], [9, 9]) == (3, 3)
assert best_combo([[3, 9, 2, 1], [7, 1, 2, 3], [2, 3, 8, 1]], [60, 70, 50, 60]) == (6, 5, 4)
assert best_combo([[9, 7, 8], [9, 4, 12]], [176, 68, 143]) == (6, 8)

\$\endgroup\$
1
  • \$\begingroup\$ Running time complexity for this solution is effectively proportional to the product of the individual scalar limits (for large arrays). \$\endgroup\$
    – drmosley
    Apr 21, 2022 at 2:39
1
\$\begingroup\$

Haskell, O(product target)

import Data.List
import Data.Ord

instance Num a=>Num[a]where
 (+)=zipWith(+)
 (-)=zipWith(-)
 (*)=zipWith(*)
 fromInteger=repeat.fromInteger
 abs=map abs
 signum=map signum

closest target vectors=
 minimumBy(comparing$sum.abs.(target-).sum.(vectors*).map fromInteger)$
 sequence$map(enumFromTo 0.succ.maximum.zipWith div target)vectors

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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