ときどきの雑記帖 RE* (新南口)

十月の旅人

シェルスクリプトマガジン

奇数月の25日が発売日だったよなあと、 先月の20日過ぎあたりから(25日より前に置いていることもあるので) 秋葉原の書泉ブックタワーに行ったときなどに 新しいのが出ていないか雑誌コーナーを見ていたのだけど、 全然見かけない。

なにかあったんだろうかとサイト を見ても特にお知らせはなく。 ふと思い立ってTwtterで検索してみると…

ありゃま。

オライリージャパンの近刊

出版予定の本のタイトルを眺めていたらこれに遭遇。

お

の翻訳本か。

よく見たら O’Reilly Japan - Books :: New and Upcoming にも出ていた。

considered harmful

Binary Circles (続き)

前回

Binary Circles

という記事にたどり着きました。 この記事に手作業で問題の文字列(のパターンの一つ)を求める手順がありますので、 興味のある方は是非手を動かして確かめてみてください😄

と書いていたことの補足。

さて。

全探索で見つかった256個の文字列を8が先頭に来るように並べ替え、 さらに重複を取り除くとこんな感じになります。

80124936DA5B7FEC
80124937FEDA5B6C
80125A4936DB7FEC
80125A4937FEDB6C
80125B6C937FEDA4
80125B6DA4937FEC
80125B7FEC936DA4
80125B7FEDA4936C
80136C925B7FEDA4
80136DA4925B7FEC
80136DA5B7FEC924
80136DB7FEC925A4
80137FEC925B6DA4
80137FEDA4925B6C
80137FEDA5B6C924
80137FEDB6C925A4

するといくつかの規則めいたものが見えてきます。 たとえば

  • 8 0 1 は必ずこの順番で現れる
  • 7 F E は必ずこの順番で現れる
  • 0 、F 、8、7以外の文字の後に現れる文字はそれぞれについて2種類(ある|しかない)

といったところです。

ではこれを踏まえた上でリンク先の記事を読み進めます。

Let X be the hex representation of 4 bits.
The "X<<0" column is what would happen if you
dropped the leftmost bit and added a zero on
the right.  The "X<<1" column is what would
happen if you dropped the leftmost bit and
added a one on the right. Let X' be the
hex representation of the 4 bit pattern that
will follow X in the series.

16進数を表すものなのでそれを表現する(区別する)のに 4ビットが必要になります。 そしてある文字の後続に来うる数字(16進数字をあらわす文字)というのは、 その数字のビットパターンを左へ1ビットシフトし、空いたビットに 0か1のいずれかを入れたものになります (シフト後の最上位ビットは無視)。

これを16進表記で

X X' X X' X«0 X«1
0-? 8-? 0 1
1-? 9-? 2 3
2-? A-? 4 5
3-? B-? 6 7
4-? C-? 8 9
5-? D-? A B
6-? E-? C D
7-? F-? E F

こんな感じの表にまとめます。

この表は 0と8の後続にできる(これる)のは0(X«0の場合)か1(X«1の場合)、 1と9の後続にできるのは2(X«0の場合)か3(X«1の場合)、 のように読みます。

Since you don't want to repeat any 4 bit pattern,
0 will never follow 0 and F will never follow F.
This allows you to fill in four of the blanks:
0-1, 8-0, F-E, 7-F

最終的に求めたい文字列では16進文字16個を重複なく並べるという縛りがあるので、 表には存在している0→0とF→Fという並びは許されません。 従って、0の後続は1、Fの後続はEということが確定します。 同時にFの前が7、0の前が8というのも確定するので 8の後続は0、7の後続はFに決まります。

ということで先の表の?の部分をこれらの数字に置き換えていきます。

X X' X X' X«0 X«1
0-1 8-0 0 1
1-? 9-? 2 3
2-? A-? 4 5
3-? B-? 6 7
4-? C-? 8 9
5-? D-? A B
6-? E-? C D
7-F F-E E F

4箇所埋まりました。

Next, abiding by the "smallest possible value" rule,
since the 4 zeroes must be at the beginning and the 4 ones
must be at the end (and the ends join to make the circle):
E-C, 6-D, and C-8, 4-9 must also be paired up.

次に 「“smallest possible value” rule」 を使って?の部分を数字に置き換えます。

