小松鼠嚇了一跳,有了魔法眼鏡後,這世界看起來完全不一樣了

2013年4月27日 星期六

用正常人的方式在 Go 裡面做大數運算

Go 裡面沒有 Operator Overloading 的功能,所以雖然內建 Big Integer,但長一點的計算會變得很醜,比方說你要算個 (5*2+3*6)%10 好了,樣子就會有點像是
a := big.NewInt(5)
a.Mul(a, big.NewInt(2))
b := big.NewInt(3)
b.Mul(a, big.NewInt(6))
a.Add(a, b)
a.Rem(a, big.NewInt(10))
更複雜一點的算式就更難懂了。其他像是矩陣、分數、向量、多項式或者任何自訂的計算 type,下場都一樣悲慘。
底下是利用內建的 parser,壤我們可以用正常人的語言在 Go 裡面計算。
雖然有人會說什麼失去了編譯時期靜態檢查的特性,但真要比除錯,寫個 E("(5*2+3*6)%10") 絕對比上面一串外星文出錯的機會比較小一點。
可以到 http://play.golang.org/p/Toqkc4XY2J玩玩看。

2013年4月25日 星期四

Go 1.1 達到類似 Python 的 map 及 list comprehension


Go 1.1 的 reflect 新增了 SliceOf, ChanOf,以及 MakeFunc。
SliceOf 及 ChanOf 可以達到類似於 Python 裡面的 list 及 iterator 的功能,MakeFunc 可以搭配 Call 使用,達到類似 decorator 的功能。
以下是簡單測試了一下 Python 的 map 及類似 list comprehension 的效果。


2013年4月15日 星期一

Google Jam 2013 資格賽題目的數學證明


這篇用英文打的,就不轉成中文了。原來的題目可以在這裡找到。

1 Problem A. Tic-Tac-Toe-Tomek

No math involved, but complex number is builtin in python and go, so I use to represent “ “, T, O, X. So if , then some one won.

2 Problem B. Lawnmower

Theorem. is a possible pattern if for every .
Proof.
Can be easily proved by induction on , where .
         
     

3 Problem C. Fair and Square

Let , where and . Denote by the -th digit of , then we have .
Assume is a palindrome, i.e., for every .
Let be the coefficient of of that is,

Theorem. is also a palindrome iff for all .
Proof.
( )
Trivial.
( )
Observe that for all . We prove the statement by mathematical induction on for .
Case :
Since and it is easy to see that . So .
Moreover, we also know that has digits and hence for all .
Case :
Suppose for all , we want to show .
By the induction hypothesis, we know that for all . So
On the other hand, Therefore, , hence
  
  
Corollary. is also a palindrome iff .
Proof.
.
( )
for every by Cauchy-Schwarz inequility.
( )
Trivial.
In particular, if , then .

4 Problem D. Treasure

Let be the set of all key types. Assume .
Construct a directed graph as following:
  • iff we starts with at least one key of type .
  • If , then iff there is a key of type in a box of type . for every palidrone by Cauchy-Schwarz inequility.
Denote by the number of boxes of type and the total number of keys of type (including the keys you start with and keys in boxes).

Theorem. All box can be opened iff for every , and there is a directed path from to in graph .
Proof.
( )
If , then we don’t have enough keys of type to open all boxes of type .
If there is no path from to , then it means we are unable to get any key of type .
( )
We prove this by induction on the number of boxes. Denote by the number of boxes.
Assume for every , and there is a directed path from to in graph .
Case :
Then all vertices in are leaves except and the type of the only box. So there must be an edge from 0 to the type of the box.
Case :
Suppose the theorem holds for the case with boxes.
There are at least one . Consider we open a box of type (that contains a key of type if possible). Assume we destroy the key and the box just opened, then we have a setting of boxes. In this setting, we still have for all . Let be the directed graph of this -box setting.
If , then all children of in become children of , can still reach all other types in .
Assume .
If , then we can open a box of type that contains a key of type .
Otherwise, because , we still hold at least one key of type after we open a box of type (and destroy the key).
Either way, . Therefore, for every child of in , either
1. (if a key of type is in the box we just opened), or
2. and so there is a path from to and then to .
So can still reach very vertex in .
By induction hypothesis, the remaining can also be opened.
  
  
By the proof of the theorem, there is a simple algorithm to open all boxes: open any box unless you have just one key of that type and box does not contain a key that can open itself.
However, this algorithm may not yield a "lexicographically smallest" way to open the boxes.
The solve the problem, you should open the box with smallest number such that either this box is the last one of type or there is still a way to get a type key.

2013年4月13日 星期六

悖論的演講投影片


這是今天在 IMO 第二階段選訓營的投影片內容,簡報內容改自以前通識課的演講。但聽眾不同,所以內容還是差異不少。一些東西有講,沒有在簡報裡。許多圖取自 wikipedia 的 CC 圖片,投影片裡沒有註明,但是演講時都會口頭提到。



2013年4月7日 星期日

魔術師的小朋友問題

(圖由 seanmcgrath CC-BY 授權)

