2015-01-29

闘会議2015のアナログゲームエリアのボードゲームの紹介

きたる闘会議2015アナログゲームエリアでは、様々なボードゲームが遊べる。すでに当日設置されるゲームは決まっているのだが、公式サイトはまだ更新されていない。

闘会議はスタッフの多くがドワンゴ社員である。ボドゲのインストができるスタッフが少なく、急遽社内のボドゲ好き社員に応援が要請されて、私もスタッフとして参加することになった。

何しろ、闘会議というのは今回が初めてなので、当日の雰囲気が全く予想できない。全くのボドゲ初心者が来るのか、はたまた、ガチ勢が来るのか。初心者にはボドゲに触れてもらい、上級者はそのまま楽しめるような雰囲気なればいいのだが。

ともかく、当日設置されているボドゲの一覧を紹介しようと思う

初級エリア

初級エリアのボードゲームは、どれも説明が簡単で、未経験者でもすぐに遊べるボードゲームが選ばれている。

  • おばけキャッチ

    参加人数は2-6人。短時間のアクションゲームである。カードに描かれた物を早いものがちで取るゲームだ。

  • ワードバスケット

    参加人数は2-8人。しりとりだ。はじめの文字だけではなく、終わりの文字も指定されている。筆者はこのゲームが非常に苦手だ。強い人はとてつもなく強いのだが。

  • どうぶつしょうぎ

    参加人数は2人。大胆に簡略化した将棋だ。

  • よんろのご

    参加人数は2人。大胆に簡略化した碁だ。

中級エリア

中級ボードゲームは、事前に少し長い説明が必要になってくるものもある。

  • ポーカー

    十分に有名なゲーム。ガチ勢に初心者が混じった場合、すぐに飛ぶだろう。

  • ラブレター

    手札を回していきながら相手の手札の中身を予想して勝負を仕掛けるゲーム。

  • ワンナイト人狼

    参加人数3人から7人。人狼系

  • 赤ずきんは眠らない

    参加人数4-6人。人狼系

  • ごきぶりポーカー

    参加人数2-6人。「これはゴキブリです」と言いながらハエやクモを渡すブラフゲーム。

  • エセ芸術家ニューヨークへ行く

    参加人数5-10人。ひとつのキャンバスにみんなで一筆づつ指定された物の絵を書いていく。ただし、参加者の中に一人だけ何の絵を描くか知らされていないエセ芸術家がいる。エセ芸術家をあてれば芸術家達の勝ち。ただし、何の絵を描いているかエセ芸術家にバレてしまうと芸術家達は負ける。

初級と中級のゲームは、未経験者でもできるし、時間もそれほどかからない。問題は、上級エリアだ。

上級エリア

上級ゲームは、説明にも時間がかかるし、プレイ時間も長い。1時間以上は確実にかかるゲームが多い。

  • カルカソンヌ

    参加人数2-5人。土地をつなげていくゲーム。ルールはそれほど複雑ではない。ガチ勢が来るかどうかはわからない。

  • カタンの開拓者たち

    参加人数4人。サイコロを振って資源を獲得して建築をし、10点先取するゲーム。ガチ勢の来る可能性がある。主に筆者がインスト要員として割り当てられている。

  • スコットランド・ヤード:東京

    参加人数2-8人。怪盗一人を刑事達が捕まえるゲーム。プレイ時間は長いが、ルールは簡単。ガチ勢もいない。

  • モノポリー

    参加人数2-8人。すごろくのように環状のマス目を回りながら不動産取引をして、他のプレイヤーを破産させて勝ち残るゲーム。ガチ勢の来る可能性がある。

  • 将棋

    参加人数2人。ご存知の将棋。指導できるほどの棋力を持つスタッフはいない。いい勝負になるほど実力が拮抗した参加者同士で対戦できるといいのだが、どうなることやら。

  • 麻雀

    参加人数4人。ご存知の麻雀。自動卓がないので手積み、東風戦。麻雀のルールが分からない全くの未経験者はお断わりいただく予定。

上級エリアのうち、カルカソンヌとスコットランドヤードは未経験者でも楽しめるゲームだ。ただし、プレイ時間が長めなので注意。

モノポリーは有名なゲームだ。ルールはそれほど複雑ではないが、ガチ勢がやってくる可能性もある恐ろしいゲームだ。

カタンはルールの説明にも時間がかかり、プレイ時間も長い。加えてガチ勢がやってくる可能性もある。

将棋と麻雀に関しては、どのくらいの実力を持った人間がやってくるのか予測できない。あらかじめプロを配置しているわけでもないので、完全に参加者が遊べる場所を提供するだけになる。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-28

ドワンゴのプログラミングコンテストをクリアできなかったお話

dwangoプログラミングコンテスト2016

ドワンゴが主催するプログラミングコンテストの予選が、24日に行われたそうだ。筆者はクリアできなかったが、簡単なものだけ解説する。本格的な解説が読みたい人は、わざわざこの記事を読まずとも、以下で解説されているようだ。

「dwangoプログラミングコンテスト」予選問題解説 // Speaker Deck

A: プレミアム会員 - dwangoプログラミングコンテスト | AtCoder

ニコニコ動画には、プレミアム会員という制度があります。このプレミアム会員制度には月額一定の額を支払うことで加入できます。

ニワンゴくんは、この n ヶ月間連続してプレミアム会員です。 また、x ヶ月前に月の一定支払い額が 525 円から 540 円に変わったことを知っています。 つまり、この n ヶ月のうち最近の x ヶ月間は月額 540 円支払っていて、それ以外の月では 525 円払っていたことが分かっています。

n と x が与えられるので、この n ヶ月間でニワンゴくんがプレミアム会員制度に支払った合計額を出力してください。

\(525(n-x) + 540x\)を計算すればよい。

#include <iostream>
 
int main()
{
    int n = 0 ;
    int x = 0 ;

    std::cin >> n >> x ;
 
    int payment = ( n - x ) * 525 + x * 540 ;
 
    std::cout << payment << '\n' ;
}

B: ニコニコ文字列 - dwangoプログラミングコンテスト | AtCoder

0 から 9 の数字から成る文字列 S が与えられます。

ある文字列 X について、X="25" または X="2525" または X="252525" …… というふうに "25" を何回か繰り返した文字列になっているとき、X はニコニコ文字列であるといいます。 たとえば "25" や "25252525" はニコニコ文字列ですが、"123" や "225" はニコニコ文字列ではありません。

あなたの仕事は、文字列 S について、ニコニコ文字列となるような連続した部分文字列の取り出し方が何通りあるかを答えることです。 文字列として同じであっても、取り出し位置が異なっていれば別々に数えます。

与えられた文字列から連続した"25"をすべて探し出し、25の数を数える。N個の"25"が連続した文字列の部分文字列の取り出し方は、1+2+3+...+N通りあるので、\(\frac{N(1 + N)}{2}\)で計算すればよい。

ただし、Sの長さは100000以下であるとのことなので、もし\(\frac{N(1 + N)}{2}\)の計算に32bit符号付き整数を使っていた場合、50000回連続した文字列が渡されると、50001 * 50000を計算しようとするとオーバーフローしてしまう。

連続した"25"文字列は、C++11で追加された<regex>ライブラリを使えばよい。

#include <iostream>
#include <string>
#include <regex>

unsigned long long int count( unsigned long long int n )
{
    return ( 1 + n ) * n / 2 ;
}

int main()
{
    std::string str ;
    std::cin >> str ;

    std::regex re(R"((?:25)+)") ;

    std::sregex_iterator iter( str.cbegin(), str.cend(), re ) ;
    std::sregex_iterator end ;

    unsigned long long int sum = 0 ;
    for ( ; iter != end ; ++iter )
    {
        auto n = iter->str().length() / 2 ;
        sum += count( n ) ;
    }

    std::cout << sum << '\n' ;
}

ただし、このコードはatcoderを通らない。理由は、atcoderのC++11のコンパイラーがGCC4.8.1という2年前の化石バージョンで、libstdc++がregex_iteratorをサポートしていないからだ。そのため、以下のようにregex_searchを複数回呼び出すというマヌケなコードを書かなければならない。

#include <iostream>
#include <string>
#include <regex>

unsigned long long int count( unsigned long long int n )
{
    return ( 1 + n ) * n / 2 ;
}

int main()
{
    std::string str ;
    std::cin >> str ;

    std::regex re(R"((?:25)+)") ;

    std::smatch m ;

    unsigned long long int sum = 0 ;

    auto iter = str.cbegin() ;
    auto end = str.cend() ;


    while ( iter != end )
    {
        std::regex_search( iter, end, m, re ) ;
        auto n = m.str().length() / 2 ;
        sum += count( n ) ;

        iter = m[0].second ;
    }

    std::cout << sum << '\n' ;
}

と思ったが、これも時間制限内に終わらない。Wandboxで試しても終わらないので、どうもlibstdc++ 4.8.1のregexライブラリには問題があるようだ。

[Wandbox]三へ( へ՞ਊ ՞)へ ハッハッ

2年前のC++コンパイラーなど使うべきではないという教訓が得られた。

C: ゲーマーじゃんけん - dwangoプログラミングコンテスト | AtCoder

期待値の計算方法がわからないのでモンテカルロ法で解こうとしたが、必要な精度が出ずに敗北した。小数点以下6桁は辛い。

なんでも、必要な精度を出すためには、1兆回は試行しなければならないそうだ。制限時間は2分。すると、一回の試行は0.12ナノ秒で終えなければならない。無理だ。

本の虫: 全プログラマーが知るべきレイテンシー数

最終的に以下のようなクソコードを書きちらしたが、もちろん必要な精度は出ない。ちなみに、atcoderはfutureを使うと実行時エラーになる。

#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <future>
 
enum { Rock = 0, Paper = 1, Scissors = 2 } ;
 
template < typename Iter, typename RNG >
unsigned long long int play( Iter begin, Iter end, RNG rng )
{
    unsigned long long int i = 0 ;
 
for ( ; ; ++i )
{
    int n = std::distance( begin, end ) ;
 
 
    // 勝者決定判定
    if ( n == 1 )
    {
        break ;
    }
 
    // じゃんけん
    std::generate( begin, end, rng ) ;
 
 
    // 出された手が 1 種類の場合 
    int first_hand = *begin ;
    bool b = std::all_of( begin, end,
        [=](int x) { return x == first_hand ; } ) ;
 
    if ( b )
    {
        continue ;
    }
 
    // 出された手が 2 種類以上の場合
 
    // 手をカウント
    
    auto rock = std::count( begin, end, Rock ) ;
    auto paper = std::count( begin, end, Paper ) ;
    auto scissors = std::count( begin, end, Scissors ) ;
 
 
    // 出したプレイヤーの数が最も少ない手に注目する。 
 
    // そのような手が 3 種類あった場合
    if ( rock == paper && rock == scissors )
    {
        continue ;
    }
 
 
    auto hands = { rock, paper, scissors } ;
    auto minor = std::min( hands ) ;
 
    // 出ていない手がある場合
    if ( minor == 0 )
    {
 
        typename Iter::difference_type h[3] = { rock, paper, scissors } ;
        std::remove( h, h + 3, 0 ) ;
        auto m = std::min( h[0], h[1] ) ;
        end = begin + m ;
        
    }
    else {
        // すべての手が出た場合
        end = begin + minor ; 
    }
   
}
 
    return i ;
 
}
 
 
constexpr unsigned long long int trial = 10000 ;
 
 
unsigned long long int gamer_zyanken( int n )
{
    std::mt19937 engine ;
 
    std::uniform_int_distribution<> dist( 0, 2 ) ;
 
 
    std::vector<int> players( n ) ;
 
    unsigned long long int sum = 0 ;
 
    for ( int i = 0 ; i != trial ; ++i )
    {
        sum += play( players.begin(), players.end(), [&]{ return dist(engine) ; } ) ; 
    }
 
    return sum ;
}

 
int main()
{
    int n ;
    std::cin >> n ;
 
    auto f1 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f2 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f3 = std::async( std::launch::async, gamer_zyanken, n ) ;
    auto f4 = std::async( std::launch::async, gamer_zyanken, n ) ;
 
    unsigned long long int sum = f1.get() + f2.get() + f3.get() + f4.get() ;
 
    double result = double(sum) / double(4 * trial) ;
 
    std::cout << result << '\n' ;
}

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-26

Convictedというボドゲが送られてきた

私宛に、Convictedというボードゲームが贈られてきた。調べたところ、Kickstarterで出資を受けたボードーゲームらしい。

The Convicted - expand your town and fight for survival by Mateusz Albricht — Kickstarter

設定としては、囚人が未開地の開拓を条件に王から恩赦を受けて、野蛮人や怪物などの襲撃から防衛しつつ、都市を発展させていくというものらしい。

具体的なルールは把握していないが、極めて重いゲームで、プレイには90分以上かかるらしい。

C++11の時間ライブラリ: chrono

<chrono>は、C++11で追加された時間ライブラリである。

単位時間を扱うためのduration、起点からの経過時間を扱うためのtime_point、現在の起点からの経過時間を取得するためのclockからなる。Cの標準ライブラリのtime_tとtime(), clock_gettime()を置き換えることが出来る。日付機能は含まれていない。

duration

時間について考える。一時間は60分である。1分は60秒である。1秒は1000ミリ秒である。

単位の異なる時間の値を相互に変換するのは、簡単な計算だ。

unsigned int min_to_sec( unsigned int min )
{
    return min * 60 ;
}

しかし、実引数minに渡される値の単位が分であることを保証する方法はない。間違えたとしても、コンパイルエラーにはならない。

chronoでは、時間単位を扱うライブラリ、durationを追加した。これは型安全に時間の計算をしてくれる。


#include 

int main()
{
    // 15分
    std::chrono::minutes min(15) ;

    // 分を秒に変換
    std::chrono::seconds sec = min ;

    // 900
    std::cout << sec.count() << std::endl ;

    // エラー、余りが発生する可能性があるため
    min = sec ;

    // OK
    min = std::chrono::duration_cast<std::chrono::minutes>( sec ) ;
}

durationテンプレートには、よく使う時間単位、hours, minutes, seconds, miliseconds, microseconds, nanosecondsというtypedef名があらかじめ宣言されている。

また、C++14からは、時間単位のtypedef名へのユーザー定義リテラルが定義されている。それぞれ、h, min, s, ms, us, nsとなっている。

auto hours = 3h ;
auto seconds = 100s ;

auto sum = 1h + 5min + 3s ;

durationクラスは、メンバー関数countにより、内部表現の値を得ることができる。単位はdurationテンプレートの特殊化のとおりだ。

