2011年10月24日星期一

1977

1977年什么也没有发生。今天,2011-10-24,也不是什么特殊的日子。
但是当混用python和awk时,神奇的事情就这样发生了。

os.system("awk '{print %s}' a.txt" % str(datetime.date.today()))

输出
1977

坑爹啊。。。

2011年10月16日星期日

Fwd: 分析笑话:数学系有三个班

“数学系有三个班”是真的,可我从来没听过这样有趣的对话:
先分析一下原版的吧,说来惭愧,还是老婆给我讲明白的呢。

数学系一共3个班。
男生:你是3班的么?
女生:原来你是2班的啊!
男生:你是1班的啊!


初始:
男生知道自己是2班的,男生知道女生不是自己班的,所以男生知道女生是1班或3班的
女生知道自己是1班的,女生知道男生不是自己班的,所以女生知道男生是2班或3班的
第一句话:
男生问女生是不是3班的,相当于宣布自己不是3班的,因为如果男生是3班的,他就不用问这个问题了。这里假设这两个人认识自己班的所有人,并且彼此知道这一点。
所以女生知道男生是2班的了。
第二句话:
女生说“原来你是2班的啊”,相当于宣布自己之前不知道男生是2班的,现在得到足够的信息知道了。
第三句话:
男生是如何推断出女生是1班的呢?
假设女生是3班的,那么女生只能知道男生是1班或2班的。那么男生告诉女生自己不是3班的并没有给女生提供任何新的信息。那样的话,女生就不足以推断出男生是2班的。这和第二句话不符。
所以女生只能是1班的。



趁老婆还在玩iCloud没去睡,再分析一个鬼谷子版的吧

一天,鬼谷子随意从2-99中选取了两个数。他把这两个数的和告诉了庞涓, 把这两个数
的乘积告诉了孙膑。但孙膑和庞涓彼此不知到对方得到的数。第二天, 庞涓很有自信的
对孙膑说:虽然我不知到这两个数是什麽,但我知道你一定也不知 道。随后,孙膑说:
那我知道了。庞涓说:那我也知道了。

这其实就是YaoQiZhi老师课上讲的Mr. S & Mr. M的故事,当时觉得好难啊,现在学了点python,觉得暴力破解法很直接,code也不过一屏。


from itertools import product
from collections import defaultdict
n=552
a0 = set([p for p in product(range(2,n), range(2,n)) if p[0]<p[1]])
print len(a0)
s=defaultdict(set)
m=defaultdict(set)
for (x,y) in a0:
        s[x+y].add((x,y))
        m[x*y].add((x,y))
print len(s)
print len(m)
#I don't know, you don't know
a2=set([(x,y) for (x,y) in a0 if len(s[x+y])>=2 and len(m[x*y])>=2])
print len(a2)
#I know you don't know
a3=set([(x,y) for (x,y) in a2 if all([len(m[p*q])>=2 for (p,q) in s[x+y]])])
print len(a3)
#you know
a4=set([(x,y) for (x,y) in a3 if len(a3 & m[x*y])==1])
print len(a4)
#I know
a5=set([(x,y) for (x,y) in a4 if len(a4 & s[x+y])==1])
print a5


ytwang$ time python v.py
150975
1097
77432
105205
4753
2058
set([(4, 13)])

real     0m18.002s
user     0m17.919s
sys     0m0.079s



计算复杂度的瓶颈在求a3,也就是“我知道你不知道”这句话蕴含了绝大多数信息量。




2011年10月10日星期一

Fwd: 内省+变长参数的lambda表达式

最近看某同事写的python代码写的很漂亮,不禁羡慕。
恰好另一个同事买了本python教程,便拿来学学。
写了个练习。

From Evernote:

内省+变长参数的lambda表达式

class Client:
    def __init__(self, endpoint):
        self.endpoint = endpoint
    def wget(self, query):
        url = "http://%s/%s" % (self.endpoint, query)
        import urllib
        #todo wget and return response
        return url
    def __getattr__(self, attr):
        return lambda **kargs : self.wget(attr + "?" + "&".join(["%s=%s" % (k, kargs[k]) for k in kargs]))
   
   
if __name__ == '__main__':
    a = Client("baidu.com")
    print(a.q(keyword = "s"))
    print(a.q(keyword = "s", charset = "UTF-8"))



结果


2011年10月6日星期四

滑雪板理论

我假设你滑的是双板。
当你倒在雪地里,发现两个雪板都不见了,那是最开心的。你可以立刻起身,东张西望,去捡你的雪板。你可以先捡左脚的雪板,再捡右脚的雪板,也可以先捡右脚的雪板,再捡左脚的雪板。你可以在雪地上自由行走,比穿着雪板的时候自由得多。只要不被后面失速的其他人再次撞到就好。
当你倒在雪地里,发现左脚的雪板不见了,右脚的雪板还在脚上,是很郁闷的。你的右脚别在那里,不仅不能发力,而且不能提供合适摩擦力。单靠左腿的力量又不足以起身。你有两种选择,要么等人来拉你一把,当然这意味这你将命运交给了运气和泊松过程,要么你用撑杆把右脚的雪板脱掉,如果你的撑杆没扔出去的话。如果选择后者,相当于你把问题规约成了两个雪板都不见了的情形。你可能知道这个问题解起来更容易,也可能是歪打正着。
当你倒在雪地里,发现左脚得雪板还在脚上,右脚得雪板却不见了,也是很郁闷的。你右腿的力量可能强些,因为你踢足球,但是单凭右腿起身仍有些费力。你无非多一种选择:拼了命地站起来。虽然教练不是这样教你的。
当你倒在雪地里,发现两只雪板都TM还在脚上,你可以像个婴儿一样哭了。你觉得很亏,因为不仅要费力把两只雪板一只只脱掉,从这白茫茫的斜坡上站起来,还要把这双雪板摆成平行于等高线的角度,小心穿进去。你觉得委屈,因为这比掉了一只雪板还要费事,却在外人眼里看来还挺幸运的。

