nikeeshi のコーディング記

コーディングの成果をはっつけるとこ。このブログにあるソースコードはNYSL Version 0.9982に従い公開します(2014/06/18)。

TCO14MRound1

注意

思った通りにうごきません!!!

やりたかったこと

スコアが変化するまでを1ステップとして、適当にビームサーチ。

セルの隣接記録を持っておくと、離れた場所のセルを交換できる。(昔に戻って入れ替えてくる) この性質を何とか使う。

やったこと(厳密にはやってない)

ランダムで2*2の四角と色を選ぶ。その色をかき集めてくる。(ここのアルゴリズムに問題あり) ランダムをたくさんやればいい奴見つかりそう。

コード

#include <vector>
#include <list>
#include <queue>
#include <complex>
#include <string>
#include <iostream>
#include <random>
#include <tuple>
#include <functional>
#include <algorithm>
#include <climits>
#include <fstream>
using namespace std;
std::ofstream ofs("log.txt");
auto m=mt19937();
auto rnd=[&](int x) {return uniform_int_distribution<>(0, x-1)(m); };
template <class T>
void print(vector<T> arr) {
    for(int i=0; i<arr.size(); i++)cerr<<arr[i]<<" ";
    cerr<<endl;
}
template<class T>
struct withKey
{
public:
    int key;
    T value;
    bool operator<(const withKey& a)const {
        return key<a.key;
    }
};
template<class T>
withKey<T> make_withKey(int key, T value) {
    return withKey<T>{key, value};
}
template <class T>
void appendvector(vector<T>& arr1,const vector<T>& arr2) {
    arr1.reserve(arr1.size()+arr2.size());
    for(auto e:arr2)arr1.push_back(e);
}
class LackofTheColor { public: int tilesize; };
class SquareRemover
{
public:
    //utilities
    int INF=INT_MAX;
    using point=complex<int>;
    inline int getX(point a) {
        return real(a);
    }
    inline int getY(point a) {
        return imag(a);
    }

    inline int x_distance(point a, point b) {
        return abs(getX(a)-getX(b));
    }
    inline int y_distance(point a, point b) {
        return abs(getY(a)-getY(b));
    }
    inline int distance(point a, point b) {
        return abs(real(a)-real(b))+abs(imag(a)-imag(b));
    }

    auto nearer(point p)->function<auto(point, point)->bool> { return [&](point x, point y) {return distance(x, p)<distance(y, p); }; }
    auto farther(point p)->function<auto(point, point)->bool> { return [&](point x, point y) {return distance(x, p)>distance(y, p); }; }

    using square=complex<int>;//the smaller
    bool valid(square s) {
        return 0<=getX(s)&&getX(s)<N-1
            && 0<=getY(s)&&getY(s)<N-1;
    }
    vector<point> area(square s) {
        vector<point> ret={ s, s+right, s+down, s+right+down };
        return ret;
    }
    function<auto(int)->square> rndsq=[&](int N) {return square(rnd(N-1), rnd(N-1)); };
    using vs=vector<square>;
    function<auto(int)->vs>allsquare=[&](int N) {
        vector<square> ans;
        for(int i=0; i<N-1; i++)
        for(int j=0; j<N-1; j++){
            ans.push_back(square(i, j));
        }
        return ans;
    };

    vector<square> squarearound(point p) {
        vector<square> op={ p, p+left, p+up, p+left+up };
        vector<square> ret;
        for(square s : op){
            if(valid(s))ret.push_back(s);
        }
        return ret;
    };

    using direction=complex<int>;
    const direction left= direction(0, -1);//-y
    const direction right=direction(0, 1);//y
    const direction up=   direction(-1, 0);//-x
    const direction down= direction(1, 0);//x

    template <class T>
    using field=vector<vector<T>>;

    using board_t=vector<string>;

    using color=int;

    using vc=vector<color>;
    function<auto (int)->vc> allcolor=[&](int colors) {
        vector<color> ans;
        for(int i=0; i<colors; i++)
            ans.push_back(i);
        return ans;
    };