緊接著 Party 魔術的互動表演後,你拿出繩子準備表演「剪繩還原」。

預想著熟悉到不能再熟悉的程序,你的嘴角不禁微微上揚。
如果說有什麼讓你得意的表演,那這套「剪繩還原」就是。
在幾個精心設計的橋段和對白之後,繩子將被觀眾剪成幾段。
然後,你會對繩子吹口氣,將早已由觀眾剪斷的繩子回復原狀。現場的氣氛將達到最高潮。
這不是連一般業餘魔術師也會一點的剪繩還原效果。
你手中的這條繩子,在配合獨門技法和心理鋪陳後,將會充滿不可思議的魔法。
這不是普通的剪繩還原,這是你的剪繩還原。
繩子是貨真價實的被剪斷了,而最後,繩子也紮紮實實的還原了。過程絕對透明,完全沒有任何作弊的可能。

你還記得上次表演後,觀眾驚奇的表情,不可置信的反覆檢查繩子,企圖找到一點蛛絲馬跡。

當然,他們沒有找到。

在確定沒有任何作弊的可能後,像數學證明一樣的必然,觀眾們只能承認事實只有一種可能性,那就是繩子真的還原了。

這樣,他們心滿意足的做出結論(或更貼切的說,再度確認):這個世界上確實存在著超越人類理解的神秘事物。

晚上,他們將伴著好夢入睡,以愉快的心情面對未來生活中的挑戰,懷抱希望!
你並沒有花太多力氣,就能記住了這些細節。因為每次表演後都是一樣的情形!沒有例外。
即使是最疑心頑固的觀眾,也一樣。就算是剛才那幾個小搗蛋鬼也一樣。
因為這是你的責任,你身為魔術師的責任。所以你希望能讓觀眾感受到驚奇帶來的愉悅感。

而「剪繩還原」從來沒有讓你失望過!

就在你拿出繩子後,突然聽見一位小朋友在台下大聲說:「我看過了耶...你是不是要學電視上大魔競的剪繩還原?」。

「天哪!我連剪刀都還沒拿出來啊。」你心中跑出來這樣一句話。

這麼直接的把梗破掉,那還怎麼變?好好的魔術就這樣被浪費了?我的剪繩還原就這樣被糟蹋掉了?

不過,那不是你心中跑出來的第一句話。雖然很容易就被忽略掉,但你腦海浮現的第一句話是:「我想拿個榔頭把釘子鎚下去」

一般人大概只會把它當成腦中那種不經意出現的靈光。因為和現在遇到的危機毫無關聯,所以很容易就一閃而過。
但這句話並沒有在你腦中一閃而過。你不是一般人。事實上,你非常清楚它是怎麼跑出來的。

「如果榔頭是你唯一的工具,那你會習慣把問題當成是釘子。」這是心理學家 Abraham Maslow 的名句。
其實你並不清楚 Abraham Maslow 和他的需求層次理論是什麼,又或者他在什麼場合下說過這句話名言。

你也不想知道。

你是在「如何處理搗蛋者」這本書的介紹裡看到這句話的。
也許在潛意識裡,你把小朋友當成了釘子。
不過,不需要什麼人本主義理論,也知道在這裡拿榔頭打小孩,似乎不太適當。這還真是個難題啊。

相當然爾,書裡應該有提到處理這種狀況的方法。

問題是你沒看過。

這次,你要靠你自己解決這個問題。

他為什麼會講這句話?他想說些什麼?
也許他完全沒有惡意。也許只是像「蔡依林,我在電視上看過耶。你是我電視上看過的同一個蔡依林嗎?」或者「搓牌我知道耶,你要學電影上賭聖的特異功能搓牌嗎?」。
你想,大概只要回答說「半對半不對,你等下耐心看看就知道我的意思了」
當然,你不用解釋半對指的是「剪繩還原」,而半不對則是說你不是學電視的,你的程序和梗更高級,更有趣。但只要這樣利用話語的模糊性,就能繼續保持懸疑性。
但問題的不光是他想說什麼。觀眾不只一人。更重要的可能是其他人怎麼解讀他的意思。

所以,你想好要怎麼回答了。

「小朋友,你好厲害喔,你一定了看很多電視吧」明褒暗貶,說不定等下回去,他一個星期就只能看一個小時電視了。算是給搗蛋者小小的懲罰吧。
不過小朋友顯然只能看到光明的,高興的點了點頭。

「所以,有多少人曾經在電視上看過用繩子魔術的?沒有關係,舉手給大家看看。」
當然,你注意到說的是「繩子魔術」,沒有必要把「剪繩還原」的效果一直重複先講。你也可以舉例說,像是綁人、打結這類的,提醒大家繩子的魔術有很多種。
但是現在,你覺得光是這樣說應該就夠了。你很小心,你很確定你還沒有真的承認你要變「剪繩還原」。當然你也絕對沒有否認。
也許跟一般人的常識相反,但魔術師其實是不能說謊的。至少不應該在表演時說。
你也注意到你說的是「繩子魔術」而不是「魔術」。因為你也不想有太多人舉手。雖然那不會是太大的問題。

