為什麼我們還沒有萬能家務機器人?

2012將至，
為什麼我們還沒有機器人可以幫我整理衣服?
為什麼我們還沒有機器人可以幫我收拾房間?

或者更積極一些的問題
我們要克服哪些技術上的困難才能做出家務機器人?
哪個技術是我最感興趣的?

牢騷才發完，便發覺最近Honda公開了Asimo的最新情況 [1] (連結內含影片)
我們得到甚麼新東西?
1. 單腳跳，很有意思，不過還不知道有甚麼用
2. 時速 9km小跑，還不錯，當個跑腿小弟挺合適
3. 推餐車，單手轉開水壺蓋，並將水倒至紙杯中。Cool，有服務生的潛力。

唯一的遺憾是Sony向來保密，所以沒有內部的技術資料。我認為走開源路線的Willow Garage會有更好的發展。他們的PR2現在可以...幫你買三明治、做早餐，摺襪子。

Firebug幫你抓取網頁上Flash內顯示的圖片

好幾個月沒有新文章。這段時間本來想寫些 Perl 和 Web 技術的學習心得，但是總覺得沒啥好寫，要寫教學類的文章太花時間，而且也不會寫的比現有的文章更好；要寫最新技術也不成，自己還在入門的程度。考慮太多反而啥都沒寫。
後來想想反正我也不是靠blog吃飯，只要寫的東西能讓自己高興就好了，所以發了這篇短文 :)

