即便有了方便的 Eclipse+ADT ，偶尔在命令行下敲个 adb 也是少不了的。像我这样每天要切换操作系统的开发者，下面这个错误提示是每天都要遇到的：

Re-installation failed due to different application signatures.
You must perform a full uninstall of the application. WARNING: This will remove the application data!
Please execute ‘adb uninstall your.package.namespace’ in a shell.¹⁾

如果你忘记了你已连接了多台设备就兴匆匆地敲入，

那么下面这个错误也是不可避免的：

这时候又得用

然后再选择，复制，粘帖打印出来的目标序列号，才能再执行。

不过现在好了，dtmilano 提供了一个可交互的adb，原文见此。

这个交互的 adb 由两个脚本组成，第一个是android-select-device。用于提示用户选择设备。

把上面代码复制保存到 android-select-device 这个文件里。第二个文件是my-adb，它是用来代替原本的adb的。当adb devices 多于一个的时候就会调用 android-select-device 让用户选择设备。

同样的把上面代码复制保存到文件 my-adb 。
接下来把这两个脚本加入到 $PATH 里面。我的做法是在 $ANDROID_SDK_HOME 里面建个 my-tools 文件夹，再把脚本放进去。然后直接在 $PATH 里添加这个目录

最后给 my-adb 加个 adb 别名，让它替换掉原来的 adb。

确保环境变量生效后，就可以键入 adb 试试看了。如果运行失败，确保两个脚本的权限为可执行，如 744 。

运行 adb hell 后，如果有多个设备的话，你应该可以看到文章一开始的输出：

不过这个脚本也是有缺陷的，不管 adb 的子命令需不需要指定device，只要多于一个设备连接着，它都会提示选择设备。

注解

1) 这个问题是由于不同的机器使用不同的debug.keystore，导致安装的时候验证错误。所有开发的机器使用相同的debug.keystore便可以避免这个问题再次发生。在 Eclipse 下 Window -> Preferences -> Android -> Build -> Custom debug keystore 中可以更改。

Lights Out(关灯游戏) 是一款经典的老游戏，维基百科上说Lights Out 是在1995年由 Tiger Toys 第一次发行。接触它却在去年的时候Gnome3的小游戏里。Lights Out 的规则很简单，游戏由一个 5 * 5 格的棋盘构成，每格子都是一颗灯，灯肯定是有两种状态，亮或者暗。游戏一开始棋盘上会亮起一些灯，你的目标就是把所有亮起灯都关掉，亮起的灯点一下就会关掉，但游戏当然不会这么简单，点一下灯的时候还会有一些附加影响，准确的说就是点一下灯的时候会切换它和四周也就是是上下左右的灯的状态。找到了一个在线的Lights Out，http://www.addictinggames.com/puzzle-games/lightsout.jsp。一般能过第五关就差不多了吧。

不过即便是第一关，如果一开始摸不到基本的门道，乱点的话基本上想点回来是很难的，为什么？$2^{25}$等于多少 ，作为一个合格的码农应该脱口而出，33554432 ！好吧我承认我也是用计算器的。要玩这游戏首先要明白一个道理：你关的不是灯，是寂寞…噢不，是开关！先不管棋盘上的灯光状态如何，也不管一个开关可以控制多少颗灯，只要知道你点一下方块，就等于切换一次开关，开关就从状态1转换到状态0，再点一下方块，开关又从状态0切换回状态1。这里的0和1也就是开关开和关两种状态，明白这一点很重要，把所有开着的开关都关闭就是完成游戏，所有开着的开关都关闭，肯定没有灯是亮的是吧，但是反过来并不一定成立哦，后面会说到这个。它还可以继续往下推，第一点，每一个方块只有点第一下才是有意义的，点第二下也就切换会原始状态，点N下也就是来来回回切换而已。第二点，开关关闭的顺序无关紧要。从上往下点，从下往上点都没关系。

