iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 28
3
Software Development

活用python- 路遙知碼力,日久練成精系列 第 28

【小白馬的程式大冒險】Day28- 黑白羊爭過河,無可奈何之橋

(注意: 本劇本有許多天馬行空的元素,喜歡看傳統教科書者請斟酌閱讀)
給還沒看過本故事的讀者序章傳送門

前情提要: 小白馬來到石壁前,上了一個四位數密碼鎖,提示說要實作出一個函數回傳密碼。底下是昨天小白馬想出的實作內容…

小白馬的第二試煉-續

實作函數enterPassword(Str)找到每個單詞之間的空白數量。
範例: (為了讓讀者們看的清楚,這邊先以表示空白。)

input: The□□□secret□□□□password□□□is□□□□□5678.
output: 3435 (中間空白數量依序為3、4、3、5)

若是有人正在看著這畫面的話一定很滑稽,
一匹馬拿著筆電坐在山洞的石壁前打程式。
我是住在小瑪星球的居民小白馬
原本我身邊有著很多高科技產品而過著愜意的生活,
誰知道突然被一隻法力高強的巫師盯上要我參加程式試煉,
現在就在這烏漆馬黑的鬼地方了…

要得到空白的長度啊…
到底我要怎樣取得「空白」呀…
我腦筋是真正的一片「空白」,
要說空白的話我想到的就是字串的split()函數了。
我試著敲下這串程式碼:

Str = "The   secret    password   is     5678."
def enterPassword(Str):
    return Str.split()
    
print(enterPassword(Str))

結果為['The', 'secret', 'password', 'is', '5678.']
如果不是要求空白長度,
而是要求每個單詞的長度簡直輕而易舉,
只要把函數回傳改成return list(map(len, Str.split()))就好了嘛。
等等,我腦中浮現了一幅經典的錯覺圖…

https://ithelp.ithome.com.tw/upload/images/20190930/20117114cTUPej9TY8.png

圖地反轉的靈閃

我有個絕妙的點子可以解開這個問題了,
有時很配服自己的靈閃(小瑪語: 靈光一閃的意思)呢…
這幅黑白圖,當你把黑色當背景,想必你看到的是一個燭台吧。
但若你反過來將白色當背景,就會看到兩側的人臉。
這邊的The secret password is 5678.這幾個字就彷彿是「圖」一樣,
而我看不到的「空白」,就是背景,
那麼既然如此,只要將「空白」和「字」互換就可以「看」到空白了。
在這美妙的靈閃中,
我修改程式如下:

Str = "The   secret    password   is     5678."
def enterPassword(Str):
    trans= ''.join(['A' if c==' ' else ' ' for c in Str])
    return list(map(len, trans.split()))
    
print(enterPassword(Str))

函數中,我寫了一個列表生成式,將空白字元全換成了A,其它字元全換成了空白。

也就是說,原來字串是
The   secret    password   is     5678.
經轉換後會變成
   AAA      AAAA        AAA  AAAAA     

躲在背景中的空白變成了字元A「浮現」出來了。
此時一樣用我原本的方法list(map(len, trans.split()))
便可以得到那串一堆A字元的長度了。

看來,俗話說有數學細胞程式就寫的好,
藝術細胞有時也行。
我上傳了這個函式,
石壁順利打開了。

第二章- 無可奈何橋

石壁後的世界,一座「無可奈何橋」連結著山路的兩側,
橋的兩端,住著「黑羊族」與「白羊族」,
由於橋很狹窄,寬度只能容納一隻羊通過,
無奈今天黑、白羊兩族又在爭著過橋了,如圖:
https://ithelp.ithome.com.tw/upload/images/20190930/20117114YBug3CwNCw.png

橋由7個石柱支撐著,黑、白羊在兩側僵持著不想退讓。
白羊老大率先問候:「黑羊兄,做啥呢?」
在小瑪星球上,羊族是高傲族群,
牠們發展出來的方言也是非常的精煉,
牠們的羊語可能比我們的python語言更簡潔呢,
彷彿要把講話的口水省去一般,
主詞、動詞、受詞隨著心情省略也是常有的事。

黑羊老大回道:「走這橋,白羊兄先退後?」
原來一個正常的敘事句「走這橋」,
果然被白羊老大聽成「走著瞧」。
白羊老大不服輸的回:「吾白羊高貴,字典無退後二字。」
黑羊老大有被激怒:「那看誰角力強!」
一下子氣氛緊張起來,
彷彿隨時雙方會用羊角衝過去,
無奈橋太窄了,
一不小心會墜谷的,黑、白羊只好硬是僵持著…

彷彿若有光

「復前行,欲窮其林。林盡水源,便得一山。山有小口,彷彿若有光。」
我是小白馬,剛剛解完山壁謎題太開心了,
正好吟首<桃花源記>,慶祝出了石洞又看到光啦。
我繼續跋涉著,
接下來的山路盡是單行道倒也不怕迷路。

其實過了第一關後,
我心裡踏實許多了,
倒也不像第一次親眼看到魔法時那麼恐懼了。
我原以為程式試煉該像西天取經一樣,
歷經九九八十一難才能煉成,
但想想也就三關而已,
咬牙過去就是了。

魔王說過我的闖關順序是瑪呀之巔->無可奈何橋->巫師烏馬宮殿
我已經通過瑪呀之巔了,
前面那就是無可奈何橋吧。
咦咦?奇怪,怎麼橋上有六隻羊擋住我去路啊?
這樣我怎麼過橋啦…啊啊啊。
遠遠還可以聽到羊群爭吵的聲音。
黑羊老大咆哮著:「退下,則寬恕汝之無禮。」

奇怪,同樣在小瑪星球,羊語怎麼那麼難懂?文言文?
白羊老大回嗆:「同句回贈,退下則放你一『羊』。(註:原意是放你一馬,轉化為羊語)」
我是看的出來山羊們吵的很兇,可牠們的羊語方言還真難懂…
應該是牠們都想過橋但都不想後退的意思吧。

對了,這裡是「無可奈何橋」,
巫師黑馬的錦囊寫說感到「無可奈何」時打開它,
指的應該就是這狀況吧,
我打開錦囊,放著一張紙條:

當你打開這紙條時,想必你已經來到無可奈何橋了,
橋的命名由來是因為兩側住著強勢的黑、白山羊族群,
每當羊群在爭過橋,
其它路人都無法通行而感到無可奈何。

山羊族是高傲的族群,一旦上橋便不願意後退了。
牠們每次只能有一隻羊移動,
移動方式有:
1. 向前一格走到前方空格
2. 跳過對方一隻羊進入前面的一個空位(不可跳過兩隻羊)

牠們現在站的位置應該是這樣:
黑羊 黑羊 黑羊 空格 白羊 白羊 白羊
你可以假設黑羊=1,白羊=-1,空格=0,
用一個列表表示為[1,1,1,0,-1,-1,-1]。

注意若此時亂動的話,羊群便會阻塞而過不了橋,
比如說前兩隻黑羊各往前走一格,
變成[1,0,1,1,-1,-1,-1]。
那就真的別想過橋了。

好在現在有個完美的解法可以讓黑、白羊都過橋,
可以經過若干次移動後,讓羊的位置變為
白羊 白羊 白羊 空格 黑羊 黑羊 黑羊
列表表示就是 [-1,-1,-1,0,1,1,1]

你會問為什麼前面的羊到了還不上岸,
那是因為羊族民族性強,
羊老大會等羊兒就定位才上岸。

避免山羊忍不住衝過去打架,
趕快寫個程式找出這完美解法吧。

我其實本來擔心不知道怎麼過橋,
不過意外感覺這個錦囊是佛心來著,
把方法和目標寫的非常詳細啊,
可在我終於讀完這長長的錦囊指示後,
黑羊老大示威一樣的往前走了一格,
然後繼續吼著:「來吧,怕你呀?」
糟了,我閱讀速度太慢了嗎?

https://ithelp.ithome.com.tw/upload/images/20190930/2011711403SRjfkQJe.png

這難辦呀,讓山羊隨意走的話,
我到天黑都別想過橋了,
而且天黑的話,
橋名末三個字會讓人聯想到…,
呃呃…還是不去聯想了。
我一邊趕快打程式,一邊試著安撫羊群,
我喊著:「黑羊兄,白羊兄,兩位請稍安勿躁,我有個讓兩邊都不必後退而能夠讓兩族安然過橋的方法。」
白羊老大望向我:「哦,來了位馬兄?不叫吾族後退都行。」
黑、白羊協議了一下,
「馬兄,十五分鐘給出解OK?」
黑羊老大:「不然讓白羊族嘗嘗黑羊旋風角的厲害。」
白羊老大:「黑羊族才嘗我白雪之刃角。」
真是的…感覺就像小孩吵架一樣…
橋就這麼窄而已,你們到底在執著什麼啦…

n皇后問題的遞迴靈感

我在中巫師的斷網魔咒前,
曾讀過心原一馬老師Day21- 黑魔法,recursion,recursion depon一文中講遞迴技巧的黑魔法,
並在Day22- project2 - 遞迴之經典八皇后問題這一篇漂亮的運用遞迴解了n皇后問題。
我總覺得山羊過橋問題很像是可以用遞迴黑魔法解的感覺。
感覺上,我假設goatmove(goats)這個函數可以找到山羊過橋問題的所有解法,
參數goats是個列表比如說[1,1,1,0,-1,-1,-1]
那麼它的解法可以由羊走的下一步所有可能解法得到。
應該能這樣說吧?
一邊回憶一馬老師n皇后問題的思路,
我一邊很快為程式打個草稿:
這邊設個默認參數move,記錄山羊走到結束位置的行動。

def goatmove(goats, move=()):
    if goats 達到終止條件:
        return [move]
    ans = []
    for 所有山羊可能的移動:
        ans += goatmove(移動後的goats, move+(某個山羊移動))