由來是這樣的，最近在 PTT c_chat 版上看到關於 Creative Comic Collection 創作集的討論正夯(沒看過的人趕快到 http://digitalarchives.tw/Theme/CCC/CCC6/index.jsp 去看)。我覺得這是學界的國家燒錢計劃中成果相當好的一個。

CCC第六期的主題是青澀韶光-台灣女學生圖錄，我發現網頁上方的Flash有提供預覽的功能:
http://digitalarchives.tw/Theme/CCC/CCC6/CCC6_02.jsp
不過很可惜的是他的桌步下載只有一張而已啊 [1]

為了多抓幾張圖，我嘗試用Flash編輯工具來看看Flash裡面是否有圖，不過很可惜的是他的Flash是專門做幻燈片的，所以是在執行時才會載入圖片。

後來轉念一想，既然Flash是在執行時才向Server讀取圖片，那我只要知道Flash程式透過瀏覽器去哪邊抓圖不就好了。嘗試一下Firebug的網路連線監看功能，馬上就看出來啦。


http://digitalarchives.tw/Theme/CCC/CCC6/C6/large/01.jpg

http://digitalarchives.tw/Theme/CCC/CCC6/C6/large/03.jpg

不過圖片果然是被裁剪過的，這告訴我們不要只想偷別人的圖哪 XD，應該要直接向作者請求才對

[1] 桌步由此下載: http://digitalarchives.tw/Theme/CCC/download.jsp 蚩尤那張不錯，不過我最想要的是A士和Salah.D的那兩張 :)

初學 XSLT 心得: 將 XML 文件轉換成 MediaWiki 文件

這篇文章紀錄我接觸 XSLT 的心得，可供有興趣的朋友參考。

首先解釋一下主題，假設我們手上有一份 XML 文件，是一份紀錄書店銷售紀錄的 XML 文件，內容為各個分店所賣出的書籍和BD。

<?xml version="1.0"?>
<?xml-stylesheet type="text/xsl" href="store2wiki.xsl"?>
<sale>
    <store name="Taipei">
        <book ISBN="9784757733299">
            <title>バカとテストと召喚獣</title>
            <author>井上堅二</author>
        </book>
        <book ISBN="9784757735057">
            <title>バカとテストと召喚獣2</title>
            <author>井上堅二</author>
        </book>
        <BD EAN="4935228096671">
            <title>Madoka Magica Vol.1"</title>
        </BD>
    </store>
</sale>

這樣的文件，正常人類是不會想看的，連我自己打起來都很累。那個角括號看起來真的很不習慣。所以啦，為了要把這份文件做成易讀的格式，我決定用 wiki 的條列方式來呈現此文件，利用縮排來呈現 XML 中的樹狀結構。

• Store: Taipei
• Book (IAN=978-4757733299)
• title: バカとテストと召喚獣
• author: 井上堅二
• Book (IAN=978-4757735057)
• title: バカとテストと召喚獣2
• author: 井上堅二
  
• BD: (IAN=4935228096671)
• title: Madoka Magica Vol.1

這樣看起來是不是清楚多了?
wiki 的種類很多，我採用 Wikipedia 的系統 MediaWiki，用它的語法的話，文件必須寫成如下的形式:

* store: Taipei
:* book (IAN=9784757733299)
::* title: バカとテストと召喚獣
::* author: 井上堅二
:* book: (IAN=9784757735057)
::* title: バカとテストと召喚獣2
::* author: 井上堅二
:* BD: (IAN=4935228096671)
::* title: Madoka Magica Vol.1

每一行前面的星號是標明項目，冒號的數量表示縮排的深度。

問題定義完成。在開始之前，先解釋一些名詞
XML: 全名是 Extensible Markup Language，中文可翻成延伸標記語言。這是一種表示資料的方式。邏輯上來看，是將資料表示成樹狀結構，每個element都會有自己的屬性，並且可以擁有子element。不熟的朋友可參考 http://www.w3schools.com/xml/

XSLT: 全名是 XSL Transformations，可用來將XML文件轉換成另外一個 XML 或 HTML。不過當你了解他的轉換原理後，就會了解到他可以將XML轉成任何格式的文件。這也就是我這次嘗試使用XSLT將XML轉成MediaWiki的理由。

XSLT讓我們定義轉換XML文件的方法，簡單來說我們要提供的是一套規則，說明對於哪些element要施行何種轉換，瀏覽器會依據規則幫我們轉換文件。簡單的說，瀏覽器會從樹根出發，採用一個可以施行的規則，輸出對應的文字。一般說來在規則中會指示瀏覽器移動到子element，並繼續套用規則。

開始動工。我設計規則只有一條: 印出目前的 element 的所有屬性，每個一行，然後繼續處理子element。大約十多行 XSLT 就可以做到。

指定規則是用 template 指令: <xsl:template match="*">
我們用match來指定element的名稱，有符合的就會套用此規則，這裡採用了萬用字元*，所以可以對應到任何element。
接下來用<xsl:value-of select="name()"/>印出此element的名稱。接著是用<xsl:for-each select="@*">找出此element的所有屬性，注意到屬性的開頭是@。
以上三個指令就能讓我們作絕大多數的事，template是用來建立規則，value-of 是用來輸出文字，for-each是用來處理每個子element。


說起來簡單，麻煩的是要在每行的最前面加入冒號，這必須根據目前的深度來決定。
為了解決這個問題，我用了一個小技巧，由於在每個element我們可以使用 ancestor::* 取得他的祖先，這會是一個sequence，因此我使用 for-each 指令，每看到一個祖先element就印出一個冒號。請見第7行。
另外有兩個小地方要注意。

1. XML 中的空白字元: 回頭看看我們的 XML 檔案，裡面含有縮排的空白字元，但是我們輸出時不想要這些空白字元(還有換行符號!)所以加入第三行指令 <xsl:strip-space elements="*"/> 以去除這些字元，各位可以把這行拿掉看看會如何 :)
2. 將最內層的 element 和 parent 一起顯示: 你會注意到 title 和 author 這兩個 element 內部只含有文字，對於 XSLT 來說，文字也算是 element 的一個子 element，所以依照我們的規則，他會被顯示在下一行。但是我不想要這種結果，所以就採用了11~13行的手法，11行表示只套用內含文字的子element，然後12行印出換行，最後13行再套用剩餘的子element。

總計15行code搞定!

<?xml version="1.0" encoding="ISO-8859-1"?>
<xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">
    <xsl:strip-space elements="*"/>
    <xsl:output indent="no" method="text" />
    <xsl:template match="text()">:<xsl:value-of select="."/></xsl:template>
    <xsl:template match="*">
        <xsl:for-each select="ancestor::*">:</xsl:for-each>* <xsl:value-of select="name()"/>
        <xsl:for-each select="@*">
            <xsl:text> (</xsl:text><xsl:value-of select="name(.)"/>=<xsl:value-of select="."/><xsl:text>)</xsl:text>
        </xsl:for-each>
        <xsl:apply-templates select="text()"/>
        <xsl:text>&#10;</xsl:text>
        <xsl:apply-templates select="*"/>
    </xsl:template>
</xsl:stylesheet>

參考資料
[1] W3C 的官方文件 http://www.w3.org/TR/xslt
[2] FAQ 專區 http://www.dpawson.co.uk/xsl/sect2/sect21.htm

讓 Perl 走進你的生活

本文是用來回顧剛接觸 Perl 的心得，以及推薦新手跳入 Perl 所寫的。

從 1987 年 Larry Wall 發明 Perl 以來，今年 Perl 已經24 歲，可能比你我還年輕，不過以電腦語言的角度來看算是老了。筆者在多年前就已經接觸過 Perl，可惜當時覺得程式艱澀難懂，不如 C 來的直接。直到最近因工作需要重新學習，才發覺過往的偏見。

借用 Alan Perlis 的話: "A language that doesn't affect the way you think about programming, is not worth knowing." (若是一種語言不會影響你對寫程式的想法，那便不值得學習。)
而讓我改變對寫程式的想法的，便是 Learning Perl 這本書。

Learning Perl的作者 Randal L. Schwartz (以下簡稱 Randal)在書的第一章就指出，Perl是非常高階的語言，所以code的密度很高，長度只有相對應的C的四分之一到四分之三。我認為用一個中文字來表現Perl的編程精神就是"短"。短程式的好處不少，不論是閱讀時間或是寫程式的時間都比較短。這就像是自然語言中的成語，可以把一段故事濃縮成寥寥數字。

借用 Randal 第一章的程式碼來說明


while (<>) {
  chomp;
  print join("\t", (split /:/)[0, 2, 1, 5] ), "\n";
}

希望第一次看到 Perl 的朋友不要轉頭離開。
任何程式語言的目的都是為了幫助使用者解決問題，而不是折磨使用者。
這段Perl程式目的是: 依序讀取命令列中每個檔案的每一行，去除尾部的換行符號厚，依冒號分隔欄位，並列印出其中四個欄位的值。假設我們有下的檔案 data.txt:

Id:Name:Age:Gender:Height:Weight

001:John:20:Male:180:70
002:Alice:17:Female:160:50



當我們在命令列下這樣的指令時:

> perl program.pl data.txt

結果會是:

Id      Age     Name    Weight
001     20      John    70
002     17      Alice   50


如果你看到這裡，一定會想知道這段程式要怎麼解析，<>是甚麼? chomp是甚麼? join 和 split 是甚麼?
在此筆者不會做完整解釋，請隨著 Randal 一同進入 Perl 的世界即可，那過程會比我現在說明得更加有趣數十倍。不過我想帶給各位Perl這種所謂"高階"程式的精神，就是要符合使用者的自然習慣。我們可以用一種很不嚴謹的角度來看剛才這段程式。首先我們想要一行一行處理資料，所以就需要一個 while 迴圈，由於我們要從命令列指定的檔案讀出資料，這整件事就用一個名詞 <> 來表示，讀到一行資料以後要用冒號分隔，所以就使用 split。

至於讀者可能會問說，那讀入的資料是暫存在哪個變數呢? Perl認為這是可以省略的變數，所以動了一些手腳。就好比我們在日常生活中，你拿起一個裝水的杯子，下一個動作是喝水，你不需要再多說明我是從手上的杯子喝水的。

