Archive for the '無聊' Category

把舊屎寫上履歷表

2011/10/02

十年前,我讀中學時,曾經越級挑戰,代表香港到芬蘭參加國際電腦編程比賽。比賽分上下兩場,各歷時五小時。參賽者要在限時內編寫程式解決幾條難題,然後上載至中央主機,主辦單位以幾組不公開的數據測試,程式於極短時間輸出正確答案便得分,高分者勝。比賽的主要難度,在於程式需要作龐大的運算,若非應用較高深的算法,程式難以在短時間內完成執行。

其中一條問題,我毫無頭緒,只懂得以極慢的算法找出答案,若把這方法上載,程式必然超時,必得零分。於是我心生一計,在自己的電腦窮盡所有測試數據,以龜速找答案,然後把所有數據和答案都寫在程式碼裏。主辦單位測試時,程式只消在的程式碼裏找答案,一定夠快。

問題只有一個:程式將會過於龐大,遠超當時電腦能承受的負荷。不過我既然別無他法,最差結果頂多是零分,我就把幾百MB的程式碼上載至主機,可惜比賽結束時主機仍沒有反應。當晚大會的賽後報告,指有選手因為上載過大的程式碼,導致主機不勝負荷。於是,大會要更改下半場的賽例:程式碼不能大於10MB。

我當場的反應是:當局因我更改賽則,我好勁,這是壯舉,我贏不了比賽,我卻擊敗賽則!

未幾,我開始擔心,因為從隊友們的眼神語氣,感到他們未必接受這樣勇闖灰色地帶的行為。我們自小學習要循規蹈矩,考試最好滿分,十項最好全能,操行最好優異,卻從不鼓勵think-out-of-the-box。踏鋼索鑽空子,在香港不太歡迎。我怕別人指責我浪費代表香港的難逢機會;我怕別人責怪我不學無術只懂旁門左道。至幾年後,隊友們向他人介紹我時,仍然會語帶嘲諷地提及這個「壯舉」,我厚著面皮一笑置之,一絲後悔當日的魯莽。

最近,我開始在矽谷工作,跟同事談起這往事時,他竟然問:「為甚麼你不寫在履歷表上?早知你曾在國際賽搞事,開始時就對你友善一點,給你艱難複雜的任務。」然後,他侃侃而談和其他同事以前在故鄉搞事的事跡,不亦樂乎。我才發現,在科技界裏,原來「搞過事」是履歷表的重要項目,人們並不太欣賞循規導矩的乖乖,鑽空子、找漏洞這些旁門左道才是常態。

從兩種截然不同的反應,大抵可知哪個地方較容易接受新鮮事。政府曾幾何時要推動創意產業,我認為注定失敗。莫說要贏在起跑線上,我們自幼稚園時,學習循規導矩地做人的那天,已經輸給別人九條街了。

Related reading:
宋漢生:科投創業人應該學「壞」

(刊於同日《香港經濟日報》)

廣告

港交所網故障,我想到的是⋯⋯

2011/08/10

為甚麼黎明的風又強又西?

2011/07/05

美國公路網發達,公路旅行(road trip)很流行。

羅德島位處東岸,新公司卻在西岸。要麼搭飛機,要麼開車。

千里迢迢到美國,甚麼總得要一試。

心底還是個學生—錢沒幾個,時間多的是—於是決定試一試road trip。

兩週前變賣家當,然後浩蕩出發,目的地加州灣區。

到過華盛頓Lexington芝加哥,現今身處South Dakota,就是那美國總統山。

對幾個總統頭像,其實沒多大興趣。在華盛頓的博物館裏,已重溫過美國歷史,總統頭這樣的政績公程不算甚麼。不過,這個區域的山頭卻幾好行。

既然行山,不如露營。

豈知半夜忽現狂風,頭頂大樹窸窣作嚮,吹得帳幕半翻半倒,夜半四點,把我從夢中驅醒。凝望眼前快倒的帳幕,心裏滿是疑惑:昨午紥營還好好的,只有陣陣涼快的微風,為何黎明前風勢特別強?

紥營時分清了東南西北,我在營內認定風是從西面來的。難以於半塌的帳幕安睡,心裏一直罵:風呀風,為甚麼你又強又西?

為甚麼黎明前往往最冷?風特別強?我一直想呀想,有點點頭緒。

風勢又強又西,全因地球自轉。

地理書說,風總是由冷的地方吹到熱的。因為熱空氣比冷空氣輕,所以熱空氣上升,冷空氣留在地上。熱空氣上升後,騰出的空間就由旁邊的冷空氣流過來補充。

空氣流動,因此成風。

太陽每天由東面升起,然後花半天往西起。東面永遠較西面先見太陽,陸地因而較早受熱。假設其他因素不變,早上東邊的溫度總比西邊高。東方熱而西方冷,又強又冷又西的風就此而來。

想及此處,明白又強又西不過自然定律。於是又沉沉睡去。

翌日晚上,把車開到營西作掩護,風勢頓然銳減。謹此作記。

港版三中三,買六合彩零風險必贏方法!!

2011/05/20

買六合彩必贏方法。

唯一假設:只有一人(或一個集團)投注,大包圍買曬四十九個冧把。

累積多寶獎金約為八十五(百萬港元,下同),大包圍成本約為一百四十,扣除鋪草皮做福社會開支後,彩池約值一百六十一。

因為大包圍,所以必中一個頭獎,六個二獎,二百五十二個三獎,如此類推,見下表。

(注:中三程度組合數學問題。中五獎之注數 = 六個中獎數字揀四個 乘 四十二個無獎數字揀兩個 = \binom{6}{4} \times \binom{49-1-6}{2} = 12915

根據假設,只有一個人買,可準確算出每獎之中獎注數,以及派彩,見下表。

可得出獎金約一百六十一,扣除成本,賺二十一。

即,零風險下,賺二千一百幾萬。

成本(注數)

(1) = 13983816 * $10

$139,838,160
累積多寶

(2)

$85,618,703
本期彩池

(3) = (1)*0.54 + (2)

$161,131,309
細獎彩池

(4)

$26,790,400
大獎彩池

(6)=(5)-(3)

$134,340,909
中獎注數 每注派彩 獎金
頭獎

1

$60,453,409

$60,453,409
二獎

6

$3,358,523

$20,151,132
三獎

252

$213,240

$53,736,228
四獎

1260

$9,600

$12,096,000
五獎

12915

$640

$8,265,600
六獎

17220

$320

$5,510,400
安慰

22960

$40

$918,400
總獎金

(7)

$161,131,169
賺蝕

(7)-(1)

$21,293,009

現問:在相同假設下,贏錢之最低累積多寶為何?

從文字認識你

2011/03/25

這個word cloud好好玩:http://timc.idv.tw/wordcloud/zh/

圖中是敝博出現最多的詞語。好準。

所以話,我一向覺得世界應該係圍住我來轉。。。

如果有人唔google都知「從文字認識你」既出處,我地就係朋友。

近來閉關寫畢業論文。

書讀得少。諗頭也少。所以無野好寫。

為甚麼尾燈是紅色的

2010/11/11

汽車紅色的尾燈是個普世現象,無論在世界任何一個角落,在巴黎浪漫迷人的香謝麗舍大道,在美國四通八達的州際高速公路,在獅子山下貫通南北的彌敦道,在台北走九遍的忠孝東路,在北韓四野無人的十線公路,在秋名山上很杰倫冠希的山路,汽車尾燈的顏色,如受物理定律主宰著,都是紅色的。

問題是,為甚麼一定要是紅色?不可以是紫色?金色?黑色?

港產片《烈火戰車2之極速傳說》正道出答案。

鄭伊健跟陳豪練電單車,賭錢外side bet一隻腳,陳輸後就給鄭打跛。陳的胞兄任達華出獄後為弟報仇,跟鄭賽車,在觀塘繞道彩虹邨交匯處把鄭及其女友林熙蕾的坐駕撞落橋底,再迫鄭出走泰國。其後鄭的頭馬譚耀文主動邀任鬥車,任囂張地說「見到尾燈當你贏」,結果譚炒車身亡。後來鄭回港報仇,跟任再練一場,比賽尾段鄭出秘密武器氫氣加速器(類似《高智能方程式》雷神內一次只能用十秒的升壓渦),在將軍澳隧道裏把任遠遠拋離,鄭經過收費站(即終點)後,任下車失望大嘆「竟然連尾燈都看不到」。

答案的徵結,就是——看不看見尾燈。

各位可能會問,看不看見尾燈跟紅橙黃綠青藍紫有甚麼關係?

物理學上,有種現象叫多普勒效應

據維基,當波源和觀察者有相對運動時,觀察者接受的波的頻率與波源會有異。當兩者接近時,頻率變高,波長變短;當兩者遠離時,頻率變低,波長變長。比方說,當消防車朝自己駛來時,它所發的警號的波長變短,聲音變得尖銳;當駛過自己後,波長變長,聲音愈見低沉。

同理,光亦含有波的特性。當一件物件離自己而行,它就會變紅(紅色波長最長),天上的星星大多有這個特質,於是科學家推斷宇宙正在擴張,這稱為紅位移現象

回到車尾燈的問題,說到這裏,答案好明顯,因為在可見光的光譜裏,紅色的波長最長,再長就變成看不見的紅外線了。那就是說,如果車速足夠快地遠離其他車,把紅色尾燈的波拉長成紅外線,任達華就看不見你的尾燈,那麼,你就贏了。

紅色尾燈,顯然,是為賽車而設的。

誰說港產片沒教育意義?!

On Gull

2010/09/02

中譯鷗,海鳥之一種。

不知「鷗」是否為音譯,稱Sea Gull為「海鳩」實更貼切也。然「鳩」解小鳥,又失原意。

翻查字書,gull除解鷗外,亦可解容易受騙的人,更可作動詞用,指欺騙/蒙騙。形容詞為Gullible。

例句:
Workers had been gulled into inflicting poverty and deprivation upon themselves.
工人們曾被鳩進貧窮與互相剝削的困境裏。

I am angry with myself for being gullible, credulous and naive.
我為自己的易鳩、輕信和天真而憤怒。

The Inception of Computer Science (Spoiler)

2010/07/28

The Inception of Computer Science

Justin Yip
Brown University
Box 1910, Providence, RI02912, USA

Abstract

A recently released movie, Inception, illustrates human ability of inception, implanting ideas to others mind through dreams. The story line is based on “Little Harmonic Labyrinth” by Douglas Hofstadter, a professor of Cognitive Science at Indiana University. The key aspect of inception is to secretly implant ideas to the subject’s subconscious that he will never know it is implanted. This article discusses the movie in a computer science perspective, and argues that the movie itself is an attempt of inception of computer science concepts into the audience’s mind.

Procedure Call

In the movie, people enter and share the same dream via a device and the dream context is created by the mental projection of all dreamers. Cobb and his teammates dash in the subject’s mind and perform certain task, i.e. extraction or inception. When success, or dead, or timeout, the dreamer leaves the dream and returns to the reality. This mechanism indeed mimics procedure call in computer programming. Variables and objects (dreamers) enter a routine (dream) and perform some tasks, when they are done, they leave the routine and resume in the caller (reality).

Sometimes, the subject’s (for example, Fischer) subconscious is trained to guard against intruder, and he may also be well-informed about mind inception/extraction hence a single dream may not be suffice to carry the operation out. Multi-level dream is therefore applied. In a dream, Cobb sedates the victim again and enter another level of dream, dream-within-a-dream. They come closer to the subject’s subconscious and the subject is more apt to accept new ideas. The same thing is very common in computer science too. A procedure often invoke other procedures for a finer grained task.

Recursion

Indeed every procedure can invoke other procedure, and such process can go infinitely. Here we consider a special case: a recursion, a self-invoking procedure.

Cobb experimented it with Mal, his wife, they went into very deep level in the dream. It was good when it started, as they had so much time and they created their world freely in the dream. However, as time goes by, they lost track of reality. Mal failed to distinguish dream and reality. She thought the reality is yet another level of dream and killed herself in hopes of getting back to the “reality”.

This problem, in computer science, is commonly known as “Stack overflow error”. Stack is a piece of memory that stores information during a procedure call. When a procedure is invoked, the invoking program will store the current position and other meta-information in the stack. Once the procedure is terminated, it uses the meta-information stored in the stack to return to its caller. But computer has limited memory capacity. A finite amount of meta-information can be kept in the stack. When the stack reaches its limit and can no longer store more information, a “Stack overflow error” is casted and the program goes to limbo. The human brain may not be as discrete as a computer, which leads to a problem of failure to detect when the brain capacity is reached. Instead, the brain may overwrite information in a lower level, and this might be the cause of Mal’s problem of messing up dream and reality.

Cobb attempts to eliminate this problem alternatively. He forbids Ariadne to create the dream context using the details in reality. He insists that the dream world should contain some inconsistent structure (inconsistent in the sense of physical reality) to allow the dreamer to distinguish dream and reality. He is essentially trying to prevent self-invoking calls. In addition, a Totem, which has different behavior in reality and dream, is also used. The Totem is actually the base condition in a recursion.

Garbage Collection

Under normal circumstance, death in a dream results in awakening in reality. When special sedative, which provides stability for multi-level dream, is used, a dead person will be sent to the state of limbo and the person in reality will turn into a state of coma, and all his memory will be gone. Saito is severely injured in the gun fight at the first level, and eventually he is dead in the third. This poses a problem for Cobb, as Saito agreed to remove Cobb’s criminal charges when the inception is succeeded. If Saito losts in the limbo, coma in reality make him impossible to honor the arrangement and Cobb will be arrested immediately at the time he reaches the immigration. Therefore Cobb needs to secure Saito in limbo. It took Saito 50 years to be located by Cobb.

If we regard each passenger in the first class cabin as a memory space, a man in coma is essentially an useless piece of memory. Such piece of useless memory is merely a waste of memory space. We call it memory leak. The object is lost (all memory references are disconnected from the root) in the course of a procedure leads to lost of a person in reality. Therefore dead people in the dream has to be garbage collected, no matter actively or passively, by someone to reclaim the memory space. Cobb is the garbage collector. First he collected Mal, then Saito. Garbage collection exists in most modern programming languages, it makes our life so much easier. Thanks Cobb!

Exponential Runtime

In optimization, we often tackle NP-complete problems by enumerating all possible solutions (in a smart way). Enumeration is often implemented as a depth-first-search, which is usually a self-invoking procedure. Every level in the search procedure usually invoke a polynomial number (to the input size) of self-invoking calls. As a direct consequence, assume every procedure takes the same running time, the whole search takes exponential time. Despite enormous effort has been made to squeeze the runtime, the optimization researchers are all in limbo thanks to the NP-hardness nature.

Our dream goes faster than the reality. 5 minutes in reality equals to 1 hour in the dream. The same mechanism applies in dream-within-a-dream. It took a split seconds for the van to drop from the bridge to the water, while so much things happened in the deeper level. It is the best demonstration of exponential explosion when we tackle NP-hard problems. Cobb and Mal created the whole world in dream, since they had so much time.

This also imposes a substantial line of research. Instead of spawning the search procedure into thousands of sub-processes to arrays of hundreds of multi-core processors, hoping one of them gets into the right branch and find a solution, we may simply dive into a dream of deeper level and solve all kinds of NP-hard problems there, and report the wall-clock time in reality. What a good way to tweak experiment! I guess I can publish 1000 papers a year. As the reader would expect, I will write them in the dream.

Conclusion

The director has hidden a vast amount of computer science concept in the movie. It is obvious that he is trying to implant computer science concepts into the audience mind. Nonetheless, of course, the author of this paper, being a computer scientist, is fully aware of that.

Acknowledgement

Thank you Pascal Van Hentenryck for an insightful discussion (GC is actually his idea).

%d 位部落客按了讚: