「7」の倍数を表す正規表現の解説

オートマトンから正規表現への変換方法について、「7の倍数」を表す正規表現 - Qiitaをもとに書きます。

オートマトンとは？

状態(計算の途中結果)をもっていて、値が入力されると現在の状態と入力値をもとに次の状態へ遷移します。入力を受けるたびに「受理状態」「非受理状態」のどちらかになります。

ちょっと分かりづらいので、例をみていきいます。

7の倍数かを判定するオートマトン

たとえば「123456789」が7で割り切れるかは、筆算を使えば調べることができます。筆算はまず1桁みて7で割り、あまりを10倍して下の桁での計算に利用します。

 0 + 1 mod 7 -> 1
10 + 2 mod 7 -> 5
50 + 3 mod 7 -> 4
40 + 4 mod 7 -> 2
20 + 5 mod 7 -> 4

ここでいう「状態」は現在のあまりです(0 -> 1 -> 5 -> 4 -> 2 -> 4と遷移しています)。入力は各桁の数字です。状態が0の場合のみ受理します。

オートマトンの状態は以下のようになっています。

入力	現在の状態	次の状態
1	0	1
2	1	5
3	5	4
4	4	2
5	2	4
6	4	4
7	4	5
8	5	2
9	2	1

最終的な状態は1(123456789 mod 7 = 1)なので、非受理状態です。

なんとなく掴めてきたところで、いよいよオートマトンから正規表現を生成していきます。

7の倍数を判定するオートマトンの全容

10進法で考えると状態の遷移パターンが多くなってしまうので、ここでは2進法で考えます。2進数でも状態は余りの種類と同じ7つ用意すればいいです。遷移は次のとおりです。

遷移図

この図の各マスは状態を表しており、辺が遷移を表します。たとえば今の状態が1のときに1が入力されたら3へ遷移することが見るだけで分かるようになっています。

状態数を減らしていく

ここから状態を減らしていき、正規表現へ持ち込みます。まず、状態6に止まるべきだった入力はそもそも受け付けない(非受理とする)ことにして、状態6を削除します。すると、3 -> 6 -> 5という遷移が3 -> 5にまとめられます。

状態6を削除したあと

このように状態数を減らしていきます。ただ、この作業、恐ろしく面倒くさくて大変なので、状態数が2になった場面まで飛ばします。

状態数を2まで減らした遷移図

辺に書かれている正規表現が大変なことになっています。

最後に状態2も削除して、正規表現に落とし込んで完了です。

2進数で7の倍数を判定する正規表現

const reg = /^(11(01*00|01*0101)*1|0|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)+$/;
console.log('検証スタート');
for (let i = 0; i < 1e6; ++i) {
    if ((i%7==0) !== reg.test(i.toString(2))) {
        throw new Error('正規表現で判定できていない数字が見つかりました');
    }
}
console.log('検証終了');

これで完成です。10⁶まで検証していますが、reg.test(n.toString(2))とn%7 == 0の結果が同じことがわかります。

7進法で7の倍数を判定する正規表現

2進数よりも遷移表が大きくなるぶん複雑になる…と思いきや、めちゃくちゃカンタンな正規表現で書けます。

/0$/ 以上です(当たり前)。

おまけ: 0000を受理しないようにする

実は上の正規表現では0000が受理されます。これを受理しないようにしてみます。

const reg = /^((11(01*00|01*0101)*1|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)(11(01*00|01*0101)*1|0|(10|11(01*00|01*0101)*01*01(1|00))((0|11)(1|00)|(10|(0|11)01)(01*00|01*0101)*01*01(1|00))*(10|(0|11)01)(01*00|01*0101)*1)*|0)$/;

まあほぼ同じです。

Space2回でfzfを呼び出すzsh script

fzf、使っていますか？ぼくはそこそこ使ってはいるのですが、どうしてもC-tを押すのが面倒くさく感じてしまいます。そこで、$ vim<space><space>のようにspaceを2回続けて入力するとfzfが起動するようにしてみました。

(わかりづらいですがspaceを2回押してfzfを起動しているんです、信じてください)

コード

zsh で連続したスペースにキーバインドを割り当てる - Qiita

この記事を参考にして実装しました。

function _double_space_to_fzf() {
    if [[ "${LBUFFER}" =~ " $" ]]; then
        LBUFFER="${LBUFFER}$(__fsel)"
        local ret=$?
        zle redisplay
        return $ret
    else
        zle self-insert
    fi
}
zle -N _double_space_to_fzf
bindkey ' ' _double_space_to_fzf

カンタンにいうと

1. spaceに_double_space_to_fzfというZLEウィジェットを登録します
2. 直前がspaceならばspaceを入力せず、fzfを起動します
3. 直前の文字がspaceでなければ、spaceをそのまま入力します

なぜfzf-file-widgetを使わないのか？

fzfはfzf-file-widgetというZLEウィジェットをC-tにバインドしています。そのため、fzf-file-widgetをそのまま使えばいいのではないか、と思うかもしれません。実際、上のコードのthen節はほとんどfzf-file-widgetそのままです。

function _double_space_to_fzf() {
    if [[ "${BUFFER}" =~ " $" ]]; then
        fzf-file-widget
    else
        zle self-insert
    fi
}
zle -N _double_space_to_fzf
bindkey ' ' _double_space_to_fzf

しかし、これだとzsh-autosuggestionsと競合してしまい表示がおかしくなってしまいます。fzf-file-widgetの typeset -f zle-line-init >/dev/null && zle zle-line-initという部分が原因のようなので、そこを除いて書き直しました。

最高のターミナルを作る2019

1. ターミナルエミュレータを選ぶ

まず端末をきちんと選びましょう。どれも同じに見えますが、フォントが効かなかったり透過できなかったり、意外と違いがあります。下の画像を見れば一目瞭然です。

左: Alacritty 右: gnome-terminal

主要なターミナルエミュレータとしてはこんな感じです。

• gnome-terminal
• Terminal.app
• xfce-terminal
• Alacritty
• terminator
• Hyper.js
• urxvt
• iTerm2

チェックポイントとしてはこんなものが挙げられます。

• 画像が表示できるか？
• Nerd Fontを正しく表示できるか？
• 透過設定ができるか？
• 背景画像が設定できるか？
• ウィンドウ枠を消せるか？
• 日本語がちゃんとストレスなく入力できるか？

僕はPowerline系のUIを使っているので、NerdFontが効かないとちょっと表示が崩れてしまいます。ウィンドウ枠が消せるか、透過ができるか、背景画像を設定できるかは好みの問題ですね。

これらすべてを満たしていて、なおかつパフォーマンス的に問題がなかったのは今の所xfce-terminal、terminatorですね。次点でAlacrittyです(Ubuntu環境なのでMacについてはわかりません)。ほかは色々と足りなすぎます。

Xfce-terminalは設定を特にいじらなくてもまともに使えるので、かなりオススメです。設定をいじるのが苦痛でない楽しいならAlacrittyは最高です。ほかはウィンドウ枠があったり透過できなかったり、やや不格好でもいいならGNOME Terminalはなんだかんだ良い選択肢になりえます。

2. シェルを選ぶ

ぼくはシェルとしてzshを使っています。理由はいくつかあります。

• Bash Scriptの知識を流用できる(多少差異はある)
• 補完が有用
• 補完の自作ができる
• プラグインが豊富
• Bashより使いやすい

fishなど独自のスクリプトを採用しているシェルは、どうしてもbash scriptより情報が少ないです。そのため、やりたいことを実現するのが困難なことが多いです。また、互換性がないため、部分的にbashへ切り替えなければならず、めんどうなことが多いです。

Bash scriptはクソです。しかし、いかんせん歴史が長いので、なにか問題が起こっても解決がしやすいです。また、多少難しい設定でもサラサラと書けてブラックボックス化しづらいです(全然リーダブルじゃないし、高度なことをすると地獄を見ますが)。

3. ツールを入れる

おすすめのツールを紹介します。

exa

Rust製のalternative ls。lsよりもカラフルで見やすく、オプションがわかりやすいです。また、ツリー表示といったlsにはない機能も搭載されています。

bat

Rust製alternative cat。lessの表示機能とcatの結合機能・パイプライン機能を組み合わせた感じです。シンタックスハイライト付きで表示されます。

httpie

HTTPクライアント。curlやwgetよりもオプションがわかりやすいです。カラフルで読みやすいのもNiceです。

ranger

ファイラー。なんと、コマンドライン上で画像プレビューまでできます。Vimライクな操作感で使いやすいです。

Neovim

特に語るまでもない。最高のエディタ。

tty-clock

デジタル時計。ターミナル上で時間を知りたいときに便利です。僕は競プロのコンテストが始まるときに使っています。

4. カラースキーム

Nordというプロジェクトを非常に気に入って愛用しています。色合いが最高にCoolです。Vim、Tmux、各種ターミナルに対応しているので、すべてで導入しました。うえの画像のような青みがかった黒が基調のテーマになっています。

Nord

サーバーの全データをぶっ飛ばしました。

タイトル通りです。全データが吹き飛びました。

経緯

CentOS8にバージョンアップするためにサーバー再構築をしたのがミスでした。確認ダイアログも出なかったので、まさか吹き飛ぶとは思っていなくてバックアップも取っていませんでした。やらかした…

現在の状況

いかんせんNginxの設定ファイルごと吹っ飛んでいるので復旧はまあまあ時間がかかりそうです。というか完全に元には戻せないですね。サーバーにしか置いてなかったデータとかもあるので被害は結構甚大です。

とりあえず最低限の復旧は今週中にしようと思います。

11/18 追記

一応一通りの復旧は終わらせました。

TrueColor対応のはなし(端末、シェル、tmux、vim)

TrueColorで表示するのは、わりかし対応がめんどうです。なぜなら、Vim、tmux、zsh、ターミナル全てで対応しなければならないからです。今回はそれぞれどういった対応をすればいいのか紹介します。

まず: TrueColor に対応できているか確認する

TrueColor 対応をする前に、そもそも今対応できているかチェックしましょう。以下のコマンドを実行してください。

$ curl -s https://gist.githubusercontent.com/lifepillar/09a44b8cf0f9397465614e622979107f/raw/24-bit-color.sh | bash

このように継ぎ目がなければOKです。↓

下のように階段状になっていたら対応できていません。↓

上でもかなり明白に違いますが、NeoVimでTrueColor対応できていないと更に明らかになります。

TrueColor非対応

TrueColor対応

TrueColor対応をしたあと、ちゃんと反映できているか上のコマンドで確認してください。

余談: ターミナルの色の種類

まず、ターミナルの色には2種類あります。

TrueColor

いわゆる#ffffff。RGBそれぞれ8ビットを用いて表現します。24ビットカラー(RGB)と、さらに透明度8ビットを合わせた32ビットカラー(RGBA)が存在します。

8-bit color

256色まで表せる方式。256までの数字のみを用います。xtermやscreenなど、それぞれで色の割り当てが異なっています。

TrueColor に対応できていない場合、8-bit color で表示されます。8-bit color は256色しか表示できないので、当然表現力はガクッと落ちます。