方丈記 – 逝水轻尘(鴨長明)

此文原文摘自【方丈記】第22-23頁。
文書卷帙之間,算是逃避性消遣,
便隨便譯了一下——

 

【原文】

ゆく川のながれは绝えずして、しかも、本の水にあらず。よどみに浮ぶうたかたは、かつ消えかつ结びて久しくとゞまりたる例なし。世中にある、人と栖と、またかくの如し。

たましきの都のうちに、棟を並べ、甍を争へる、高き、いやしき、人の住ひは、世々を經て盡きせぬものなれど、これをまことかと尋(ぬ)れば、昔しありし家は稀なり。或は去年焼けて今年作れり。或は大家滅びて小家となる。住む人もこれに同じ。所も変らず、人も多かれど、いにしへ见し人は、二三十人が中に、わづかにひとりふたりなり。朝に死に、ゆふべに生るゝならひ、たゞ水の泡にぞ似たりける。不知、生れ死(ぬ)る人、何方より来たりて、何方へか去る。また不知、假の宿り、谁が為にか心を恼まし、何によりてか目を喜ばしむる。その、主と栖と、无常を争ふさま、いはゞ朝颜の露にことならず。或は露おちて花のこれり。残るといへども朝日に枯れぬ。或は花はしぼみて露なほ消えず。消えずといへどもゆふべを待つことなし。

【譯文】

白川静流,流水逝水非静水;
泡浮尘世,且消且结且珍惜。
论及鸟鱼世人,栖居之所,亦作同理——

敷金缀玉之都,鳞次栉比,雕梁画栋间,诸人等等居所,忝列贵贱,
阑干经世而不尽不灭,然寻根溯源,旧时却无多少帝王百姓家。
细而观之,或去年所焚毁,今年得再造;
或家事衰灭,堵圮异爨,大院已成小宅。
房中之人,确实不变。而,虽栖居屋所不变,人丁不减,
然当年所见之人,已不存十分之一也。

早成晚殁,朝亡夕生,好似泡浮飞沫。
不知大江东去,逝者如斯,自何方来,向何处去;
亦不知,此生委身非我之世,寄人篱下,为谁恼心,又为何悦色。
只看那高楼宴宾间,主人争相无常,又何尝不似朝露日烯——
或露落而花残,花残不待朝日;
或花谢而露不消,露消不待夕阳。

N个女人的老死不相往来——n皇后问题

知乎问题链接:如何用C++10行内写出八皇后

前日闲暇之余乱逛,看到了这个问题,觉得蛮有意思。
也顺便想改进一下通行的官方解法,就认真写了一下,
顺便也把自己作为外行人的一点感想列在下面。

n皇后问题,较早为八皇后问题,出现于1848年。
Max Bezzel讨论的是“在国际象棋上出现8个后时,
应该如何排列,才可使她们不会相爱相杀。”

(八皇后问题的其中一个解)

虽然依照升变原则,同棋盘上可以出现17个后,
(一方全升变,一方被吃过路兵一次,加上初始两个)
但是真正走出来的可能性是微乎其微的。
况且这个问题没有考虑黑白方关系,
在象棋上也就是趣味的一问而已。
——直到图论和函数式编程思想出现,
穷举法和递归思想使得92个解终于呼之即出。

前面说到,n皇后问题的解法都是穷举法及递归,
加上回溯算法实现。这对于刚入门的傻喵来讲,
是很好的练习题目了——

' n queens cast by go basic
[loop]
input "How many queens (N>=4)";n
if n < 4 then
 print "Must be greater than 4"
 goto [loop]
end if
 
dim plot$(100,100)
dim q(n+20)
dim e(n+20)
dim o(n+20)
r=n mod 6
if r<>2 and r<>3 then 
  gosub [samp]
  goto [shoBoard]
end if
for i=1 to int(n/2)
  e(i) = 2 * i
next
for i=1 to int((n/2)+.5)
 o(i) = 2 *i-1
next
if r = 2 then gosub [edt2]
if r = 3 then gosub [edt3]
s = 1
for i=1 to n
  if e(i)>0 then 
    q(s) = e(i)
    s    = s+1
  end if
next
for i=1 to n
  if o(i) > 0 then 
    q(s) = o(i)
    s    = s + 1
  end if
next
' print board
[shoBoard]
cls
for i = 1 to n
  plot$(i,26-q(i)) = "*"
  plot$(i,24-n)    = chr$(96+i)
  plot$(n+1,26-i)  = str$(i)
next i
for ii = 1 to 100
 for jj = 1 to 100
  print left$(plot$(jj,ii)+" ",1);
 next jj
print
next ii
end
 
' the simple case
[samp] 
p = 1
for i = 1 to n
  if i mod 2=0 then 
    q(p) = i
    p    = p + 1
  end if
next i
for i = 1 to n
  if i mod 2 then 
    q(p) = i
    p    = p + 1
  end if
next
return
' edit list when remainder is 2
[edt2]
for i=1 to n
  if o(i) = 3 then 
    o(i) = 1 
   else 
    if o(i)=1 then o(i) = 3
  end if
  if o(i) = 5 then 
    o(i)= o(i) -1 
   else 
    if o(i) = 0 then 
      o(i) = 5
      return
    end if
  end if
next
 
' edit list when remainder is 3
[edt3]
for i = 1 to n
  if e(i) = 2 then 
    e(i)  = e(i)-1 
   else 
    if e(i) = 0 then 
      e(i) = 2
      goto [more]
    end if
  end if
next i
' edit list some more
[more]
for i = 1 to n
  if (o(i)=1 or o(i)=3) then 
    o(i) = o(i)-1 
   else 
    if o(i) = 0 then 
      o(i)   = 1
      o(i+1) = 3
      return
    end if
  end if
next

或是这样的尝试——

# Brute force permutations for 8 queens by R

safe <- function(p) {
  n <- length(p)
  for (i in seq(1, n - 1)) {
    for (j in seq(i + 1, n)) {
      if (abs(p[j] - p[i]) == abs(j - i)) return(F)
    }
  }
  return(T)
}
 
queens <- function(n) {
  p <- 1:n
  k <- 0
  while (!is.null(p)) {
    if(safe(p)) {
      cat(p, "\n")
      k <- k + 1
    }
    p <- next.perm(p)
  }
  return(k)
}
 
queens(8)

在好多人的口中,递归+穷举已然成为了8皇后问题的标准答案。
但是时代还是会变的,人的能力也是在随着问题进步的。
当面临N皇后问题时,传统的方法则捉襟见肘。

虽然有人推荐直接向上抽象,利用已有的库来简化方法,
但是私以为,练习归练习,学习归学习,但不能只会做一个传道者,
迷信工具,迷信顶层,而没有透彻的基础认识。
工具看了手册谁都会用,为什么用,怎么用,好不好则更加重要。
就像是学习语言或是诊断学,迷信书本只知所以然是万万不可的。
——只会利用工具的人,终究会被工具抛弃。

回到问题上来。

N皇后问题中,穷举法的复杂度为(n!),
但若是采用和某些逻辑题一样的算法,则可以大大简化代码。

首先,国际象棋的后拥有两种攻击方式:
好似城堡的十字攻击以及骑士的对角攻击,攻击范围无限制:

从而得出两个预结论——
1 N皇后于NxN棋盘上,若老死不相往来,则绝不在同一行列。
2 攻击范围有重叠时,绝非边与边重叠,只可相交,且相交仅会出现一次。
于是便可以将棋盘格子赋予是否安全的属性,1为受到攻击位置,0安全。
从第一条边向第八条边推进,标注所有可能的攻击位置,发现0则置子,
发现一个以上的安全位置,则从一个方向起下子,深度优先遍历。

于是使用位运算,将n~1横列化为n个二进制数,指定0位安全;
由预结论1,不考虑所下子横行上的攻击(下子后必然全为1);
由预结论1,copy下子所在竖列的状态至下一行;
利用位移运算符定义两种对角攻击模式。
以上图第4横行为例,下子状态标注为 0001 0000
(计算第5横行时,下子状态保留为 0001 0000,
攻击范围则将下子状态左移/右移一位,
分别是 0010 0000 和 0000 1000。
将三个状态列取或运算,则结果中的0位为安全位置。

于是——

#include <iostream>

// total:记录解;finishline:确认的行
int total = 0, finishline = 1;

// row:竖直攻击; ls:斜杠攻击; rs:反斜杠攻击
void trying(long row, long ls, long rs)
{
	if (row != finishline) // 开始新行
	{
		long position = finishline & ~(row | ls | rs);
		while(position) // 若行间无位可放...
		{
			long pointline = position & -position;
			position -= pointline;
			trying(row + pointline, (ls + pointline) << 1, (rs + pointline) >> 1);
		}
	}
	else 
	{
		total++;
	}
}

using namespace std;

int main(int argc, char *argv[]) {
	int grid = 8; // 修改grid的话,1~31皇后都能解w

finishline = (finishline << grid) - 1;

trying(0, 0, 0);

cout << total << endl;

return 0;

}

事就这么成了。

回到最早的知乎问题上去。我真的不明白为什么要限制行数,
而不是限制时间和内存,
但也因为这个问题看似哗众取宠,
便在想是不是某种形式的软广告。

不过最有意思的事情是问题下面百花齐放的代码。
有人简化变量名到一个字符,有人省略头文件,
有人把所有的东西挤成一行,自然注释都没有。
不用说美感,就连维护都是问题。
自己都看不懂了,就为了10行,图啥?
可谓是为完成任务而完成任务了的哗众取宠了。
还有人直接就import <8queens>,
抑或是贬损除了暴力枚举之外的其他算法,
真的是不知道什么逻辑了。

学习计算机科学到现在,傻喵越来越觉得,
好多东西都是如此相通的——
会用工具却拘泥于工具的人;
认为掌握工具便算精通的人;
知道规则便想创造规则的人;
末法心态的,实用主义的人。
希望我不会变成他们那样。。。

更愿意从数学汇编一步步学起,
就像当年从解剖学一步步学起,
就像当年从桥本文法开始学起,
就像当年从吹长音一步步学起,
这样,我想算是专业的负责吧。

不管。总之先把题答了——

#include <iostream>
int total = 0, finishline = 1;
void trying(long row, long ls, long rs){
if (row != finishline) { long position = finishline & ~(row | ls | rs);
while(position) { long pointline = position & -position; position -= pointline; trying(row + pointline, (ls + pointline) << 1, (rs + pointline) >> 1); }} else {total++;}} 
using namespace std;
int main(int argc, char *argv[]) {
int grid = 8; // 修改grid的话,1~31皇后都能解w
finishline = (finishline << grid) - 1; trying(0, 0, 0); cout << total << endl;
return 0;}

嗯。能看得懂,10行也就差不多这样了。

不过,如果八皇后问题真的会在项目里用到,
我则绝不会使用上面的所有程序,而会——

// 此处需使用八皇后算法,但忽略计算过程,仅使用答案节省时间。
// 八皇后解枚举数据头在******
void 8queensAnswers (0, 0, 0, 0)
//在里面做一个调用92个答案的接口,传参出去给大结构体
//保存各个答案类似于[91, 0, 4, 7, 5, 2, 6, 1, 3]这样
//或者n皇后的话[0,1][1,0][2,0][3,2][4,10][5,40]...这样

复杂度为1或是常数n,为啥不用?多好。

至于说怎么显示N皇后问题的解的话w
手动艾特@CocoaOikawa~

N皇后问题——记录下那些老死不相往来的N个女人的位置吧

以上ヾ(๑╹◡╹)ノ”

【翻译】Viva La Vida 我心不息 – ColdPlay

 

每次忧伤的时候就会发翻译呢。w

 

I used to rule the world
万千世界我曾主宰,

Seas would rise when I gave the word
山海排闼只为我而开;

Now in the morning I sleep alone
现在却在雾中醒来,

Sweep the streets I used to own
在我的故土失意徘徊。

 

I used to roll the dice
以生死押注打牌,

Feel the fear in my enemy’s eyes
品味恐惧在对手眼中绽开。

Listen as the crowd would sing:
得意侧耳万民青睐——

“Now the old king is dead
“先王老矣!”

Long live the king ”
“吾王万代!”

 

One minute I held the key
而后当我执掌权脉,

Next the walls were closed on me
却发现宫门深似海——

And I discovered that my castles stand
转身凝望社稷和城稗,

Upon pillars of salt’ pillars of sand
基地散如盐砂乱似尘埃。

 

I hear Jerusalem bells a ringing
听宣礼塔上钟声传来,

Roman Cavalry choirs are singing
看铁骑高呼 声震江海,

Be my mirror my sword and shield
做我明镜利剑和盾牌,

My missionaries in a foreign field
新约旧约传扬在国境之外。

For some reason I can’t explain
只有一事我无法释怀:

Once you gone there was never’
当你离开就不再——

Never an honest word
不再有心为我敞开,

That was when I ruled the world
这就是我一统的时代。

 

It was the wicked and wild wind
凛冽寒风挟肃杀而来,

Blew down the doors to let me in
重门猎猎投我入重霾。

Shattered windows and the sound of drums
骄傲不再、礼崩乐坏,

People couldn’t believe what I’d become
暴民要审判我的将来。

 

Revolutionaries wait
起义大军翘首以待,

For my head on a silver plate
我的头被斩下,被挂起来;

Just a puppet on a lonely string
正如傀儡断线无神摇摆——

Oh who would ever wanna be king
呜呼!谁又渴望受人膜拜!

 

I hear Jerusalem bells a ringing
听宣礼塔上钟声传来,

Roman Cavalry choirs are singing
看铁骑高呼 声震江海,

Be my mirror my sword and shield
做我明镜利剑和盾牌,

My missionaries in a foreign field
新约旧约传扬在国境之外。

For some reason I can’t explain
只有一事我无法释怀:

I know Saint Peter won’t call my name
不再有天使对我礼拜。

Never an honest word
不再有心为我敞开,

That was when I ruled the world
这就是我一统的时代。

 

(Ohhhhh Ohhh Ohhh)

 

I hear Jerusalem bells a ringing
听宣礼塔上钟声传来,

Roman Cavalry choirs are singing
看铁骑高呼 声震江海,

Be my mirror my sword and shield
做我明镜利剑和盾牌,

My missionaries in a foreign field
新约旧约传扬在国境之外。

For some reason I can’t explain
只有一事我无法释怀:

I know Saint Peter won’t call my name
不再有天使对我礼拜,

Never an honest word
不再有心为我敞开,

That was when I ruled the world
这就是我一统的时代。