如果你有迈克那么牛逼的话，相信现在已经能够透过亮着灯光看到后面隐藏的开关了吧，看不到也没关系先想象一下。我们知道一个开关控制着上下左右和本身的灯光，相对的，一颗灯亮与否，取决于它本身和四周开关的状态，当有奇数个开关开着的时候，灯就亮，偶数个的时候灯就是暗着的。再看看第一行，第一行上的一颗灯，能影响到它的开关有本身、左右，这三个都是第一 行上的开关，另外还有下方位于第二行的开关，而上方的开关因为是第一行所以是不存在的。现在假设一下，第一行所有开关都被关闭了，那么此时第一行如果还有亮着的灯，能控制这些灯的开关就只剩下第二行的开关，一颗亮着的灯，显然第二行其对着的开关肯定是打开的，相反的，第一行的灯是暗的，那么第二行对应的开关肯定是关闭的，这样第二行打开的开关就是其上面的灯还亮着的那些。照着第一行亮着的灯把第二行的开关全部关掉，现在一行的灯应该是全暗的，第二行的开关也全部关闭了，第二行还亮着的灯也就只有第三开关能影响到了。同样的，此时第二、三行的情况就跟前面第一、二行的情形一样了。以此类推，第三、四、五行的开关都可以这样关掉，此时游戏也就解决了。终于有一条有用的结论了，当第一行的开关全部关闭后，其他行的开关通过一个唯一且固定的模式来把开关全部关闭，也就是说对应着上一行亮着的灯把下一行对应的开关关闭就行。有了这个结论，现在已经把游戏的难度降低不少了，我们只要猜对第一行打开的开关就可以把游戏K.O.了。这个结论，我们把问题猜测的规模从$2^{25}=33554432$降到$2^5=32$。当然这样有点无趣，也不会变得完全没有难度。 但对于计算机来说，那确实是易过吃碗水，遍历第一行的所有可能性，再校验是不是一个解。

但是这种方法不能脱离暴力搜索，始终有点丑陋。我在看Gnome Lights Out 的源码的时候，发现了一篇论文讨论了如何用线性代数的方法来解决这个问题。非常简单的一个方法。

首先我们随便找一个开局状态，1表示灯是亮的，0表示灯是暗的。如下所示，

$\begin{vmatrix}1 & 0 & 0 & 0 & 0 \\1 & 1 & 1 & 1 & 0 \\1 & 1 & 1 & 1 & 1 \\1 & 1 & 1 & 1 & 0 \\1 & 0 & 0 & 0 & 0\\\end{vmatrix}$

把这些数字放到一列里并标上号，就成了向量$\vec b=(b_{1,1},b_{1,2},\cdots,b_{1,5},b_{2,1},\cdots,b_{5,5})^T$

当我们按一下开关，$\vec b$又会发生什么变化呢？比如按下位于坐标(1,1)的开关，记为$s_{1,1}$。当$s_{1,1}$按下时，他会改变$b_{1,1} ,b_{1,2},b_{2,1}$的状态，如果灯光原来的状态为0，那么就变成1，原来为1就变成0。这个刚好是GF(2)上的加法，GF(2)怎么说呢，其实和一般的数域没什么区别，因为只有两个元素 0， 1 。那么在这个域上 1 + 1 就等于 0 。我们把$s_{1,1}$也用向量表示，它就是这个样子的

$\vec s_{1,1}=(1,1,0,0,0,1,0,\cdots,0)$

当我们在游戏中点一下开关$s_{1,1}$，数学上就等于$\vec b + \vec s_{1,1}$ 。我们还可以继续表示其他开关的向量，比如，

$\vec s_{1,2}=(1,1,1,0,0,0,1,\cdots,0)$

$\vec s_{5,5}=(0,\cdots,0,1,0,0,0,1,1)$ 。

前面我们说过，这个游戏的目的就是把全部打开着的开关都关闭了，开关的状态我们已经用$s_{1,1},\cdots,s_{5,5}$ 表示，不多不少刚好25个，如果我们用1来表示这个开关是打开，0来表示关闭，那么一个游戏初始的开关状态也可以用一个向量来表示，
$\vec x=(x_{1,1},x_{1,2},\cdots,x_{1,5},x_{2,1},\cdots,x_{5,5})^T$。由于游戏的开关状态时未知的，是我们玩这个游戏的目的，所以这里用x表示。$\vec x$即是初始局面打开的开关，也是灯全暗变换到棋盘初始状态所需要点开的开关，所以我们也把$\vec x$称为一个策略。$\vec b$表示初始状态，$\underline{0}$灯光全暗的状态。
$\vec b =\underline{0}+x_{1,1}\vec s_{1,1}+\cdots+x_{1,5}\vec s_{1,5}+x_{2,1}\vec s_{2,1}+\cdots+x_{5,5}\vec s_{5,5}$

解上面的方程可以用下面这个线性方程来表示：$A\vec x=\vec b$
其中A是一个 25 * 25 的矩阵：

$A = \begin{vmatrix}B & I & O & O & O \\I & B & I & O & O \\O & I & B & I & O \\O & O & I & B & I \\O & O & O & I & B \\\end{vmatrix}$

I是一个 5 * 5 的单位矩阵，O是一个 5 * 5 其元全部为零的矩阵。而B是这样一个矩阵：

$B = \begin{vmatrix}1 & 1 & 0 & 0 & 0 \\1 & 1 & 1 & 0 & 0 \\0 & 1 & 1 & 1 & 0 \\0 & 0 & 1 & 1 & 1 \\0 & 0 & 0 & 1 & 1 \\\end{vmatrix}$

如果把 I, O, B 代入 A 那么 A 的每一列都对应着一个开关的s向量。

采用高斯-若爾當消元法对A的增广矩阵$(A \vec b)$，就可以求出$\vec x$ 。

如果令 $\vec b = \bf{0}$，在 5 * 5 的游戏规模下，解$A\vec x=\bf{0}$。除了 $\vec x = \bf{0}$外，还有另外两个解，分别是：

$\vec x_{1}=(0,1,1,1,0,1,0,1,0,1,1,1,0,1,1,1,0,1,0,1,0,1,1,1,0)^T$

$\vec x_{2}=(1,0,1,0,1,1,0,1,0,1,0,0,0,0,0,1,0,1,0,1,1,0,1,0,1)^T$

由此可见，5 * 5 游戏的解并不是唯一的，即便是灯光全暗，也不一定表示开关全部被关闭。另外，并不是所有可能性都有解。好了就先到这里，了解更多请见下面的链接：

• gnome game lightsout的源码
• Turning Lights Out with Linear Algebra
• mathworld 上的一个讨论
• 高斯-若尔当消元法的算法

所以呢，就把它做出来了。

用了之前我在这里提过的processing.js来实现，processing.js很好玩，以后再专门来说一说。

插件的原理很简单，当用户头像载入时，先去请求gravatar有没该用户的头像，有的话就把头像显示出来完事，没有的话就根据用户的id，即邮箱的MD5码生成一个对应的Android机器人出来，这里跟gravatar生成随机头像是一样的，然后再加上个1秒钟的渐变效果。插件都是在客户端运行的，用的是客户端的CPU不会影响到服务器，但获取gravatar图片的跨域问题也挺烦的，现在还没有真正解决。另外这个插件还有个实际点的好处，因为某墙的缘故，gravatar在墙内也是经常抽风的，用这个插件就可以避免出现一片空白，而是换成一个可爱的Android机器人。用了lazyload技术，头像的动画只会在头像出现在视图（viewport）中才会触发，相对来说对页面的流畅程度的影响比较小，不过如果评论多的话，还是慎用（话说评论N多的牛人会用这么白痴的东西吗？）。
插件的具体效果可以点几下下面的框框看看：

因为是用了processingjs，还需要导入processingjs框架，而插件本身是没有提供这个框架的，所以呢装这个插件之前，推荐先装一下这个：http://www.ramoonus.nl/wordpress/processing-js/

这个插件可以在这里下载：imandroid。

其实在用processingjs实现之前我已经在Android平台上实现了这个东东，幸好有processingjs这么像java语法的东西让我省了不少力气移植到js上来。
不浪费顺便弄了个动态壁纸（live wallpaper），到Play Store看下吧。

今天真是适合踏青的好天气，蓝天白云，风轻如梦，视野开阔。可惜手机的镜头不给力，拍不出这种开阔。

