使用svn命令进行每日codediff

什么是codediff?

每日codediff是一项简单易用,行之有效的敏捷实践,可以保证项目进展,让项目中的新人得到学习的机会,让代码规范得到更有效贯彻。 具体做法是,每天早上站立晨会之后,几个人围在一起,使用版本控制工具的diff功能, 逐行浏览前一天提交的代码,提交者对修改的代码进行介绍,讲讲代码是什么功能,为什么要做这样的修改。 当然其他人可以提出异议,并且通常会记录评审意见,以便后续跟踪。

和每周的代码评审相比,每日codediff虽然局限于每个代码片段,但时效性更强,两者互补不足,都是保证代码质量的有效手段。

better svn, better codediff

在我们的项目团队里边,一直也是使用这种方式进行处理。 公司使用的是svn,不过由于环境的限制,svn性能并不是特别理想。 经常把大量时间用在svn log,diff的等待过程中,整个codediff也因此需要比较多时间,有时需要1个多小时。 长此以往,很多人对每日codediff不重视,参与度不高,对于我来说,评审问题也很不好跟踪。

后来我想找一专门为codediff服务的工具,考察了一些开源项目,但总觉得不是特别合适我们团队的需求。 我的要求也很简单,为svn服务,操作简单,便于跟踪,而不需要正规的评审流程。后来,我决定自己开发一个。

我的做法也很简单: 定时从svn上取出最新提交记录,并把相关文件记录到数据库中去。 再弄个网页展示出来,codediff和评审通过网页来进行,

原型一出来,就在团队中试用了一段时间,效果挺好的,通常只需要10来分钟就可以了,大大提高了效率。 现在几个同事还把这东西推广到其他项目中去,反应都还不错,让我着实感到非常有面子:)。

更多细节

后来,有些同事比较感兴趣提交记录是怎么弄出来的。 因为很多人平时只是使用海龟来操作,命令行基本没使用过,所以不清楚也不奇怪。所以解释一下是怎么做的,也是我写这篇博客的重要原因。

整个工程主要使用ruby on railstwitter bootstrap做页面. 通过jruby来跑,定时任务使用quartz-jruby来做,提交记录通过svn命令来获取,我这里主要说说svn命令。

当然首先需要安装svn命令行客户端,然后通过Runtime.exec()来获取输出信息,解析这些信息入库即可。

# 获取最新版本号,使用正则/Last Changed Rev: (\d+)/得到最新版本
svn info http://hustoj.googlecode.com/svn/trunk
# 获取svn log,这个解析比较麻烦,需要用正则分组
svn log -l 1 -v http://hustoj.googlecode.com/svn/trunk
# 获取diff文件,对于更新(M)的文件
svn diff -c 1659 http://hustoj.googlecode.com/svn/trunk/web/admin/contest_list.php
# 获取完整文件,对于增加(A)删除(D)的文件,需要直接取版本
svn cat http://hustoj.googlecode.com/svn/trunk/web/admin/contest_list.php@1655

不过在实际处理的时候,默认的diff取出来的上下文太少,所以我使用了外部diff工具:

svn diff -c 1659 --diff-cmd /usr/bin/diff -x "-U20" http://hustoj.googlecode.com/svn/trunk/web/admin/contest_list.php                    

不过通过程序执行命令获取数据时还存在一点问题:获取不到diff数据。 为了解决这个问题,我再封装了一个shell文件来调用。

#!/bin/bash
svn diff -c $1 --diff-cmd /usr/bin/diff -x "-U$2" $3

总的来说,实现的难度并不大,只是遇到了一些小问题,能够把一个想法化成现实,并且确实提高了效率,还是挺满意的。

量杯倒水游戏

量杯倒水

量杯倒水

这个问题常见于趣味题和面试题,题意大概是这样的:有两个只有最大刻度的量杯(如10毫升,3毫升), 并且有无限量的水。求怎么倒出x毫升的水?

思路与猜想

首先我们来操作一下,例如倒出4毫升的水,同时把大小量杯表示为a,b

  1. b装满,倒入a(a有3ml,b有0ml)
  2. b再装满,倒入a(a有6ml,b有0ml)
  3. b再装满,倒入a(a有9ml,b有0ml)
  4. b再装满,倒入a(a有10ml,b有2ml)
  5. a倒掉,b倒入a(a有2ml,b有0ml)
  6. 重复2-4的动作(此时a有10ml,b有1ml)
  7. a倒掉,b倒入a(a有1ml,b有0ml)
  8. b装满,倒入a(a有4ml,b有0ml)

假如我们再继续操作的话,还可以找到7ml,这样0ml~10ml的体积都是可以测量出来的。这是不是一般规律?

虽然我们进行了许多次操作,但操作是有规律的:b总是往a倒水直到a装满,这时b会剩余一点。 这样才能得到不同于a,b的体积。我们重复这个操作的过程,不考虑a装满的情况, 在a中出现的水t可以用t=mb-na来表示(a>t>=0,m>=0,n>=0)。其中m可以表示为往a倒水的次数, n表示a装满的次数。

首先考虑一下a,b不是互质的情况,假设他们的最大公约数为u,那么狠显然没法倒出t小于u的体积。 这种情况可以归结为两边除去u的情况。

现在再来考虑a,b互质的情况,我们需要考虑的是,对于t,是否都存在m,n使t=mb-na成立?

贝祖定理

我们从数学归纳法出发,很明显t=0的情况是满足要求的,假设t=1的要求也能够满足, 那么有t=mb-na成立就可以推导出t+1=m1b-n1a+m2b-n2a也是符合mb-na的。

如何证明存在m,n使得mb-na=1?这个倒不用自己动手,有个叫贝祖定理的数学定理,可以很容易推导出这个结论。

从wiki上看到的资料,贝祖定理可以证明a,b互质,存在xa+yb=1,其中x,y为整数 不过好像跟我们的要求有点出入。不过没关系,很显然x,y如果没有不等于0的话,必须有个是负数,

如果x是负数,显然符合要求,如果y是负数,那么总存在一个数k(k>0)使得y+ka>0,那么 1=xa+yb=xa+yb-kab+kab=(x-ka)a+(y+ka)b,这样也是可以符合要求的。

所以,按照我们的操作方式,假设a,b的最大公约数为u,就可以找到0ml,uml,2uml…aml的体积。

再思考

如果有多个量杯,情况会是怎样?

要倒出一定量的水,上述操作是否是最快的?

使用jekyll和markdown遇到的问题

不能正常生成页面

我是使用windows来弄的,在git shell里边操作。发现有时候页面根本不生成, 即使我把_site下面的文件全部生成,还是没动静。后来发现,需要设置一下环境的字符编码,例如export LC_ALL=zh_CN.UTF-8 可以在启动脚本里边修改,例如修改RUBY_HOME/bin/jekyll.bat,增加

SET LANG=zh_CN.UTF-8
SET LC_ALL=zh_CN.UTF-8

最近发现一个新的方法

chcp 65001

tags不能正常发布

tags如果列举多个的话,除了用逗号分割之外,必须在逗号之后加上空格,否则不能在github上正常发布。 但奇怪的是,在本地却是没有问题的。

列表不能正常显示

这个也比较奇怪,无论是有序列表还是无序列表,只能有部分能正常显示。 我试了很久,发现如果列表项里边没有数字或英文字符就不能显示。

这个问题已经解决了,原来在每个列表前面需要空行

高亮代码有问题

高亮代码不容易呀,需要python支持,还有安装easy_install Pygments。 但对于某些python版本来说,这样还不行,出现Liquid error: Bad file descriptor。 需要修改gems\albino-1.3.3\lib\albino.rb

另外,有时候高亮不是很合适,可以选择引用,只要每行前面至少加4个空格或1个tab就可以了。我习惯在每个引用块前后加一个空行。

在段落中硬换行

我原来以为不能硬换行,原来markdown也支持,只需要在需要换行的地方后面加至少两个空格就可以了。

