CodeRunner 2015 QualA

main.cpp

#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <complex>
#include <stdlib.h>
#include <unistd.h>
#include <math.h>
using namespace std;

typedef complex<double> pt;

// JC4RK6V15BQIZIT2QBSDN16DF21Z2VWR

// https://game.coderunner.jp/query?token=[your_token]&v=0,1

// https://game.coderunner.jp/query?token=JC4RK6V15BQIZIT2QBSDN16DF21Z2VWR&v=0,1

int submit(const vector<pair<int,int>> &pts)
{
    stringstream ss;
    ss << "curl -s 'https://game.coderunner.jp/query?token=JC4RK6V15BQIZIT2QBSDN16DF21Z2VWR&v=";
    sleep(1);

    stringstream tt;

    for (int i = 0; i < (int)pts.size(); i++) {
        if (i > 0) tt << ",";
        tt << pts[i].first << "," << pts[i].second;
    }

    ss << tt.str() << "' > tmp";
    int ec = system(ss.str().c_str());

    if (ec != 0)
        return -1;

    int sc = -1;
    {
        ifstream ifs("tmp");
        ifs >> sc;
    }

    {
        ofstream ofs("record", ios::app);
        ofs << tt.str() << ":" << sc << endl;
    }

    return sc;
}

#define EPS (1e-10)
#define EQ(a,b) (abs((a)-(b)) < EPS)

inline double dot(const pt &a, const pt &b) {
  return (a.real() * b.real() + a.imag() * b.imag());
}

inline double cross(const pt &a, const pt &b) {
  return (a.real() * b.imag() - a.imag() * b.real());
}

inline double distance_ls_p(const pt &a, const pt &b, const pt &c) {
  if ( dot(b-a, c-a) < EPS ) return abs(c-a);
  if ( dot(a-b, c-b) < EPS ) return abs(c-b);
  return abs(cross(b-a, c-a)) / abs(b-a);
}

int is_intersected_ls(const pt &a1, const pt &a2, const pt &b1, const pt &b2) {
  return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
         ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}

inline pt intersection_ls(const pt &a1, const pt &a2, const pt &b1, const pt &b2) {
  pt b = b2-b1;
  double d1 = abs(cross(b, a1-b1));
  double d2 = abs(cross(b, a2-b1));
  double t = d1 / (d1 + d2);

  return a1 + (a2-a1) * t;
}

bool is_cross(const pt &a, const pt &b, const pt &c, const pt &d)
{
    if (is_intersected_ls(a, b, c, d)) {
        return true;
    }

    if (distance_ls_p(a, b, c) < 0.5) {
        return true;
    }

    if (distance_ls_p(a, b, d) < 0.5) {
        return true;
    }

    return false;
}

bool check(const vector<pt> &pts, vector<pair<int, int>> &ixs, int cix)
{
    for (int i = 0; i < (int)ixs.size(); i++) {
        if (i == cix) continue;

        if (ixs[i].first == ixs[cix].first) return false;
        if (ixs[i].first == ixs[cix].second) return false;
        if (ixs[i].second == ixs[cix].first) return false;
        if (ixs[i].second == ixs[cix].second) return false;

        if (is_cross(pts[ixs[i].first],
                     pts[ixs[i].second],
                     pts[ixs[cix].first],
                     pts[ixs[cix].second]
                     )) {
            // ofstream ofs("cross.ps");

            // for (auto &ix: ixs) {
            //     ofs << pts[ix.first].real() << " " << pts[ix.first].imag() << endl;
            //     ofs << pts[ix.second].real() << " " << pts[ix.second].imag() << endl;
            //     ofs << endl;
            // }

            // throw runtime_error("hoge");

            return false;
        }
    }
    return true;
}

double local_calc(const vector<pt> &pts, vector<pair<int, int>> &ixs)
{
    double ret = 0;
    for (auto &pa: ixs)
        ret += abs(pts[pa.first] - pts[pa.second]);
    return ret;
}

