//
//  main.cpp
//  doudizhu
//
//  Created by alex on 2023/3/2.
//

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

//暂时没有考虑大小王炸弹,多个炸弹也没有考虑, 连对没有考虑, 多个三带几也没有考虑
#define King_Small 16
#define King_Big 17

map<int,int> vector2map(vector<int> v)
{
    map<int,int> s;
    for(int i = 0;i < v.size(); ++ i)
    {
        if(s.contains(v[i]))
            s[v[i]] ++ ;
        else
            s[v[i]] = 1;
    }
    return s;
}

//长度为2的map是否符合
bool isMapLengthEquad(map<int,int>m, int length1, int length2)
{
    if(m.size() != 2)
        return false;
    int a =  (*(m.begin())).second;
    auto it = m.begin();
    ++it;
    int b =(*(it)).second;
    if(a == length1 && b == length2)
        return true;
    if(a == length2 && b == length1)
        return true;
    
    return  false;
}


bool isVectorEqual(vector<int> v1, vector<int> v2)
{
    if(v1.size() != v2.size())
        return  false;
    for(int i = 0;i < v1.size(); ++ i)
    {
        if(v1[i] != v2[i])
            return  false;
    }
    
    
    return true;
}
//长度为3的map是否符合
bool isMapLengthEquad(map<int,int>m, int length1, int length2, int length3)
{
    if(m.size() != 2)
        return false;
    int a =  (*(m.begin())).second;
    auto it = m.begin();
    ++it;
    int b =(*(it)).second;
    ++it;
    int c = (*(it)).second;
    vector<int> v1;
    v1.push_back(a);
    v1.push_back(b);
    v1.push_back(c);
    vector<int> v2;
    v2.push_back(length1);
    v2.push_back(length2);
    v2.push_back(length3);
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    if(isVectorEqual(v1,v2))
        return  true;
    
    return  false;
}


bool isBomb(map<int,int> m)
{
    if(m.size() == 1)
        return m.begin()->second == 4;
    else if(m.size() == 3)
        return isMapLengthEquad(m, 4, 1, 1) || isMapLengthEquad(m, 4, 2, 2);
    return  false;
}

//v有顺序
bool isSequence(vector<int> v)
{
    for(int i = 0;i < v.size(); ++ i)
    {
        if(v[i] >= 15)
            return false;
    }
    for(int i = 1;i < v.size(); ++ i)
    {
        if(v[i] - v[i-1] != 1)
            return  false;
    }
    
    return  true;
}

bool isOK(vector<int> v)
{
    sort(v.begin(), v.end());
    if(v.size() == 0)
        return true;
    else if(v.size() == 1)
        return true;
    else if(v.size() == 2)
    {
        return v[0] == v[1];
    }
    else if(v.size() == 3)
    {
        return v[0] == v[1] && v[1]== v[2];
    }
    else if(v.size() == 4)
    {
        //炸弹
        if(v[0] == v[1] && v[1]== v[2] && v[2] == v[3])
            return true;
        //是否是3带1
        if(isMapLengthEquad(vector2map(v), 3, 1))
            return true;
        return false;
    }
    else if(v.size() == 5)
    {
        //是否是3带1对
        set<int> s;
        if(isMapLengthEquad(vector2map(v), 3, 2))
            return true;
        if(isSequence(v))
            return true;
        return false;
    }
    else if(v.size() == 6)
    {
        //是否是4带2
        auto m = vector2map(v);
        if(isMapLengthEquad(m,4,1,1))
            return true;
    }
    else if(v.size() == 8)
    {
        //是否是4带2对
        auto m = vector2map(v);
        if(isMapLengthEquad(m,4,2,2))
            return true;
    }
        
    return isSequence(v);
}


int pow2(int t)
{
    int ret = 1;
    while(t --)
    {
        ret *= 2;
    }
    return  ret;
}


void printVector(const vector<int>& v)
{
    for(int i = 0;i < v.size(); ++ i)
    {
        printf("%d,", v[i]);
    }
    printf("\n");
}

vector<int> mapsize2vector(map<int,int> m)
{
    vector<int> ret;
    for(auto it = m.begin(); it != m.end(); ++ it)
    {
        ret.push_back(it->second);
    }
    return ret;
}

bool isSameMap(map<int,int>& m1, map<int, int>& m2)
{
    auto v1 = mapsize2vector(m1);
    auto v2 = mapsize2vector(m2);
    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    return v1 == v2;
}

int getMainEleInMap(map<int,int>&m)
{
    int ret = 0;
    int max = 0;
    for(auto it = m.begin(); it != m.end(); ++ it)
    {
        int num = it->second;
        if(num >= max)
        {
            max = num;
            ret = it->first;
        }
    }
    
    
    return ret;
}