この「“smallest possible value” rule」が具体的にどういうことを 指しているのかわからなかったのですが、おそらく 最終的な16個の文字の並びを16進16桁の数値とみなしたときに できるだけ小さな値になるように数字を選ぶということだろうと思います。

そうすると「リング」の終端にFが来るようになり、 ここからFの後続が確定できます。

表の上ではE からはCかDのいずれかが可能ですが、Cのみに決まります。 そしてそれにより同じくCかDかが後続できる6の後続がDに決まります。 さらにCからは8と9のいずれかが可能ですが、ここでは8しかありえません (もうちょっと詳しく書くべきところとは思いますが、各自で ビットの並びを書くなどしてみてください)。

ここまでの結果を表に反映すると

X X' X X' X«0 X«1
0-1 8-0 0 1
1-? 9-? 2 3
2-? A-? 4 5
3-? B-? 6 7
4-9 C-8 8 9
5-? D-? A B
6-D E-C C D
7-F F-E E F

こうなります。

Let's try a zero after the 1 (the sooner we place zeroes,
the smaller the overall number will be):
1-2, 9-3

1 の後には 2 か 3 のいずれかを選べますがここでは2を選びます。 すると9の後続は3で確定しますので

X X' X X' X«0 X«1
0-1 8-0 0 1
1-2 9-3 2 3
2-? A-? 4 5
3-? B-? 6 7
4-9 C-8 8 9
5-? D-? A B
6-D E-C C D
7-F F-E E F

こうなります。

次に

Let's try squeezing another zero in after the 2:
2-4, A-5

2の後続として4を選択します(同時にAの後続が5に確定)。 それを反映すると

X X' X X' X«0 X«1
0-1 8-0 0 1
1-2 9-3 2 3
2-4 A-5 4 5
3-? B-? 6 7
4-9 C-8 8 9
5-? D-? A B
6-D E-C C D
7-F F-E E F

こうなります。

このとき

Since A goes to 5, you can't let 5 go to A, so:
5-B, D-A

Aの後続を5にしたので、5の後続をAにすることはできません。 従って5の後続はBとなり、それによりDの後続がAと決まります。

X X' X X' X«0 X«1
0-1 8-0 0 1
1-2 9-3 2 3
2-4 A-5 4 5
3-? B-? 6 7
4-9 C-8 8 9
5-B D-A A B
6-D E-C C D
7-F F-E E F

残るは二か所ですが、3の後続に7を選んでしまうと

If 3 goes to 7 then
B-6-D-A-5-B and the circle gets short-circuited.

B-6-D-A-5-B という「短いループ」ができてしまいます。 従ってここでは7とすることはできないので6を選びます。 すると

If 3 goes to 6 then
B-7-F-E-C-8-0-1-2-4-9-3-6-D-A-5-B

という16個すべてを使った「ループ」ができます。 これを表に反映すると

X X' X X' X«0 X«1
0-1 8-0 0 1
1-2 9-3 2 3
2-4 A-5 4 5
3-6 B-7 6 7
4-9 C-8 8 9
5-B D-A A B
6-D E-C C D
7-F F-E E F

となり、0から始めれば

Voila! We have our circle:
0-1-2-4-9-3-6-D-A-5-B-7-F-E-C-8-0

という結果が得られます (お疲れ様でした)。

ところで

X X'  X X'  X<<0  X<<1 
0-1   8-0     0     1  s
1-2   9-3     2     3  
2-4   A-5     4     5  
3-6   B-7     6     7  
4-9   C-8     8     9  s
5-B   D-A     A     B  s
6-D   E-C     C     D  s
7-F   F-E     E     F  s

元記事の表には末尾に s がある行があるんですがこれが何を意味しているのか読み取れませんでした (わかったら教えてください)。

さて、得られた16文字の並びを2進表記し、 連続する2文字の3ビットの共通部分を取り除いたうえで円形に並べると

                0
         1             0
     
     1                     0
     
   1                         0
     
  1                           1
     
   0                         0
     
     1                     0
         0             1
                1

となります。 この円の16か所のいずれからでも順に読んでいくと (一種類の文字列をローテート下)16種類の文字列が得られます。

≪ prev The Hunt for Red October
next ≫ 10月はたそがれの国