Created
February 6, 2013 16:12
-
-
Save wistery-k/4723644 to your computer and use it in GitHub Desktop.
shanten sample code 1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <fstream> | |
#include <vector> | |
#include <map> | |
#include <algorithm> | |
#include <chrono> | |
#define rep(i, n) for(int i = 0; i < n; i++) | |
#define all(v) (v).begin(), (v).end() | |
using namespace std; | |
map<int, vector<pair<int, int> > > shanten_tbl; | |
void shanten_init() { | |
ifstream f("shanten.txt"); | |
int n; | |
f >> n; | |
int key, v; | |
rep(i, n) { | |
f >> key >> v; | |
shanten_tbl[key] = vector<pair<int, int> >({ | |
make_pair(v/1000%10, v/100%10), make_pair(v/10%10, v%10) | |
}); | |
} | |
shanten_tbl[0] = vector<pair<int, int> >({ make_pair(0, 0), make_pair(0, 0) }); | |
} | |
int pick_menta(int tehai_[40], int need_mentsu) { | |
vector<vector<pair<int, int> > > mts(3); | |
int tehai[40]; | |
rep(i, 40) tehai[i] = tehai_[i]; | |
rep(i, 3) { // 各スートについて | |
// 孤立牌を除去 | |
for(int j = 1; j <= 9; j++) { | |
bool is_koritsu = | |
(j - 2 < 1 || tehai[i * 10 + j - 2] == 0) && | |
(j - 1 < 1 || tehai[i * 10 + j - 1] == 0) && | |
(j + 1 > 9 || tehai[i * 10 + j + 1] == 0) && | |
(j + 2 > 9 || tehai[i * 10 + j + 2] == 0) && | |
(tehai[i * 10 + j] == 1); | |
if(is_koritsu) { | |
tehai[i * 10 + j] = 0; | |
} | |
} | |
int hash = 0; | |
for(int j = 1; j <= 9; j++) { | |
hash = hash * 10 + tehai[i * 10 + j]; | |
} | |
mts[i] = shanten_tbl[hash]; | |
} | |
int m_jihai = count_if(tehai + 31, tehai + 40, [](int x){ return x >= 3; }); | |
int t_jihai = count_if(tehai + 31, tehai + 40, [](int x){ return x == 2; }); | |
int ans = 1 << 27; | |
rep(i, 1 << 3) { | |
int m = m_jihai; | |
int t = t_jihai; | |
rep(j, 3) { | |
pair<int, int> mt = mts[j][(i >> j) & 1]; | |
m += mt.first; | |
t += mt.second; | |
} | |
t = min(t, need_mentsu - m); | |
ans = min(ans, 8 - 2 * m - t); | |
} | |
return ans; | |
} | |
int normal_shanten(int tehai[40], int need_mentsu) { | |
int ans = 30; | |
rep(i, 40) { | |
if(tehai[i] >= 2) { | |
tehai[i] -= 2; | |
ans = min(ans, pick_menta(tehai, need_mentsu) - 1); | |
tehai[i] += 2; | |
} | |
} | |
return min(ans, pick_menta(tehai, need_mentsu)) - (4 - need_mentsu) * 2; | |
} | |
int kokushi_shanten(int tehai[40]) { | |
vector<int> yaochu = {1, 9, 11, 19, 21, 29, 31, 32, 33, 34, 35, 36, 37 }; | |
int kind = count_if(all(yaochu), [&](int x){ return tehai[x] >= 1; }); | |
return 13 - (kind + any_of(all(yaochu), [&](int x){ return tehai[x] >= 2; })); | |
} | |
int chitoi_shanten(int tehai[40]) { | |
int toitsu = count_if(tehai, tehai + 40, [](int x){ return x >= 2; }); | |
int kind = count_if(tehai, tehai + 40, [](int x){ return x >= 1; }); | |
return 6 - toitsu + max(7 - kind, 0); | |
} | |
using namespace chrono; | |
int transform34to38[] = { | |
1, 2, 3, 4, 5, 6, 7, 8, 9, | |
11, 12, 13, 14, 15, 16, 17, 18, 19, | |
21, 22, 23, 24, 25, 26, 27, 28, 29, | |
31, 32, 33, 34, 35, 36, 37 | |
}; | |
int tehai[50005][40]; | |
int main() { | |
shanten_init(); | |
int n, tmp; | |
cin >> n; | |
rep(i, n) { | |
rep(j, 14) { | |
cin >> tmp; | |
tehai[i][transform34to38[tmp]]++; | |
} | |
} | |
auto start = system_clock::now(); | |
rep(i, n) { | |
#if 1 | |
cout << normal_shanten(tehai[i], 4) << " " << kokushi_shanten(tehai[i]) << " " << chitoi_shanten(tehai[i]) << endl; | |
#else | |
normal_shanten(tehai[i], 4); | |
kokushi_shanten(tehai[i]); | |
chitoi_shanten(tehai[i]); | |
#endif | |
} | |
cerr << duration_cast<milliseconds>(system_clock::now() - start).count() << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment