背景：Greenplum Team的Big Standup
Greenplum Team有一个源自从Pivotal时代的晨会仪式，称为Big Standup。2020年4月，被收购成为VMware Greenplum后，由于VMware的未来办公模式，永久的远程办公（甚至可以改Base），中国团队每天的Standup改为线上的zoom，为了更加活泼有趣，主持人需要想一个游戏，或者做一个小分享。这个活动成为了每天最吸引人的事情了。
谜题介绍：Dog Bunny Puzzle
有一个同事，找了一个有趣的类似华容道的益智游戏，对应的网站是 https://www.dogbunnypuzzle.com/。2022年12月24日的那个关卡如下图:
点击❓可以查看规则，下面我简单介绍一下：
- 这个图的顶点称为Location，上面可以有Icon，比如最上面的顶点里，Icon是一个胡萝卜
- 顶尖之间的有路径，有的是有向路径，有的是无向，有向路径就是只能顺着箭头方向通过
- 有的路径上有标签，也就是这个路径可以通过的先决条件，比如上图中狗和兔子之间的路径，有两个标签，一个胡萝卜和一根骨头，含义是，必须有东西站在包含这些Icon的Locatin上，此路才通。有时候标签可以为否的，比如必须某Icon的Location上没有东西，才可以铜鼓
- 一个Location上可以被多个东西占据
- 游戏给一个初始图，然后最终的目的是让兔子站在胡萝卜上，狗站在骨头上。
算法思路
当时玩儿完了的时候，我立刻想到了PAIP里的General Problem Solver (参考我之前的blog)，回头看了看我当时的实现，并没有支持复杂的condition（如上面介绍，此谜题里的先决条件是一个复合的布尔表达式，可以是and和not的联合。改一改应该是可以解决的。
本周末的时候，我准备改GPS来求解，但玩了一把之后，立刻想到了新的算法来解决。我的思路很简单，逻辑链条如下:
- Locations是有限的，假设有N个
- 有三个Object（俩🐰一🐶），所以总共的状态数不超过N^3，后面简单分析状态数的枚举
- 每一个状态就意味着一个局面，在每一个局面，可以选择任一Object移动，只有潜在的畅通的路径才可以走，只移动一个Object，到达另一个局面（另一个状态）即发生状态转移
- 遍历所有潜在的状态，可以构造出完整的状态转移图
- 利用Dijkstra算法或者BFS，可以求从起始到完成的最短路径（也就是游戏解法）
状态数问题
如果任务两只🐰是不同的，状态数就是Location数的立方。下面讨论两只兔子是不区分的场景。这时候状态总数是N * (N_1 + N_2), 其中:
- N是Locations的总数
- N_1是两兔子在同一个位置选择数，有N_1=N
- N_2是两兔子不在同一个位置选择数，有{N \choose 2}
采用N^3会让编程简单一些，不区分🐰会减少几乎一半儿的状态，同时可以多训练一些编程，因此我们选择后者。
状态编码
状态编码解决的问题是，构造自然数和状态场面的一一映射。这样，给定一个自然数，可以快速的还原游戏的场面，反之亦然。Location的编码从0开始: 0,1,2,\dots,N-1.
🐰和🐶的状态是正交的，可以用进制把它们组合起来。基数选择数目大的，很显然是🐰的N+{N \choose 2}.🐶只有一只，因此其状态id可以就很简单的映射到位置，🐰有俩，状态id到兔子的位置，多一些处理。令K = N + {N \choose 2}
\text{StateID} = \text{StateID}_{\text{dog}} * K + \text{StateID}_{\text{bunnies}}其中 \text{StateID}_{\text{dog}} \in [0, N), \text{StateID}_{\text{bunnies}} \in [0, N+{N \choose 2}) , \text{StateID} \in [0, N(N+{N \choose 2})).
进一步研究🐰状态编码，一个排列的思路如下:
- 第0层: 俩🐰间隔0（就是在一起），有N个, \{0,0\}, \{1,1\} \dots, \{N-1,N-1\}
- 第1层: 俩🐰间隔1，有N-1个，\{0,1\}, \{1,2\},\dots, \{N-2,N-1\}
- \dots
- 第i层: 俩🐰间隔i，有N-i个，\{0,i\}, \{1,i+1\},\dots,\{N-1-i, N-1\}
- \dots
- 第N-1层:俩🐰间隔N-1，有1个，\{0, N-1\}
编码的时候，采用正金字塔会容易一些，把上面的层号修改一下：
- 第N层: 有N个, \{0,0\}, \{1,1\} \dots, \{N-1,N-1\}
- 第N-1层: 有N-1个，\{0,1\}, \{1,2\},\dots, \{N-2,N-1\}
- \dots
- 第i层: 有i个，\{0,N-i\}, \{1,N-i+1\},\dots,\{i-1, N-1\}
- \dots
- 第1层:有1个，\{0, N-1\}
第i层的第j个位置(i\in [1, N], j\in [0,i-1])的状态编码是S，则有:
S = \frac{1}{2}(i-1)i + j第1层只有1个状态，它对应的坐标是(1, 0)的状态编码是0.最后一个状态的坐标是(N, N-1)，状态编码是\frac{1}{2}(N-1)N + (N-1)，恰好满足总状态数要求。
下面推理如何给定S求解对应的坐标，有了坐标，求解位置状态就简单了。
i(i-1) \le 2S = (i-1)i + 2j < i(i+1) \implies (i-\frac{1}{2})^2 \le 2S + \frac{1}{4} < (i+\frac{1}{2})^2 \implies i-\frac{1}{2} \le \sqrt{2S+\frac{1}{4}} < i+\frac{1}{2} \implies i \le \sqrt{2S+\frac{1}{4}} + \frac{1}{2} < i + 1 \implies i = \lfloor \sqrt{2S+\frac{1}{4}} + \frac{1}{2} \rfloor下面的Erlang代码模块是完整的状态编码，请注意代码最后的单元测试，包含了完整的两个locations时候的情况。
-module(state).
-include_lib("eunit/include/eunit.hrl").
-export([get_state_id_from_locations/2]).
-export([get_locations_from_state_id/2]).
-type locations()::{DogLocation::integer(),
BunnyLocation1::integer(),
BunnyLocation2::integer()}.
-spec get_state_id_from_locations(locations(), integer()) -> integer().
get_state_id_from_locations({DogLoc, Bunny1Loc, Bunny2Loc}, Nlocs) ->
StateId_dog = get_state_id_of_dog(DogLoc, Nlocs),
StateId_bunnies = get_state_id_of_bunnies(Bunny1Loc, Bunny2Loc, Nlocs),
StateId_dog * ((Nlocs * (Nlocs - 1)) div 2 + Nlocs) + StateId_bunnies.
-spec get_state_id_of_dog(integer(), integer()) -> integer().
get_state_id_of_dog(DogLoc, _Nlocs) -> DogLoc.
-spec get_state_id_of_bunnies(integer(), integer(), integer()) -> integer().
get_state_id_of_bunnies(Bunny1Loc, Bunny2Loc, Nlocs) ->
Diff = abs(Bunny1Loc - Bunny2Loc),
I = Nlocs - Diff,
J = min(Bunny1Loc, Bunny2Loc),
((I-1) * I) div 2 + J.
-spec get_locations_from_state_id(integer(), integer()) -> locations().
get_locations_from_state_id(StateId, Nlocs) ->
K = (Nlocs * (Nlocs - 1)) div 2 + Nlocs,
StateId_dog = StateId div K,
DogLoc = get_dog_location_from_state_id(StateId_dog, Nlocs),
StateId_bunnies = StateId rem K,
{Bunny1Loc, Bunny2Loc} = get_bunnies_locations_from_state_id(StateId_bunnies, Nlocs),
{DogLoc, Bunny1Loc, Bunny2Loc}.
-spec get_dog_location_from_state_id(integer(), integer()) -> integer().
get_dog_location_from_state_id(StateId_dog, _Nlocs) -> StateId_dog.
-spec get_bunnies_locations_from_state_id(integer(), integer()) -> {integer(), integer()}.
get_bunnies_locations_from_state_id(StateId_bunnies, Nlocs) ->
I = trunc(math:sqrt(2*StateId_bunnies + 0.25) + 0.5),
J = StateId_bunnies - (((I-1) * I) div 2),
Diff = Nlocs - I,
Bunny1Loc = J,
Bunny2Loc = J + Diff,
{Bunny1Loc, Bunny2Loc}.
%% UNIT TEST
-ifdef(EUNIT).
state_test() ->
%% Nlocs = 2, two locations 0, 1
%% all possible states are (listed in nature number order) 6 in total
%% (0). 0:{dog, bunny}, 1:{bunny}
%% (1). 0:{dog, bunny, bunny}, 1:{}
%% (2). 0:{dog}, 1:{bunny, bunny}
%% (3). 0:{bunny}, 1:{dog, bunny}
%% (4). 0:{bunny, bunny}, 1:{dog}
%% (5). 0:{}, 1:{dog, bunny, bunny}
?assert(get_state_id_from_locations({1,0,1}, 2) =:= 3),
?assert(get_state_id_from_locations({0,0,1}, 2) =:= 0),
?assert(get_locations_from_state_id(2, 2) =:= {0,1,1}),
?assert(get_locations_from_state_id(5, 2) =:= {1,1,1}).
-endif.
对状态完成了编码操作后，我们就可以按自然数顺序遍历状态，根据当前状态，找出下一个潜在状态。移动状态需要根据当前游戏的结构图，因此下面我们研究如何建模、编码游戏结构。
游戏结构模型
建模游戏的图，分成两部分：建模顶点(Location)和建模边(Path)。
顶点有自己的唯一编号以及可能会有Icon，所以它可以是一个key-value的store，具体实现可以就是Association Lists，只要接口抽象足够，后续如果不满意性能再改也很容易。由于顶点编码从0开始，并且不会改变，所以我们可以选择array获取随机访问的性能。
边首先至少需要有两个顶点，然后需要一个布尔标记是否有向，一旦有向则需要能判断出方向（一个简单的实现是写在前面的顶点是源）。边上还需要有先决条件，根据我为数不多游戏经历，可以设计成两个list，每个元素都是与的关系，第一个list是表明必须有，第二个则必须没有(not)。也需要能基于顶点快速搜素到关联的边。为此我们可以把所有的边存成一个array，然后构建起始位置的索引(location到边序号的映射)。
整合上述讨论，用如下的Erlang代码实现模块puzzle_struct:
-module(puzzle_struct).
-include_lib("eunit/include/eunit.hrl").
-export([get_locations_icons/2, create_puzzle/2, get_location_paths/2]).
-export_type([puzzle_struct/0]).
%% Empty location can be thought as a special case:
%% there is a null icon. Location Id is started from 0.
-type locations()::array:array(atom()).
-type path()::{IsDirected::boolean(), V1::integer(), V2::integer(), YesLabels::[atom()], NoLabels::[atom()]}.
-type paths()::array:array(path()).
-type path_index()::dict:dict(Key::integer(), Value::[integer()]).
-type puzzle_struct()::{Locations::locations(),
Paths::paths(), V1_Index::path_index(), V2_Index::path_index(),
Nlocs::integer()}.
-spec get_location_paths(puzzle_struct(), integer()) -> [path()].
get_location_paths({_Locs, Paths, V1_index, V2_index, _Nlocs}, LocId) ->
P1 = case dict:find(LocId, V1_index) of
{ok, P1s} -> P1s;
error -> []
end,
P2 = case dict:find(LocId, V2_index) of
{ok, P2s} -> P2s;
error -> []
end,
[array:get(I, Paths)
|| I <- sets:to_list(sets:from_list(P1 ++ P2))].
-spec get_location_icon(integer(), locations()) -> atom().
get_location_icon(Id, Locations) ->
Size = array:size(Locations),
case Size >= Id of
false ->
array:get(Id, Locations);
true ->
erlang:error("array index out of bound")
end.
-spec get_locations_icons({integer(), integer(), integer()}, locations()) -> [atom()].
get_locations_icons(State={_DogLoc, _Bunny1Loc, _Bunny2Loc}, Locations) ->
lists:filter(fun (A) -> A /= nil end,
[get_location_icon(Loc, Locations) || Loc <- tuple_to_list(State)]).
-spec create_index_from_paths(paths(), integer()) -> path_index().
create_index_from_paths(Paths, KeyPos) ->
L = lists:sort([{element(KeyPos, Path), I} || {I, Path} <- array:to_orddict(Paths)]),
dict:from_list(array_agg(L)).
-spec create_puzzle(paths(), locations()) -> puzzle_struct().
create_puzzle(Paths, Locations) ->
{Locations, Paths,
create_index_from_paths(Paths, 2),
create_index_from_paths(Paths, 3),
array:size(Locations)}.
-spec array_agg([{A, B}]) -> [{A, [B]}].
array_agg(L) ->
array_agg(L, []).
%% no data left, we are done, just return the result;
array_agg([], Agg) -> Agg;
%% just start, put the 1st data into agg result
array_agg([{Key, Value}|L], []) ->
array_agg(L, [{Key, [Value]}]);
%% still in the same group, agg the data into it
array_agg([{Key, Value}|L], [{Key, Values}|Agg]) ->
array_agg(L, [{Key, [Value|Values]}|Agg]);
%% group is changed, add a new agg
array_agg([{Key1, Value}|L], Agg=[{_, _Values}|_]) ->
array_agg(L, [{Key1, [Value]}|Agg]).
%% UNIT TEST
-ifdef(EUNIT).
array_agg_test() ->
L = [{a,1}, {a,2}, {a,3}, {b,5}, {c,4}, {c,2}],
?assert(array_agg(L) =:= [{c,[2,4]},{b,[5]},{a,[3,2,1]}]).
puzzle_struct_test() ->
%% use the demo 12.24
Locations = array:from_list([carrot, house, null, null, tree, null, bone]),
Paths = array:from_list([
{false, 0, 1, [tree], []},
{false, 1, 2, [bone, carrot], []},
{false, 2, 3, [house], []},
{false, 3, 4, [house], []},
{false, 4, 5, [], []},
{true, 5, 3, [], []},
{false, 3, 6, [], []},
{true, 2, 6, [], []},
{true, 6, 5, [], []}
]),
{_, _, V1_index, V2_index, N} = create_puzzle(Paths, Locations),
?assert(N =:= 7),
?assert(lists:sort(dict:fetch(3, V1_index)) =:= [3, 6]),
?assert(lists:sort(dict:fetch(5, V2_index)) =:= [4, 8]).
-endif.
状态转移图
计算下一个状态的时候，需要把状态编号转换为具体的locations，上面的Erlang程序用一个三元的tuple::{DogLocation, Bunny1Location, Bunny2Location}来表示，注意由于我们选择了🐰是不区别的，因此在上述locations中🐰位置是升序（Bunny1Location < Bunny2Location）。
下一状态是移动某个Object产生的转移，需要选出所有Object可能尝试的Path，同时还需要验证Path上的先决条件。有了所有的基础设施后，这部分并不难。我们在完成图搜索算法后，实现。
路径搜索算法
有了状态图，希望找到一条从起始到终点的路径就是很经典的图算法了。Dijkstra算法可以完成。但这里我们的状态转移图，每条边权重都一样，其实这就是一个宽度优先搜索BFS可以解决的问题了。
BFS的本质就是中间状态的存储数据结构是队列Queue (FIFO)。我们还需要记住搜索的历史。搜索的过程会记录已经扫描过的点，记录每个点的时候，附加记录一个前继即可。搜索需要快速访问状态的邻接关系，因此我们想办法优化这块的访问性能。
这部分代码如下是Erlang的graph模块:
-module(graph).
-include_lib("eunit/include/eunit.hrl").
-export([new/0, add_edge/2, bfs/3]).
-type edge()::{From::integer(), To::integer(), Action::any()}.
-type graph()::[edge()].
-type index()::dict:dict(integer(), [integer()]).
-type indexed_graph()::{array:array(edge()), index()}.
-type queue()::[integer()].
-spec new() -> graph().
new() -> [].
-spec add_edge(edge(), graph()) -> graph().
add_edge(Edge, Graph) -> [Edge|Graph].
-spec bfs(graph(), integer(), integer()) -> [any()].
bfs(Graph, Start, End) ->
IndexedGraph = index_graph(Graph),
VisitedSet = dict:new(),
Queue = [Start],
bfs(IndexedGraph, Queue, End, VisitedSet).
-spec bfs(indexed_graph(), queue(), integer(), dict:dict(integer(), {integer(), any()})) -> [any()].
bfs(_IndexedGraph, [], _End, _VisitedSet) ->
erlang:error("search failed");
bfs(IndexedGraph, [S|Q], End, VisitedSet) ->
Edges = get_all_next_edges(IndexedGraph, S),
NextS = [{To, Action}
|| {_, To, Action} <- Edges, not dict:is_key(To, VisitedSet)],
NewQ = Q ++ [To || {To, _}<- NextS],
NewVisitedSet = lists:foldl(fun ({To, Action}, Dict) ->
dict:store(To, {S, Action}, Dict)
end, VisitedSet, NextS),
case dict:is_key(End, NewVisitedSet) of
true ->
fetch_search_path(NewVisitedSet, End);
false ->
bfs(IndexedGraph, NewQ, End, NewVisitedSet)
end.
-spec fetch_search_path(dict:dict(integer(), {integer(), any()}), integer()) -> [any()].
fetch_search_path(VisitedSet, End) ->
fetch_search_path(VisitedSet, End, []).
fetch_search_path(VisitedSet, State, Actions) ->
case dict:find(State, VisitedSet) of
{ok, {Prev, Action}} ->
fetch_search_path(VisitedSet, Prev, [Action|Actions]);
error ->
Actions
end.
-spec index_graph(graph()) -> indexed_graph().
index_graph(Graph) ->
EdgesArray = array:from_list(Graph),
L = lists:sort([{From, I}
|| {I, {From, _To, _Action}} <- array:to_orddict(EdgesArray)]),
Index = dict:from_list(array_agg(L)),
{EdgesArray, Index}.
-spec array_agg([{A, B}]) -> [{A, [B]}].
array_agg(L) ->
array_agg(L, []).
%% no data left, we are done, just return the result;
array_agg([], Agg) -> Agg;
%% just start, put the 1st data into agg result
array_agg([{Key, Value}|L], []) ->
array_agg(L, [{Key, [Value]}]);
%% still in the same group, agg the data into it
array_agg([{Key, Value}|L], [{Key, Values}|Agg]) ->
array_agg(L, [{Key, [Value|Values]}|Agg]);
%% group is changed, add a new agg
array_agg([{Key1, Value}|L], Agg=[{_, _Values}|_]) ->
array_agg(L, [{Key1, [Value]}|Agg]).
-spec get_all_next_edges(indexed_graph(), integer()) -> [edge()].
get_all_next_edges({EdgeArray, Index}, S) ->
case dict:find(S, Index) of
{ok, NextEdgeIds} ->
[array:get(Id, EdgeArray) || Id <- NextEdgeIds];
error ->
[]
end.
%% UNIT TEST
-ifdef(EUNIT).
graph_test() ->
%% 0
%% / \
%% 4 1
%% | \ |
%% 3 ——2
%% \ |
%% 5
E1 = {0, 1, '0->1'},
E2 = {1, 2, '1->2'},
E3 = {0, 4, '0->4'},
E4 = {4, 2, '4->2'},
E5 = {4, 3, '4->3'},
E6 = {2, 3, '2->3'},
E7 = {2, 5, '2->5'},
E8 = {3, 5, '3->5'},
G = add_edge(E1, add_edge(E2, add_edge(E3, add_edge(E4, add_edge(E5, add_edge(E6, add_edge(E7, add_edge(E8, new())))))))),
?assert(bfs(G, 0, 5) =:= ['0->4','4->3','3->5']).
-endif.
主程序
这部分实现主程序:
- 载入游戏模型
- 构建状态转移图
- 图搜索求解
完整的代码实现请参考 https://github.com/kainwen/dog_bunny_puzzle 。最终的程序只用了一个模块，图的部分使用了Erlang自带的digraph。也可以直接BFS。
1227的demo图片为
建模的文本文件是：
7
house
tree
null
carrot
bone
null
well
9
1-->0;bone
1~~2
2~~3
3-->1
3~~0
0~~4;well
4~~5;house
3-->5;house
5~~6;tree
4,6,6
4,3,3
1227的demo跑出的结果如下：
2> io:format("~p~n", [dog_bunny_puzzle:solve("src/demo1227.txt")]).
[{move,dog,from,4,to,0},
{move,dog,from,0,to,3},
{move,dog,from,3,to,1},
{move,bunny,from,6,to,5},
{move,dog,from,1,to,2},
{move,dog,from,2,to,3},
{move,dog,from,3,to,0},
{move,bunny,from,5,to,4},
{move,dog,from,0,to,3},
{move,dog,from,3,to,1},
{move,bunny,from,4,to,0},
{move,bunny,from,6,to,5},
{move,dog,from,1,to,2},
{move,dog,from,2,to,3},
{move,dog,from,3,to,5},
{move,bunny,from,5,to,4},
{move,bunny,from,0,to,3},
{move,bunny,from,3,to,1},
{move,dog,from,5,to,6},
{move,bunny,from,4,to,0},
{move,dog,from,6,to,5},
{move,dog,from,5,to,4},
{move,bunny,from,0,to,3},
{move,bunny,from,1,to,0},
{move,bunny,from,0,to,3}]
ok
3>
Demo的视频如下：
2022.12.28更新
本想玩儿一下今天的，结果发现它们不讲武德，弄了两只🐶，我昨天的代码写死了一只🐶。好吧，两只的改起来很容易，请参考 https://gist.github.com/kainwen/c8260a7da06bc3c09584d60c4bbf7d0e, 如果是任意只，状态压缩有点没想清楚。
