JavaScriptでかの有名な水の移し替えパズルを解く【反復深化深さ優先探索】

元ネタ

問題

水が5L入る容器と3L入る容器がある、この2つの容器だけを使って、
4Lの水を量るにはどうすれば良いですか？
水はいくらでも使えるものとします。

ソース

class 容器クラス {
    constructor(最大容量) {
        this.容量 = 0;
        this.最大容量 = 最大容量;
    }
    get 残り容量() {
        return this.最大容量 - this.容量;
    }
    水を入れる() {
        this.容量 = this.最大容量;
    }
    水を捨てる() {
        this.容量 = 0;
    }
    水を移す(dst容器) {
        const 移動する容量 = Math.min(this.容量, dst容器.残り容量);
        this.容量 -= 移動する容量;
        dst容器.容量 += 移動する容量;
    }
}

function 探索(容器A, 容器B, 残り操作回数, 操作内容配列 = []) {
    const old容器A容量 = 容器A.容量;
    const old容器B容量 = 容器B.容量;
    for (const 容器 of [容器A, 容器B]) {
        for (const 操作 of ["水を入れる", "水を捨てる", "水を移す"]) {
            let 操作内容 = "";
            switch (操作) {
                case "水を入れる":
                    if (容器.残り容量 === 0) {
                        break;
                    }
                    操作内容 = `${容器.最大容量}L容器を満タンにした。　　`;
                    容器.水を入れる();
                    break;
                case "水を捨てる":
                    if (容器.容量 === 0) {
                        break;
                    }
                    操作内容 = `${容器.最大容量}L容器を空っぽにした。　　`;
                    容器.水を捨てる();
                    break;
                case "水を移す":
                    if (容器.容量 === 0) {
                        break;
                    }
                    const dst容器 = [容器A, 容器B].filter(e => e !== 容器)[0];
                    if (
                        dst容器.残り容量 === 0 ||
                        容器.容量 + dst容器.残り容量 === dst容器.最大容量
                    ) {
                        break;
                    }
                    操作内容 = `${容器.最大容量}L容器から${dst容器.最大容量}L容器へ注いだ。`;
                    容器.水を移す(dst容器);
                    break;
            }
            操作内容 += `【${容器A.最大容量}L容器: ${容器A.容量}L, ${容器B.最大容量}L容器: ${容器B.容量}L】`;
            操作内容配列.push(操作内容);
            if (容器A.容量 === 4 || 容器B.容量 === 4) {
                return 操作内容配列;
            }
            if (残り操作回数 > 0) {
                const result = 探索(容器A, 容器B, 残り操作回数 - 1, 操作内容配列);
                if (result !== false) {
                    return result;
                }
            }
            容器A.容量 = old容器A容量;
            容器B.容量 = old容器B容量;
            操作内容配列.pop();
        }
    }
    return false;
}

for (let depth = 0; depth < 10000; depth++) {
    const result = 探索(new 容器クラス(3), new 容器クラス(5), depth);
    if (result !== false) {
        for (let i = 0; i < result.length; i++) {
            console.log(`${i + 1}: ${result[i]}`);
        }
        break;
    }
}

実行結果

1: 5L容器を満タンにした。　　【3L容器: 0L, 5L容器: 5L】
2: 5L容器から3L容器へ注いだ。【3L容器: 3L, 5L容器: 2L】
3: 3L容器を空っぽにした。　　【3L容器: 0L, 5L容器: 2L】
4: 5L容器から3L容器へ注いだ。【3L容器: 2L, 5L容器: 0L】
5: 5L容器を満タンにした。　　【3L容器: 2L, 5L容器: 5L】
6: 5L容器から3L容器へ注いだ。【3L容器: 3L, 5L容器: 4L】

別の方法