第五回オフラインリアルタイムどう書くの回答例(C++ その2)

FugataroO さんの http://qiita.com/items/00b7ea931950c7910c56 にインスパイアされました。

前回、組み合わせ(combination)を作るのにかなり頭を悩ませたんですが、FugataroO さんのコードを見ていて、「どのみちフィルタリングするんだから作れるサブシーケンス全部作ってフィルタリングすりゃいい」ということに気がつきまして。で、いろいろbrushupしていったらサブシーケンスの生成が非常に簡単に書けることがわかりまして（アルゴリズムの教科書に書いてありそう…）。で、こんなんなりました。

joinとかsplitとかを自前で書いたので全体は長くなりましたが、本体はとても簡単になりました。

あ、お題はこちらです http://qiita.com/items/5c10c132e1f78131563f
入力としてpatterns.tsvというタブ区切りのテキストファイルがあることを期待しています。

#include <iostream>
#include <fstream>
#include <string>
#include <vector>

// 札の強さ（1〜14）、出せる札の条件を満たしていない場合は0
std::size_t getRank(const std::string& s)
{
    static const std::string ranks = " 3456789TJQKA2o";

    if((s.size() % 2) != 0)
    {
        return 0;
    }

    std::size_t rank = ranks.find(s[1]);
    for(std::size_t pos = 3; pos < s.size(); pos += 2)
    {
        std::size_t r = ranks.find(s[pos]);
        if(rank == (ranks.size() - 1))
        {
            rank = r;
        }
        else if((r != (ranks.size() - 1)) && (r != rank))
        {
            return 0;
        }
    }
    return rank;
}

// sの全サブシーケンスをssに格納
void subsequences(const std::string& s, std::vector<std::string>& ss)
{
    std::vector<std::string> result;
    result.push_back("");
    for(std::size_t pos = 0; pos < s.size(); pos += 2)
    {
        int n = result.size();
        for(int i = 0; i < n; ++i)
        {
            result.push_back(result[i] + s.substr(pos, 2));
        }
    }
    ss.swap(result);
}

// 不適合組み合わせ検出器
struct IsInvalid
{
    const std::size_t rank;
    const std::size_t size;

    IsInvalid(const std::string& s) : rank(getRank(s)), size(s.size()) {}
    bool operator () (const std::string& s) const
    {
        // サイズ（枚数）があってない or 強さが場の札以下
        return (s.size() != size) || (getRank(s) <= rank);
    }
};

// derimiterで文字列を分割して、分割した個々の文字列をssに格納
void split(const std::string& s, char derimiter, std::vector<std::string>& ss)
{
    std::vector<std::string> result;
    std::size_t pos;
    std::size_t head = 0;
    do
    {
        pos = s.find(derimiter, head);
        result.push_back(s.substr(head, pos - head));
        head = pos + 1;
    } while(pos != std::string::npos);
    ss.swap(result);
}

// 文字列の列ssをderimiterを挟んだひとつの文字列に連結、ssが空のばあいは"-"を返す
std::string join(const std::vector<std::string>& ss, const std::string& derimiter)
{
    if(ss.size() == 0)
    {
        return "-";
    }

    std::vector<std::string>::const_iterator i = ss.begin();
    std::string result = *i;
    ++i;
    for(; i != ss.end(); ++i)
    {
        result += derimiter;
        result += *i;
    }
    return result;
}

// 問題をときます
std::string solve(const std::string& input)
{
    std::size_t comma_pos = input.find(',');

    // 場と手札に分割
    std::string field = input.substr(0, comma_pos);
    std::string hands = input.substr(comma_pos + 1);

    std::vector<std::string> ss;
    subsequences(hands, ss); // 手札でできる組み合わせを全部挙げる
    ss.erase(std::remove_if(ss.begin(), ss.end(), IsInvalid(field)), ss.end()); // 不適な組み合わせを削除する
    return join(ss, ","); // 連結する
}

// 以下、テストコード

struct Pattern
{
    Pattern(const std::string& s) : name(), input(), expected()
    {
        std::size_t d1 = s.find('\t');
        std::size_t d2 = s.find('\t', d1 + 1);
        if((d1 != std::string::npos) && (d2 != std::string::npos))
        {
            name     = s.substr(0, d1);
            input    = s.substr(d1 + 1, d2 - d1 - 1);
            expected = s.substr(d2 + 1);
        }
    }

    std::string name;
    std::string input;
    std::string expected;
};

std::string sort_cards(const std::string& s)
{
    if(s == "-")
    {
        return s;
    }

    std::vector<std::string> ss;
    split(s, ',', ss);

    for(std::vector<std::string>::iterator i = ss.begin(); i != ss.end(); ++i)
    {
        std::vector<std::string> sss;
        for(std::size_t pos = 0; pos < i->size(); pos += 2)
        {
            sss.push_back(i->substr(pos, 2));
        }
        std::sort(sss.begin(), sss.end());
        *i = join(sss, "");
    }
    std::sort(ss.begin(), ss.end());
    return join(ss, ",");
}

int main(int, char* [])
{
    std::ifstream patterns("patterns.tsv");
    int           count_cases    = 0;
    int           count_failures = 0;
    std::string   s;
    while(std::getline(patterns, s).good())
    {
        ++count_cases;
        Pattern     pattern(s);
        std::string actual = solve(pattern.input);
        if(sort_cards(actual) != sort_cards(pattern.expected))
        {
            ++count_failures;
            std::cout << "Failure in " << pattern.name << "\n"
            << "expected: \"" << pattern.expected << "\"\n"
            << "  actual: \"" << actual << "\"\n";
        }
    }
    std::cout << "\nCases: " << count_cases << "  Failures: " << count_failures << "\n";

    return 0;
}