页面生成太慢

当你的文章越来越多的时候,页面生成的时间会变得非常夸张,jekyll没有提供参数来控制。 为了解决这个问题,有个办法就是过滤某些没有变化的文件,因为大多数情况下,我们只是对特定的文件进行修改而已。 摸索了很久,最后我直接拿jekyll源码开刀,见让include和exclude支持正则add glob support to include,exclude option

围棋中气的判断

围棋玩法

围棋本身的规则是非常简单的。判断一个子能不能落在某个点是最基本的问题。
如果不能吃掉对方但这个子周围还有气(空点)的话,是可以落子的。
如果能吃掉对方但不是打劫这种特殊情况的话,也是可以落子的。
我们先不考虑打劫这种情况,问题就归结为如何判断某个子是否有气,而杀子就是判断四周的子是否有气。

用递归来判断

假设有个方法try2kill(r,c),它可以用来判断r行c列的子是否有气,如果没气返回true,否则返回false。

递归过程如下:

  1. 判断四周是否存在一个气,就是有个空格(0),如果有返回false。
  2. 否则,给当前点记录为预杀状态(x)(表示自己周围没有明显的气)
  3. 再依次判断四周的点,对每个点例如左边(left):
  4. 如果左边未出边界且和当前点是同一颜色(但并非预杀状态),则调用try2kill进行判断
  5. 如果其中一个点有气(try2kill返回false),则直接返回false
  6. 如果四周都判断完,没有发现明显的气,则返回true(这样所有预杀状态的都是没气的,都会被杀掉)

打劫处理

打劫有个特殊的地方就是不能立即回提,本质上是不能在对弈过程中出现同形。
一个比较简单有效的办法就是,记录落子次序和每次的吃子数(通过上面的判断逻辑)。 这两个记录都是很容易记录的。判断是否打劫违规就是当前手和上一手的吃子数是否都为1。 且当前落子点对应上手的死子点,当前死子点对应上手的落子点。
这些条件符合的话,这就是一次违规。

后续

有了这些判断逻辑,要实现整个走法已经不是问题了,有兴趣的可以试试。
当然,围棋最复杂的地方还是人工智能领域,现阶段的电脑围棋还是比较弱的。

连连看中如何判断连通

连连看基本玩法

连连看的玩法非常简单,判断两个块是否可以消除的规则是:必须是同一类型的块,可以通过至多 三条直线相连,并且直线没有被其他的块所阻拦。

数据结构表示

可以用一个二维数组来表示整个界面,不同类型的点用不同的值k来表示,那么一个点可以用k和(x, y)来表示。 空白处的值设置为0。另外为了方便处理只在边边上可以连通的情况,可以加上边界(二维数组加上两行两列,并设置为0)。 判断点a和b是否可以连通,如果是不同类型的点很好判断,判断a.k==b.k即可。 那么,问题就变成判断两个点a(a.x, a.y)和b(b.x, b.y)是否可连通。

简单的算法

我用的是一种比较直观的算法,当然还有其他很多算法(在网上资料搜一下就有很多了)。

首先为了方便理解,先不考虑两个点在同一线上的情况。那么两个点能够连上的情况只有就是横竖横或竖横竖两个情况 先考虑两个点是否可以横竖横连接的情况,参考下面的算法步骤:

  1. 给整个边界加上一圈空点(0)(方便后面计算)。
  2. 计算x轴上a,b两点左右两边的空点,这样可以算出两者公共的空点(x坐标相同),只有通过这些空点才可能联通达到横竖横的情况。
  3. 对每个公共的点,假设x坐标为c,那么就是点(c,a.y)和(c,b.y),再判断这两个点能否联通。
  4. 假设a.y小于b.y,那么就是看从(c,a.y+1)到(c,b.y-1)这些点是否都为空。
  5. 如果是空(0)的,表示最初的两个点是可以联通的。

到这里,一切已经ok了。另外一种情况跟这个是一样的, 而在一条直线上的情况只是这种判断的特殊情况而已。