果殼網(wǎng)已完凌停，不知道我發(fā)過的帖子什么時候會消失粱年，于是我要把它們搬到簡書。
但這篇不是搬運罚拟，只是想說一下這個帖子背后的故事……以及代碼台诗。
Wolfram|Alpha 在顯示計算或查詢的結(jié)果之前，往往需要思考一番赐俗。幾年前拉队，它在思考過程的中會顯示一個漂亮的圖案。現(xiàn)在那個圖案已經(jīng)變成了一個無聊的 COMPUTING...阻逮，不過網(wǎng)上還是留下了一點痕跡粱快，比如說知乎的這個問題：Wolfram|Alpha在搜索時出現(xiàn)的圖案有什么含義?和 StackOverflow 的這個問題：What is the cellular automaton shown as loading screen on Wolfram Alpha?
我也一直想知道這是什么圖案。它顯然是一個元胞自動機叔扼，大小不同的點表示不同的狀態(tài)事哭；而且狀態(tài)不止一種，因此肯定不是生命游戲瓜富，也不是生命游戲家族（Life-like）的規(guī)則鳍咱。但它思考的速度太快，我總是來不及看清它到底是什么規(guī)則与柑。
直到有一天谤辜，我在人人網(wǎng)上——當(dāng)時人人網(wǎng)還不是直播平臺——看到這么一個截圖：
不知那位同學(xué)用的是什么截圖工具丑念，能夠截得這么清晰涡戳，而且沒有掉幀∏郏總之，有了這個截圖椎眯，我就能把它導(dǎo)入到 Mathematica挠将，一幀一幀地慢慢看……并不能看出它是什么規(guī)則，甚至不能看清它有幾種狀態(tài)——最小的兩種點個頭差不多编整，只是顏色的深淺稍稍有點區(qū)別舔稀，肉眼不容易看清。不過我還是看出了一點規(guī)律：稍大一點的點會變得越來越大掌测，直到爆掉内贮，消失。而且汞斧，我還看到了這個一個振蕩子：
除了 Life-like 的規(guī)則粘勒，還有什么規(guī)則竞端？我在 Golly （最好的元胞自動機模擬器，沒有之一）的幫助里看到了一類叫 Generations 的規(guī)則庙睡，覺得和這個有點像事富。不過那里給的幾個 Generations 規(guī)則的例子和 Wolfram|Alpha 的這個元胞自動機都對不上。
Generations 的規(guī)則和 Life-like 的規(guī)則類似乘陪，每個細(xì)胞也有死活兩種狀態(tài)统台，下一回合的狀態(tài)由這一回合的死活、以及與它相鄰的活細(xì)胞的個數(shù)來決定啡邑。與 Life-like 不同的是贱勃，活細(xì)胞在臨死之前，還能茍延殘喘幾個回合谤逼，但死亡的過程并不受周圍的細(xì)胞影響募寨，最終也無法擺脫死亡的命運。
比如說森缠，那個叫 Frogs 的元胞自動機拔鹰，規(guī)則按 Golly 的寫法是 12/34/3。最后這個數(shù)字 3 表示它有三種狀態(tài)：一個是死贵涵，一個是活列肢，一個是正在死亡恰画。也就是說，一個活細(xì)胞在臨死前只能多活一個回合瓷马。前面的 12 說的是：一個活細(xì)胞要想繼續(xù)好好活著拴还，八個鄰居里活細(xì)胞的個數(shù)必須是1或者2； 34 的意思則是：一個已經(jīng)死掉的細(xì)胞要想活過來欧聘，周圍的活細(xì)胞個數(shù)必須是3或者4片林。
Wolfram|Alpha 的元胞自動機應(yīng)該也是 Generations 一類蒋伦，但肉眼不容易看出具體是什么規(guī)則弓摘。不過不要緊，我們還有 Mathematica痕届。直接看不出韧献，我們就把圖片二值化了看，拆成一個個連通分支來看研叫，數(shù)清了每個點周圍的活細(xì)胞個數(shù)再看锤窑。
當(dāng)年的代碼我沒有留著。下面的代碼都是新寫的嚷炉，用了不少這幾年才引進(jìn)的新函數(shù)果复。
首先當(dāng)然是導(dǎo)入圖片并去掉重復(fù)幀。我一開始沒發(fā)現(xiàn)截圖中有重復(fù)幀渤昌，導(dǎo)致結(jié)果很奇怪虽抄，還以為它不是 Generations 的規(guī)則。
CA = First /@ Split@Import["WolframAlphaCA.gif"];
先試著把第一幀二值化一下独柑，發(fā)現(xiàn)它還有一個框框：
Binarize[CA[[1]]]
摘掉黑框再二值化。二值化的閾值不能太低忌栅，以免最小的點消失车酣；也不能太高，以免相鄰的點連起來索绪。試了好幾個數(shù)湖员，0.85 是最合適的。
Binarize[ImagePad[#, -BorderDimensions@#], 0.85] &@CA[[1]]
看起來不錯娘摔。于是我就把每一幀都二值化了。順手還給它們反個色唤反，以方便下一步處理凳寺。
CABinarized = 1 - Binarize[ImagePad[#, -BorderDimensions@#], 0.85] & /@ CA;
現(xiàn)在每個細(xì)胞——死細(xì)胞不算——是這個圖片的一個連通分支。細(xì)胞的狀態(tài)對應(yīng)于連通分支的大小肠缨。于是可以用上 ComponentMeasurements 函數(shù)逆趋。
先來看看這些細(xì)胞的位置。還是先看第一幀晒奕，算出所有連通分支的重心闻书，把所有的橫坐標(biāo)和所有的縱坐標(biāo)分別從小到大排列：
Union /@ Transpose[Last /@ ComponentMeasurements[CABinarized[[1]], "Centroid"]]
結(jié)果是：
{{8.5, 18.5, 28.5, 38.5, 48.5, 58.5, 68.5, 78.5, 88.5, 98.5, 108.5,
118.5, 128.5, 138.5, 148.5, 158.5, 168.5, 178.5, 188.5, 198.5,
208.5, 218.5, 228.5, 238.5, 248.5, 258.5, 268.5, 278.5, 288.5,
358.5, 368.5, 378.5, 388.5, 398.5, 408.5, 418.5, 428.5, 438.5,
448.5, 458.5, 468.5, 478.5, 488.5, 498.5, 508.5, 518.5, 528.5,
538.5, 548.5, 558.5, 568.5, 578.5, 588.5, 598.5, 608.5, 618.5,
628.5, 638.5, 648.5},
{12., 12.2193, 21.5, 22., 31.5, 32., 41.5, 42., 51.5, 52., 61.5, 62.,
71.5, 72., 81.5, 82., 91.5, 92., 101.5, 102., 111.5, 112., 121.5,
122., 131.5, 132., 141.5, 142., 151.5, 152., 161.5, 162., 171.5,
172., 181.5, 182., 191.5, 192., 201.5, 202., 211.5, 212., 221.5,
222., 231.5, 232., 241.5, 242., 251.5, 252., 261.5, 262., 271.5,
272., 281.5, 282., 291.5, 292., 301.5, 302., 311.5, 312., 321.5,
322., 331.5, 332., 341.5, 342., 351.5, 352., 361.5, 362., 372.}}
可以看出相鄰的兩個點之間大概差10個像素，整個圖片中的細(xì)胞個數(shù)是 65 × 37脑慧。這里出現(xiàn)了一個很奇怪的 12.2193魄眉，是因為最下面一排有一個點只露出了大半。為了避免這種問題漾橙，我去掉了最外面的一圈細(xì)胞杆融，只取重心的橫坐標(biāo)在 15 和 645 之間楞卡，縱坐標(biāo)在 15 和365 之間的那些連通分支霜运。
然后看連通分支的大小。取了一下 Union蒋腮，發(fā)現(xiàn)圖片的每一幀淘捡，在去掉了最外面的一圈細(xì)胞之后，連通分支的大小都只有 {6, 9, 37, 69} 這么四種：
Union[Last /@
ComponentMeasurements[#, "Count",
15 < #Centroid[[1]] < 645 &&
15 < #Centroid[[2]] < 365 &]] & /@ CABinarized
于是這四種不同大小的活細(xì)胞和瀕死的細(xì)胞池摧，再加上死細(xì)胞焦除，一共有五種狀態(tài)。最初的截圖里分不太清的兩種狀態(tài)作彤，在這里分別對應(yīng) 6 和 9膘魄。
然后我們可以把這些圖片化成代表細(xì)胞狀態(tài)的數(shù)組，把 {6, 9, 37, 69} 分別換成 {1, 2, 3, 4}竭讳，死細(xì)胞還是用 0 表示创葡。
CAArray =
SparseArray[
Round[(#[[2, 1]] - {8.5, 12})/10] -> (#[[2, 2]] /.
Thread[{6, 9, 37, 69} -> Range@4]) & /@
ComponentMeasurements[#, {"Centroid", "Count"},
15 < #Centroid[[1]] < 645 && 15 < #Centroid[[2]] < 365 &],
{63, 35}] & /@ CABinarized;
如果它真的是 Generations 的規(guī)則，每個細(xì)胞在下一回合的狀態(tài)就完全由它在這一回合的狀態(tài)和周圍的活細(xì)胞的個數(shù)來決定绢慢。于是來算一算灿渴，看看是否如此：
Union@Flatten@
BlockMap[{#[[1, 2, 2]], Count[#[[1]], 1, {2}]} -> #[[2, 2, 2]] &,
CAArray, {2, 3, 3}, 1]
結(jié)果是：
{{0, 0} -> 0, {0, 1} -> 0, {0, 2} -> 0, {0, 3} -> 1, {0, 4} -> 0,
{0, 5} -> 1, {0, 6} -> 0, {0, 7} -> 1, {0, 8} -> 0, {1, 1} -> 2,
{1, 2} -> 2, {1, 3} -> 2, {1, 4} -> 1, {1, 5} -> 1, {1, 6} -> 1,
{1, 7} -> 2, {1, 8} -> 1, {1, 9} -> 2, {2, 0} -> 3, {2, 1} -> 3,
{2, 2} -> 3, {2, 3} -> 3, {2, 4} -> 3, {2, 5} -> 3, {2, 6} -> 3,
{2, 7} -> 3, {2, 8} -> 3, {3, 0} -> 4, {3, 1} -> 4, {3, 2} -> 4,
{3, 3} -> 4, {3, 4} -> 4, {3, 5} -> 4, {3, 6} -> 4, {3, 7} -> 4,
{3, 8} -> 4, {4, 0} -> 0, {4, 1} -> 0, {4, 2} -> 0, {4, 3} -> 0,
{4, 4} -> 0, {4, 5} -> 0, {4, 6} -> 0, {4, 7} -> 0}
結(jié)果中的這些數(shù)據(jù)是 {本回合的狀態(tài), 周圍的活細(xì)胞個數(shù)} -> 下一回合的狀態(tài)。比如說胰舆， {1, 3} -> 2 表示某個細(xì)胞的狀態(tài)是 1骚露，也就是一個活細(xì)胞；它周圍的活細(xì)胞個數(shù)缚窿，包括它本身棘幸，是 3；它在下一回合的狀態(tài)是 2倦零，也就是說剛剛開始死亡够话。這里同樣的鍵總是對應(yīng)同樣的值蓝翰，因此每個細(xì)胞在下一回合的狀態(tài)確實由這兩個數(shù)來決定。
我們還能看出女嘲，0 只會變成 0 或 1畜份， 1 只會變成 1 或 2，2 只會變成 3欣尼，3 只會變成 4爆雹，4 只會死亡。
果然是 Generations愕鼓。
再來算算這個規(guī)則在 Golly 里該怎么寫：
{Cases[%, ({1, x_} -> 1) :> x - 1], Cases[%, ({0, x_} -> 1) :> x],
Max@%[[;; , 1, 1]] + 1}
結(jié)果是 {{3, 4, 5, 7}, {3, 5, 7}, 5}钙态，也就是說它在 Golly 里叫做 3457/357/5。
這個規(guī)則的含義是：它有五種狀態(tài)菇晃。0 表示死册倒，1 表示活，2磺送、3驻子、4 都是死亡的過程。每個回合每個細(xì)胞的變化如下：
-
0-> 如果相鄰的活細(xì)胞個數(shù)是3估灿、5崇呵、7，則變成1馅袁，否則還是0 -
1-> 如果相鄰的活細(xì)胞個數(shù)是3域慷、4、5汗销、7犹褒，則保持是1，否則變成2 -
2->3 -
3->4 -
4->0
接下來我們把時間交給 Golly弛针。Mathematica 只負(fù)責(zé)畫圖叠骑。
