JavaScriptでオブジェクト間の最短距離を求める方法

問題の概要

まず、次のように各キーが数値の配列を持つオブジェクトがあると仮定しましょう。

const obj = {
    obj1: [ 0, 10 ],
    obj2: [ 3, 9 ],
    obj3: [ 5, 12, 14 ]
};

求められているのは、このようなオブジェクトを受け取って処理するJavaScript関数の作成です。各オブジェクトには複数の距離ポイント（候補となる数値）が含まれていますが、他のオブジェクトのポイントと組み合わせる際に選べるのは、各オブジェクトから1つだけである点に注意してください。

組み合わせと距離の考え方

上記の例では、obj1に2個、obj2に2個、obj3に3個の要素があるため、3つのオブジェクトは 2 × 2 × 3 の12通りの組み合わせが可能です。

たとえば、[0, 3, 5] という組み合わせの場合、3つのオブジェクト間の距離は次のように計算されます。

5 - 0 = 5;

同様に、[10, 9, 5] を選んだ場合は次のようになります。

10 - 5 = 5;

また、[0, 3, 12] を選んだ場合の距離は次の通りです。

12 - 0 = 12;

私たちが達成したいのは、こうした組み合わせの中から最短距離となるものを見つけることです。この例では答えは [10, 9, 12] となり、距離は次のように計算できます。

12 - 9 = 3;

なお、ここでいう「最短距離」とは、選ばれたグループ内における最大値と最小値の差を意味します。

実装コード

この問題を解くコードは以下のようになります。

const obj = {
    obj1: [ 0, 10 ],
    obj2: [ 3, 9 ],
    obj3: [ 5, 12, 14 ]
};
const findNearest = (obj = {}) => {
    let parts = [undefined, undefined, undefined];
    let i;
    let res;
    const data = Object
    .values(obj)
    .map((a, i) => a.map(v => [v, i]))
    .reduce((a, b) => a.concat(b))
    .sort((a, b) => a[0] - b[0] || a[1] - b[1]);
    for (i = 0; i < data.length; i++) {
        parts[data[i][1]] = data[i][0];
        if (parts.some(v => v === undefined)) continue;
        if (!res || Math.max(...parts) - Math.min(...parts) <
        Math.max(...res) - Math.min(...res)) {
            res = parts.slice();
        };
    };
    return res;
};
console.log(findNearest(obj));

コードの仕組み（解説）

このアルゴリズムは、次の手順で動作します。

1. Object.values() ですべての配列を取り出し、各数値に対して「どのオブジェクト由来か」を示すインデックスをタグ付けします。
2. すべての数値を1つの配列にまとめた後、昇順にソートします。
3. ソート済みの配列を先頭から順に走査しながら、すべてのオブジェクトから少なくとも1つずつ数値が揃った状態（スライディングウィンドウ）を追跡します。
4. その時点の最大値と最小値の差を計算し、既存の最小差よりも小さければ結果を更新していきます。

このアプローチにより、全12通りの組み合わせを個別に生成して調べる必要がなく、ソートされたデータを一度走査するだけで、最短距離となる組み合わせを効率よく特定できます。

出力結果

コンソールには次の出力が表示されます。

[ 10, 9, 12 ]