童年時的遊戲有了新解法
算窯是我小時候和小夥伴常常玩的遊戲。尤其在夏天，三五個在樹蔭下，聽著知了鳴叫，吃著涼絲絲的冰棒——真是一段無憂無慮的童年時光。。。
這是一位朋友在部落格裡面介紹的遊戲規則：
這是我們這一帶兒玩得最廣泛的遊戲了，就是在地上挖十個坑，分兩排，一排五個。然後用50個珠子（一般是用楝棗子，就是楝樹的種子）每坑5個子。。。規則是：先走的一方全部抓起一坑的珠子，按逆時針方向，一個坑放一個珠子，手中珠子放完後，就抓起緊挨著剛放上珠子的一個坑的珠子，再往下一個坑一個坑地放。什麼時候正趕上相臨的坑沒有珠子的時候，那麼相隔一個坑的坑內珠子就全歸了先行的一方，*如果這個坑的相臨還是個空坑，那麼相隔的一個坑的珠子也同樣歸先行的一方*。。。接下來是另一方接著走，想抓哪個坑就抓哪個坑，方向和方法一樣，最後，看誰的珠子多，誰勝出。
其實玩之前，也會去想一個最優解，默默在心裡面走上兩輪就已經不錯了。但是多數情況下還是靠著猜來進行。現在有了一定的程式設計知識，可以考慮怎麼透過演算法來求取最優解。
這裡所謂的最優解是指：在已知每個坑石子分佈的情況下，給出抓哪個坑的石子來進行遊戲才能獲得最多的石子（這裡不考慮捎帶的情況，即遊戲規則中描述的斜體字）。
如果沒有玩過也沒關係，在紙上稍加模擬，很快就能熟悉。本文重點在於說明解題思路。
那我們怎麼算出來是哪一個位置呢？不如用最笨的方法，把每一位置都試一遍。
接下來，
我們應該抽象出遊戲的規則，據此編寫計算機所能夠執行的程式。
我們從規則中知道，石子抓取後逆時針進行丟放。但是程式中二維陣列的計算要比一維陣列複雜，比如生成二維陣列，會再巢狀一層迴圈。那麼我們有沒有方法簡化呢？
因為是兩行五列，不如把它簡化為一行十列。相當於把（2，5），（2，4），（2，3），（2，2），（2，1）位置的坑依次排列在（1，5）的後面。這樣我們就有了1行10列的陣列，在石子數量超過其後面剩餘的坑的數量的時候就可以從（1，1）的位置繼續。
那對於放石子，我們應該怎樣簡化呢？第一次抓取的石子在某一個坑放完後，緊接著就抓與它相鄰的坑接著放。那麼我們可以這樣想：如果抓取的石子數是
，那麼就給接下來的坑裡面的數字均加上1。如果某一次抓取的石子非常多，以至於能夠把10個坑迴圈1次以上，那麼就會存在有的坑裡石子的數量加2。這樣會出現一個問題：我們仍然會遇到2行5列的時候，擺脫不了迴圈計算，動態修改陣列數值的麻煩。
那麼不如這樣考慮：假設陣列A為變換後的1行10列的陣列。
表示第
個坑（注意到，這裡的i為程式中的陣列索引，從0開始）。為了避免迴圈計算每個坑中的石子，我們先將每一個坑裡面石子的數量展開為一個
![[1,1,1,1,1...1]](https://img.heatask.com/upload/website_attach/8LbArDoLqCKNkFpAV=-+UEezKGvh3mRdMwQApK7ABHP_VgDPteqjZdmQv_ekkC5yE-=JGcbyr_Ly6WiPtekoTBvzoHJhIwZ4o-WH7E9gj-xiw.jpeg)
樣子的陣列。然後用0補全該陣列兩頭。使得到的陣列長度正好為10的最小公倍數（稍後解釋，此處當時靈感一閃，快速捕捉到的）。定義
表示第
個坑中的石子組成的展開陣列。
表示第$i$個坑中的石子數量。
為
![[0,0,0,...0,1,1,1,1,1...1,0,0,0,...0]](https://img.heatask.com/upload/website_attach/sSrUqtsERUvVll6NDuI01_mFI-OWzw3el3bUo+uUnAadDPsgJasctrFP5frJonfzQ1iXsxBLNbmeQWZU9TWyym_b8LtZgMH-97aXsxBMNbmeQiZU9TYyym_a8LtZzqkCQ+Mwaj7nlFNpletg=k_6oYZoYmM+p0ayK.jpeg)
。其中
的長度
len_array
=
（
math
。
ceil
（（
this_value
+
this_index
+
1
）
/
len
（
A
）））
*
len
（
A
）
解釋一下
的組成：［0，0，0，0。。。0表示拿走石子的坑
之前的坑和當前拿走石子的坑
中的石子數量，長度代表包含的坑數。拿走石子的坑的數量（最後一個0）在程式碼中表示為
A
［
this_index
］
=
0
表示拿起坑中的石子數目展開後的狀態。0，0，0，0。。。0］表示其後補充數量，該數量正好為組成
的長度為10的最小公倍數（10為坑的總數量）。
在摺疊
之前，我們需要將它變為短陣列。
# 把長陣列分割為短陣列
short_array
=
［］
number_array
=
len
（
value_array
）
/
len
（
A
）
for
i
in
range
（
int
（
number_array
））：
short_array
。
append
（
value_array
［
i
*
len
（
A
）：
i
*
len
（
A
）
+
（
len
（
A
））］）
（
“這是短陣列{array}”
。
format
（
array
=
short_array
））
把長陣列分割為短陣列
short_array
=
［］
number_array
=
len
（
value_array
）
/
len
（
A
）
for
i
in
range
（
int
（
number_array
））：
short_array
。
append
（
value_array
［
i
*
len
（
A
）：
i
*
len
（
A
）
+
（
len
（
A
））］）
（
“這是短陣列{array}”
。
format
（
array
=
short_array
））
這樣，我們就可以透過摺疊
，並與拿走石子後的原陣列縱向合併為一個矩陣
new
。
# 因為取走了this_value 處的值，所以A［this_index］=0
A
［
this_index
］
=
0
np_A
=
np
。
array
（［
A
］）
#矩陣運算為二維陣列以用來合併
np_short_array
=
np
。
array
（
short_array
）
（
“原陣列拿走值之後 {array}”
。
format
（
array
=
np_A
））
（
“這是矩陣後的短陣列{array}”
。
format
（
array
=
np_short_array
））
new
=
np
。
concatenate
（（
np_A
，
np_short_array
），
axis
=
0
）
（
“將組合起來”
）
（
new
）
然後計算矩陣在
axis=0
方向上的累加。其累加和即為我們走完
坑中
個石子之後的新序列
next_array
。
（
“縱向累加，由上至下”
）
next_array
=
list
（
new
。
cumsum
（
0
）［
-
1
］）
（
next_array
）
透過等價變換，讓我們把問題進一步抽象和簡化。
再接下來就是不斷迴圈這種方式，
直到什麼時候正趕上相臨的坑沒有珠子
，就得到最後獲取的石子數量。由於我們無法得知會經過多少回合，且本回合的最終結果最為下一回合的起始，所以給一個終止條件，並使用遞迴方法完成後面的工作。
if
next_array
［
next_index
］
！=
0
：
self
。
calcu_array
（
next_index
，
next_array
）
else
：
（
“你最終得到的獎勵
%d
”
%
next_array
［（
next_index
+
1
）
%
len
（
self
。
A
）］）
return
next_array
［（
next_index
+
1
）
%
len
（
self
。
A
）］
最後，透過迴圈呼叫
calcu_array
方法，得到每一個位置
最終能夠獲取的石子數量，並組合為一個字典。求取字典最大值，並用
loc
函式得到最終結果。
在解決這個問題的每一步，我都會先思考真實的場景，模擬出常規情況，同時查出每一種特殊情況，然後再用邏輯進行抽象描述和概括。雖然說，能夠用邏輯描述出來，一定程度上就能透過程式設計的語言寫出來。但是寫之前或者寫完之後，一定要思考一個最簡單的模型出來——寫之前要思考怎樣寫才好，寫完之後在重構的過程中，要思考怎麼變得更簡單才好。
童年的小遊戲讓我和小夥伴一起消磨著漫長時光，而又在我長大成人後帶給我更多解決問題層面的樂趣。全身心投入進去，時光不僅過得飛快，還可能倒流——穿越時光，讓我回到了童年那個知了鳴叫的夏天。
完整程式碼（Python）修改完善後會放到github中。
