Codes, Notes & Scribblesabout programming, music and my life

做来自己用的，没什么技术含量。原图均来自ffffound。

上学期“概率统计与随机过程”课的笔记，用xmind做的思维导图，仅供参考。。

Screenshot

要从新浪搬到Wordpres，网上广为流传的方法是利用blogbus的博客搬家服务获得blogbus格式的xml，然后再用一个Python写的脚本把它转换成WordPress认识的格式。但是这种方法在最近新浪博客升级以后就失效了。于是自己用现学的scala写了一个小程序，搬家时能保留标签、目录、评论及评论回复这些信息。

猛击[这里]下载。注意，此程序仅支持2010年初的新版新浪博客，之前或之后的版本都不支持。

要运行程序，你需要确保已经安装过JRE。双击运行后显示如图界面，填入自己的博客地址（不要省略“http://”），然后点击“Start”即可。这时“Start”按钮变为灰色，标题栏显示“Extracting”。等待几分钟，当标题栏显示为“Done”、“Start”按钮重新变为可用时，程序所在目录下会出现一个blog.xml文件。把这个文件直接导入WordPress就可以了。

代码也打在jar包里了，MIT协议。欢迎报告bug。

下面是废话。

恩由于新浪用了ajax，评论信息是通过xhr异步读取的，用一般的方法没法抓到。我纠结许久，最后是用了非常ad hoc的方法解决的，不知道有没有什么什么不太麻烦的通用解决方案呢。

再扯两句scala。我都想不起来当初具体是怎么想到要学scala的，也许是为了了解下函数式编程，也许只是想在jvm上有一个喜欢的语言吧——Java写起来太不爽了；Java社区的低效和保守也已经开始显出C++的影子。

scala确实是非常强大和灵活；我在见到一些颇富技巧性的hack之后都有些怀疑scala社区的风气会不会慢慢变得像C++社区一样过分热衷技巧的炫耀。不过scala的设计目标就是以较简单的语法规则获得最大的scalability，不需要通过挖掘语言规范里的犄角旮旯来实现一些必要功能，所以不会像C++一样成为一门本身已相当复杂，却还需要别人反过来教语言发明者如何使用的语言。

scala毕竟表现力比Java强太多，代码也简洁太多。比如这次我需要实现一个抛出异常后重试若干次的逻辑，只需定义一个函数：

def tryFor[T](times: Int)(op: => T): T = {
  if (times <= 0) throw new RuntimeException("Operation failed.")
  try { return op } catch {
    case e: Throwable => e.printStackTrace
  }
  tryFor(times - 1)(op)
}

然后这样使用：

val source = tryFor(5) {new Source(url)}

程序就会不断获得网页源代码，并在5次失败后抛出异常。Java实现同样的东西可不会如此优雅了。又如下面这段代码返回一篇博文xml：

private def generateEntryXml(entry: BlogEntry) = {
  <item>
    <title>
      {entry.title}
    </title>
    <wp:post_date>
      {dateFormat.format(entry.postDate)}
    </wp:post_date>
    <category>
      {entry.category}
    </category>
    {for (tag <- entry.tags) yield <category domain="tag">{tag}</category>}
    <content:encoded>
      {xml.Unparsed(handleNewLines(entry.content))}
    </content:encoded>
    <wp:status>publish</wp:status>
    {for (comment <- entry.comments) yield generateCommentXml(comment)}
  </item>
}

注意，xml标签直接作为scala的源代码的一部分在代码中出现！虽然我觉得这样会使scala语言多出一种“特殊情况”，增加语言的复杂性，但不得不承认这样的设计确实非常优美简洁。

我比较看好scala，以后自己做跑在jvm上的东西scala应该是首选语言。推荐有兴趣的童鞋也了解一下。

在打算了很久之后，终于从写了三年多新浪博客搬出来了~

一方面新浪的限制太多，而且每次系统升级一下都可能会破坏我的一部分内容。另一方面，作为一个21世纪有理想有抱负的IT民工，唯一的blog竟然开在新浪实在是情何以堪啊。而在墙内根本选不出理想的BSP情况下，我抱着“DNS白名单一定不会实施”的幻想，终于决心独立出来了。

两年之内不会换的域名：http://blog.tomtung.com/

效果就是每次启动终端时都有一个小动物什么的讲一句有意思的话：doubanclaim469c1764e4db1ecf

说话的东西和说的话都随机出现。这个效果是我在Linux Mint里面看到的，感觉很有爱。下周考Unix环境编程，周末恶补一下，顺便写这个小脚本练手。

以我在用的 ubuntu 为例。首先确保安装 fortunes 和 cowsay 两个包。前者用于显示各种各样的趣味短句，后者则提供了一头会说话的奶牛（和其它各种诡异的东西）。关于fortunes还有一些有趣的包你可能也想一起安装，比如fortune-zh里有唐诗宋词，fortunes-ubuntu-server则有关于使用Ubuntu Server的贴士，等等。

新建一个文件cowsay-fortune，把以下代码复制进去：

#!/bin/bash
# Cow randomly says a hopefully interesting adage

# Get a short message from fortune, both offensive and not.
# Remove -a if you don't want to see offensive ones.
# Remove -s if you don't mind reading the long messages.
msg=`fortune -a -s`

# Randomly pick a mode of the cow
modes=("" -b -d -g -p -s -t -w -y ); mode=${modes[$(($RANDOM % 9))]}

# cowsay or cowthink?
cowdos=(cowsay cowthink); cowdo=${cowdos[$(($RANDOM % 2))]}

# Radomly pick a cow picture file
speaker=`cowsay -l | sed '1d;s/ /\n/g'| sort -R | head -1`

# That's it ^^
echo "$msg" | $cowdo -n -f $speaker $mode

保存后加上执行权限：

chmod +x cowsay-fortune

然后把这个文件复制到/usr/bin下

sudo cp cowsay-fortune /usr/bin

最后打开/etc/bash.bashrc

sudo gedit /etc/bash.bashrc

并在最后加上一行：

cowsay-fortune

保存后打开终端，应该就是这个效果了：

顺便抱怨一下，shell编程时对空格的要求也太诡异了吧。。一会儿要求空，一会儿要求不空，一会儿又不限制。。。

新浪的 spamer 越来越多，很早就想搬到独立的 wordpress 上去，但是一直没顾上。只好先在sina这里凑合着了。

Description

Input

Output

Sample Input

 3 4 5 10
 1 2
 0

Sample Output

 46
 2 4 10
 4
 1 2

Source

Asia Guangzhou 2003

Solution

很久不更新了，写个水水的解题报告充数。。。这是最近做的算法习题，网上看到这题的题解都是二分+贪心的，这里提供一个dp解法。

理解题意的时候有一点需要特别注意：题目所描述的整个过程是“并行”的。所以所有人都到达各自楼层的用时只与最晚到达的人有关。

首先，由于去各楼层乘客的具体数目对结果没有影响，为表述方便，我们假设每个目标楼层只有一个人要去，并且把各个目标楼层与要去该楼层的那个乘客对应。下面在说“电梯里还剩i个人”的时候，就是在说“电梯里的乘客还要去i个楼层”。

粗略的阶段划分和状态表示还是很简单的。

电梯从第1层开始层层上升，每层都看做一个阶段，任意时刻的状态都可以由“电梯在几楼”和“电梯上都有谁”这两个参数唯一确定。初始状态就是“电梯在1楼”和“所有人都在电梯上”。

在每个阶段需要做出决策，选择让电梯上的哪些人下来自己走（如果没人下来就表示电梯在这层不停）。每个决策发生后，原来电梯里的人被分成两拨：一拨留在电梯上继续上升，另一拨离开电梯开始爬楼锻炼身体。要求某个状态下电梯里的所有人到达各自楼层所需的最短时间，只需要找到一个最优的决策，使得上述两拨人中最晚到达的人尽早到达。

即，若设决策后留在电梯里的人全部到达各自楼层需要时间 T1，离开电梯的人全部到达需要时间 T2，则要求的就是 min{ max(T1, T2) }。其中 T1 可由“当前层数+1”和“决策后剩下的人”确定的状态得到；T2 则是下电梯的人中走的最远的那位所花的时间。

按照上述想法很容易列出转移方程。但是“电梯上都有谁”这一参数有 2^n 种取值，整个算法的复杂度因此能到达令人发指的O(m*2^2n)，对于m=31，n=30的数据规模这是不可接受的。

我们需要设法减少需要考虑的状态数目。下面给出两个引理：

1. 电梯决定停在第k层时：要去 1..k 层的人应选择在这时下电梯，这样一定可以得到当前决策下的一个最优解。如图：

2. 电梯在第k层时，若要去 k+r 层的人选择在这时下电梯，则：要去k+1..k+r-1层的人也应选择在此时下电梯，这样一定可以得到当前决策下的一个最优解。如图：

以上两点很容易证明。由这两点可以得到一个很简单但足以解决问题的结论：

无论电梯停在哪一层，若要去第 k 层的人选择在这时下电梯，则：所有要去低于k层（第1..k-1层）的人也应选择在此时下电梯，这样一定可以得到当前决策下的一个最优解。如图：

也就是说，如果把初始时的 n 名乘客按照各自要去的层数从高到低（注意此顺序与输入相反）排列，并依此编号为第 1、2、3…n 个人，第 i 个人要去第 f[i] 层（f[1]>f[2]>…>f[n]），那么可以认为任意时刻电梯里乘客的编号都是 1, 2,..,x 这样一个连续序列。也就是说，对于电梯里的人我们只需要考虑编号为 1, 2, 3 或 1, 2, 3, 4, 5 这样连续排列的情况，而无需考虑 1, 2, 4（缺3）或2, 3, 4（缺1）这样的情况。

这样一来，每个状态都能由两个数[i,j]来表示：电梯在第i层，电梯里有j个人，即要去楼层最高的第1,2,..,j个人。

下面给出转移方程：

f[i,j]表示电梯在第i层，电梯上有要去楼层最高的j个人时，电梯上的人全部到达各自楼层所需的最短时间

f[i,j] = min{ max(t1, t2) } (0<=k<=j)

t1 = f[i+1, k] + 电梯停留时间 + 电梯上升一层所用时间

t2 = max{ |d[l] – i| * 人爬一层楼所用时间 } ( k+1<=l<=j )

边界条件、最优解的构造方法以及其它细节问题不再赘述，详见代码。复杂度O(m*n^2)。代码中其实还有优化的空间，但已经是0ms过的，没必要了。

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <cstring>
using std::memset;

#include <algorithm>
using std::max;

#include <cmath>
using std::abs;

#include <limits>
using std::numeric_limits;

#include <vector>
using std::vector;

const int maxN = 30, maxF = 31;
const int ve = 4, st = 10, vw = 20; // 电梯上一层所需时间；电梯停一层所需时间；人走一层所需时间

int n, f[maxN + 1];

bool input()
{
    cin >> n;
    if (n==0) return false;

    // 注意：f[1..n]中楼层数从高到底排列
    for (int i = n; i>=1; --i)
        cin >> f[i];

    return true;
}

int dp[maxF + 1][maxN + 1], nextJ[maxF + 1][maxN + 1];

// 现在电梯在第currF层，第L到第R人离开电梯
// 函数返回这些离开电梯的人中最晚到达目的楼层所需的时间
int tLeave(int currF, int l, int r)
{
    if (l>r)  return 0;
    // 仅需考虑两端
    return max(abs(currF-f[l]), abs(currF-f[r])) * vw;
}

// 现在电梯在第i层，电梯里本来有j个人，在要下电梯的人离开后还剩jj个人
// 函数返回这些留在电梯里的人中最晚到达目的楼层所需的时间
int tStay(int i, int j, int jj)
{
    // 没人下电梯
    if (j==jj)
        return dp[i+1][jj] + ve;
    // 所有人都离开电梯
    else if (jj==0)
        return 0;
    // 第1层不计算电梯停留时间
    else if (i==1)
        return dp[i+1][jj] + ve;
    //普通情况
    else
        return dp[i+1][jj] + ve + st;
}

void calculate()
{
    // 边界：电梯在顶楼时所有人都必须下电梯
    int topFloor = f[1];
    for (int j = 1; j<=n; ++j)
        dp[topFloor][j] = tLeave(topFloor,1,j);

    for (int i = topFloor - 1; i>=1; --i)
        for (int j = 1; j<=n; ++j)
        {
            dp[i][j] = numeric_limits<int>::max();
            for (int jj = 0; jj <= j; ++jj)
            {
                // 取离开电梯的人和留下的人中的最晚到达者
                int tmp = max(tStay(i,j,jj),tLeave(i,jj+1,j));
                if (dp[i][j] > tmp)
                {
                    dp[i][j] = tmp;
                    nextJ[i][j] = jj;
                }
            }
        }
    cout << dp[1][n] << endl;
}

void rebuildSolution()
{
    vector<int> stops;
    int j = nextJ[1][n], topFloor = f[1];
    for (int i = 2; i<=topFloor; ++i)
        if (nextJ[i][j]!=j)
        {
            stops.push_back(i);
            j = nextJ[i][j];
            if (j==0) break;
        }

    cout << stops.size();
    for (int i = 0; i!=stops.size(); ++i)
        cout << ' ' << stops[i];
    cout << endl;
}

void solve()
{
    memset(dp,0,sizeof(dp));
    memset(nextJ,0,sizeof(nextJ));
    calculate();
    rebuildSolution();
}

int main()
{
    while (input())
        solve();
}

拿本本的摄像头录的，同步有点问题不想调了= = 能弹成这样我很满意了恩~

p.s. 使用了强大的开源视频处理软件 VirtualDub 进行视频捕获和剪辑，欢迎猛击链接到其主页围观。

比较无法理解为什么 .NET 类库里面没有提供足够对RFC822格式日期时间的支持。网上有人实现，但是都不太让人满意。比较囧的是，关于单字母表示时区，好几个实现都只考虑了 Z、A、M、N、Y 五个 spec 里直接列出的字母……我在用的 Argotic 也是这样。所以就自己实现了一个 parser，然后修改 Argotic 的代码直接用它。

点这里下载源代码及其单元测试。需要的话就拿去吧，lgpl。

我实现的时候相比严格的 spec 又放宽了一些，比如允许小时、分钟、秒只有一位数字（spec 要求必须两位），允许不指定时区，允许用四位数字表示年份（这个是 rss 的 spec 要求的），允许只指定日期不指定时间。如果你觉着不爽就自己改改吧，看代码就知道非常好改（就在“Set Format Strings”那个 region 里）。

欢迎报告bug。

终于看完了《Agile Principles, Patterns, and Practices in C#》的第一个Section，上学期间读这些书的进度还真不是一般的慢……第一次尝试用MindMap做笔记，感觉不错，不过效率还是不够高。老蒋说我笔记做得太详尽了，像抄书…反思中。

篇幅所限，书中还是有很多内容不够深入。一些内容需要另一本书的篇幅深入讨论（如重构），甚至需要看一本书才能从纸上谈兵转到实践（如TDD、Acceptance Tests）。。。望不到头的书单啊T_T

做笔记使用的工具是 XMind。

单击这里进入下载页面。

（需要下载才能看到全部内容）

我们口语课结课，要求imagine一个产品，然后做presentation和tv commercial。然后我们就很恶趣味同时很正经地做了Grass Mud Horse。下面是幻灯片~_~

(特别说明，那个仿别摸我的Logo是PS大牛Catt同学搞的)

关于这个GMH这个诡异的名字，我们是这么和外教解释的：吃进去的是Grass，X出来的是Mud，多么Eco-friendly啊~~~~

……好吧，是有点冷，我只是不知道该更新什么了就发这个上来凑数，恩。

P.S.今天最后一次口语课，才注意到我们班竟然有个叫Dick的…………………………这说明什么呢？

说明，我不但词汇量小，知道的单词也想不起来- -