2010年10月21日 星期四

Mathematica研究:rookPolynomial

rookPolynomial[list_] :=
Plus @@ Flatten@
Apply[Times,
Flatten[list //. {a_ /; Union@Flatten@a == {1, x} :> a,
{{{a_, c_}}, b___} :> {b, {{1}}, {{x}}},
{a : {{x} ..}, b___} :> {b, a},
{{b_, d___}, c___} :> {c, {d},
Append[Select[{d},
Length[#] <
2 || (#[[1]] != b[[1]] && #[[2]] !=
b[[2]]) &], {x}]}}, {3}], {2}]

以上是mathematica的code。這演算法特別適合rule based的寫法,寫出來很簡潔。使用方法:
rookPolynomial[{{{1,1},{1,2},{1,3},{2,1},{2,2}}}],數字是格子座標,視為矩陣的index。

西洋棋中的城堡可直行橫行,在任意形狀的棋盤上放置數個城堡,如果這些城堡不互相攻擊,則每個城堡必須彼此不在同行同列上。rook polynomial就是每種排列法的生成函數,特別適合用來解決有限制的排列問題(或稱瓶頸指派問題)。例如八個人排成一列,甲不排1,3,5位,乙不排2,3,4位之類的,或是更複雜的問題(例如不規則的棋盤形狀),這種問題在高中時通常是用排容原理來計算,但是限制位數一多,或是棋盤形狀非常不規則,那排容原理會顯的非常繁雜,這時rook polynomial就可派上用場了。

值得注意的是,如果沒有禁止的位置,棋盤形狀是正方形,那是有公式可計算的。手動計算rook polynomial時,可以做行列交換換得一個更容易計算的棋盤,上面的程式就沒那麼聰明,不過基於電腦運算的快速,還是會比手算來得快上許多。詳細情況可以查找離散數學的教科書,或是wiki,上面的程式可以幫助你檢驗答案。實作時,如果禁位少,也可利用直接對禁位作rook polynomial,再利用排容原理計算。

2010年10月15日 星期五

Mathematica研究:常用的rule 和 functional program,以Quick Sort 為例