「好的,那有多少人在現場看過呢?不只是在電視上而已喔!請舉手。」
其實這本來就不是什麼大問題。你的表演本來就有價值,你根本不需要誇大。現場看到的本來就比電視上看到要好得多。
籃球轉播跟現場看哪個好?
演唱會轉播跟參與現場演唱會哪個好?
在電視上看美國跟去美國哪個好?
這些是每個人都知道的常識,你只要提醒他們而已。
還是有好幾個人舉手,現在魔術的風氣挺不錯的,比十幾年前好太多了。但是你也不排除其中有幾個是想表現自己見多識廣的那種類型。

「那有多少人不只在現場看過,而且還上台當助手幫忙?」
剛才殘餘的幾隻手也放下了。不過即使還有一兩個人舉手也無妨。
因為很快就會被一堆手淹沒。
「現在,」你停頓了一下,「有誰想要上台來,不但能當助手幫忙,近距離看,而且還有機會施展魔法喔!想要上來幫忙的朋友,請舉起手來。」
經過你的提醒,觀眾意識到你表演的價值,瞭解到這個機會有多難得,也瞭解到拿電視上的表演跟現場表演比有多蠢。
你不用花太大力氣,因為這些是大家本來就知道的事實。
在許多擺動的手之中,你挑了一個適合當助手的觀眾上台。當然,你聽得到許多落選者帶點失望的聲音,但當你要他們為上台來幫忙的觀眾鼓掌時,掌聲依然非常熱烈。
你知道他們已經把自我移情到上台來的觀眾身上,一個因為這個難得機會能現場、即時參與神秘魔術表演而變得不平凡的平凡人。

接下來,修改一下程序吧,你想。改成讓觀眾吹口氣,讓繩子還原比較好。
因為你剛才說過,不但讓他上台當助手,還有機會施展魔法。也許跟一般人的常識相反,但魔術師其實是不能說謊的。至少不應該在表演時說。
咦,還是只能在表演時說謊?
你也搞不太清楚了。

──
2008年的舊文修改重貼

2013年4月2日 星期二

沒國際觀是因為媒體很爛,那然後呢?

最近你可能看到不少人在轉這篇清大彭明輝教授部落格的文章:台灣有一種病,很深,深到…………。內容大致上是說,台灣人欠缺國際觀,並非因為英文很差,而是因為媒體太爛。

我並非不同意他觀察到的現象。如果媒體增加國際新聞以及有深度的報導,的確會提升整體民眾的國際知識。

當然很多人會開始轉台,轉去看新聞龍捲風、台灣龍捲風或者狂愛龍捲風之類的東西。
但至少,看新聞鬼扯節目可以增加星際觀,還能訓練資訊過濾的能力。
本土長壽劇裡早晚會有跨國企業鬥爭,然後牽扯到國際政治軍事角力的劇情。順帶還可以介紹一些醫療科技,比方電子義肢、電子眼、換臉、複製人之類的,對劇情鋪陳應該很有幫助。
偶像劇也可以有像是與 CIA 情報頭子的浪漫邂逅,相知相遇、進而定情的故事。當然中間會穿插許多跟國際情勢息息相關的劇情,比方男主角有一筆征討利比亞的私人軍費無法兌換的落難情節,獲得女主角援助後,主角擊敗格達費,然後駕著直升機前來求婚。

所以我完全同意如果媒體增加國際深度,就會增加整體國民的國際觀的這個因果關係。
但全世界最沒用的就是這個「如果」。
這樣的說法,就像說:你被曬傷,並非因為你沒擦防曬油就出門,而是因為太陽太大。如果太陽沒有那麼大,就不會被曬傷了。

有用的是,要怎麼讓如果不再是如果。

媒體太爛已經是常識了。但原因呢?要怎麼改善?
媒體中並非沒有外國新聞的資訊,如文茜世界週報、公視新聞、還有一些時段比較少的國際新聞。但為什麼這麼少?是財團控制?還是民眾口味的問題?還是市場太小?
我不知道,但有很大的機會是,暫時很難改變這個情況。

就像我們知道地球與太陽的關係並非宇宙中星球的常態,但我們就是生活在地球上啊。

就是因為台灣媒體很爛,才要加強英文或其他外文能力,特別是聽讀能力。這樣,才能突破限制,得到需要的資訊。

當然我們也許會希望很多人來翻譯資訊,但我們真的願意讓這麼多有用人力來做這些事嗎?還是讓他們做些更有創造力的事情?這是需要計算的。

要改變媒體,並非不可能,而且是持續要做的事。但對個人來說,加強英文能力是現階段就可行,可以突破媒體限制的作法。

在你還沒想到怎麼讓太陽不要發出紫外線之前,看到別人宣導擦防曬油或著撐傘,其實不用憂慮別人不知道真正的原因是太陽太熱。
畢竟,如果不知道太陽太熱,為什麼要擦防曬油或撐傘?