写了一个脚本通关水排序解谜，玩个游戏也太难了-五八三

游戏初体验

昨晚回到家，又在b站看到这款游戏的广告，我去搜了一下，下来玩玩。不过这其实看的应该是另一个游戏的广告，只不过那个游戏盗用了这边的视频……

这个游戏需要你把所有所有试管都变成纯色的，你每次可以把一个试管的颜色块，倒入另一个试管中，前提是另一个试管顶部的颜色和你倒出的颜色一样，或者为空。

一开始玩，还蛮简单的，玩到六七十关发现不太对劲。特别特别难……游戏开发者的套路开始了……虽然可以理解，开发游戏的目的就是为了赚钱，但一关有三十几个步骤才能通关，是不是有点小过分了。看一次30秒的广告+被套路耽误的时间，大概得1分钟，如果一个关卡需要35个步骤，那我得看7分钟的广告，基本不用玩了。

其实游戏开发者可以收点钱，现在的广告基本是按点击结算的，他这边疯狂诱骗大家点击，体验很差，搞得我都不敢给他开联网权限，不如收点钱，绝对比广告费要多呀…… 我看微信小程序那边1000次广告展示，正常的转化率只有不到10次点击，开发者到手不到2元。

无可奈何，但还是有点想玩

他这个游戏有一个提示功能，而且会根据你的操作来动态给，说明代码层面肯定是可以通过穷举法或者什么方法得到一个解法的。

午休的时候我就在想，这部分代码要怎么写呢，想一下，没想出来，又继续躺着玩。想着要怎样才能用代码把这个游戏的规则给描述出来。

初步做法抽象两个对象出来，一个对象叫水瓶，另一个叫组合器。

export declare enum WaterBottleColor {
    深蓝 = 0,
    浅蓝 = 1,
    深绿 = 2,
    浅绿 = 3,
    青 = 4,
    红 = 5,
    紫 = 6,
    褐 = 7,
    橙 = 8,
    粉 = 9,
    灰 = 10,
    黄 = 11
}
export declare class WaterBottle {
    private colors;
    constructor(colors: WaterBottleColor[]);
    getColors(): WaterBottleColor[];
    getSpareVolume(): number;
    isFull(): boolean;
    push(color: WaterBottleColor): void;
    pop(): WaterBottleColor | undefined;
    isEmpty(): boolean;
    isPure(): boolean;
    isOk(): boolean;
}

import { WaterBottle } from "./water_bottle";
export declare class Combiner {
    private waterBottlesHistory;
    private operationMemory;
    private bestSolution;
    constructor(waterBottles: WaterBottle[]);
    private checkWaterBottles;
    private isOk;
    private isWaterBottleEqual;
    private isOperationEqual;
    private isOpreationRepeat;
    private cloneWaterBottle;
    private tryOpreation;
    private search;
    start(): void;
}

解法很暴力，但是很有效

穷举法+缓存，深度优先搜索，尽量找到最优解，免得步骤太多眼花。

    private search(steps: string[]): string[] | undefined {
        // 如果解法比已知最优解长，就没必要求解了
        if (this.bestSolution && steps.length >= this.bestSolution.length) return this.bestSolution

        const currentHistory = last(this.waterBottlesHistory)
        // 穷举法
        for (let [leftIndex, leftWaterBottle] of currentHistory?.entries() || []) {
            for (let [rightIndex, rightWaterBottle] of currentHistory?.entries() || []) {
                // 自己不能和自己操作
                if (leftIndex === rightIndex) continue

                const currentSteps = last(steps) === `${rightIndex} -> ${leftIndex}` ? [...steps.slice(0, -1), `${leftIndex} -> ${rightIndex}`] : [...steps, `${leftIndex} -> ${rightIndex}`]

                // 尝试操作，如果行得通会产生一个新的历史
                const newHistory = this.tryOpreation(leftWaterBottle, rightWaterBottle)
                if (!newHistory) continue

                // 如果新解法产生了，需要对比新解法的长度，如果更短，则更新
                if (this.isOk(newHistory)) {
                    if (!this.bestSolution || this.bestSolution.length > currentSteps.length) console.log(currentSteps, currentSteps.length)
                    if (!this.bestSolution || this.bestSolution.length > currentSteps.length) this.bestSolution = currentSteps
                }

                // 如果本次操作和之前的历史有重复，会引发死循环，应该避免进入递归
                const { isRepeat, bestSteps } = this.isOpreationRepeat(newHistory, currentSteps)
                if (isRepeat) continue

                this.waterBottlesHistory.push(newHistory)
                const searchResult = this.search(bestSteps)
                this.waterBottlesHistory.pop()

                if (!this.bestSolution) this.bestSolution = searchResult
                if (this.bestSolution?.length && searchResult?.length && this.bestSolution.length > searchResult.length) this.bestSolution = searchResult
            }
        }
        return this.bestSolution
    }

试着跑了一下，改了2小时的bug吧~真夸张，步骤这么多，我要是靠运气蒙得多久了。