最後結尾放上 Learning Perl 這本書的封面，各位請不要拿錯了呀 :)

shuffling / random permutation

又到了野人獻曝的時間了 :)

最近和前輩在聊面試有那些問題可以出
前輩提到一個經典的問題：如何隨機排序一組撲克牌?
換個說法，就是要產生一種52張牌的排列。

前輩提到這個問題可以用排序演算法來解決。
我上維基查了一下，果然在Knuth的大作 The art of computer programming 中有給出兩個演算法 [1]。

假設我們要排序的陣列是 src，大小為N，以 0-based 作為索引方式。
第一個演算法是這樣的:產生另外一個陣列 a，給 a 中的每一個元素一個亂數，接下來對 a 排序，排序的同時將 src 內元素依相同順序移動。排序時可以選用任意的演算法，因此可以在 O(N lg N) 時間內完成。

Knuth 書中的第二個方法更有效率，只需 O(N) 時間即可完成。演算法是: 從 i=N-1 開始依次往前走訪陣列的每個位置，對於每個 i ，產生一個亂數 0<=j<i ，並交換 src[i], src[j]。以 python 來寫的話會像這樣:

for i in range(N-1, 0, -1):
    j = random.randint(0,i)
    src[i], src[j] = src[j], src[i]

有看過這些演算法的朋友會覺得到目前為止都是老調重彈，沒錯，請在往下看。我認為這兩個演算法其實是有關連的，第二個方法可視為第一個方法的特例: 也就是使用 selection sort 來做排序。selection sort 的想法為，每次從未排序的數列中挑出最大(或最小)的一個，將其移到排序完的數列。用簡單的例子來表現:

假設我們要按遞增順序排序這四個數字: 3 2 4 1

第一步是找出最大的數字 4，並放到陣列尾端
3 2 (4) [1] => 3 2 1 | 4

第二步會找到 3，並放到 4 的前面
(3) 2 [1] | 4 => 1 2 | 3 4

接下來會找到 2，順序不變
1 (2) | 3 4 => 1 | 2 3 4

排序完成!

觀察每一步的過程，可分成兩階段，第一階段是找出未排序數列中最大的數字，第二階段是交換到排序數列的開頭。其中第一階段原本要花費 O(n) 的時間以找出最大的值所在的位置，但是既然在第一個演算法中，每個位置的值都是亂數，所以我們可以直接從中隨機挑一個位置當作是最大的數字，這樣有相同的效果，而且時間複雜度只有 O(1)。

好，獻曝完畢 :p

以 selection sort 能夠說明第二個演算法是第一個方法的特例，也許嘗試其他排序法會帶來不同的發現呢。

[1] http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle#The_modern_algorithm

Kurukshetra Athena 來自印度的數學程式競賽

上週從 Project Euler 傳來一個數學程式競賽的消息。
競賽的網址如下:
http://www.athena.kurukshetra.org.in/

這個競賽的題目都是數學相關問題，包含動態規劃、數論和許多領域，厲害的人也許能夠不依賴電腦就算出答案哩。雖然今年比賽已經結束了，有興趣的人還是可以去看看題目，並期待明年的比賽!

我今年沒有花很多時間，一周的時間內只完成了七題 :p
Score: 700 (完成七題)
Rank: 241

Question 6

There are 52735727364727372 students and 2889221271829121 teachers in a school . On children's day each teacher brings x toffees with him/her . All the toffees are collected and distributed equally to all the students . At the end it was found that there was exactly one toffee remaining .
What is the least possible value of x ?


我的想法
恩，這是很經典的一個問題。
首先我發現到分配之後只剩下一顆太妃糖，這表示老師的數目a和學生的數目b是互質的。接著把未知數 x 和 a,b 關聯起來，並且引入一個輔助變數 y 來表示每個學生所拿到的太妃糖數目，寫成數學形式是:
ax-by=1

接著我去查詢兩個互質的數有甚麼關連，發現了一個形式相似的公式: Bézout's identity，此公式說對於任意非零整數a和b，令其最大公因數為d，則存在x和y使得 ax+by=d。

