计算机网络课的第一次实验在 Windows 平台上做的（好吧后面的都是……），网络基本命令中的 arp, ping, tracert 什么的和 Unix 下并没有什么区别，但是 nbtstat 在 Unix 下貌似没有对应的等价物了。

幸好不久前 alick 要做 PDF 转换服务于是配了一台 Windows Server 2008R2 VM (ws.tuna.tsinghua.edu.cn)，上面还跑了 cygwin 和 openssh server，于是就直接 ssh 上去(实际上是 mosh)来做计网实验了。

不过奇葩的事情发生了：

~$ nbtstat
zsh: command not found: nbtstat

第一反应是 Windows 版本太高没有 nbtstat 了……远程桌面过去开 cmd 之后发现是有 nbtstat 的，用文件管理器也可以看到 C:\Windows\System32 下确实有 nbtstat.exe。但是在 cygwin 下：

~$ ls /cygdrive/c/Windows/System32/nbtstat.exe
ls: cannot access /cygdrive/c/Windows/System32/nbtstat.exe: No such file or directory

在 Cygwin 下看到的文件系统和 cmd/文件管理器中看到的文件系统是不一样的……

放狗搜了下，发现我果然不孤单，一样有人在 Cygwin 上用 nbtstat 未遂。一位貌似 Cygwin developer 的人(他的头像是那个简陋的 Cygwin logo)回复提到是 File System Redirector 作祟。

Cygwin 是 32bit 应用程序，而 ws.tuna.tsinghua.edu.cn 是 64bit 的 OS。简单的说这是 WOW64 (Windows 32-bit on Windows 64-bit) 的一个 hack，32bit 的应用程序跑在 64bit 系统上时 C:\Windows\System32 实际上是 C:\Windows\SysWoW64。而 nbtstat.exe (因为某种神奇的原因)是 64bit-only 的，所以就直接 command not found 了。

还好这个 hack 保留了一个绕过的方法，使用 C:\Windows\Sysnative 还是可以访问真正的 system32 的。所以解决方案就是把这个目录加到 PATH 中：

~$ export PATH=/cygdrive/c/Windows/Sysnative:$PATH
~$ which nbtstat
/cygdrive/c/Windows/Sysnative/nbtstat

继续做作业吧喵……

原题

Consider nine clocks arranged in a 3x3 array thusly:

|-------|    |-------|    |-------|    
|       |    |       |    |   |   |    
|---O   |    |---O   |    |   O   |          
|       |    |       |    |       |           
|-------|    |-------|    |-------|    
    A            B            C

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O   |    |   O   |
|   |   |    |   |   |    |   |   |
|-------|    |-------|    |-------|
    D            E            F

|-------|    |-------|    |-------|
|       |    |       |    |       |
|   O   |    |   O---|    |   O   |
|   |   |    |       |    |   |   |
|-------|    |-------|    |-------|
    G            H            I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

Example

Each number represents a time accoring to following table:

9 9 12       9 12 12       9 12 12        12 12 12      12 12 12 
6 6 6  5 ->  9  9  9  8->  9  9  9  4 ->  12  9  9  9-> 12 12 12 
6 3 6        6  6  6       9  9  9        12  9  9      12 12 12 

[But this might or might not be the `correct' answer; see below.]

PROGRAM NAME: clocks

INPUT FORMAT

SAMPLE INPUT (file clocks.in)

9 9 12
6 6 6
6 3 6

OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

解题报告

这道题是有所谓的“数学解法”的。注意到：

• 钟的数量和可能的 move 的数量都是 9。
• 钟只有四个状态（12, 3, 6, 9）。这四个状态可以用同模域 ℤ₄ （在有限域算术中也记作 GF(2²)）上的 0, 1, 2, 3 表示。把钟“往后播一格”的操作就是简单的加 1。

定义钟的初始状态是 向量 a，钟 A-G 分别对应于下标 1-9。定义向量 x，x_i = 执行 Move i 的次数，这是我们要求解的向量。x_i 和 a_i 都是 ℤ₄ 的成员。方程是：

A⋅x = −a ⇒ x = −A^-1⋅a

其中 A 是一 9×9 矩阵，为

matrix([[1, 1, 0, 1, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 1, 0, 0, 0, 0],
        [0, 1, 1, 0, 0, 1, 0, 0, 0],
        [1, 0, 0, 1, 1, 0, 1, 0, 0],
        [1, 0, 1, 0, 1, 0, 1, 0, 1],
        [0, 0, 1, 0, 1, 1, 0, 0, 1],
        [0, 0, 0, 1, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 1, 0, 1, 1, 1],
        [0, 0, 0, 0, 0, 1, 0, 1, 1]])

矩阵用的是 numpy 的记法（直接复制的……），不过应该是自明的。各行对应的系数就是题目对各 Move 的说明。所以我们要做的就是在 ℤ₄ 上求矩阵 A 的逆。

不过……numpy 貌似并没有提供对有限域算术的支持。所以只能先算出矩阵的行列式和伴随矩阵，然后手工做 ℤ₄ 上的除法。然后……numpy 貌似也不能直接直接计算伴随矩阵，那就只能先算逆再乘上行列式了：

% ipython2 --pylab
...
In [21]: a
Out[21]:
matrix([[1, 1, 0, 1, 0, 0, 0, 0, 0],
        [1, 1, 1, 0, 1, 0, 0, 0, 0],
        [0, 1, 1, 0, 0, 1, 0, 0, 0],
        [1, 0, 0, 1, 1, 0, 1, 0, 0],
        [1, 0, 1, 0, 1, 0, 1, 0, 1],
        [0, 0, 1, 0, 1, 1, 0, 0, 1],
        [0, 0, 0, 1, 0, 0, 1, 1, 0],
        [0, 0, 0, 0, 1, 0, 1, 1, 1],
        [0, 0, 0, 0, 0, 1, 0, 1, 1]])

In [22]: det(a)
Out[22]: 4.9999999999999982

In [23]: int_(round_(-inv(a) * 5) % 4)
Out[23]:
array([[1, 2, 1, 2, 2, 3, 1, 3, 0],
       [1, 1, 1, 1, 1, 1, 2, 0, 2],
       [1, 2, 1, 3, 2, 2, 0, 3, 1],
       [1, 1, 2, 1, 1, 0, 1, 1, 2],
       [1, 2, 1, 2, 3, 2, 1, 2, 1],
       [2, 1, 1, 0, 1, 1, 2, 1, 1],
       [1, 3, 0, 2, 2, 3, 1, 2, 1],
       [2, 0, 2, 1, 1, 1, 1, 1, 1],
       [0, 3, 1, 3, 2, 2, 1, 2, 1]])

于是……用得到的矩阵乘上 a 就可以了。写法的话，可以把系数存成数组然后实现一下乘法，或者手写也行（因为维数也只有 9）。

Ref

USACO 答案中的 Pascal 程序……以及这里。

/************** Begin file sqliteInt.h ***************************************/
/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** Internal interface definitions for SQLite.
**
*/

传送门之一: Tcl on wikipedia, if you like it :)

传送门之二: Tcl Tutorial 下面会反复引用到，因此简称 TT。

Tcl 的语法非常好玩，让我有很强烈的实现它的冲动。我正在写一个 Tcl 解释器，为了帮助自己理清思路，写这一篇文章。闲言少叙，以下先介绍 Tcl 的基本语法。

puts、命令语句和注释语句

Ref:

[TT1] TT: Simple Text Output

# ================= 华丽的注释 =================
# `puts` 类似其它语言的 `print`。
puts "Hello, Tcl."
puts "Hello-"; puts "Tcl!" ;# 一行两句。再附带注释。

puts "Hi" # 额……我不是注释。这一句会产生语法错误。
puts "Another hi" ; # 貌似必须要有分号。But...

# Nice try. 但上面那句依然不是合法的注释。不过我是。
 # 我也不是合法的注释……

看出注释的规则了吗？首先你应该猜到了，分号 ; 和换行都可以分割语句。注释的 # 必须是语句的第一个字符，此后的的 # 则是普通字符。此外，只有换行可以结束注释，分号不行。例子：

puts #我不是注释
puts Hi ;# 注释啦啦啦; 这里依然是注释

上面的 #我不是注释 没有加引号。它是裸词，下面马上就要讲到。此外，分号不结束注释，只有换行才行。

字面量(literal)："" {} 和裸词(bareword)

Ref:

[TT1] TT: Simple Text Output

[TT2] TT: Grouping Arguments with ""

[TT3] TT: Grouping Arguments with {}

puts "Hello, Tcl." ;# 引号界定的字面量
puts {Hello, Tcl.} ;# 花括号界定的字面量
puts Hello,\ Tcl.  ;# 裸词
puts Hello, Tcl.   ;# 错误：两个裸词。`puts`只接受一个字符串参数。

|| 双引号

双引号界定的字面量内部支持 C 的转义序列，此外还允许内嵌换行：

puts "\n\t\"" ;# 换行符、制表符和双引号
puts "
\t\""         ;# 和上句输出相同

完整的转义序列语法参见 [TT2]。

|| 花括号

略显奇葩的是，花括号没有被设计成语句块界定符；它也只字面量界定符，只是内部不支持转义序列：

puts {\n\t} ;# => \n\t
puts {
int main();
}

但是花括号有一个有趣的性质。左右花括号是配对的，这一点就十分类似 C 的语句块了：

puts {{ } { }} ;# => { } { }
puts {
int main() {
    printf("Hello, world!\n");
}
}

然而花括号中并没有其它的语法结构，例如双引号界定的字面量：

puts {"Quoted?}"} ;# 错误；花括号内部并不识别引号界定的字面量
puts {"Quoted?}   ;# => "Quoted?

继续花括号：

puts {\{}      ;# => \{
puts {\}}      ;# => \}

如上所见，在花括号字面量内用 \{ 和 \} 可以防止它们参与花括号匹配，但是它们的值仍然是 \{ 和 \} 而不是 { 和 }。

后面我们将看到，花括号的这些性质如何被巧妙地用来构建 Tcl 的语句块。

|| 裸词

不以双引号或者左花括号开头的字面量就是裸词(bareword)。裸词使用空白符界定；如果要在裸词内部嵌入空白符，应使用转义序列。

puts }               ;# => }
# 单引号是普通字符，不是字面量界定符。
puts 'I'm\ bare      ;# => 'I'm bare
puts \n\tBare,\ too! ;# => <换行><制表>Bare, too!

你可能已经猜到，反复出现的 puts 命令(command)（等同于一般所说的函数或者过程）其实也是一个裸词。在 Tcl 中上述三种字面量是等价的：

 puts   Hello!
"puts" "Hello!"
{puts} {Hello!}

这种语法单元都是 Tcl 的词(word)。

|| 语句结构(statement)

既然裸词和另外两种字面量是等价的，Tcl 如何区分把 puts 这类 函数/命令/指令/过程和字符串区分开？类似于 shell 语言，只有每个语句的第一个词是命令，其余的都是简单的字符串。

puts puts #; => puts

语法小结

用上下文无关文法(Context-free grammar, CFG)给出本文描述的 Tcl 语法。

下面的 CFG 使用我自创的记法。单引号内表示简单的终止符号(terminal symbol)，圆括号内是 UNIX 正则表达式(UNIX regular expression)。:= 左侧给出的是非终止符号(non-terminal symbol)，右侧是推导规则(induction rule)。同一个符号的多个规则之间隐含的是逻辑或 |。

本文略去了不少细节，所以下面并不是正确的 Tcl 语法。此外下述语法假定 Tcl 源文件以一个换行结尾。

source    := 'eof'
             statement source
statement := comment
             command
comment   := '#' ([^\n]*) '\n'
command   := '\n' | ';'
             word command
word      := bareword | quoted | curlied
quoted    := '"' ([^"]*) '"'

bareword 和 curlied 的语法我暂时没有找到比较简单的描述方法……

为了满足自己的吐槽需求，特将今天的课的吐槽点列举如下……

NOTICE: 此条目需要补充更多来源。

• 老师曰，C++ 比 C 强大，更适合用来构建大型软件。实际上，C 依然经常被用来构建大型软件[1]。因为 C++ 虽然有更多特性，但是太乱了……所以有些人宁愿用相对简单的 C。
• 老师曰，Apple、Google 和 AT&T 用得最多的都是 C++。事实上，Apple 的主力开发语言是 Objective-C，而 Google 则是 Java 和 Python。AT&T 我就不是很了解了……
• 老师貌似不知道我说的外部连接是啥意思。老师问我，哪些东西放在 .h 文件里面哪些放在 .c 里面，我说具有外部连接的就放在 .h 文件里面。老师说我说得不全对，然后用他的话把外部连接解释了一次。。
• 老师曰，C 的 char 类型是有符号(signed)的。实际上，char 类型可能是 signed 也可能是 unsigned，C 的标准对此没有规定。例如，据 ZZ 所说，gcc 的 char 是 unsigned char，而 VC 的 char 是 signed char。(UPDATE: gcc 的 char 是 signed char。)
   

附注

1. Programming Language Popularity 针对各大语言的采用比率给出了详细的统计。

原来的 xiaqqaix.tk 的虚拟空间有问题，因为本来就很便宜，懒得去交涉了，况且我也不是很清楚什么地方出了问题……

Anyway, 这是我的又一个博客。is-programmer.com 使用基于 Ruby on Rails 的 Chito，整体感觉很不错。