int main()
{
    std::chrono::seconds s(10) ;

    s.count() ; // 10

    auto s2 = s + s ;

    s2.count() ; // 20

    std::chrono::hours h(1) ;
    h.count() ; // 1

    s = h ;

    s.count() ; // 3600
}

time_point

time_pointは、ある起点時間からの経過時間を表現するクラスだ。time_point同士を減算すると、その結果はdurationになる。time_pointを直接構築することはあまりない。time_pointは、clockから得ることができる。C標準ライブラリのtime_tに比べて、型安全になっている。

clock

clockは、現在のtime_pointを取得するクラスだ。staticメンバー関数のnowでtime_pointを取得できる。

int main()
{
    // 処理前の起点からの経過時間
    auto t1 = std::chrono::system_clock::now() ;

    // 処理
    std::this_thread::sleep_for( std::chrono::seconds(1) ) ;

    // 処理後の起点からの経過時間
    auto t2 = std::chrono::system_clock::now() ;

    // 処理の経過時間
    auto elapsed = t2 - t1 ;

    // 単位は未規定
    std::cout << elapsed.count() << std::endl ;
}

system_clockは、システム上のリアルタイムクロックを表現するclockである。

このクロックの使うdurationは未規定である。そのため、経過時間を実際の時間単位で知りたければ、duration_castが必要になる。

int main()
{
    // 処理前の起点からの経過時間
    auto t1 = std::chrono::system_clock::now() ;

    // 処理
    std::this_thread::sleep_for( std::chrono::seconds(1) ) ;

    // 処理後の起点からの経過時間
    auto t2 = std::chrono::system_clock::now() ;

    // 処理の経過時間をミリ秒で取得
    auto elapsed = std::chrono::duration_cast< std::chrono::milliseconds >(t2 - t1) ;

    // 単位はミリ秒
    std::cout << elapsed.count() << std::endl ;
}

C++規格は、起点時間がいつなのかを規定していない。経過時間はtime_pointのメンバー関数tiem_since_epochで取得できる。また、system_clockから得られるtiem_pointは、time_tに変換できる。

int main()
{
    // time_point
    auto t1 = std::chrono::system_clock::now() ;
    // 起点時間からの経過時間
    std::cout << t1.time_since_epoch().count() << '\n' ;

    // time_t
    auto t2 = std::chrono::system_clock::to_time_t( t1 ) ;
    std::cout << t2 << '\n' ;

    // tme_point
    auto t3 = std::chrono::system_clock::from_time_t( t2 ) ;

    std::cout << t3.time_since_epoch().count() << std::endl ;
}

system_clockのtime_pointとtime_tが、同じ時間単位の分解能を使っているとは限らない。

clockはsystem_clockだけではない。他にも、steady_clockがある。これは、実時間の経過によって、time_pointの経過時間が減らないことが保証されている。

int main()
{
    // time_point
    auto t1 = std::chrono::steady_clock::now() ;

    // この間にシステムの時刻が過去に変更されるかもしれない


    auto t2 = std::chrono::steady_clock::now() ;


    // trueであることが保証されている
    bool b = t2 >= t1 ;
}

その他のclockにも、constexpr staticデータメンバーのis_steadyの値によって、steady_clockと同じ保証があるかどうかを確かめることができる。

// true/false
bool b = std::chrono::system_clock::is_steady ;

C++規格はもうひとつ、high_resolution_clockを規定している。これは、時間の分解能が高いclockであると規定されている。

auto t1 = std::chrono::high_resolution_clock::now() ;
// 処理
auto t2 = std::chrono::high_resolution_clock::now() ;

// 処理のかかった時間
auto e = t2 - t1 ;

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

GCCのoverrideのバグらしきもの

ask.fmにこのような質問がきた。

C++では、overrideはキーワードではない。overrideは、特定の文脈でだけ文法で認識され、それ以外の場所では、単なる識別子となる。

そのため、以下のようなコードが書ける。

struct override { } ;

struct B
{
    virtual auto f() -> override ;
} ;

struct D : B
{
// GCC: error: two or more data types in declaration of 'type name'
    auto f() -> override override ;
} ;

しかしなぜかGCCは開発版の5.0ですら、コンパイルエラーとなる。

まさか未だにこのような面白い問題が残っているとは。

GCC Bugzillaを検索したところ、同じ不具合は報告されていないようなので、報告してみた。

Bug 64794 – GCC failed at virtual function with "override" trailing return type name, followed by override virt-specifier

Clangでは問題がない。

ドワンゴ広告

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-25

人の顔が認識できない

どうも、私は人の顔を認識する能力が劣っているのではないかと、最近考えるようになった。

妖怪ハウスに何度か遊びに来ている客に、つい、「どちら様でしたっけ」と訪ねてしまうことがよくある。そのたびに、「もう何度も会いましたよ」とか、「何度も同じことを聞かれていますよ」などと言われるのだが、やはり思い出すことができない。