bool check(const vector<pair<int,int>> &v)
{
    map<int, int> ss;
    for (auto &it: v) {
        ss[it.first]++;
        ss[it.second]++;
    }

    for (auto &kv: ss)
        if (kv.second > 1)
            return false;

    return true;
}

vector<pair<int,int>> load()
{
    ifstream ifs("record");

    int best = 0;
    vector<pair<int,int>> v;
    for (string line; getline(ifs, line); ) {
        istringstream iss(line);
        vector<pair<int,int>> pp;
        for (; ; ) {
            int a, b;
            char c;
            iss >> a >> c >> b >> c;
            pp.emplace_back(a, b);

            if (c == ':') break;
        }
        int sc = -1;
        iss >> sc;

        if (sc > best) {
            best = sc;
            v = pp;
        }
    }

    cout << "Starting from: " << best << endl;

    return v;
}

double calc_score(const vector<pair<int,int>> &pts, double sc)
{
    return sc - pts.size() * 50;
}

void inspect()
{
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 1000; j++) {
            vector<pair<int,int>> pts{{i, j}};
            int sc = submit(pts);

            cout << i << " " << j << " " << sc << endl;
        }
    }
    exit(0);
}

pt calc_pos(const pt &a, double da,
            const pt &b, double db,
            const pt &c, double dc)
{
    pt r {1000, 1000};

    double decay = 0.1;
    for (int i = 0; i < 50000; i++) {
        double far = 0;
        pt tar;

        {
            pt t = r - a;
            double d = da - abs(t);
            if (abs(d) > abs(far)) {
                far = d;
                tar = a;
            }
        }
        {
            pt t = r - b;
            double d = db - abs(t);
            if (abs(d) > abs(far)) {
                far = d;
                tar = b;
            }
        }
        {
            pt t = r - c;
            double d = dc - abs(t);
            if (abs(d) > abs(far)) {
                far = d;
                tar = c;
            }
        }

        if (far > 0)
            r -= (tar - r) * decay;
        else
            r += (tar - r) * decay;
        decay *= 0.999;
    }

    // cout << abs(r - a) - da << ", "
    //      << abs(r - b) - db << ", "
    //      << abs(r - c) - dc << endl;

    return r; //(round(r.real()), round(r.imag()));

    /*
    double near = 1e10;
    pt p;
    for (int x = -250; x <= 250; x++) {
        for (int y = -250; y <= 250; y++) {
            pt q(x, y);
            double d =
                abs(abs(q - a) - da) +
                abs(abs(q - b) - db) +
                abs(abs(q - c) - dc);

            if (d < near) {
                near = d;
                p = q;
            }
        }
    }

    return p;
    */
}

vector<pt> load_pts()
{
    ifstream ifs("data");

    map<pair<int,int>, double> dist;

    for (int a, b, c; ifs >> a >> b >> c; ) {
        if (c < 0) {
            cout << a << ", " << b << ", " << c << endl;
            throw runtime_error("hoge");
        }

        dist[make_pair(a, b)] = c;
    }

    pt p0 {0, 0};
    pt p1 {dist[make_pair(0, 1)], 0};
    pt p2 = calc_pos(p0, dist[make_pair(0, 2)], p0, dist[make_pair(0, 2)], p1, dist[make_pair(1, 2)]);

    vector<pt> pts;
    pts.push_back(p0);
    pts.push_back(p1);
    pts.push_back(p2);

    for (int i = 3; i < 1000; i++) {
        pts.push_back(calc_pos(p0, dist[make_pair(0, i)], p1, dist[make_pair(1, i)], p2, dist[make_pair(2, i)]));
    }

    // for (auto &p: pts)
    //     cout << p << endl;

    return pts;
}

vector<pt> test_pts()
{
    vector<pt> ret;
    for (int i = 0; i < 1000; i++) {
        pt p(rand() % 200, rand() % 200);
        ret.push_back(p);
    }
    return ret;
}

int main()
{
    auto dat = load_pts();
    // auto dat = test_pts();

    {
        ofstream ofs("plot.dat");
        for (auto &p: dat)
            ofs << p.real() << " " << p.imag() << endl;
    }

    vector<pair<int,int>> pts;
    double best_score = 0;
    double prev = best_score;

    int turn = 0;
    for (double temp = 250; ; temp *= 0.999999999, turn++) {
        if (turn % 1000000 == 0)
            cout << temp << endl;

        auto bak = pts;

        int op = rand() % 4;

        if (op == 0) {
            if (pts.size() == 0) continue;

            int ix = rand() % pts.size();
            pts.erase(pts.begin() + ix);
        }
        else if (op == 1) {
            if (pts.size() == 0) continue;

            int ix = rand() % pts.size();

            auto bak = pts[ix];
            pts[ix].first = rand() % 1000;
            pts[ix].second = rand() % 1000;

            if (!check(dat, pts, ix)) {
                pts[ix] = bak;
                continue;
            }
        }
        else if (op == 2) {
            int i = rand() % 1000;
            int j = rand() % 1000;

            pts.emplace_back(i, j);

            if (!check(dat, pts, pts.size() - 1)) {
                pts.pop_back();
                continue;
            }
        }
        else if (op == 3) {
            if (pts.size() < 2) continue;

            int i = rand() % pts.size();
            int j = rand() % pts.size();

            if (i == j) continue;

            swap(pts[i].first, pts[j].first);

            if (!check(dat, pts, i) ||
                !check(dat, pts, j)) {
                swap(pts[i].first, pts[j].first);
                continue;
            }
        }

        double score = local_calc(dat, pts);

        if (score >= 0 && (score >= prev || (rand() % 10000) / 10000.0 < exp( (double)(score - prev) / temp))) {
            if (score > best_score) {
                best_score = score;
                cout << "best: " << best_score << ", " << pts.size() << " @" << temp << endl;

                // for (auto &i: pts) cout << dat[i.first] << " - " << dat[i.second] << ", ";
                // cout << endl;
                {
                    ofstream ofs("best.ps");
                    for (auto &i: pts) {
                        ofs << dat[i.first].real() << " " << dat[i.first].imag() << endl;
                        ofs << dat[i.second].real() << " " << dat[i.second].imag() << endl;
                        ofs << endl;
                    }
                }

                // if (score >= 8000) {
                //     int ss = submit(pts);
                //     cout << "SUMBIT: " << ss << " (" << score << ")" << endl;
                // }
            }
            prev = score;
        }
        else {
            pts = bak;
        }
    }

    return 0;
}

/*
int main()
{
    inspect();

    srand(time(NULL));

    vector<pair<int,int>> pts = load();

    double best_score = submit(pts);

    best_score = calc_score(pts, best_score);

    double prev = best_score;

    cout << "*** " << best_score << endl;

    double temp = 25;

    for (; ; temp *= 0.995) {
        cout << "temp: " << temp << ", " << pts.size() << endl;

        auto bak = pts;

        int op = rand() % 3;

        if (op == 0) {
            if (pts.size() == 0) continue;

            int ix = rand() % pts.size();
            pts.erase(pts.begin() + ix);
        }
        else if (op == 1) {
            if (pts.size() == 0) continue;

            int ix = rand() % pts.size();

            pts[ix].first = rand() % 1000;
            pts[ix].second = rand() % 1000;
        }
        else {
            int i = rand() % 1000;
            int j = rand() % 1000;

            pts.emplace_back(i, j);
        }

        if (!check(pts)) {
            pts = bak;
            continue;
        }

        double score = submit(pts);
        cout << "score: " << score << ", avg: " << (double)score / pts.size() << endl;

        score = calc_score(pts, score);

        if (score > 0 && (score >= prev || (rand() % 10000) / 10000.0 < exp( (double)(score - prev) / temp))) {
            cout << "*** upd: " << op << endl;
            best_score = score;
            prev = score;
        }
        else {
            cout << "ng: " << op << endl;
            pts = bak;
        }
    }

    return 0;
}
*/