真的有點怕山羊一衝動就打起來了,
下面是很深的山谷,在橋上打架的話真的太危險了…
我趕緊將程式細節都補上:

def goatmove(goats, move=()):
    if goats==[-1,-1,-1,0,1,1,1]: #遞迴終止條件
        return [move]
    ans = []
    length = len(goats)
    for i in range(length): #檢查每隻羊是否能動
        if i<length-2 and goats[i]==1 and goats[i+1]==-1 and goats[i+2]==0: #向右跳
            new_goats = goats[:]
            new_goats[i], new_goats[i+2] = new_goats[i+2], new_goats[i]
            ans+= goatmove(new_goats, move+(i,"向右跳"))
        if i>1 and goats[i-2]==0 and goats[i-1]==1 and goats[i]==-1: #向左跳
            new_goats = goats[:]
            new_goats[i], new_goats[i-2] = new_goats[i-2], new_goats[i]
            ans+= goatmove(new_goats, move+(i,"向左跳"))
        if i<length-1 and goats[i]==1 and goats[i+1]==0: #向右走
            new_goats = goats[:]
            new_goats[i], new_goats[i+1] = new_goats[i+1], new_goats[i]
            ans+= goatmove(new_goats, move+(i,"向右走"))
        if i>0 and goats[i-1]==0 and goats[i]==-1: #向左走
            new_goats = goats[:]
            new_goats[i], new_goats[i-1] = new_goats[i-1], new_goats[i]
            ans+= goatmove(new_goats, move+(i,"向左走"))
    return ans
    
goats = [1,1,0,1,-1,-1,-1]
print(goatmove(goats))

我輸入初始位置[1,1,0,1,-1,-1,-1]做測試(因為黑羊老大剛剛擅自先移動了),
結果為:[(4, '向左跳', 5, '向左走', 3, '向右跳', 1, '向右跳', 0, '向右走', 2, '向左跳', 4, '向左跳', 6, '向左跳', 5, '向右走', 3, '向右跳', 1, '向右跳', 2, '向左走', 4, '向左跳', 3, '向右走')]
太棒了,找到一組解,
由於山羊移動可能有向右跳向左跳向右走向左走四種可能,
一時之間我想不到什麼好方法,
程式就這麼冗長了…
但總之救羊要緊。

支撐橋的七個石柱上恰好有0~6的數字編號
我程式解答(4, '向左跳')就是石柱編號4的羊往左邊跳的意思,
再繼續看(5, '向左走')就是石柱編號5。

指引過橋

此時的我像整頓交通的警察,指揮羊群過橋,
以滿足牠們都不想退後又想過橋的高傲。
我下第一道指令「4號 向左跳」,
只見白羊老大,真的來個華麗的跳躍,
躍過黑羊老大到了2號石柱。

https://ithelp.ithome.com.tw/upload/images/20191001/20117114PmgdVm6SKX.png

這一幕真的讓我嘆為觀止!
巫師的錦囊寫說牠們可以「跳過對方一隻羊」,
我還有點半信半疑,
看了這完美的跳躍後,
我不禁心想「天啊,你們羊族都練過輕功是不是?」
我繼續下達指令「5號 向左走」、「3號 向右跳」、「1號 向右跳」、「0號 向右走」、…
全部十四個指令下完了,
黑白羊站的位置真的從「黑羊 黑羊 黑羊 空格 白羊 白羊 白羊」變成
「白羊 白羊 白羊 空格 黑羊 黑羊 黑羊」了。
這大概也是我第一次覺得程式真的可以應用在生活上。
雖說這種奇特的生活可能不太常見就是了…

臨走前,黑、白羊還不忘問候個幾句,
白羊:「安然過橋,先放汝一羊。」
黑羊:「趕著過橋,不與汝計較。」

我是不太懂羊族方言啦,
不過該不會其實黑、白羊感情還不錯,
在享受鬥嘴的樂趣?

不然其實山羊都會輕功跳躍的話,
真想要決鬥的話,
早衝過去跟對方比武了,
也不會等我慢慢打程式了。

我通過無可奈何橋
在深山荒野中,
竟真有座城堡,
那就是巫師烏馬宮殿了。

說實在,我只在巫師寄給我的照片中看過牠,
想到即將見到本尊還是有點怕怕的,
畢竟牠光是寄封信給我就展示暫停時間的能力了。
現在想起,我仍對於小瑪星球上存在魔法這件事感到很不真實…
畢竟高科技產品用習慣了,
我真不太想相信世界上有魔法

城堡大門此刻開啟,
彷彿已經在迎接著我的到來…

未完待續…若喜歡本系列故事,歡迎追蹤小馬哦
小馬首次嘗試寫奇幻故事希望文筆還行


上一篇
【小白馬的程式大冒險】Day27- 行百里路半九十,鐵人賽末三篇會到達巔峰就是這個道理
下一篇
【小白馬的程式大冒險】Day29- 最後的試煉,跳躍吧馬兒
系列文
活用python- 路遙知碼力,日久練成精30

尚未有邦友留言

立即登入留言