首先取消了分类目录，全部通过标签来做归类管理。像我这种随便吐槽的博客用分类目录，很多时候都觉的是种自我限制，相对的标签就自由许多，同时也有归类的功能。这方面不得不说Evernote很有相见之明，不过我很久没用Evernote了，听说它也是顶不住用户的压力开始支持分类管理了。至于技术文章，我把它归为笔记类，和其它笔记，摘抄都记录到我的wiki里，wiki目前还是通过分类管理的，分得细致很多，不过我觉得更合理的话应该要配合上标签，即便没有客户端和没有标签管理下DokuWiki还是完全替代了我对Evernote的使用，何况标签这个功能装个插件就有了，Wiki的自由和可扩展性是无可替代的。一直有个将dokuwiki变身为云笔记想法，主要目的本地和服务器同步文件，还有Web编辑器太弱了，想通过Emacs来做桌面客户端，再来个Android App，加上一些自己常用网站的接口插件，就差不多了。我已经启动这个项目很久了（见wiki-note），不过一直没有动工过，果然是拖延症患者吧。

取消了分类目录，我就希望博客更整洁些，所以决定采用单栏模板让文章内容的空间大一些。但苦于找不到比较入眼的单栏主题，无奈选择自己看教程做，本想基于twentyten来改的，无意间发现 CriticalZero这个站，它的设计令我耳目一新，特别是头部用条斜线来切割页面，相当大胆，用的好的话就是小清新，用不好的话就像眼前这个网站一样-_-(纯粹213需要，无意贬低原作者)。虽然他页面内容的排版也漂亮，但文章的空间太小不适合我的需求。所以我还是采用传统的纵向排列，这样保证了文章有足够大的宽度，看起来舒服些。其它细节我也搬了不少过来，再加上一些从其它主题搬过来的设计和来自 Gentleface 的图标、乱来的配色，不过 Web Colors 真的很有帮助。就这样左抄抄右抄抄，像我这样的前端苦手也能完成一款wordpress主题。

我的第一款wordpress主题就叫做BetaD吧。BetaD是twentyten（wordpress自带主题）的子主题（child theme），设计主要来自 CriticalZero ，Copy的太多都不好意思说是参考了。目前是dirty又buggy，只在Chrome和Firefox下测试过，我自己发现的就有不少bug，也没要提供任何可自定制的接口，下次再修复吧。有兴趣的同学到这里看下：https://github.com/dourokinga/BetaD

另外，不知大家有发现没，这个主题的背景是动态生成，在研究代码是时候，发现了相当酷的框架processing.js，是用来做html5交互动画的。这个背景就是用这个框架生成的，看起来十分强大的样子，一定要来研究下。

另外，意外的是在debug下还能工作的挺好的。

NBANDROID-71基本可以算解决了。

见此,如何在Netbeans上配置Android开发环境

Lyrics Grabber2 可以说我理想中的歌曲下载插件，主要是它可以批量抓取更新歌词，又可以自定义抓取脚本方便扩展(见此HowToMakeProviderInPython)，实在强大。不过还是有一些不足，比如找到的歌词没有给出来源（Provider），歌词服务器（Provier）不能更改优先级，还有就是出现多个歌词的匹配问题，既有多个服务器的，也有一个服务器的多个歌词的，希望能增加人工选择的选项。不过 Lyrics Grabber2刚好一年没更新了，再更新实在希望不大。

再者，现在Lyrics Grabber2里面的千千静听歌词抓取脚本（TTPlayer(LRC).py）是用不了的。我了解一下，把bug总结如下：

bug_1:36行

导致搜索失败的主要原因，现在千千静听搜索歌词的服务器变了

bug_2:103行
另一个导致搜索失败的原因，用来生成code的字符串应该用utf-8编码，而用minidom.parseString出来的字符串已经是utf-16le的了.

bug_3:114行
这一行应该是打错了. 条件应该是 c >= 0×80:

bug_4:42行
同样是编码问题，导致Levenshtein算法失效，因为比对的是两个不同编码的字符串。

修复完bug后，就可以成功查词了。但是结果并不理想。