一行實現quick sort演算法:
QuickSort[l_List] :=
l /. {x_, y__} :>
Join @@ QuickSort /@ {Select[{y}, # < x &], {x},
Select[{y}, # >= x &]}


/. :expr/.rules
applies a rule or list of rules in an attempt to transform each
subpart of an expression expr.

_ :_ or Blank[]
is a pattern object that can stand for any Mathematica expression.
x_ gives a name to _ as x
x:{pattern} gives a name to pattern as x


__
:__ (two _ characters) or BlankSequence[]
is a pattern object that can stand for any sequence of one or more
Mathematica expressions.

___ :___ (three _ characters) or BlankNullSequence[]
is a pattern object that can stand for any sequence of zero or more \
Mathematica expressions.

.. :p.. or Repeated[p]
is a pattern object which represents a sequence of one or more \
expressions, each matching p.

:> :lhs:>rhs or lhs:>rhs
represents a rule that transforms lhs to rhs, evaluating rhs only
after the rule is used.

@@ :Apply[f,expr]
or f@@expr replaces the head of expr by f.

/@ :Map[f,expr] or f/@expr
applies f to each element on the first level in expr.

& :Function[body]
or body& is a pure function. The formal parameters are # (or #1), #2, etc.

2010年10月11日 星期一

戀夏五百日

戀夏500日

這是一部解析戀愛的電影,卻不是一部男女戀愛的電影。它對於男女之愛是站在一個批評論述的立場,而不是帶觀眾享受一段愛情的故事。

片中男女主角想法都相當偏執,男方認為有命中注定的真愛,女方認為愛情只是幻想,奇怪的是兩人居然談起戀愛。之後女方很突兀的分手之後男方忽然性格大轉變,認為愛情只是幻想,女方卻接受了男方的想法,認為有命中注定的真愛,甚至還跟別人結了婚。之後男方又遇到一個女生,領悟到雖然都只是巧合,但何不接受它呢?所以男方學習到了一個中庸的愛情觀,這就是電影所要告訴我們的:沒有命中注定的愛,但也不是全然幻想。正所謂「耳遇之而成聲,目遇之而成色,乃造物者之無盡藏,而汝與我之所共適也。」。白話來說就是會遇到,雖然只是巧合,但是是否接受利用,全操之在己,就算愛情只是腦中分泌的化學物質作祟,那又如何呢?雖然不應該像小女生(片中的小女生例外,她是本片當中的智者)幻想一個非你不可的愛,但是自己依然可以認真看待,並獲得幸福。

雖然影片揭示了愛情的真相,但並不能說它是一部精采的電影,這可從我打了三十分鐘的瞌睡可以得到證明。年輕男女經常荷爾蒙分泌過剩,這部電影就是一劑良藥。但是年紀稍大一些的大概會覺得很無聊,反而「男女生了沒」裡面有更多葷笑話可看。這也證明了一件事:「真實」的電影不會好看。

2010年10月1日 星期五

幾個將棋要點

有關交換棋子:西洋棋和象棋中,你吃我後我吃你可以簡化局面,但是在將棋中剛好相反,交換後反而更加複雜,尤其是角行的交換。以下所講只是原則,並非絕對如此。

1. 振飛車不換角。振飛車通常會用美濃圍為主來加強王將橫向的防禦,弱點是王將斜前方易被角行牽制受攻,所以交換角行通常是不好的。

2. 居飛車不換車。居飛車通常以矢倉圍為主,加強王將縱向的防禦,弱點就是在8段的橫向。換飛車之後等於開放對方飛車打入8段,通常不會是好事。

另外,進攻方交換棋子之後,通常是進攻方有利。因為交換棋子反而增大了棋子的機動性,原本要在棋盤上慢慢走,變成持駒之後卻可以放在幾乎任何地方(除少數禁手之外)。

有關金將銀將:金將的威力在自陣和敵陣中最大,在棋盤中央反而行動受限。銀將相反,在棋盤中央廝殺最激烈的戰場威力最大,這是因為可以斜行的關係。棋盤中央充滿步兵,直行的道路易被阻擋,但斜行就可穿插自如。常可看到敵陣中有金銀將橫向並排的組合,這時誘使金將斜行或銀將直行是個策略,因為這使他們無法迅速回到原本的位置。

有關防禦:將棋雖然攻殺非常激烈,但是防禦也同等重要。不管怎麼圍玉,最後雙方一定會進行到互拆對方圍玉,這時拆的快的就贏了,什麼時候考慮暫停進攻對防禦進行補強,這有賴於對速度的判斷。互攻的情況下,如果雙方都不防禦,誰能先一步詰棋?

另外,就是如何應付飛車角行之類的大駒來襲?最好的方法是能夠將對方反彈回去,這樣對方會浪費手順,而自己趁機補強。因為大駒來襲通常會先遠攻,這樣攻擊範圍較廣,而且可以有下一步升變的效果,這時要讓他彈回去得先引誘他逼近自陣,再利用金銀步等逼他返回原位或後退幾步,這樣對方攻勢沒變,自己已補強防禦並且賺到手順。

有關攻擊:通常是要三顆棋仔以上的配合,光靠兩顆通常很難成事。棋盤中央的戰鬥發起人幾乎都是步兵,最常見的狀況是飛角銀就位之後,棄步做進攻開端,以突破對方某一筋為主要目標。不過棄步之後必須確定自己之後有子可打入,不然也沒用。

持有桂馬時,角行是你的好朋友,角行在斜方向牽制步兵之後,常可造成桂馬可直接在步兵前頭打入的局勢。桂馬可沒有拐馬腳,是唯一可以跳過對方棋子來吃子的駒,持駒有桂馬時通常比棋盤上的桂馬可怕。