第五回オフラインリアルタイムどう書くの実装例(C++11)

第五回オフラインリアルタイムどう書く( http://atnd.org/events/32979 )。
問題は下記 URL。
http://nabetani.sakura.ne.jp/hena/ord5dahimi/
で。
ruby の実装 ( http://qiita.com/items/65923e184b2331c266e8 ) をほぼそのまま C++11 に移植してみた。

```c++:dahi.cpp
// use -std=c++0x or -std=c++11
#include <iostream>
#include <vector>
#include <string>
#include <set>
#include <tr1/functional>

using namespace std;
using namespace std::tr1;
const int JOKER=13;

int strength1( string const & str )
{
    return string("3456789TJQKA2o").find( str[1] );
}

int strength( vector<string> const & c )
{
    return strength1( 
        *min_element( 
            c.begin(), c.end(), 
            []( string const & a, string const & b)->bool{  return strength1(a)<strength1(b);  } ) );
}

bool legal_hand( vector<string> const & cand )
{
    set<int> s;
    transform( cand.begin(), cand.end(), inserter( s, s.end() ), strength1 );
    return s.size()==1 || ( s.size()==2 && *s.rbegin()==JOKER );
}

template< typename itor_t >
vector<string>
cardset( itor_t const & b, itor_t const & e )
{
    vector<string> r;
    for( itor_t it = b ; it!=e && it-1!=e ; it+=2 ){
        r.push_back( string( it, it+2 ) );
    }
    return r;
}

template< typename itor_t >
std::vector<string>
concat( std::vector<string> const & a, itor_t b, itor_t e )
{
    std::vector<string> r(a);
    r.insert( r.end(), b, e );
    return r;
}

template< typename itor_t >
void
combination( 
    itor_t b, itor_t e, int size, 
    function< void( vector<string> const & ) > const & pred )
{
    typedef string value_type;
    if (size==0){
        pred( std::vector< value_type >() );
    } else if ( size<=e-b ){
        combination( b+1, e, size, pred );
        combination( b+1, e, size-1,[&]( vector<value_type> const & c ){
            pred( concat( c, b, b+1 ) );
        });
    }
}

template< typename container_t >
string join( container_t const & c, string const & sepa )
{
    string result;
    for( auto it = c.begin() ; it != c.end() ; ++it ){
        result += ( it != c.begin() ? sepa : string() )+*it;
    }
    return result;
}

string solve( string const & input )
{
    size_t comma=input.find( ',' );
    auto f=cardset( input.begin(), input.begin()+comma );
    auto hand=cardset( input.begin()+comma+1, input.end() );
    int sf=strength(f);
    set< string > candidates;
    combination( hand.begin(), hand.end(), f.size(), [&]( vector<string> const & c ){
        if ( legal_hand(c) && sf<strength(c) ){
            candidates.insert( join( set<string>( c.begin(), c.end() ), "" ) );
        }
    });
    string result = join( candidates, "," );
    return result.empty() ? "-" : result;
}

set< string >
normalized( string const & str )
{
    set<string> r;
    auto sorted = []( string const & s )->string{
        string r=s;
        sort( (int16_t*)r.data(), (int16_t*)( r.data()+r.size()/2*2) ); // evil implement.
        return r;
    };
    for( size_t ix=0;;){
        size_t comma=str.find( ",", ix );
        if ( comma==string::npos ){
            r.insert( sorted( str.substr( ix )) );
            return r;
        } else {
            r.insert( sorted( str.substr( ix, comma-ix )));
            ix=comma+1;
        }
    }
}

bool are_same( string const & a, string const & b )
{
    return normalized( a ) == normalized( b );
}

void test( string const & input, string const & expected )
{
    string actual = solve( input );
    cout << input << "\n   :" 
        << actual << "\n   :" 
        << expected << "\n    -> " 
        << ( are_same( actual, expected ) ? "ok" : "*** FAIL ***" )<< endl;
}

int main()
{
    /*#1*/ test( "DJ,", "-" );
    /*#7*/ test( "ST,D6S8JoC7HQHAC2CK", "Jo,C2,CK,HA,HQ" );
    /*#10*/ test( "Jo,HAC8DJSJDTH2", "-" );
    /*#24*/ test( "JoD4H4,D3H3S3C3CADASAD2", "DACASA" );
    /*#31*/ test( "DTCTSTHT,S3SQH3HQD3DQC3CQJo", "HQSQJoDQ,SQCQDQJo,DQCQHQJo,SQHQJoCQ,CQDQHQSQ" );
}
```

いつもどおりテストの大半は省略。
まだ lambda の文法に慣れてない。

C++11 の algorithm と string を調べればもう少し楽できるのかもしれないと考えているものの、今のところはこんな感じ。

std::next_permutation はあるのに std::next_combination がないのが残念。