然而,倒在雪地里,还是很舒服的,至少它是一个稳态。
滑雪最不舒服的时候,是你发现自己已经超速,失去了对身体平衡和速度的控制的时候。
你喜欢一切尽在掌控,你后悔干嘛要跑到中级道上来吃饱了撑的没事找罪受。
你感到身体正在向左倾斜,同时向右旋转,你努力回忆教学视频上的内容,大脑却一片空白。
你感受到梯度下降,同时感受到无法忽略的水平位移。
你盼望着奇迹发生,身体赶快恢复平衡,严格按梯度下降,然后安全地在紧支集外面着陆。
但是力不从心,你知道你坚持不到平地了,你重心在下沉,心里盼望着赶快进入另一种稳态,哪怕摔得很难看。
你盼望着摔得两只雪板都不见了才好,如果不能,摔得两只雪板都在脚上也行,无非费点事,脱掉爬起来再穿上。
你想赶快结束这个痛苦的"要摔还没摔,没摔就要摔"的该死状态。
你开始破罐破摔,给自己捣乱,右脚外脚掌向里扣,想引入一个扰动,把自己弄倒。
然而速度太快了,这点扰动简直蚍蜉撼树,无济于事。
你重心继续下沉,两腿僵硬,死盯着雪板的前尖,越来越害怕,心里除了念着"wo cao wo cao"就已经没有了任何建设性意见。
就在这时,你发现你已经开始减速了。抬头看看。是的,恭喜你,你已经到平地了。
这时你腿一软,pia,摔那儿了。

这不是看辛普森。

2011年10月4日星期二

上帝存在,帕斯卡说的

“我们既不知道上帝的存在,也不知道上帝的本质。然而我们将倾向于哪一边呢?……,这里进行的是一场赌博,…… 让我们来权衡一下在上帝存在的赌注中的得失。让我们估计这两种可能性,如果你赢了,你赢得所有;如果你输了,你却一无所失。因此,你就不必迟疑去赌上帝的存在吧。”
这是帕斯卡在他的《思想录》中说的。
这其实是说一个条件期望。在相信上帝存在的条件下,期望收益是正的。在不相信上帝存在的条件下,期望收益是0。中国民间关于鬼神等无法实证的事物是否存在,流传着一句神似的说法:宁可信其有。

在那个年代,不奇怪,帕斯卡身边有个和他一样对古典概率论痴迷的神经质,比如费马。
一个周日的下午,帕斯卡和费马在巴黎的一个咖啡馆觉得无聊,于是玩抛硬币。正面费马得一分,背面帕斯卡得一分,谁先得到10分谁赢,输的买单。
15次后,费马得8分,帕斯卡得7分。这时他们玩烦了,决定提前结束这个无聊的游戏。他们不是中国人,不会争着去买单。也不是美国人,不会evenly share the bill。
他们太无聊了,决定用一种他们认为公平的方式来结束这个周末。
于是帕斯卡管邻桌的教授借来了笔和纸。帕斯卡和费马在几轮争论后,最终接受了费马的解法:
游戏将在至多4轮后结束,只需要将2^4种可能的序列枚举出来即可。h表示正面,t表示背面,*表示费马赢。
h h h h * h h h t * h h t h * h h t t *
h t h h * h t h t * h t t h * h t t t
t h h h * t h h t * t h t h * t h t t
t t h h * t t h t t t t h t t t t

显然这16种序列出现的可能性相同,所以11/16的概率是帕斯卡买单了。因此,公平起见,帕斯卡付账单的11/16,费马付剩下的。

帕斯卡当时不会想到,这其实是金融工程中经典的风险资产定价问题。
假设账单价格为1法郎,对于帕斯卡来说,他收益是一杯咖啡,成本有两种可能,一种是自己请客,也就是赌输了,支付1法郎,另一种是费马请客,自己一分钱不掏。前者的概率为11/16。帕斯卡可以选择一路赌下去,碰碰运气,不过他选择了无风险投资,避免自己全盘皆输,因为局势已经不利于自己了。费马也同意这个无风险的方案,因为他可以立即套现,什么也没有做就立即赚到1/2-5/16=3/16法郎,落袋为安。
为什么帕斯卡此时必须支付11/16法郎?
如果帕斯卡支付的少于11/16法郎,那么费马将选择继续赌下去,因为他可以算出来,在当前情形下,赌下去期望的花费更少。
如果帕斯卡支付的多于11/16法郎,那么帕斯卡还不如赌下去。
所以帕斯卡没有其他选择,只能支付他的条件期望。
当然,这里假设帕斯卡和费马都是风险中性的投资者。要是其中一个或者两个是风险厌恶型或风险偏好型,就另当别论了。