Skip to content

Instantly share code, notes, and snippets.

@tanakh
Last active October 2, 2015 14:11
Show Gist options
  • Save tanakh/19861afedde1a8365a45 to your computer and use it in GitHub Desktop.
Save tanakh/19861afedde1a8365a45 to your computer and use it in GitHub Desktop.
TMCTF Programming 500
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
using namespace std;
int size = 3;
string start, goal;
set<string> expand(const set<string> &ss)
{
set<string> ret;
for (auto cur: ss) {
int pix = 0;
for (int i = 0; i < cur.size(); i++) {
if (cur[i] == goal[0]) {
pix = i;
break;
}
}
int r1 = pix / size;
int c1 = pix % size;
int r2 = r1 ^ 1;
for (int dc = -1; dc <= 1; dc++) {
int c2 = c1 + dc;
if (!(c2 >= 0 && c2 <size))
continue;
swap(cur[r1 * size + c1], cur[r2 * size + c2]);
ret.insert(cur);
swap(cur[r1 * size + c1], cur[r2 * size + c2]);
}
}
return ret;
}
void init()
{
for (int i = 0; i < size * 2; i++)
start += (char)('A' + i);
goal = start;
swap(goal[0], goal[goal.size()-1]);
cout << start << ", " << goal << endl;
}
bool has_common(const set<string> &a, const set<string> &b)
{
auto p = a.begin();
auto q = b.begin();
while (p != a.end() && q != b.end()) {
if (*p == *q) return true;
if (*p < *q) p++;
else q++;
}
return false;
}
int calc_dist(const string &s, const string &g)
{
set<string> fron_a, fron_b;
fron_a.insert(s);
fron_b.insert(g);
for (int i = 0; ; i++) {
cout << "depth: " << i * 2 << "\r" << flush;
if (has_common(fron_a, fron_b)) {
cout << endl;
return i * 2;
}
fron_a = expand(fron_a);
cout << "depth: " << i * 2 + 1 << "\r" << flush;
if (has_common(fron_a, fron_b)) {
cout << endl;
return i * 2 + 1;
}
fron_b = expand(fron_b);
}
abort();
}
int main(int argc, char *argv[])
{
size = atoi(argv[1]);
init();
auto cur = start;
string ans;
for (;;) {
cout << "*** " << cur << endl;
int pix = 0;
for (int i = 0; i < cur.size(); i++) {
if (cur[i] == goal[0]) {
pix = i;
break;
}
}
int best = 999;
string best_n;
int best_t = 0;
int r1 = pix / size;
int c1 = pix % size;
int r2 = r1 ^ 1;
for (int dc = -1; dc <= 1; dc++) {
int c2 = c1 + dc;
if (!(c2 >= 0 && c2 <size))
continue;
swap(cur[r1 * size + c1], cur[r2 * size + c2]);
int dist = calc_dist(cur, goal);
if (dist < best || (dist == best && r2 * size + c2 < best_t)) {
best = dist;
best_n = cur;
best_t = r2 * size + c2;
}
swap(cur[r1 * size + c1], cur[r2 * size + c2]);
}
ans += (char)('A' + best_t);
cur = best_n;
if (best == 0)
break;
}
cur = start;
cout << cur << endl;
for (auto &c: ans) {
int pos1 = c - 'A';
int pos2 = 0;
for (int i = 0; i < cur.size(); i++) {
if (cur[i] == goal[0]) {
pos2 = i;
break;
}
}
swap(cur[pos1], cur[pos2]);
cout << cur << endl;
}
cout << ans << endl;
return 0;
}
#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <unordered_map>
using namespace std;
inline int hand(int p, int s)
{
if (p + s <= 21) return p + s;
return p;
}
double calc(int p, int d, int s, int total, vector<int> &yama)
{
if (d > 21) return 1;
int ds = hand(d, s);
if (ds >= 17) return ds < p ? 1 : 0;
double ret = 0;
for (int i = 1; i <= 13; i++) {
if (yama[i-1] == 0) continue;
int nd = d, ns = s;
if (i == 1) {
nd += 1;
ns = 10;
}
else {
nd += min(i, 10);
}
double prod = (double)yama[i-1] / total;
yama[i-1]--;
ret += prod * calc(p, nd, ns, total - 1, yama);
yama[i-1]++;
}
return ret;
}
double solve(int p, int s, int total, vector<int> &yama)
{
if (p > 21) return 0;
double ret = calc(hand(p, s), 3, 0, total, yama);
double hit = 0;
for (int i = 1; i <= 13; i++) {
if (yama[i-1] == 0) continue;
int np = p, ns = s;
if (i == 1) {
np += 1;
ns = 10;
}
else {
np += min(i, 10);
}
double prod = (double)yama[i-1] / total;
yama[i-1]--;
hit += prod * solve(np, ns, total - 1, yama);
yama[i-1]++;
}
return max(ret, hit);
}
int main(int argc, char *argv[])
{
vector<int> yama(13, 8);
yama[0]--;
yama[1]--;
yama[2]--;
int total = 13 * 8 - 3;
cout << fixed << setprecision(4);
cout << "TMCTF{HIT:" << solve(3, 10, total, yama) << ":STAND:" << calc(13, 3, 0, total, yama) << "}" << endl;
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment