Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

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;
}
emattsan
ソフトウェアエンジニア、言語オタク
http://d.hatena.ne.jp/E_Mattsan/
esm
We build applications which work well and make customers happy.
http://www.esm.co.jp
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした