# NxM List Combination Closest to Target

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]


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)

• 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]
– tsh
Mar 7, 2022 at 7:16
• @tsh When there are multiple possible outputs of equal absolute difference, output any single answer. Mar 7, 2022 at 15:41
• 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? Mar 7, 2022 at 17:07
• @Lecdi Updated prompt. It should be fastest time complexity. Mar 7, 2022 at 17:29
• think 8 * [9, 4, 12] = [72, 32, 96] Apr 19, 2022 at 12:31

# 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)


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

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!