    using swapping=tuple<point, point>;

    template <class T>
    vector<T>&& randomPartialPermutation(vector<T>&& arr) {
        const int& N=arr.size();
        for(int i=1; i<N; i++)
            swap(arr[N-i], arr[rnd(N)]);
        return move(arr);
    }

    void squarecheck_full(board_t& f, int& seed) {
        for(square s : allsquare(N)){
            for(color c : allcolor(colors)){
                auto ar=area(s);
                if(any_of(ar.begin(), ar.end(), [&](point p) {return f[getX(p)][getY(p)]==c; })){
                    for(int i=0; i<4; i++){
                        point& p=ar[i];
                        f[getX(p)][getY(p)]=seed;
                        seed = (seed * 48271) % 2147483647;
                    }
                    return squarecheck_full(f, seed);
                }
            }
        }
        return;
    }

    void apply(vector<swapping> opes, board_t& f, int seed) {
        for(auto ope:opes){
            squarecheck_full(f, seed);
            int ax=getX(get<0>(ope));
            int ay=getY(get<0>(ope));
            int bx=getX(get<1>(ope));
            int by=getY(get<1>(ope));
            swap(f[ax][ay], f[bx][by]);
        }
        return;
    }

    //parameters
    int colors;
    vector<string> board;
    int boardsize;
    int& N=boardsize;
    int startSeed;

    point bettersearch(board_t& board, square s, color c, point target) {
        point ans;
        int mindis=INF;
        auto ar=area(s);
        for(int x=0; x<N; x++)
        for(int y=0; y<N; y++)
        if(board[x][y]-'0'==c
           &&(find(ar.begin(), ar.end(), point(x, y))==ar.end()
           || target==point(x, y)
           ))
        {
            int d=INF;
            for(point p : area(s))
                d=min(d, distance(p, point(x, y)));
            if(mindis>d){ans=point(x,y);mindis=d;}
        }
        return ans;
    }
    //(-d,(x,y))
    priority_queue<withKey<point>> search4(board_t& board, square s, color c) {
        priority_queue<withKey<point>> options;
        for(int x=0; x<N; x++)
        for(int y=0; y<N; y++)
        if(board[x][y]-'0'==c)
        {
            int d=INF;
            for(point p : area(s))
                d=min(d, distance(p, point(x, y)));
            options.push(make_withKey(-d, point(x, y)));
        }
        if(options.size()<4)throw LackofTheColor{ options.size() };
        return options;
    }

    //a->b
    vector<swapping> randomPathShift(point a, point b) {
        direction xdir, ydir;
        if(getX(b)-getX(a)>0)xdir=down;
        else xdir=up;
        if(getY(b)-getY(a)>0)ydir=right;
        else ydir=left;
        vector<point> di(distance(a, b), ydir);
        for(int i=0; i<x_distance(a, b); i++)
            di[i]=xdir;
        auto randomed_di=randomPartialPermutation(move(di));
        vector<swapping> ans;
        point cur=a;
        for(int i=0; i<randomed_di.size(); i++){
            point nextpoint=cur+randomed_di[i];
            ans.push_back(swapping(cur, nextpoint));
            cur=nextpoint;
        }
        return ans;//OK
    }

    vector<swapping> gather4Path(board_t& board, square s, color c) {
        auto que=search4(board, s, c);
        vector<point> options;
        while(options.size()<4){
            auto pick=que.top();
            que.pop();
            options.push_back(pick.value);
            while(que.top().key==pick.key){
                options.push_back(que.top().value);
                que.pop();
            }
        }
        vector<swapping> ans;
        for(auto p:area(s)){
            auto nearest=min_element(options.begin(), options.end(), nearer(p));
            appendvector(ans, randomPathShift(*nearest, p));
            options.erase(nearest);
        }
        return ans;//OK
    }

