一个令程序鼠反复惊叹的小游戏

挺标题党的哈,等你看到是什么游戏你会觉得更标题党的。

规则十分简单

哎呀,在很多广告上看到过。规则很简单:

  • 只能向相同颜色或者空试管中倒入最上层液体
  • 如此反复直到将颜色完全分离(每个试管中一个颜色)

没了,就这么简单,我老妈一下子就学会了。

可玩性很高

全程都是满足强迫症的过程,舒适感很高,不限制步数。休闲,难度也比较适宜。而且关卡非常之多,可能几千个?!(至少

关卡生成十分简单

说点编程层面的。

生成新关卡只需要用程序逆向操作就行,几个试管反复相互倾倒,倾倒次数大致可以代表关卡难度。所以别说几千,就是几万关卡生成起来也没啥压力,而且算力消耗可以说非常小。

关卡存储十分简单

储存最终(初始)数据即可,就一个数组,需要存储的字节数很少,这样即便携带大量关卡程序也不需要很大。

运行逻辑十分简单

判断是否可以倾倒就行了,所有颜色分离就通关。都是简单而明确的条件,很好判断,不需要对解密过程有过多关注。

甚至……

老鼠拍着大腿说:这么绝妙的点子我怎么就想不到呢?这游戏我也能做啊!然而,没想到就是没想到,笨蛋就要有承认自己是笨蛋的勇气。

对,老鼠是笨蛋,现在在卡关。我老妈玩到了上千关,我 264 关还没过去。

我觉得我好歹是个程序“鼠”,我整个程序解题算了,然后……我发现除了暴力穷举,我一时半时的还真没啥解题思路……(拍大腿,我是笨蛋,是笨蛋捏!

1 Like

汉诺塔变种?

有一点类似,但不知道怎么求解

液体会溢出吗?如果不会溢出那所有操作都是可逆的,也用不上穷举啊

来个链接?

不过同类型的非常多,我没有对比过谁好谁坏,这个没啥大问题就够我玩很久很久了

真笨,你弄几个米缸,里面放上点大米、小米、高粱、绿豆、黄豆啥的,不就是一个全新的游戏了嘛!

1 Like

稍微试了下 A* 搜索,似乎因为我想到的 heuristic(空试管0,纯色1,混合=颜色数+1) 不太满足 admissible 条件(不会过多估计距离),所以结果可能不是最优,但是至少可以找出来一组能达到结果的操作顺序了。

from typing import List, Union, Tuple, Set
from collections import Counter
import json
from queue import PriorityQueue
from itertools import combinations, chain, combinations_with_replacement

class Tube:
    def __init__(self, content_or_tube):
        # first: lowest, last: highest
        if isinstance(content_or_tube, Tube):
            self.content = content_or_tube.content[:]
        elif isinstance(content_or_tube, list):
            self.content : List = content_or_tube

    @property
    def last_color_count(self):
        if self.empty:
            return 0
        last_color = self.content[-1]
        count = 1
        for i in range(len(self.content) - 2, -1, -1):
            if self.content[i] == last_color:
                count += 1
            else:
                break
        return count


    def pour_out(self):
        last_color = self.content[-1]
        poured_out = []
        while len(self.content) > 0 and self.content[-1] == last_color:
            poured_out.append(self.content.pop())
        return poured_out

    def pour_in(self, colors):
        if len(self.content) == 0:
            pass
        elif self.content[-1] != colors[0]:
            raise Exception("incompatible colors")

        self.content = self.content + colors


    @property
    def mix_value(self):
        color_count = len(set(self.content))
        # return color_count
        if color_count == 0:
            return 0
        elif color_count == 1:
            return 1
        else:
            return color_count + 1

    @property
    def empty(self):
        return len(self.content) == 0
    
    @property
    def top(self):
        return self.content[-1]

    def __eq__(self, other):
        return self.content == other.content

    def __hash__(self) -> int:
        return hash(str(self.content))

    def __str__(self):
        return self.content.__str__()

    def __repr__(self):
        return repr(self.content)

class State:
    # basically a multiset
    def __init__(self, tubes_or_state, cost=0):
        self.internal_dict = {}
        self.cost = cost
        if type(tubes_or_state) is State:
            self.internal_dict = dict(tubes_or_state.internal_dict)
        elif type(tubes_or_state) is list:
            self.internal_dict = dict(Counter(tubes_or_state))

    
    def perform_move(self, tube_src, tube_dst):
        if tube_src not in self.internal_dict or self.internal_dict[tube_src] == 0:
            raise Exception("tube_src not in state")
        if tube_dst not in self.internal_dict or self.internal_dict[tube_dst] == 0:
            raise Exception("tube_dst not in state")
            
        self.internal_dict[tube_src] -= 1
        self.internal_dict[tube_dst] -= 1

        if tube_src in self.internal_dict and self.internal_dict[tube_src] == 0:
            self.internal_dict.pop(tube_src)
        if tube_dst in self.internal_dict and self.internal_dict[tube_dst] == 0:
            self.internal_dict.pop(tube_dst)

        src = Tube(tube_src)
        dst = Tube(tube_dst)

        dst.pour_in(src.pour_out())

        self.internal_dict[src] = self.internal_dict.get(src, 0) + 1
        self.internal_dict[dst] = self.internal_dict.get(dst, 0) + 1        

    @property
    def mix_value(self):
        sum_value = 0
        for tube, count in self.internal_dict.items():
            sum_value += tube.mix_value * count
        return sum_value
    
    @property
    def target_mix_value(self):
        color_set = set()
        for tube in self.internal_dict.keys():
            color_set.update(tube.content)
        return len(color_set)

    def __hash__(self) -> int:
        str_key_dict = {repr(k):v for k,v in self.internal_dict.items()}
        return hash(json.dumps(str_key_dict, sort_keys=True))

    def __str__(self):
        return f"{str(self.internal_dict)}"
    
    def __repr__(self):
        return self.internal_dict.__repr__()

    def __eq__(self, other):
        return self.internal_dict == other.internal_dict

    def __lt__(self, other):
        if self.mix_value + self.cost != other.mix_value + other.cost: 
            return self.mix_value + self.cost < other.mix_value + other.cost
        else:
            return str(self) < str(other)

def generate_moves(state: State):
    new_state_with_move = []

    tubes_having_2_or_more = [(tube, tube) for tube in state.internal_dict.keys() if state.internal_dict[tube] >= 2]

    for tube1, tube2 in chain(tubes_having_2_or_more, combinations(state.internal_dict.keys(), 2)):

        moves = [(tube1, tube2)]
        if tube1 != tube2:
            moves.append((tube2, tube1))

        for tube_src, tube_dst in moves:

            move = (str(tube_src), str(tube_dst))
            # print(move)
            # skip condition
            if tube_src.empty:
                # empty source
                continue
            if not tube_dst.empty and tube_src.top != tube_dst.top:
                # incompatible colors
                continue
            if tube_src.mix_value == 1 and tube_dst.empty:
                # useless move
                continue
            if len(tube_dst.content) >= 4:
                # overflow
                continue
            if tube_src.last_color_count + len(tube_dst.content) > 4:
                # overflow
                continue

            # print(move , " accepted")

            new_state = State(state, cost=state.cost + 1)
            new_state.perform_move(tube_src, tube_dst)
            new_state_with_move.append((new_state, move))
            # print("new state", new_state)
            # input()

    return new_state_with_move


def a_star_search(initial_state: State):
    target = initial_state.target_mix_value

    frontier = PriorityQueue() # lowest priority first
    # item: (state, moves), priority: heuristic(mix_value) + cost (steps taken)
    frontier.put((initial_state, list()))

    existing_states = set()
    existing_states.add(initial_state)

    while not frontier.empty():

        (state, moves) = frontier.get()
        # print(state)
        # input()

        # print(f"{len(frontier.queue)} states remaining", state.mix_value, state.cost)

        if state.mix_value == target:
            # print("found!")
            # print(state)
            return moves
        
        for new_state, move in generate_moves(state):
            if new_state in existing_states:
                continue
            new_move = moves.copy()
            new_move.append(move)
            frontier.put((new_state, new_move))
            existing_states.add(new_state)

def main():


    tubes = [
        Tube([4,3,2,1]),
        Tube([7,5,6,5]),
        Tube([3,9,7,8]),
        Tube([9,1,2,10]),
        Tube([7,4,1,9]),
        Tube([6,8,12,11]),
        Tube([12,12,4,10]),
        Tube([7,10,2,1]),
        Tube([2,5,5,10]),
        Tube([8,4,3,9]),
        Tube([6,12,11,3]),
        Tube([8,11,11,6]),
        Tube([]),
        Tube([])
    ]
    # print(tubes)
    state = State(tubes)
    # print(state)

    # print(state.target_mix_value)

    found_moves = a_star_search(state)
    print("required moves:", len(found_moves))

    for idx, move in enumerate(found_moves):
        print(f"{idx+1}: {move[0]} -> {move[1]}")



if __name__ == "__main__":
    main()

示例:注意颜色要倒着输入(从底部到顶部)

required moves: 39
1: [9, 1, 2, 10] -> []
2: [2, 5, 5, 10] -> [10]
3: [2, 5, 5] -> []
4: [9, 1, 2] -> [2]
5: [7, 10, 2, 1] -> [9, 1]
6: [7, 10, 2] -> [2, 2]
7: [10, 10] -> [7, 10]
8: [9, 1, 1] -> []
9: [7, 4, 1, 9] -> [9]
10: [8, 4, 3, 9] -> [9, 9]
11: [4, 3, 2, 1] -> [7, 4, 1]
12: [4, 3, 2] -> [2, 2, 2]
13: [4, 3] -> [8, 4, 3]
14: [7, 4, 1, 1] -> [1, 1]
15: [4] -> [7, 4]
16: [7, 10, 10, 10] -> []
17: [12, 12, 4, 10] -> [10, 10, 10]
18: [12, 12, 4] -> [7, 4, 4]
19: [7, 5, 6, 5] -> [5, 5]
20: [8, 11, 11, 6] -> [7, 5, 6]
21: [6, 8, 12, 11] -> [8, 11, 11]
22: [6, 8, 12] -> [12, 12]
23: [3, 9, 7, 8] -> [6, 8]
24: [7] -> [3, 9, 7]
25: [7, 4, 4, 4] -> []
26: [3, 9, 7, 7] -> [7]
27: [3, 9] -> [9, 9, 9]
28: [6, 12, 11, 3] -> [3]
29: [8, 4, 3, 3] -> [3, 3]
30: [8, 4] -> [4, 4, 4]
31: [6, 8, 8] -> [8]
32: [7, 5, 6, 6] -> [6]
33: [7, 5] -> [5, 5, 5]
34: [7, 7, 7] -> [7]
35: [8, 11, 11, 11] -> []
36: [6, 12, 11] -> [11, 11, 11]
37: [6, 12] -> [12, 12, 12]
38: [8, 8, 8] -> [8]
39: [6, 6, 6] -> [6]

好耶!老鼠学到了新知识!

这里是我理解错了,还是前面细节描述的不够清楚。此题中每个试管只能容纳4格的内容。也就是初始状态下只能是这些试管往空试管里倒。

现在修复了,加了对于容量超出的判断。

不明觉厉,十分感激,我学习一下

哭了,和我的设备不兼容。

相关游戏里随便选,应该都大差不差的

大致思路和人类处理这个问题是类似的,尽可能减少颜色的混合,不过也会考虑已经移动过的步数。输入在 main() 里,可以先复制到本地用 Python 运行试试。输出结果我手动模拟了一下应该是可用的,不过那个 App 似乎没法跳关,因此没法验证是否真的可以使用。

这一关挺难的,但是你问我他为什么难,我就说不出来了。我不知道是究竟符合了哪些特征,反正我做了好多次,到最后都走进了死胡同。

這個遊戲設計的很好,如果一開始先由易到難,比如只有五根管,再後來越來越多,這樣可以使玩家更容易漸入佳境。

可能是因为顶层颜色可选项太多,容易开局失误?

至少跑了一下之前的程序还是能跑出解的,虽然步数有点多

    tubes = [
        Tube([3,3,2,1]),
        Tube([6,5,2,4]),
        Tube([8,1,7,1]),
        Tube([11,9,10,9]),
        Tube([6,1,6,10]),
        Tube([2,12,11,12]),
        Tube([8,9,2,5]),
        Tube([11,10,7,4]),
        Tube([4,10,12,8]),
        Tube([3,11,6,7]),
        Tube([5,7,5,8]),
        Tube([4,12,9,3]),
        Tube([]),
        Tube([]),
    ]
required moves: 42
1: [11, 10, 7, 4] -> []
2: [11, 10, 7] -> []
3: [6, 1, 6, 10] -> [11, 10]
4: [3, 11, 6, 7] -> [7]
5: [6, 5, 2, 4] -> [4]
6: [6, 1, 6] -> [3, 11, 6]
7: [8, 1, 7, 1] -> [6, 1]
8: [8, 1, 7] -> [7, 7]
9: [8, 1] -> [6, 1, 1]
10: [5, 7, 5, 8] -> [8]
11: [8, 9, 2, 5] -> [5, 7, 5]
12: [6, 5, 2] -> [8, 9, 2]
13: [5, 7, 5, 5] -> [6, 5]
14: [5, 7] -> [7, 7, 7]
15: [6, 5, 5, 5] -> [5]
16: [3, 11, 6, 6] -> [6]
17: [4, 10, 12, 8] -> [8, 8]
18: [2, 12, 11, 12] -> [4, 10, 12]
19: [2, 12, 11] -> [3, 11]
20: [4, 10, 12, 12] -> [2, 12]
21: [11, 10, 10] -> [4, 10]
22: [11] -> [3, 11, 11]
23: [6, 1, 1, 1] -> []
24: [3, 3, 2, 1] -> [1, 1, 1]
25: [6, 6, 6] -> [6]
26: [2, 12, 12, 12] -> []
27: [3, 3, 2] -> [2]
28: [8, 9, 2, 2] -> [2, 2]
29: [4, 12, 9, 3] -> [3, 3]
30: [8, 9] -> [4, 12, 9]
31: [8, 8, 8] -> [8]
32: [4, 12, 9, 9] -> []
33: [4, 12] -> [12, 12, 12]
34: [4, 4] -> [4]
35: [4, 10, 10, 10] -> []
36: [4, 4, 4] -> [4]
37: [3, 11, 11, 11] -> []
38: [11, 9, 10, 9] -> [9, 9]
39: [11, 9, 10] -> [10, 10, 10]
40: [11, 9] -> [9, 9, 9]
41: [11, 11, 11] -> [11]
42: [3, 3, 3] -> [3]

像这种我一般卡好久(反正也不是特别专心的去玩),实际过程也差不多是暴力求解,反复尝试。