要解出 x 和 y 可使用 Extended Euclidean algorithm，用 python 來寫的話只需要六行，而且還支援大數運算，真是相當輕鬆。

def extended_gcd(a,b):

  """Return x,y satisfy ax+by=gcd(a,b)"""
  if a % b == 0:
    return 0,1
  else:
    r = extended_gcd(b, a % b)
  return r[1], r[0] - (r[1] * (a / b))

找到 x, y 之後回到原來的問題。理論上符合 ax+by=d 的 (x,y) 有無限多組，此題目要求我們找的 x 為最小的正整數，剛好 extended_gcd 演算法得到的就是題目所要的。

字串遊戲 -- 如何快速計算文章中每個字出現的次數?

最近讀了 Bentley 所寫的 Programming Pearls 的專欄15，討論的主題為字串。這本書在台灣的能見度似乎不高，基峰出了一本中譯本之後很快就絕版了，想買都買不到，現在我手上是一本英文版加上朋友從借來的中譯版:)
這本是值得一看的好書，強烈推薦。

看完專欄15後，忍不住手癢動手實驗一下。
第一小節的問題是，給你英文聖經的電子檔，請找出書中一共有多少個單字? 出現頻率最高的單字為何?

首先我到 http://printkjv.ifbweb.com/ 下載整本文字檔格式的聖經
此版本的聖經共有 4,397,206 個字元。

書中提供的第一個小程式是 C++ 版本，使用 map 作為存放單字的資料結構。map 的實作為平衡二元搜尋樹，所以加入單字或是尋找已出現過的單字的複雜度都為 O(log n)。
以下的程式是我稍微修改過的版本:

inline bool isletter(char c)
{
  return (c>='a' && c<='z') || (c>='A' && c<='Z');
}
string trim_nonword_char(string s)
{
  string sout;
  for(unsigned int a=0; a<s.size(); a++)
    if (isletter(s[a]))
  sout.push_back(s[a]);
  return sout;
}
void main(void)
  typedef map<string, int> mymap;
  mymap M;
  mymap::iterator j;
  string t;
  while(cin >> t)
  {
    string tb = trim_nonword_char(t);
    if (tb.size() > 0)
      M[tb]++;
  }
  int totalwords = 0;
  for (j=M.begin(); j != M.end(); j++)
  {
    cout << j->first << " " << j->second << "\n";
    totalwords += j->second;
  }
  cout << "Total number of words = " << totalwords << endl;
}

我們的mymap中，key的型態是string，而value的型態是int，用來儲存出現次數。18~23行從標準輸入讀入一個word，去除非英文字母字元後放入map之中。利用了map的強大能力，緊緊短短數行程式就完成了這個工作。25~29行印出每個word和他出現的次數，由於採用二元搜尋樹的實作，你會發現 word 是依照順序由小到大排序的。

至於第二個問題，如何依照找出頻率最高的單字，Bentley 建議可以使用另外一個map，使用頻率做為key，出現的單字做為value。由於數個單字有可能出現相同次數，所以我們使用 vector<string> 做為value來儲存這些單字。依此實做的C++程式僅有四行。

map<int, vector<string>> cmap;
for (j=M.begin(); j != M.end(); j++)
{
    cmap[j->second].push_back(j->first);
}

注意map的順序是由小到大，所以cmap裡面最後面才是出現字數最多的單字。

現在我們可以回答開頭的問題:此檔案共有804875個單字，其中有14683個不重複單字，出現頻率最高的十個單字為:


62910 the
39290 and
35055 of
13783 to
12884 that
12863 And
12547 in
9773 shall
9756 he
8985 unto

在我的電腦上處理這個檔案所花的時間為1.1秒，拜硬體的進步所賜，比起 Bentley 十年前所得到的7.6秒快了近十倍。

這就是最快的方法了嗎? 非也，Bentley在書中提到可以用 hash 取代 map 來加快速度。