Subscribed unsubscribe Subscribe Subscribe

Sierpinski triangleワンライナー

perldoc Acme::EyeDrops から引用。
こういう図形のことはしっていたけど、こういう名前だったのか。
シェルピンスキーのギャスケット - Wikipedia

$ perl -le '$x=2**pop;print$"x--$x,map$x&$_?$"x2:"/\\",0..$y++while$x' 4
               /\
              /\/\
             /\  /\
            /\/\/\/\
           /\      /\
          /\/\    /\/\
         /\  /\  /\  /\
        /\/\/\/\/\/\/\/\
       /\              /\
      /\/\            /\/\
     /\  /\          /\  /\
    /\/\/\/\        /\/\/\/\
   /\      /\      /\      /\
  /\/\    /\/\    /\/\    /\/\
 /\  /\  /\  /\  /\  /\  /\  /\
/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\/\

ぬは。すげーー!


解読してみる。

$ perl -MO=Deparse -le '$x=2**pop;print$"x--$x,map$x&$_?$"x2:"/\\",0..$y++while$x' 4
BEGIN { $/ = "\n"; $\ = "\n"; }
$x = 2 ** pop(@ARGV);
print $" x --$x, map(($x & $_ ? $" x 2 : '/\\'), 0 .. $y++) while $x;

最初に、$x に 2の<引数>乗の値が入る。引数が1なら2、引数が2なら4、引数が3なら8、...

$x = 2 ** pop(@ARGV);

で、この $x が0より大きい限りはwhile文として以下が繰り返される。

print $" x --$x, map(($x & $_ ? $" x 2 : '/\\'), 0 .. $y++) 

ちなみに -l スイッチによって $\ = "\n" になっているので、print1回毎に改行される。
最初に空白を出力すると同時にこの $x をデクリメントしていく。

print $" x --$x

$" はデフォルトで半角スペース、それを x 演算子で $x 個つなげたもの、をまず出力している。これで三角形の左側の空白を作っているわけだ。
このデクリメントは別にprint関数内じゃなくてwhileの評価の部分でしてもいい気がする。

$ perl -le '$x=2**pop;print$"x$x,map$x&$_?$"x2:"/\\",0..$y++while$x--' 4
$ perl -MO=Deparse -le '$x=2**pop;print$"x$x,map$x&$_?$"x2:"/\\",0..$y++while$x--' 4
BEGIN { $/ = "\n"; $\ = "\n"; }
$x = 2 ** pop(@ARGV);
print $" x $x, map(($x & $_ ? $" x 2 : '/\\'), 0 .. $y++) while $x--;

というように書き換えても動作は同じだと思う。


ここからがメインの三角形の部分。

map(($x & $_ ? $" x 2 : '/\\'), 0 .. $y++)

$y はどこにも定義されていない変数なので、0から始まりwhile文が回る毎にインクリメントされていく。
ということはmap関数の第2引数に入るLISTはwhile文で繰り返されるたびに

(0)
(0, 1)
(0, 1, 2)
(0, 1, 2, 3)
...

というように増えていくことになる。
で、このLISTに対しmap関数で行っている操作。

($x & $_ ? $" x 2 : '/\\')

ぱっと見ただけではよく分からない…
実際に $x をデクリメントさせ LIST を増加させながら見てみよう。

$ perl -le 'print map { 7 & $_ ? "  " : "/\\" } 0 .. 0'
/\  
$ perl -le 'print map { 6 & $_ ? "  " : "/\\" } 0 .. 1'
/\/\  
$ perl -le 'print map { 5 & $_ ? "  " : "/\\" } 0 .. 2'
/\  /\  
$ perl -le 'print map { 4 & $_ ? "  " : "/\\" } 0 .. 3'
/\/\/\/\  
$ perl -le 'print map { 3 & $_ ? "  " : "/\\" } 0 .. 4'
/\      /\  
$ perl -le 'print map { 2 & $_ ? "  " : "/\\" } 0 .. 5'
/\/\    /\/\  
$ perl -le 'print map { 1 & $_ ? "  " : "/\\" } 0 .. 6'
/\  /\  /\  /\  
$ perl -le 'print map { 0 & $_ ? "  " : "/\\" } 0 .. 7'
/\/\/\/\/\/\/\/\/

なるほ…ど…?なんとなく見えてきたような…?
0 から $y までの数値のうち、$x との論理積が真(0以外の値)になるときだけ空白になっている。
つまり1つ以上の共通のビットが立っているときだけが真。
もうちょい並べて考えてみる。

$x      0..$y
f(1111) 0
e(1110) 01
d(1101) 0*2
c(1100) 0123
b(1011) 0***4
a(1010) 01**45
9(1001) 0*2*4*6
8(1000) 01234567
7(0111) 0*******8
6(0110) 01******89
5(0101) 0*2*****8*a
4(0100) 0123****89ab
3(0011) 0***4***8***c
2(0010) 01**45**89**cd
1(0001) 0*2*4*6*8*a*c*e
0(0000) 0123456789abcdef

'*'に置き換えたところが論理積が真になる部分。
確かにシェルピンスキーのギャスケットを描いている。
こう書いてみると、なんとなく納得はできる。
この性質を利用してやれば最初のワンライナーでたしかにあの図形が描けるね、と。


けど、どうしてこうやって作ることができるのかが分からない。
このアイデアが天才的すぎて、考えたヤツ変態だ、としか思えない。。。
デクリメントする数値と、増加していくリストの各要素との「論理積」をとることでこのシェルピンスキーのギャスケットを描けるようになる原理を知りたい。
もうちょっと考えてみよう。
もしくは誰か頭の良いヒト教えてくれないかなー