由上图可以看出是，英文和简体没压力但繁（正）体中文就不行了。显然还需对title做些处理。通过对千千静听进行测试，发现千千静听对查询串的处理远不止 71 72 73 所在的那样。
大概做了下面这些过滤：

• 英文转小写
• 去括号，大中小还有全角的小括号
• 去除半角特殊符号，空格，逗号，etc。
• 去除全角特殊符号
• 繁（正）体转换为简体

繁（正）体转换为简体，找不到好的现成方案（针对unicode字符集uft-8编码的）。只能动用谷歌翻译的api了。没想到谷歌翻译倒工作的很好。不过毕竟是多一个网络请求，建议不需要的时候可以把它注释掉，以加快查询速度。其他过滤功能也可以根据情况去掉，已加强效率。FYI:脚本更改后立即生效，无须重启foobar2000的。

针对这些，增加了下面的新方法

注意:谷歌翻译的api已经过期了，会导致查词失败，新的翻译api又要收费还很贵，见http://code.google.com/apis/language/translate/v2/pricing.html，坑爹呢这是。幸好还有Bing做后援。虽然不给力，但简繁转换还是没问题的。下面的代码改用Bing的翻译服务：

这样，大部分流行歌曲特别是华人音乐，都可以表示毫无压力。

千千静听的大部分歌词都是简体的……

歌名特殊符号的也能识别了

You Ain’t Goin Nowhere在千千静听里面也是Fault。

但是这样并不完美，毕竟是黑盒测试，比如 中千千静听的後(/u8C5F)字并没有转换到后 ，如下图：

最後の放課後 在千千静听中可以找到，花は桜 君は美し -instrumental- 则同样找不到

不过目前也就这能做到这样。

改好的脚本在此:TTPlayer(LRC).py

另外，乐辞的脚本也是不行的，顺手也改好了。Lyricist(LRC).py

btw：千千静听的歌词库，只要是热门的，流行的，出名的歌曲都挺全的，不知是从哪里来的。

一个矩形空间上,布置出错综复杂的墙,本文讨论的主要是这种结构的简单迷宫.可以想象出在下图这样的结构里,推倒某些墙壁.来生成迷宫.当然墙不是随便可以推倒的.

这样的结构姑且称为完全方格图(square grid graph)吧.从图论角度上看,这样的结构等同于下面这张图.圆圈表示顶点,线段表示边.

而最上面的迷宫,就可以认为上面那张完全方格图的生成子图,仔细观察上面的迷宫,就会发现无论从那里开始走,都可以到达迷宫中的任意一个地方(顶点).用图论术语来讲也就是说迷宫它还必须是一个连通图,这个可以理解,迷宫里到达不了的地方实际上没有意义.

另外继续观察还可以发现,无论你从那个地方出发,只要不往回走,就永远也回不到原来出发的地方.也就是不会绕圈圈.图论上说这叫做没有回路.当然回路这个可以有,有回路的迷宫更让人迷惑也可以更好玩,但这还得取决于回路如何设计.简单起见,这里生成的迷宫没有回路.就这两个特性,就可以给这种迷宫下定义了:完全方格图的没有回路连通生成子图.也就是完全方格图的生成树.

图的生成树算法那就相当广泛了,一次广度优先搜索(BFS)或深度优先搜索(DFS),都可以构建出图的生成子树.只要让选择下一个顶点的策略随机化,每次搜索出来的就是一个随机生成树也就是随机生成的迷宫.但是BFS生成出来的结果由于其他顶点相对于起始顶点的深度不变,导致迷宫随机性不够理想,下面提到的Prim算法算是一种对BFS的不错改进.DFS生成的过程比较生动就像是在挖地道一样推倒一面面墙.用来生成迷宫就比较直观也比较适合.

还有经典的最小生成树算法,Kruskal和Prim,都可以用来生成迷宫.当然完全方格图所有边都是单位权值的.所有生成树都是最小的,要运用Kruskal和Prim要做的改变就是将原来已以小优先的选择边策略改为随机选取.出来的是一个随机生成树.

