第8回オフラインリアルタイムどう書くの参考問題の回答例。C++で。その2

ステートマシンで解いてみました。
思ったほどには簡単にはならなかったなー、というのが印象。

お題はこちら http://qiita.com/items/24b9be4ee3bae4c89a95

追記：ブログに解説を書きました→ http://d.hatena.ne.jp/E_Mattsan/20130320/1363738892

#include <iostream>
#include <sstream>
#include <string>

static const std::string NIBBLES[] =
{
    "0000", "1000", "0100", "1100", "0010", "1010", "0110", "1110",
    "0001", "1001", "0101", "1101", "0011", "1011", "0111", "1111"
};

static const std::string HEXES = "0123456789abcdef";

static const int STATES[][2] =
{
    {  1,  5 }, {  6,  2 }, {  3, 11 }, { 16,  4 },
    { 17,  7 }, { 23,  8 }, { 13,  9 }, { 10, 20 },
    { 12, 26 }, { 14, 15 }, { 18, 19 }, { 21, 22 }, { 24, 25 }
};

static const int CHAR_CODE    = 13;
static const int INVALID_CODE = 18;
static const int TERMINAL     = 26;

char state2char(int state)
{
    return "tsnid cloaerh"[state - CHAR_CODE];
}

std::string solve(const std::string& input)
{
    std::string bits;
    for(std::string::const_iterator i = input.begin(); i != input.end(); ++i)
    {
        bits += NIBBLES[HEXES.find(*i)];
    }

    std::string::size_type pos = 0;
    std::string            result;
    int                    state = 0;
    for(;;++pos)
    {
        if(bits.size() <= pos) { pos = std::string::npos; break; }

        state = STATES[state][bits[pos] - '0'];

        if(state == INVALID_CODE) { pos = std::string::npos; break; }
        if(state == TERMINAL)     { break; }
        if(state >= CHAR_CODE)    { result += state2char(state); state = 0; }
    }

    if(pos != std::string::npos)
    {
        std::ostringstream output;
        output << result << ":" << (pos + 1);
        return output.str();
    }
    else
    {
        return "*invalid*";
    }
}

void test(const std::string& input, const std::string& expected)
{
    std::string actual = solve(input);
    std::cout << actual << " => " << (actual == expected ? std::string("o") : ("x:" + expected)) << "¥n";
}

int main(int, char* [])
{
    /*0*/ test( "16d9d4fbd", "ethanol:30" );
    /*1*/ test( "df", "e:5" );
    /*2*/ test( "ad7", "c:10" );
    /*3*/ test( "870dcb", "t:6" );
    /*4*/ test( "880f63d", "test:15" );
    /*5*/ test( "a57cbe56", "cat:17" );
    /*6*/ test( "36abef2", "roll:23" );
    /*7*/ test( "ad576cd8", "chant:25" );
    /*8*/ test( "3e2a3db4fb9", "rails:25" );
    /*9*/ test( "51aa3b4c2", "eeeteee:18" );
    /*10*/ test( "ad5f1a07affe", "charset:31" );
    /*11*/ test( "4ab8a86d7afb0f", "slideshare:42" );
    /*12*/ test( "ac4b0b9faef", "doctor:30" );
    /*13*/ test( "cafebabe", "nlh:17" );
    /*14*/ test( "43e7", "sra:15" );
    /*15*/ test( "53e7", "eera:15" );
    /*16*/ test( "86cf", "tera:16" );
    /*17*/ test( "b6cf", "hon:15" );
    /*18*/ test( "0", "*invalid*" );
    /*19*/ test( "c", "*invalid*" );
    /*20*/ test( "d", "*invalid*" );
    /*21*/ test( "e", "*invalid*" );
    /*22*/ test( "babecafe", "*invalid*" );
    /*23*/ test( "8d", "*invalid*" );
    /*24*/ test( "ad", "*invalid*" );
    /*25*/ test( "af", "*invalid*" );
    /*26*/ test( "ab6e0", "*invalid*" );
    /*27*/ test( "a4371", "*invalid*" );
    /*28*/ test( "a4371", "*invalid*" );
    /*29*/ test( "96e3", "*invalid*" );
    /*30*/ test( "0dc71", "*invalid*" );
    /*31*/ test( "2a9f51", "*invalid*" );
    /*32*/ test( "a43fb2", "*invalid*" );
    /*33*/ test( "ab6e75", "*invalid*" );
    /*34*/ test( "a5dcfa", "*invalid*" );
    /*35*/ test( "ca97", "*invalid*" );
    /*36*/ test( "6822dcb", "*invalid*" );

    return 0;
}