JavaScriptで等式の整合性を検証する方法：Union-Findを使った実装解説

問題概要

配列 arr を唯一の引数として受け取るJavaScript関数を作成する必要があります。

配列 arr の各要素は、次の2種類のいずれかの形式で表された文字列の等式です。

• 'X===Y'
• 'X!==Y'

ここで、X と Y は任意の変数を表します。

この関数の目的は、配列内のすべての等式に対して適切な値を各変数に割り当てたとき、すべての等式が同時に成立（true）となるような割り当てが存在するかどうかを判定することです。

入力例

const arr = ['X===Y', 'Y!==Z', 'X===Z'];

出力例

const output = false;

出力の解説

X、Y、Z にどのような値を選んでも、3つの等式すべてを同時に満たすことはできません。「XとYが等しい」「YとZは異なる」「XとZが等しい」という条件は互いに矛盾しているためです。

解決アプローチ：Union-Find（素集合データ構造）

この問題は「Union-Find（ユニオン・ファインド）」と呼ばれるデータ構造を用いることで効率的に解くことができます。基本的な考え方は以下のとおりです。

• '===' の等式が出現したら、その2つの変数を同じグループ（連結成分）に統合します。
• '!==' の不等式は、すぐには判定せず、後で検証できるようにリストに保存しておきます。
• 最後に、保存しておいたすべての不等式について「2つの変数が異なるグループに属しているか」を確認します。もし同じグループに属していれば、その不等式は絶対に成立しないため、全体の結果は false となります。

実装コード

const arr = ['X===Y', 'Y!==Z', 'X===Z'];
const validateEquations = (arr = []) => {
    const map = {};
    const len = {};
    const inValids = [];
    const find = (item) => {
        while(map[item] && item !== map[item]){
            map[item] = map[map[item]];
            item = map[item];
        };
        return item;
    };
    const add = (a, b) => {
        const first = find(a);
        const second = find(b);
        if(first === second){
            return;
        };
        if(len[first] < len[second]){
            map[first] = second;
            len[second] += len[first];
        }else{
            map[second] = first;
            len[first] += len[second];
        }
    }
    arr.forEach((item) => {
        const X = item[0];
        const Y = item[4];
        map[X] = map[X] || X;
        map[Y] = map[Y] || Y;
        len[X] = len[X] || 1;
        len[Y] = len[Y] || 1;
        if(item[1] === '!'){
            inValids.push([X, Y]);
        }else{
            add(X, Y);
        };
    });
    return inValids.every(([a, b]) => find(a) !== find(b))
};
console.log(validateEquations(arr));

コードのポイント解説

• find関数：ある変数が属するグループの代表（ルート）を探す関数です。探索中に経路を途中の親へ直接つなぎ替える「経路圧縮」を行っており、以降の探索が高速になります。
• add関数：2つのグループを統合する関数です。サイズの小さい方を大きい方につなぐことで、木構造が偏るのを防ぎ、計算量を抑えています。
• メイン処理：item[1] が '!' なら不等式として inValids 配列に記録し、それ以外（'='）なら add 関数でグループを統合します。
• 最終判定：every() を使い、記録しておいたすべての不等式について「2つの変数のルートが異なること」を確認しています。1つでも同じルートを持つペアがあれば false を返します。

出力結果

コンソールに出力される結果は以下のとおりです。

false

今回の入力例では 'X===Y' と 'X===Z' により X・Y・Z がすべて同じグループに統合されますが、'Y!==Z' という不等式がこれと矛盾するため、最終的な判定結果は false となります。