読者です 読者をやめる 読者になる 読者になる

パターンマッチを練習する日々

問題編

情報工学ってなんだろう...

計算量に関して - 矢沢久雄の情報工学“再”入門を祝すCommentsAdd Star経由で、矢沢久雄の情報工学“再”入門という記事を知ったのですが、指摘されている通り、確かに内容が激しく怪しいです。

以前、「日経ソフトウエア」という雑誌を読んでいると、この矢沢さんが書いてある記事があったんですよ。

設問 ヘビ

ある世界には、文字だけで出来た不思議なヘビが住んでいます。

このヘビはA種とB種の2種類が確認されていますが、それ以外の種類がいる可能性もあります。

A種は ">'"の後に1個以上の"="が並んだ後、"#"が来て、さらに前と同じ個数の"="が続き、"~"(半角チルダ)で終わります。

B種は">^"の後に"Q="が1個以上並んだ後、"~~"(半角チルダ2個)で終わります。

A種の例: >'===#===~    >'==#==~
B種の例: >^Q=Q=Q=Q=~~  >^Q=Q=~~

ヘビを文字列データとして受け取り、それがどんな種類かを判別して、A種の場合はA、B種の場合B、A種でもB種でもない場合はNAを出力して出力するプログラムを作成してください。

(略)

あの・・・正規表現って思いっきり有限オートマトンと同じもの・・・
Perlの正規表現とかだったらマッチした回数とか取得できるんでしょうか。

(引用されている「日経ソフトウエア」記事中の明らかな誤字については修正させていただきました)

回答編

こういうパターンにマッチするような正規表現(のような拡張された何か)で書けるか? ということでしょうか。B種の方は問題ないですね。 A種の方は確かに'#' の左と右の '='の数を揃えないといけないですが、確かにPerlならできますねw

5.10以降のPerlであればこういう書き方ができます。

#!/usr/bin/perl
# -*- coding: utf8 -*
use strict;
use warnings;
use feature ':5.10';

my $pattern_a = qr{
    ^
    >'           # >' が来て
      (=*)          # = の0回以上の繰り返し(内容を保存)
       \#           # '#'
      \g{-1}        # 先ほど保存した内容と同じもの
    ~               # ~
    $
}x;

foreach my $l (<DATA>) {
  chop $l;
  say $l;
  say "  match!" if $l =~ /$pattern_a/;
}

__END__
>'===#===~
>'===#==~
>'==#==~
>'==#===~

結果:

>'===#===~
  match!
>'===#==~
>'==#==~
  match!
>'==#===~

おもしろい.そして Perl すごい.

練習編

Mathematica でも解いてみた.

Snake[target_String] :=
 Switch[ Characters[target],
  {">", "'", x : "=" .., "#", x : "=" .., "~"}, "A",
  {">", "^", PatternSequence["Q", "="] .., "~", "~"}, "B",
  _, "NA"]

テスト.

In = Snake /@
     { ">'===#===~",
       ">'===#==~",
       ">'===#===~'<",
       "->'===#===~",
       ">'#~",
       ">^Q=Q=~~",
       ">^~~" }

Out = {"A", "NA", "NA", "NA", "NA", "B", "NA"}

最近になってようやく気付いたわけだけど,Mathematica のパターンマッチングは便利だ.とても便利だ.
やはりこの言語は卒業(というより修了だけど)後も手放すべきではないのかもしれない.それはかなり財布に厳しい選択だけど.