Panda Noir

JavaScript の限界を究めるブログでした。最近はいろんな分野を幅広めに書いてます。

「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つ用意すればいいです。遷移は次のとおりです。

f:id:panda_noir:20191212171736j:plain
遷移図

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

状態数を減らしていく

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

f:id:panda_noir:20191212171822j:plain
状態6を削除したあと

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

f:id:panda_noir:20191212113127j:plain
状態数を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('検証終了');

これで完成です。106まで検証していますが、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. ターミナルエミュレータを選ぶ

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

f:id:panda_noir:20191202115057p:plain
左: Alacritty 右: gnome-terminal

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

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

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

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

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

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

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

2. シェルを選ぶ

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

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

Bash Script自体はクソですが、いかんせん歴史があるので問題が起きたときに解決がカンタンです。また、ちょっと難しい設定でもサラサラ書けてブラックボックス化しない点もいいですね(読むのはつらいし、あまりに高度なことをやろうとすると地獄を見ますが)。Bash Scriptをやめて独自のスクリプトを採用しているシェルは、導入例が少なくなってしまうので、やりたいことを実現するのが困難なことが多いです。

3. ツールを入れる

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

exa

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

f:id:panda_noir:20191202114410p:plain

f:id:panda_noir:20191202114706p:plain

bat

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

f:id:panda_noir:20191202114438p:plain

httpie

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

f:id:panda_noir:20191202114448p:plain f:id:panda_noir:20191202114500p:plain

ranger

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

f:id:panda_noir:20191202114510p:plain

Neovim

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

tty-clock

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

f:id:panda_noir:20191202114520p:plain

4. カラースキーム

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

Nord

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

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

経緯

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

現在の状況

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

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

11/18 追記

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

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

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

対応できているか確認する

まず以下のコマンドを実行してみてください。

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

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

f:id:panda_noir:20191106185205p:plain

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

f:id:panda_noir:20191106185214p:plain

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

f:id:panda_noir:20191106185316p:plain
TrueColor非対応
f:id:panda_noir:20191106185323p:plain
TrueColor対応

TrueColor対応したくなりましたよね?

ターミナルに関わる色の種類

端末での色には2種類ある。

TrueColor
いわゆる#ffffff。RGBそれぞれ8ビットを用いて表現する。24ビットカラー(RGB)と、さらに透明度8ビットを合わせた32ビットカラー(RGBA)が存在する。
8-bit color
256色まで表せる方式。256までの数字のみを用いる。xtermやscreenなど、それぞれで色の割り当てが異なっている。
続きを読む