Instance.h
#pragma once
#include <algorithm>
#include <cassert>
#include <cmath>
#include <fstream>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <vector>
using namespace std;
const string OUTPATH = "../output/";
const string MSPATH = "makespan/";
const string DISTPATH = "distance/";
const string INPATH = "../input/";
const string EXT = ".in";
const string OUTEXT = ".out";
string remove_ext(string s) {
size_t last_slash = s.find_last_of("/");
if (last_slash != string::npos)
s = s.substr(last_slash + 1);
size_t last_dot = s.find_last_of(".");
if (last_dot == string::npos)
return s;
return s.substr(0, last_dot);
}
string out_file_full(string name, bool makespan) {
return OUTPATH + (makespan ? MSPATH : DISTPATH) + name + OUTEXT;
}
const int INF = 0x3f3f3f3f;
struct pt {
pt() : x(0), y(0) {}
pt(int x, int y) : x(x), y(y) {}
int x, y;
pt operator+(const pt& oth) const { return pt(x + oth.x, y + oth.y); }
pt operator-(const pt& oth) const { return pt(x - oth.x, y - oth.y); }
bool operator==(const pt& oth) const {
return tie(x, y) == tie(oth.x, oth.y);
}
bool operator!=(const pt& oth) const {
return tie(x, y) != tie(oth.x, oth.y);
}
bool operator<(const pt& oth) const { return tie(x, y) < tie(oth.x, oth.y); }
};
int abs(const pt& p) { return abs(p.x) + abs(p.y); }
int dist(const pt& a, const pt& b) { return abs(a - b); }
long long dot(const pt& a, const pt& b) { return a.x * b.x + a.y * b.y; }
double norm(const pt& a) { return sqrt(dot(a, a)); }
ostream& operator<<(ostream& stream, const pt& p) {
stream << "(" << p.x << ", " << p.y << ")";
return stream;
}
// Move encoding
// 0: Stand still
// 1: North
// 2: East
// 3: South
// 4: West
const int dx[] = {0, 0, 1, 0, -1, 1, -1, 1, -1};
const int dy[] = {0, 1, 0, -1, 0, 1, -1, -1, 1};
const pt dxy[] = {pt(0, 0), pt(0, 1), pt(1, 0), pt(0, -1), pt(-1, 0),
pt(1, 1), pt(-1, -1), pt(1, -1), pt(-1, 1)};
const vector<string> dirnames = {"", "N", "E", "S", "W"};
const int opposite_dir[] = {0, 3, 4, 1, 2};
namespace std {
template <> struct hash<pt> {
size_t operator()(const pt& p) const { return (p.x << 9) + p.y; }
};
template <> struct hash<pair<pt, int>> {
size_t operator()(const pair<pt, int>& p) const {
return hash<pt>()(p.first) ^ (hash<int>()(p.second) << 1);
}
};
} // namespace std
struct instance;
bool verify(instance& ins);
bool improvement(instance& ins, bool makespan);
bool improvement_custom(instance& ins, string full_filename, bool makespan);
struct instance {
string name;
int n, m; // n is the number of robots, m obstacles
int time;
vector<pt> start;
vector<pt> target;
vector<pt> obstacle;
vector<vector<int>> moves; // list of simultaneous moves (not sparse)
// big score is bad
// TODO we don't actually use this
long double score;
bool operator<(const instance& other) const { return score > other.score; }
bool done(int i) { return abs(start[i] - target[i]) == 0; }
bool done() {
for (int i = 0; i < n; i++)
if (!done(i))
return false;
return true;
}
void clear() {
name = "";
n = m = 0;
time = 0;
score = 0;
start.clear();
target.clear();
obstacle.clear();
moves.clear();
}
instance sub_instance(const vector<size_t>& sub_robots) {
instance ret;
ret.clear();
ret.m = m;
ret.obstacle = obstacle;
ret.time = time;
ret.n = sub_robots.size();
for (int i = 0; i < ret.n; ++i) {
ret.start.push_back(start[sub_robots[i]]);
ret.target.push_back(target[sub_robots[i]]);
}
ret.moves.resize(ret.time);
for (int t = 0; t < ret.time; ++t)
for (size_t i = 0; i < sub_robots.size(); ++i)
ret.moves[t].push_back(moves[t][sub_robots[i]]);
return ret;
}
void merge_sub_instance(const instance& sub,
const vector<size_t>& sub_robots) {
time = max(time, sub.time);
while (moves.size() < size_t(time))
moves.emplace_back(n);
for (int t = 0; t < sub.time; ++t)
for (size_t i = 0; i < sub_robots.size(); ++i)
moves[t][sub_robots[i]] = sub.moves[t][i];
for (int t = sub.time; t < time; ++t)
for (size_t i = 0; i < sub_robots.size(); ++i)
moves[t][sub_robots[i]] = 0;
}
void read(string filename) { // clear instance and read new instance
clear();
filename = remove_ext(filename);
name = filename;
string filepath = INPATH + filename + EXT;
// cerr << "READING FILE " << filepath << endl;
ifstream in(filepath);
in >> n >> m;
for (int i = 0; i < n; i++) {
int x, y;
in >> x >> y;
start.emplace_back(x, y);
}
for (int i = 0; i < n; i++) {
int x, y;
in >> x >> y;
target.emplace_back(x, y);
}
for (int i = 0; i < m; i++) {
int x, y;
in >> x >> y;
obstacle.emplace_back(x, y);
}
}
void read_custom(string fullpath) {
ifstream in(fullpath);
string in_name;
in >> in_name;
read(in_name);
int idump;
in >> idump;
in >> time;
moves = vector<vector<int>>(time, vector<int>(n));
for (auto& vi : moves)
for (auto& i : vi)
in >> i;
}
string out_file(bool makespan) { return out_file_full(name, makespan); }
void read_out(bool makespan) { // read moves and time
ifstream in(out_file(makespan));
// dump extra info, and get time
string dump;
in >> dump;
int idump;
in >> idump;
in >> time;
moves = vector<vector<int>>(time, vector<int>(n));
for (auto& vi : moves)
for (auto& i : vi)
in >> i;
}
void write_input(string filename) {
// Re-outputs the input string
// Only really used for converting json
ofstream out(INPATH + filename + EXT);
// cout << "writing to " << INPATH << filename << EXT << endl;
out << n << ' ' << m << '\n';
for (const auto& p : start)
out << p.x << ' ' << p.y << '\n';
for (const auto& p : target)
out << p.x << ' ' << p.y << '\n';
for (const auto& p : obstacle)
out << p.x << ' ' << p.y << '\n';
}
void write_mapf(string filename) {
const string MAPF_OUTPATH = "../mapf_input/";
const string MAPF_MAP_EXT = ".map";
const string MAPF_AGENT_EXT = ".agent";
const int GAP = 2;
string map_filepath = MAPF_OUTPATH + filename + MAPF_MAP_EXT;
string agents_filepath = MAPF_OUTPATH + filename + MAPF_AGENT_EXT;
ofstream mapout(map_filepath);
ofstream agentout(agents_filepath);
cerr << "writing to " << map_filepath << " and " << agents_filepath << endl;
// compute map for mapf
pt mx(-1, -1);
string blank(120, '.');
vector<string> g(120, blank);
for (auto& p : obstacle) {
g[p.x + GAP][p.y + GAP] = '@';
mx.x = max(mx.x, p.x);
mx.y = max(mx.y, p.y);
}
for (auto& p : start) {
mx.x = max(mx.x, p.x);
mx.y = max(mx.y, p.y);
}
for (auto& p : target) {
mx.x = max(mx.x, p.x);
mx.y = max(mx.y, p.y);
}
mx.x += 2 * GAP;
mx.y += 2 * GAP;
mapout << mx.x << ',' << mx.y << '\n';
while ((int)g.size() > mx.y) {
g.pop_back();
}
for (auto& s : g) {
s.resize(mx.x);
mapout << s << '\n';
}
agentout << n << '\n';
for (int i = 0; i < n; i++) {
agentout << start[i].x + GAP << ',' << start[i].y + GAP << ',';
agentout << target[i].x + GAP << ',' << target[i].y + GAP << '\n';
}
}
void complete_write(bool makespan) {
string out_f = out_file(makespan);
// cout << "writing to " << out_f << endl;
ofstream out(out_f);
out << name << '\n'; // also include the instance name for convenience
out << n << '\n'; // also include the value of n for convenience
out << time << '\n';
for (const auto& v : moves) {
for (int i = 0; i < n; i++) {
out << v[i] << " ";
}
out << '\n';
}
}
void write() {
// TODO: add code that overwrites only new solution is better
// (and have two output directories)
if (!verify(*this)) {
cerr << "Verification failed! Not writing file." << endl;
return;
}
vector<bool> vals = {false, true};
for (bool makespan : vals)
if (improvement(*this, makespan)) {
/*
cout << "writing improvement in "
<< (makespan ? "makespan" : "distance") << "!" << endl; */
complete_write(makespan);
}
}
void debug_write(string full_filename) {
ofstream out(full_filename);
out << name << '\n';
out << n << '\n';
out << time << '\n';
for (const auto& v : moves) {
for (int i = 0; i < n; i++) {
out << v[i] << " ";
}
out << '\n';
}
}
void improve_only_debug_write(string full_filename, bool makespan) {
if (!verify(*this)) {
cerr << "Verification failed! Not writing file." << endl;
return;
}
if (improvement_custom(*this, full_filename, makespan)) {
cerr << "It's a (debug) improvement (" << full_filename << ")!" << endl;
debug_write(full_filename);
}
}
};
void slowdown(instance& ins, int slow) {
vector<vector<int>> m2;
vector<int> zeroes(ins.n);
for (auto v : ins.moves) {
m2.push_back(v);
for (int i = 0; i < slow; i++)
m2.push_back(zeroes);
}
ins.time = m2.size();
ins.moves = m2;
}
// the reverse problem (and solution)
void reverse_instance(instance& ins) {
ins.start.swap(ins.target);
reverse(ins.moves.begin(), ins.moves.end());
for (auto& v : ins.moves) {
for (int& d : v) {
d = opposite_dir[d];
}
}
}
vector<vector<int>> combine_movesets(const instance& ins1,
const instance& ins2) {
assert(ins1.n == ins2.n);
assert(ins1.m == ins2.m);
assert(ins1.target == ins2.start);
vector<vector<int>> moves = ins1.moves;
for (auto& vi : ins2.moves)
moves.push_back(vi);
return moves;
}
bool verify(instance& ins) {
if (ins.time != int(ins.moves.size()))
return false;
vector<pt> locations = ins.start;
set<pt> obstacle_s;
for (pt& p : ins.obstacle) {
obstacle_s.insert(p);
}
int t = 0;
for (auto& step : ins.moves) {
map<pt, int> dir_from_loc;
for (int i = 0; i < ins.n; ++i) {
dir_from_loc[locations[i]] = step[i];
}
for (int i = 0; i < ins.n; ++i) {
pt p = locations[i] + dxy[step[i]];
// determine if move is a collision
if (obstacle_s.count(p) > 0 ||
(dir_from_loc.count(p) > 0 && dir_from_loc[p] != step[i])) {
cout << "failed on timestep t=" << t << endl;
return false;
}
// move if it's not (doesn't affect later loop checks)
locations[i] = p;
}
++t;
}
return locations == ins.target;
}
// lower score is better
int score(instance& ins, bool makespan) {
if (!verify(ins))
return INF;
assert(ins.time == int(ins.moves.size()));
if (makespan)
return ins.time;
int distance = 0;
for (auto& step : ins.moves) {
for (int i = 0; i < ins.n; ++i) {
if (step[i] != 0)
++distance;
}
}
return distance;
}
double average_makespan(instance& ins) {
vector<int> counter(ins.n);
double ms = 0;
for (auto& step : ins.moves) {
for (int i = 0; i < ins.n; i++) {
if (step[i]) {
ms += 1 + counter[i];
counter[i] = 0;
} else {
counter[i]++;
}
}
}
return ms / ins.n;
}
double squared_makespan_sum(instance& ins) {
double ms = 0;
for (int i = 0; i < ins.n; i++) {
double cur = 0;
int counter = 0;
for (size_t s = 0; s < ins.moves.size(); ++s) {
if (ins.moves[s][i]) {
cur += 1 + counter;
counter = 0;
} else {
counter++;
}
}
ms += cur * cur;
}
return ms;
}
bool improvement(instance& ins, bool makespan) {
instance dupe = ins; // copy most info from ins
// dupe.read(ins.name);
// cout << "out_file_full=" << out_file_full(ins.name, makespan) << endl;
dupe.read_out(makespan);
int old_score = score(dupe, makespan);
int new_score = score(ins, makespan);
/*
cout << "makespan=" << (makespan ? "true" : "false")
<< ", old score=" << old_score << ", new score=" << new_score << endl;*/
if (old_score == new_score) {
// Break ties by average makespan
if (squared_makespan_sum(ins) < squared_makespan_sum(dupe)) {
return true;
}
}
return new_score < old_score;
}
bool improvement_custom(instance& ins, string full_filename, bool makespan) {
instance dupe; // copy most info from ins
// dupe.read(ins.name);
// cout << "out_file_full=" << out_file_full(ins.name, makespan) << endl;
dupe.read_custom(full_filename);
if (ins.n != dupe.n)
return false;
int old_score = score(dupe, makespan);
int new_score = score(ins, makespan);
/*
cout << "makespan=" << (makespan ? "true" : "false")
<< ", old score=" << old_score << ", new score=" << new_score << endl;*/
if (old_score == new_score) {
// Break ties by average makespan
if (squared_makespan_sum(ins) < squared_makespan_sum(dupe)) {
return true;
}
}
return new_score < old_score;
}