    vector<swapping> bettergather4Path(board_t& board, square s, color c) {
        board_t b_copy(board);
        vector<swapping> ans;
        for(auto p:area(s)){
            auto nearest=bettersearch(b_copy,s,c,p);
            appendvector(ans, randomPathShift(nearest, p));
        }
        return ans;
    }
    vector<int> playIt_randomAns(int colors, board_t board, int startSeed) {
        //init
        this->colors=colors;
        this->board=board;
        this->startSeed=startSeed;
        this->boardsize=board.size();
        vector<int> ans;
        auto push=[&](int&& x, int&& y, int&& dir) {
            ans.push_back(x);
            ans.push_back(y);
            ans.push_back(dir);
        };
        auto randomans=[&]() {
            if(rnd(2)==0)
                push(rnd(N-1)+1, rnd(N), 0);
            else
                push(rnd(N), rnd(N-1), 1);
        };
        for(int i=0; i<10000; i++)
            randomans();
        return ans;
    }
    vector<swapping> playIt_hoge(int colors, board_t board, int startSeed) {
        //init
        this->colors=colors;
        this->board=board;
        this->startSeed=startSeed;
        this->boardsize=board.size();
        vector<swapping> ans;
        auto addans=[&]() {
            appendvector(ans,randomPathShift(point(0,0),point(N-1,N-1)));
        };
        while(ans.size()<=10000)addans();
        while(ans.size()>10000)ans.pop_back();

        return ans;;
    }
    vector<swapping> playIt_randomgreedy(int colors, board_t board, int startSeed) {
        //init
        this->colors=colors;
        this->board=board;
        this->startSeed=startSeed;
        this->boardsize=board.size();
        vector<swapping> ans;
        auto addans=[&]() {
            vector<swapping> ops;
            square curs;
            color curc;
            back:
            try{
                ops=bettergather4Path(this->board, rndsq(N), rnd(colors));
                for(int i=0; i<10; i++){
                    square shoge;color choge;
                    auto m=bettergather4Path(this->board, shoge=rndsq(N), choge=rnd(colors));
                    if(ops.size()>m.size()){
                        ops=m;
                        curs=shoge;
                        curc=choge;
                    }
                }
            } catch(...){
                goto back;
            }
            apply(ops, this->board, this->startSeed);
            appendvector(ans, ops);
            ofs<<"sq:"<<curs<<curc<<endl;
        };
        while(ans.size()<=10000)addans();
        while(ans.size()>10000)ans.pop_back();

        return ans;
    }
    vector<int> playIt(int colors, board_t board, int startSeed) {
        auto toanstype=[&](vector<swapping> vs) {
            vector<int> ans;
            for(int i=0; i<vs.size(); i++){
                swapping& s=vs[i];
                auto a=get<0>(s);
                auto b=get<1>(s);
                ans.push_back(getX(a));
                ans.push_back(getY(a));
                for(int i=0; i<4; i++){
                    direction dir=vector<direction>{up, right, down, left}[i];
                    if(b-a==dir){
                        ans.push_back(i);
                    }
                }
            }
            return ans;
        };
        auto ret=playIt_randomgreedy(colors, board, startSeed);
        /*for(int i=0; i<ret.size(); i++)
            ofs<<get<0>(ret[i])<<"\t"<<get<1>(ret[i])<<endl;*/
        return toanstype(ret);
    }
};
//***************************

int main() {
    int colors;
    int N;
    cin>>colors>>N;
    vector<string> board(N);
    for(int i=0; i<N; i++)
        cin>>board[i];
    int startSeed;
    cin>>startSeed;
    ofs<<"input:"<<endl;
    ofs<<colors<<endl;
    ofs<<N<<endl;
    for(int i=0; i<N; i++)
        ofs<<board[i]<<endl;
    ofs<<startSeed<<endl;
    ofs<<"output:"<<endl;
    auto ret=SquareRemover().playIt(colors, board, startSeed);
    for(int i=0; i<10000; i++)
        ofs<<ret[3*i]<<"\t"<<ret[3*i+1]<<"\t"<<ret[3*i+2]<<endl;
    for(int i=0; i<30000; i++)
        cout<<ret[i]<<endl;
    return 0;
}