極めつけは、妖怪ハウスに住んでいた元住人ですら、顔を忘れていたことだ。なるほど、言われてみれば確かに、住んでいた当時はそのような顔をしていた気もする。しかし確証が持てない。名前は忘れていないし、その人物の言動も覚えている。話してみると、なるほど、確かにそのような声でそのような口調であったので、本人なのであろうが、やはり問題の顔面がそのようなものであったかどうか断定できない。

どうも私は、個人を識別するのに、服、髪型、体型などの情報を使っているのではないかと思われる。

思えば、同じような体型と髪型の人間が似たような服を着ていた場合、間違えてしまうことがよくあるのだ。

関係しているかどうかわからないが、私は人の顔面がイケメンや美人であるかどうかをうまく評価することができない。よく人が、「誰々はイケメンである、美人である」などと評しているのを聞いても、私にはよくわからないのだ。

これまでの経験から推定するに、世の中のイケメン、美人と他人が評価している人間に共通する項目というものは、頬骨が張り出るほど頬が痩せこけていて、髪が頬を隠すほど長いものを言うものだと思われる。しかし、これは思えば顔の外側の特徴だ。目鼻や口の特徴ではない。

はてさて、困ったことだが、どうしようもない。

2015-01-20

C++の正規表現ライブラリ: std::regex

いまさらながら、C++の正規表現ライブラリを調べている。

C++の正規表現ライブラリ、std::regexは、boost::regexを土台に設計されている。boost::regexの正規表現の文法は、perlなのに対し、std::regexは、ECMAScriptである。この理由は、しっかりと正規表現の文法が定義されていて、外部規格として参照できる品質のものが、perlには存在しないためだ。std::regexはposixと拡張posixとawkとgrepとegrepの正規表現にも対応している。

本記事では、ECMAScriptの正規表現を使う。また、参考のためのECMAScriptのコードも使う。

全体一致

文字列全体が正規表現に一致するかどうかを調べたいとする

var re = /1234/ ;
var text = "1234" ;

var result = re.test( text ) ;

これを、std::regexを使って書くと以下のようになる。

#include <regex>

int main()
{
    std::regex re("1234") ;
    std::string text("1234") ;

    bool result = std::regex_match( text, re ) ;
}

C++には、正規表現リテラルはないので、文字列リテラルで正規表現を記述する。

もうすこし正規表現らしいことをしてみよう。連続した数字に一致する正規表現を使ってみる。

var re = /\d+/ ;
var text = "1234" ;

var result = re.test( text ) ;

残念ながら、C++の文字列リテラルで/\d+/を書こうとすると、エスケープシーケンスのためにエラーになる。

std::regex r1 = "\d+" ; // エラー
std::regex r2 = "\\d+" ; // OK

"\\d+"と書けば動くのだが、これはとても書きづらい。C++11で追加された生文字列リテラルを使えば、自然に書けるようになる。

std::regex re = R"(\d+)" ;

外側の括弧は生文字列リテラルの文法なので紛らわしいが、バックスラッシュを二重に書くよりはマシだろう。

部分一致の検索

以下のようなECMAScriptのコードをC++で書きたいとする

var re = /\d+/ ;
var text = "There are 99 bottles." ;

var a = re.exec( text ) ;
var result = a[0] ; // "99"

C++では、以下のように書ける。

int main()
{
    std::regex re( R"(\d+)" ) ;
    std::string text="There are 99 bottles." ;

    std::smatch m ; // std::match_results<string::const_iterator>
    std::regex_search( text, m, re ) ;

    std::cout << m.str() << std::endl ;
}

部分一致を検索するには、regex_searchを使う。結果は、match_resultsで受け取ることができる。

部分一致をすべて検索。

以下は、部分一致をすべて検索するECMAScriptのコードである。

var re = /\d+/g ;
var text = "123 456 789" ;

// ["123", "456", "789"]
var result = text.match( re ) ;

C++では、イテレーターを使ってregex_searchを繰り返し呼び出すことで書くことができる。

std::vector< std::string >
search( std::string const & text, std::regex const & re )
{
    std::vector< std::string > result ;

    auto iter = text.cbegin() ;
    auto end = text.cend() ;

    std::smatch m ;

    while ( std::regex_search( iter, end, m, re ) )
    {
        result.push_back( m.str() ) ;
        iter = m[0].second ;
    }

    return result ;
}

int main()
{
    std::regex re( R"(\d+)" ) ;
    std::string text="123 456 789" ;

    auto result = search( text, re ) ;

    for ( auto & elem : result )
    {
        std::cout << elem << std::endl ;
    }
}

とはいえ、これは面倒だ。

C++には、このように部分一致を複数見つける用途に、regex_iteratorを用意している。これを使えば、以下のように書くことができる。

std::vector< std::string >
search( std::string const & text, std::regex const & re )
{
    std::vector< std::string > result ;

    std::sregex_iterator iter( text.cbegin(), text.cend(), re ) ;
    std::sregex_iterator end ;

    for ( ; iter != end ; ++iter )
    {
        result.push_back( iter->str() ) ;
    }

    return result ;
}

置換

以下のように、DogをCatに置き換えたいとする。

var re = /Dog/g ;
var text = "Dog is nice. Dog is cute. Dog is awesome." ; 

// "Cat is nice. Cat is cute. Cat is awesome."
var result = text.replace( re, "Cat" ) ;

C++では、regex_replaceを使って書くことができる。


int main()
{
    std::regex re( R"(Dog)" ) ;
    std::string text("Dog is nice. Dog is cute. Dog is awesome.") ;

    // "Cat is nice. Cat is cute. Cat is awesome."
    auto result = std::regex_replace( text, re, "Cat" ) ;
}

以下のように最初の一致だけを書き換えたい場合、

var re = /Dog/ ;
var text = "Dog is better than dog." ; 

// "Cat is better than dog."
var result = text.replace( re, "Cat" ) ;

以下のように書くことができる。

int main()
{
    std::regex re( R"(Dog)" ) ;
    std::string text="Dog is better than dog." ;

    // "Cat is better than dog."
    auto result = std::regex_replace( text, re, "Cat",
        std::regex_constants::format_first_only ) ;
}

置換はECMAScriptの文法と同じだ。

// ECMAScript
var text = "123 456"
var re = /(\d+) (\d+)/ ;

// "456 123"
var result = text.replace( re, "$2 $1" ) ;
// C++
std::string text("123 456") ;
std::regex re(R"((\d+) (\d+))") ;

// "456 123"
auto result = std::regex_replace( text, re, "$2 $1" ) ;

サブマッチ

正規表現は括弧でキャプチャをすることができる。

var re = /(\d+) (\d+) (\d+)/ ;
var text = "123 456 789" ;

// ["123 456 789", "123", "456", "789"]
var result = text.match( re ) ;

C++では、match_resultsから得られるsub_matchをたどることで、同等のことができる。


std::vector< std::string >
match( std::string const & text, std::regex const & re )
{
    std::vector< std::string > result ;

    std::smatch m ; // match_results

    std::regex_match( text, m, re ) ;

    for ( auto && elem : m )
    {// elemはsub_match
        result.push_back( elem.str() ) ;
    }

    return result ;
}

int main()
{
    std::regex re( R"((\d+) (\d+) (\d+))" ) ;
    std::string text="123 456 789" ;

    // {"123 456 789", "123", "456", "789"}
    auto result = match( text, re ) ;

    for ( auto && elem : result )
    {
        std::cout << elem << std::endl ;
    }
}

std::regexを一通り触ってみた感想としては、Boost.Regexのうち、規格として定義できる部分だけ定義したという感じだ。

std::regexと現行の主要なライブラリ(libstdc++とlibc++)の実装を調べると、ASCII文字か、あるいは単なるバイト列に対して使うことが出来る正規表現でしかなかった。charとwchar_tには対応している。ただし、ASCII文字以外には対応していない。UTF-8を使えばバイト列として一致させることはできた。つまり、

// 通常の文字列リテラルのエンコードはUTF-8の環境
std::regex re(R"(いろは にほへ)") ;
std::string text("いろは にほへ") ;

std::regex_match( text, re ) ;

これは動く。ただし、wchar_tは動かない。

std::wregex re(R"(いろは にほへ)") ;
std::wstring text(L"いろは にほへ") ;

// 動かない
std::regex_match( text, re ) ;

UTF-8は単なるバイト列だと考えるしかない。例えば以下は動かない。

// 通常の文字列リテラルのエンコードはUTF-8の環境
std::regex re(R"(.)") ;
std::string text("あ") ;

// 動かない
std::regex_match( text, re ) ;

char16_t、char32_tは、libstdc++とlibc++では、コンパイルすら通らない。

というわけで、現状の規格と実装状況から言えば、ASCII文字だけに限定していいのならば、std::regexとstd::wregexは使える。Unicodeが扱いたければ、規格外の正規表現ライブラリを使うべきだ。

ドワンゴ広告

そろそろC++のブログ記事を増やしていきたい。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-16

インドでC型肝炎の薬の特許が無効化された理由

How India's Patent Office Destroyed Gilead's Global Game Plan - Businessweek

インドの特許庁が、Gilead Sciences社のC型肝炎の薬、Sovaldiの特許を無効化した理由が取り上げられていて興味深い。

該当の特許の化合物は、既存の化合物と似通っているためと、発明者が既存の薬に比べて劇的な効果の違いを証明できなかったためだという。

2015-01-15

ガラケー時代の翻訳

When I was in Japan I did proof reading for a Japanese feature phone. A major Ja... | Hacker News

Hacker Newsのコメントが面白かった

日本にいた時に、日本のガラケーの翻訳検証をしたことがある。ある有名な日本のブランドだった。あれは実に喜劇であった。

英語を検証するオーストラリア人と、ドイツ人の男と、イタリア人の女と、フランス人の私がいた。検証前に行われていたこと:英語力の貧弱な人間(おそらくはソフトウェアエンジニア)による日本語から英語への翻訳があり、その不思議な英語を、文脈を一切与えられずに文字列だけを与えられた翻訳家が別の言語に翻訳していた。

現場では、我々に示されたものは文字列だけであった。そして、製造元からやってきた「超企業秘密」な未公開のデバイスにアクセスできる担当者が一人。

半分以上もの翻訳は、文脈の欠如により間違っていた。フランス語の翻訳家は、「ゴミの日」を、「クソな日」と訳していた。おそらく、とてつもなくついていない一日をカレンダーに書き込むのに使うと考えたのだろう。

「(あるものを)削除する」のような文章が頻繁に現れた。当然、我々には、「あるものって何だ? 男性名詞か女性名詞か中性名詞かどれだ?」という疑問が生じた。もちろん、それはできない相談であった。すでにコードを書き変えるには遅すぎるため、我々は、"%n item(s)"のような汚い手法を取る必要があった。

ところで、現場のオーストラリア人は人類への希望を失いつつあった。ある文章が、完全に間違っていたのだ。その文章は英語で何らの意味をも持たなかった。それを読んだ現場の人間は「なんじゃこりゃ?」というしかなかった。我々には英語の文字列を変えることは許されていなかった。それはすでに検証済みであったからだ。

さもありなん

2015-01-14

Linus Torvalds、HFS+に激怒

CVE-2014-9390 aka "Git on case-insensitive filesystems" I did not give the…

gitが影響を受けた、HFS+で、一部の文字を区別しなかったり無視したりする問題に対して、Linusが吠えている。

マジで、HFS+はたぶん最悪のファイルシステムだな。クソすぎるぜ。NTFSもutf8の正規化で似たような問題(/の非正規化された表現を使用)があったが、まあ、今は修正されたんだろうよ。OS Xの問題は根本的すぎる。

そりゃ、古いさ。そりゃ、データ保護がクソすぎるってのはあるさ。だが、そういうのは、単に「すげーファイルシステムじゃない」って問題だ。「自分のケツすら拭けないマヌケによって設計された信じがたいクソ」ってわけじゃない。

HFS+の恐ろしさは、すげーファイルシステムではない、ということではない。いいアイディアがあると信じている人間によって、今もなおクソなファイルシステムとして設計され続けているということだ。

大文字小文字の同一視は信じられないくらいクソなアイディアだ。Appleの連中は修正するべきだがそれをしない。逆に、クソなアイディアを更にくそったれにしてUnicodeに拡張していやがる。UTF-8ですらなく、たぶんUCS2だ。

NTFSも似たようなことをやらかしたが、AppleはHFS+でその上をいくクソをやらかしている。

レガシーモデル(「もっとまともな方法を知らなかった」)における大文字小文字の同一視は、まだいい訳もたつ。だがな、Unicodeの同一性比較がファイルシステムにおいてもいいアイディアだと考えた奴はこの業界から干されるべきだろ。離乳食でもやって部屋の隅っこで邪魔にならないように食わしとけ。そうすりゃ奴らは幸せだろうし、俺らのシステムをクソみたいにしないだろうよ。

そして、NFD正規化を持ちだして、正しいunicodeをクソみたいなフォーマットに変換しやがるとは、言い訳も何もあったもんじゃねえよ。正規化はいいことだと考える奴らすらNFDはクソフォーマットだと認めてるし、データ交換のためにいいフォーマットじゃねーよ。離乳食レベルですらねぇ。設計上、ユーザーのデータをぶっ壊し続けてやがる。クソか。

で、Appleのこういうサルどもにファイルシステムのしごとを任せてるわけか? マジで?

ZFSに移行しなかった妥当な理由は色々ある(オホン、オラクル、ゴホン)にしてもだ、大文字小文字を区別するHFS+に移行させてから、それで将来的にはもっとマシなファイルシステムに移行させることもできただろうが、そいつはしなかったんだよな。大文字小文字を区別する方法があるが、Appleは隠して使わせないようにしている。

アホすぎてやってられねーぜ。

で、クソみたいな方針決定をする奴らと、そのクソを実装する奴らがいる。Johnが文句を言っている「よっしゃ、俺らはまともな機能を実装しないぜ」ってのより、「俺らはクソを実装するぜ」ってほうがはるかにひどい。

文句終わり

まあ、実際HFS+のUnicode正規化はクソだ。

2015-01-12

アンチウイルスソフトウェアの脆弱性

Breaking av software

市場に出回っているアンチウイルスソフトウェアの脆弱性についての研究発表のスライド資料が公開されている。

アンチウイルスソフトウェアは、セキュリティ向上のために重要だという意見があるが、このスライド著者は疑問を投げかけている。そもそも、ソフトウェアの追加は、攻撃できる箇所が増えるということだ。アンチウイルスソフトウェアは果たしてセキュアに作られているのか。

特に、多くのアンチウイルスソフトウェアは、カーネルドライバーを使ったりしている。もし脆弱性があればとんでもないことだ。

アンチウイルスソフトウェアの攻撃手段としては、細工されたファイルフォーマットをスキャンさせる事が大半だ。アンチウイルスソフトウェアは、様々なフォーマットのファイルをパースする必要がある。もし、そのパーサーにバッファーオーバーフローなどの不具合があれば任意のコードを実行させることができるし、パースに時間がかかりすぎれば、DOS攻撃に使える。

傑作なのは、既存のほとんどのアンチウイルスソフトウェアが、10年以上前の古臭い手法である、ゼロパディングされた巨大なファイルに展開される圧縮ファイルを現実的な時間で処理できずにリソースを浪費するということだ。

さて、アンチウイルスソフトウェア自体のセキュリティはどうかというと、これまた悲惨だ。

多くのアンチウイルスソフトウェアは、アップデートに素のHTTPを使い、しかもアップデートファイルは署名されていない。信じられない。

多くのアンチウイルスソフトウェアは、ASLRを無効にしている。これは、ヒューリスティックな検証をするために、ファイルをエミュレーター上で実行して挙動を確認するために、ASLRが邪魔になるからだ。問題は、一部のアンチウイルスソフトウェアは、システムのすべてのプロセスにASLRが無効化されたDLLを注入する。セキュアであるべきソフトウェアのセキュリティが聞いて呆れる。

多くのアンチウイルスソフトウェアは、ファイルのパースやネットワークパケットの検証に、エミュレーターやVMどころか、基本的なサンドボックスすら設けておらず、検証がroot権限で行われている。root権限が必要なのはネットワークパケットのキャプチャだけであり、そのデータの検証は、もっと権限の低いプロセスで行うべきである。

また、この研究者は、昔のコードを削除するべきであると主張している。MS-DOS時代のマルウェアや、もはや誰も使っていないファイルフォーマット用のチェックは、現代においては不必要であるし、長年誰も触っていない昔のコードには、脆弱性のある可能性が高い。アンチウイルスソフトウェア自体に脆弱性があるのと、大昔のもはやほとんど問題にならないマルウェアを検出できるのと、どちらがいいというのか。

筆者は、もうアンチウイルスソフトウェアの時代ではないと思っている。

2015-01-09

[[deprecated]] はテンプレート名には使えない

[[deprecated]]属性はテンプレートの特殊化に対して指定できる。テンプレート名に対しては指定できない。

// テンプレートAの特殊化をdeprecated扱い
template < typename T >
class [[deprecated]] A { } ;

template < template < typename > class >
class B { } ;

// deprecated
A<int> a ; 

// 規格上何もなし
B<A> b ; 

どうも現在主流のコンパイラー実装上の都合があるそうだ。

ドワンゴ広告

最近ネタ切れになってきた。ドワンゴでは正月に一気に有給を取得する社員が多いらしく、まだ空席が目立つ。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-07

巻末C++14の新機能をとりあえず書いた

EzoeRyou/cpp14-appendix

巻末: C++14の新機能

C++14のコア言語の新機能を解説するために、急遽巻末としてC++14の新機能を書いているが、とりあえずC++14で追加されたコア言語の新機能としては、全て網羅した解説を書き終えた。

文法と意味を解説するのは簡単だが、さて、これをどうやって改良しよう。

ドワンゴ広告

この記事はドワンゴ勤務中に書かれた。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0

2015-01-06

[[deprecated]]の文面の疑問点

[[deprecated]]の解説を書くためにCC++14の文面を解釈していて、以下のような疑問を持った。

§ 7.6.5 paragraph 2

The attribute may be applied to the declaration of a class, a typedef-name, a variable, a non-static data member, a function, a namespace, an enumeration, an enumerator, or a template specialization.

テンプレートの特殊化(template specialization)という用語の使用がとても気になる。

何故ならば、テンプレートの特殊化の宣言というものは、明示的なテンプレートの特殊化ぐらいしか思いつかないからだ。通常のテンプレートの特殊化は、暗黙のテンプレートの実体化された結果であり、宣言は存在しない。プライマリーテンプレートの宣言はテンプレートの宣言であり、テンプレートの特殊化の宣言ではない。

すると、テンプレート宣言にはdeprecated属性が使えないのだろうか。

「テンプレートの特殊化」という用語を使用することのもうひとつの問題は、template-idに限定してしまうということだ。template-nameはテンプレートの特殊化ではない。

// テンプレートの特殊化の宣言ではないが
template < typename T >
class [[deprecated]] A { } ;

template < template < typename > typename T >
class B { } ;

// 警告
// template-idはテンプレートの特殊化
A<int> ;

// 警告なし
// template-nameはテンプレートの特殊化ではない
B<A> b ;

現在のClangの実装は、正しく(?)A<int>とB<A>のどちらとも警告を出さない。GCCはどちらとも警告を出す。

こういう細かい文面解釈の問題が気になってしまってなかなかC++14解説の執筆が進まない。

ドワンゴ広告

この記事はドワンゴ勤務中に書いた。

ドワンゴは本物のC++プログラマーを募集しています。

採用情報|株式会社ドワンゴ

CC BY-ND 4.0: Creative Commons — Attribution-NoDerivatives 4.0 International — CC BY-ND 4.0