当然上面的算法都是基于图论的,在维基百科里还提到另外一种不用图论的算法,比较有趣,叫递归分割法(Recursive division method),我喜欢叫你建墙我挖洞法,从名字就可以看出这是一种分治法,基本的策略就是,在一个空间里建立两面相交墙,形成四个较小的空间,然后再挖上三个洞.然后再对四个较小的空间执行相同的处理.直至每个空间的长或宽为单元大小不可再分割为止.这种方法效率比较高,由于是分治法也比较适合用分布式运算.这种方法生成出来的迷宫也是符合上面所提到的连通性和没有回路两个特点,可以用递归法简单证明下,由于两面墙隔出了四个空间,开三个洞刚好使每个空间可以互相连通,且没有回路,如果从一个空间到达另一个空间必定到达该空间的其中一个子空间,也就可以到达其他三个子空间.以此类推就到达迷宫上的每一个空间.不够生成出来的迷宫却较为简单,直路太多不够扭曲.

我用html5实现一个迷宫生成算法的演示,分别针对DFS,Kruskal,Prim和最后的分治法.可以去玩一下.

抱怨一下javascript,绘画速度还是不够快,对于大一点的迷宫必须用脏矩形重绘,才能保证速度.不够画出来的效果却不咋地.

至于这种迷宫的走法,一个DFS就可以很好地解决了.

当然实际设计出迷宫不像是这些算法这么简单的,正如谁谁谁所说的

“迷宫设计不仅是线条和图案的组合，要有娱乐性、装饰性，还要考虑那些穿越迷宫者的感受，那样才趣味无穷”

有空再考虑下其他类型迷宫的生成算法.

未完待续…

参考:

http://en.wikipedia.org/wiki/Maze_generation_algorithm

http://en.wikipedia.org/wiki/Maze

有点睡意，立马上床。

于 2011 年 06 月 05 日 03:59:17

这段代码很正常，线程跑起来的结果和你想的一样，在终端上输入一行，按下回车就回显这一行，显然System.in是行缓冲的(linebuffered)，不是像getch那样输入一个就回显一个。在没有按下回车之前in.read()就一直阻塞。
再来看下这一段代码

Thread2跑起来结果跟Thread1一模一样，输入一行回显一行，但代码却有点区别，多了byte buffer[] = new byte[10];这是一个缓冲，读取的时候不是一次一个字节了，而是in.read(buffer)，这个方法等同于in.read(buffer, 0, buffer.length)，也就是说要先把buffer读满，read方法才会结束。然后我困惑了，Thread2运行起来竟然Thread1一模一样。如果你输入abc然后回车，Thread2也会立刻回显abc\n。这时候的字节数只有4还没把buffer填满，但in.read(buffer)却返回了，我参考了文档对InputStream中read(byte[] b, int off, int len) 的说明：

…将输入流中最多 len 个数据字节读入字节数组。尝试读取多达 len 字节，但可能读取较少数量。以整数形式返回实际读取的字节数。
在输入数据可用、检测到流的末尾或者抛出异常前，此方法一直阻塞。…

前一句又“尝试”又”可能”的，太模糊暂时忽略，第二提出了不阻塞的情况，看似除了“输入数据可用”理解有点模糊外，其他都明显不符合，那理应阻塞的方法是什么原因让它提前返回呢？带着这个疑问，我看了下InputStream的源码，并在Thread3中实现了一个一模一样的方法（如文档所说的，就是反复调用read()）：

Thread3跑起来果然跟Thread2不一样，算是比较可理解了，不管你按下多少次回车，只有但buffer读满了，read(in,buffer,0,buffer.length)才会返回。当然这并不是说明System.in有什么问题，System.in必须是InputStream的子类，read(byte[] b, int off, int len) 被重载，必须的。我只是好奇它到底是怎么实现的，在Thread4我做了一些尝试：

在in.available()永远有效且准确的前提下这个方法就跟System.in一样了，但我觉得这个前提很无力啊，但实际System.in它的实现是怎样的呢，还有为什么？

希望能在深入理解计算机系统找到答案，

最近看开始这本书，太棒了，才看第一章就对它入迷了，大学时代与它失之交臂真是遗憾啊。。。。啊。。。