bool canPushForSequence(const vector<int>& now, const vector<int>& last)
{
    //先前为空,现在必须出
    if(last.size() == 0)
        return now.size() > 0;
    //先前不为空,必须是炸弹或者同类型的,或者为空
    if(now.size() == 0)
        return true;
    auto map_now = vector2map(now);
    auto map_last = vector2map(last);
    if(isBomb(map_now))
    {
        //判断炸弹是否大过之前的
        if(map_now.begin()->first  > map_last.begin()->first)
            return  true;
        return false;
    }
    //不是同一类型
    bool isSame = isSameMap(map_now, map_last);
    if(!isSame)
        return false;
    
    //是同一类型
    //是顺子
    if(isSequence(now))
    {
        return now[now.size()-1] > last[last.size()-1];
    }
    //不是顺子
    return getMainEleInMap(map_now) > getMainEleInMap(map_last);
    
    return  true;
}

vector<vector<int>> getAllPushMethod(const vector<int>& a)
{
    int all = pow2(a.size());
    vector<vector<int>> ret;
    set<vector<int>> vis;
    for(int i = 0;i < all; ++ i)
    {
        vector<int> one;
        for(int k = 0;k < a.size(); ++ k)
        {
            if(i & (1<<k))
            {
                one.push_back(a[k]);
            }
        }
        if(vis.contains(one))
            continue;
        if(isOK(one))
        {
            ret.push_back(one);
            //printVector(one);
        }
        vis.insert(one);
    }
    
    //vector<int> one;
    //ret.push_back(one);
    return ret;
}

vector<int> vectorMinus(const vector<int>& a, const vector<int>& b)
{
    vector<int> ret = a;
    for(int i = 0;i < b.size(); ++ i)
    {
        auto it = find(ret.begin(), ret.end(), b[i]);
        ret.erase(it);
    }
    
    return ret;
}

bool canSolove(const vector<int>&a,const vector<int>& b,const vector<int>& last_push,int step,vector<vector<int>> _solution)
{
    
    
    auto va = getAllPushMethod(a);
    auto vb = getAllPushMethod(b);
    for(int i = 0;i < va.size(); ++ i)
    {
        if(step == 0)
        {
            printf("step(%d) : %d/%d\n",step,i,va.size());
        }
        else if(step == 1)
        {
            printf("\tstep(%d) : %d/%d\n",step,i,va.size());
        }
        else if(step == 2)
        {
            printf("\t\tstep(%d) : %d/%d\n",step,i,va.size());
        }
        else if(step == 3)
        {
            printf("\t\t\tstep(%d) : %d/%d\n",step,i,va.size());
        }
        else if(step == 4)
        {
            printf("\t\t\t\tstep(%d) : %d/%d\n",step,i,va.size());
        }
        
        vector<int> push_a = va[i];
        
        if(canPushForSequence(push_a, last_push)==false)
        {
            continue;
        }
        //printf("push_a: ");
        //printVector(push_a);
        vector<int> left_a = vectorMinus(a, push_a);
        
        vector<vector<int>> solution = _solution;
        solution.push_back(push_a);
        if(left_a.size() == 0)
        {
            /*if(step == 0)
            {
                printf("得到一个解决方案\n");
                for(int i = 0;i < solution.size(); ++ i)
                {
                    printf("\t");
                    printVector(solution[i]);
                }
            }*/
            //solution.erase(solution.begin() + 1);
            return true;
        }
        bool allOk = true;
        for(int j = 0;j < vb.size(); ++ j)
        {
            vector<int> push_b = vb[j];
            vector<int> left_b =vectorMinus(b, push_b);
            
            
            if(canPushForSequence(push_b, push_a)== false)//不能出
            {
                continue;
            }
                
            //printf("push_b: ");
            //printVector(push_b);
            //失败了
            if(left_b.size() == 0)
            {
                allOk = false;
                break;
            }
                
            
            //能出,深度搜索
            auto childHasSolution = canSolove(left_a, left_b, push_b, step + 1,solution);
            if(!childHasSolution) //存在子牌没有解决方案
            {
                allOk = false;
                break;
            }
        }
        //solution.erase(solution.begin() + 1);
        if(allOk)
        {
            if(step == 0)
            {
                printf("下一步应该出");
                printVector(push_a);
            }
            
            
            return true;
        }
    }
    
    return false;
}


int main(int argc, const char * argv[]) {
    vector<int> a = {King_Big,7,6,5,4,3,3,3,3};
    vector<int> b = {King_Small,8,8,8,8,7,6,5,4};
    //vector<int> a = {1, 3,4,5,6,7};
    //vector<int> b = {4,4,5,5};
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    //vector<int> a = {5,4,3,3};
    
//    printf("------a---------\n");
//    auto va = getAllPushMethod(a);
//    printf("------b---------\n");
//    auto vb = getAllPushMethod(b);
    
    vector<int> startPush;
    vector<vector<int>> solution;
    auto s = canSolove(a,b,startPush, 0, solution);
    printf(" ---输出结果----");
    if(s)
    {
        printf("有解决方案\n");
    }
    else
    {
        printf("没有解决方案\n");
    }
    
    return 0;
}