受APL启发的一个Ruby语句中的生命游戏

2020-05-17 09:52:06

不过,让我解释一下。上周,我偶然发现了一个新的APL道歉帖子。它深深地触动了我的心弦,并给了我一种冲动,想要再次尝试理解这种美丽而奇怪的语言。

我(有点出乎意料地)发现,除了使用广泛的字符集和极端简洁之外,APL还有两个与Ruby一点也不陌生的主要特性:通过操作链接进行计算,以及适合于所述链接的扩展的数组操作库(在Ruby中,它们由Enumerable模块表示)。

在这一点上,我觉得可能一些APL方法和示例可以非常直接地转换为Ruby,这将是惯用的Ruby。为了挑战这种感觉,我尝试翻译著名的APL单行代码Conway的Game of Life实现,并成功地在一条Ruby语句中实现了GOL。

当然,实现需要“数学数组”的概念,与APL的概念相匹配,所以从技术上讲,它是“一条语句加支持类”,但我仍然倾向于将其视为“一条语句”的概念,因为实现的类是通用的(有点像Numo::Narray),并且所使用的操作对任何Rubyist来说都很熟悉。

要立即查看最终实现,您可以直接跳到回购。本文的其余部分将严格按照APL版本中的解释来完成实现过程。

在APL中,array是一个数学数组:它是一个由标量组成的矩形多维矩阵。在Ruby代码中用APL::Ary表示,在下面的解释中简称为AA。

标量是数字、字符或其他数组。这意味着不应该混淆多维数组(矩阵,在某一维旁边有相等数量的元素)和嵌套数组。示例:

放置AA[1,2,3,4]。RESHAPE(2,2)#1 2#3 4#--二维数字矩阵放入AA[AA[1,2],AA[3,4]]#┌─┐┌─┐#│1 2││3 4│#└─┘└─┘#--两个一维数组的一维数组。#注意嵌套数组周围的框架有助于理解嵌套

A=AA[1,2]放入#1 2放入a。WRAP#┌─┐#│12│#└─┘放置一个。包起来。展开#1 2。

与通常的数学数组一样,可以使用标量(如“将2加到每个元素”)或另一个相同形状的数组(如“将数组A的项添加到数组B的类似位置的项”)来执行数学运算。

话虽如此,让我们从生活游戏的第一代开始吧:

current_gen=aa[0,0,0,0,0,0,0,1,1,0,0,1,1,0,0,0,0,1,0,0,0,1,0,0]。RESHAPE(5,5)将CURRENT_GEN#0 0 0#0 0 1 1 0#0 1 1 0 0#0 0 1 0 0#0 0 0。

到目前为止,我们刚刚创建了一个由1和0组成的数组,并将其“重塑”为5×5的二维矩阵。

放置current_gen。hRotate(1)#0 0 0#0 1 1 0 0#1 1 0 0#0 1 0 0 0#0 0 0。

#hRotate只是将每行中的值循环向左移位,类似于(仅一维)Array#Rotation of Ruby。

现在,让我们生成旋转的3种变体:1种向左,无一种,1种向右:

当前一代。包起来。产品(AA[-1,0,1],&;:hRotate)#┌─┐#│0 0 0││0 0 0││0 0 0│#│0 0 0 1 1 1││0 0 1 1 0││0 1 1 0 0│#│0 0 1 1 0││0 1 1 0 0││1 1 0 0 0│。#│0 0 0 1 0││0 0 1 0 0││0 1 0 0 0│#│0 0 0││0 0 0││0 0 0│#└─┘。

让我们从#product开始:它类似于Ruby的Array#product(将两个数组进行所有可能的组合),但有一个重要的区别:APL的“product”不只是生成组合,而是接受立即应用于它们的操作。因此,在香草红宝石中:

这里的#WRAP是必需的,所以我们将只产生一个完整的数组(作为标量)-1、0和1,而不是每个数字每个行。

现在,让我们进行更多的旋转,将所有数字垂直移位-1、0和1:

放置current_gen。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(AA[-1,0,1],&;:vRotate)#┌─┐#│0 0 0││0 0 0││0 0 0 1 1│#│0 0 0││0 0 0 1 1││0 0 1 1 0│#│0 0 0 1 1││0 0 1 1 0││0 0 0 1 0│。#│0 0 1 1 0││0 0 0 1 0││0 0 0│#│0 0 0 1 0││0 0 0││0 0 0│#└─┘#┌─┐┌─┐┌──。─┐#│0 0 0││0 0 0││0 0 1 1 0│#│0 0 0││0 0 1 1 0││0 1 1 0 0│#│0 0 1 1 0││0 1 1 0 0││0 0 1 0 0│#│0 1 1 0 0││0 0 1 0 0││0 0 0│#│0 0 1 0。0││0 0 0││0 0 0│#└─┘#┌─┐#│0 0 0││0 0 0││0 1 1 0 0│。#│0 0 0││0 1 1 0 0││1 1 0 0 0│#│0 1 1 0 0││1 1 0 0 0││0 1 0 0 0│#│1 1 0 0 0││0 1 0 0 0││0 0 0│#│0 1 0 0 0││0 0 0││0 0 0│#└─┘└。─┘└─┘。

请注意,我们当前看到的是由2维矩阵(5×5)组成的2维矩阵(3×3):内部矩阵被包裹在帧中。

放置current_gen。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(aa[-1,0,1],&;:vRotate)。Reduce(&;:+)。Reduce(&;:+)#┌─┐#│0 1 2 2 1│#│1 3 4 3 1│#│1 4 5 4 1│#│1 3 3 2 0│#│0 1 1 1│#└─┘。

这里的#Reduce是相同的可枚举数#Reduce。重要的特性是APL样式的数组是按元素求和的,所以现在我们有了所有9个矩阵的总和,表示每个单元有多少活动邻居(包括其自身)。

现在,应该注意的是,下一代应该只有3或4个细胞存活:

单元格为3表示“活着+2个邻居”(活着的条件)或“空着3个邻居”(变成活着的条件)。

4的意思是“活着+3个邻居”(活着的条件)或“空着,有4个邻居”(不是活着的条件)。

为了检查“它是否等于某物”,我们实现了.eq运算符。这可能是解决方案中最“非Rubyish”的部分:它不是生成true/false,而是提供1/0。不幸的是,对于算法来说,始终保持数字形式很重要。

放置current_gen。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(aa[-1,0,1],&;:vRotate)。Reduce(&;:+)。Reduce(&;:+)。eq(3)#┌─┐#│0 0 0│#│0 1 0 1 0│#│0 0 0│#│0 1 1 0 0│#│0 0 0│#└─┘PUT CURRENT_GEN。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(aa[-1,0,1],&;:vRotate)。Reduce(&;:+)。Reduce(&;:+)。EQ(4)#┌─┐#│0 0 0│#│0 0 1 0 0│#│0 1 0 1 0│#│0 0 0│#│0 0 0│#└─┘。

但是,我们也可以同时应用这两种操作,从而产生两个元素的数组(在APL中,多次执行一个操作的能力称为渗透):

放置current_gen。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(aa[-1,0,1],&;:vRotate)。Reduce(&;:+)。Reduce(&;:+)。EQ(AA[3,4])#┌─┐┌─┐#│0 0 0││0 0 0│#│0 1 0 1 0 0││0 0 1 0 0│#│0 0 0││0 1 0 1 0 0│#│0 1 1 0 0││0 0 0│#│0 0 0││0 0 0│。#└─┘└─┘。

现在,我们需要向第二个数组添加“它是否活着”的条件。只需使用原始数组即可轻松执行(&Amp;ing)。为了不中断我们的操作链,我们还将使用1(无操作)的第一个数组(&;amp;):

放置current_gen。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(aa[-1,0,1],&;:vRotate)。Reduce(&;:+)。Reduce(&;:+)。EQ(AA[3,4])。Zip(AA[1,current_gen],&;:&;)#┌─┐┌─┐#│0 0 0││0 0 0│#│0 1 0 1 0││0 0 1 0 0│#│0 0 0││0 1 0 0 0│#│0 1 1 0 0││0 0 0│#│0 0 0││0 0 0│#。└─┘└─┘。

这里的#zip和上面的#product一样,几乎类似于Ruby的Array#zip,但也将提供的操作应用于每一对。

放置current_gen。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(aa[-1,0,1],&;:vRotate)。Reduce(&;:+)。Reduce(&;:+)。EQ(AA[3,4])。Zip(AA[1,current_gen],&;:&;)。Reduce(&;:|)#┌─┐#│0 0 0│#│0 1 1 1 0│#│0 1 0 0 0│#│0 1 1 0 0│#│0 0 0│#└─┘。

…。这几乎就是我们的最终答案,但它仍然是一个“内含数组的标量”,我们需要将其解开:

放置current_gen。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(aa[-1,0,1],&;:vRotate)。Reduce(&;:+)。Reduce(&;:+)。EQ(AA[3,4])。Zip(AA[1,current_gen],&;:&;)。Reduce(&;:|)。展开#0 0 0#0 1 1 1 0#0 1 0 0 0#0 1 1 0 0#0 0 0。

定义寿命(CURRENT_GEN)CURRENT_GEN。包起来。产品(aa[-1,0,1],&;:hRotate)。产品(aa[-1,0,1],&;:vRotate)。Reduce(&;:+)。Reduce(&;:+)。EQ(AA[3,4])。Zip(AA[1,current_gen],&;:&;)。Reduce(&;:|)。展开末端。

Life←{↑1⍵∨.∧3 4=+/,‘1 0 1∘.⊖’1 0 1∘.⌽⊂⍵}。

def life(CURRENT_GEN)#LIFE←{--函数声明CURRENT_GEN#⍵--函数参数。包装#⊂--WRAP使其成为标量。产品(#∘.。--乘积AA[-1,0,1],#‘1 0 1-1,0,1(是的,’1是-1)&;:h旋转)#⌽--h旋转。产品(#∘.。--product AA[-1,0,1],#‘1 0 1&;:vRotate)#⊖--vRotate。Reduce(&;:+)。Reduce(&;:+)#+/,--Reduce两次?4.EQ(#=AA[3,4])#3。Zip(#--见下文?关于这3行AA[1,CURRENT_GEN],#1⍵&;:&;)。Reduce(&;:|)#∨.∧。展开#↑--展开结束#}

«我做了两个简化:放弃了实现“一次减少两个级别”(两个减少就足够短了),以及从相当复杂的APL的“内积”运算符(它接受两个函数,并将它们变成我用Zip+Reduce的常规Ruby表示的东西)。

最初的APL文章通过将Glider移动到10×10网格来演示其用法。我们试试这个吧。但首先,我们需要一种方法来显示这两个0和1,使它们看起来更漂亮一些。同样,借用APL:

def show(Grid)#APL风格的aa#valuesat(Aa)生成第一个数组中的项目数组,并使用第二个数组中的数字作为索引进行整形。将AA[';';,';█';]放入。(栅格)端点处的值_。

Glider=AA[1,1,1,1,0,0,0,0,1,0]。重塑(3,3)栅格=滑块。采用(-10,-10)显示栅格。WRAP#┌─┐#││#│█│#└─┘Generations=[GRID]9。乘以{世代<;<;生活(世代。last)}show AA[*GENERATIONS]#或者,更简单地,使用2.7的枚举器#产生:世代=枚举器。生产(栅格){|cur|寿命(Cur)}。取(10)。映射(&;:WRAP)显示AA[*层代]#┌─┐┌─┐┌─。─┐┌─┐#│。│#│#│█│#│。│█││█││██│#│█││█││██││█││██。│#│█││█││██││█│#│█││██││█│。│#│█│#└─┘└─。─┘└─┘