// Thanks, Fred, for this great contest ! //--------------------------------------------------------------------------- // POTM ENTRY: Yalta // Our Name: Pavel Ouvarov & Frederic van der Plancke // Our email: pavel@pcbecb.ihep.su // Your Name: Fred Hicinbothem // Your email: hicinbothem@att.com //--------------------------------------------------------------------------- // usage: "yalta x1 y1 x2 y2" // if macro 'TEST_CONSOLE' is defined there is an alternative usage: // "yalta vvv x1 y1 x2 y2" // where 'vvv' is any number of characters v; this will force verbose // output. (Three 'v' seems to be the best) //--------------------------------------------------------------------------- #define POTM_ENTRY //--------------------------------------------------------------------------- #define Y_VERSION "yalta20x" // Recent history (from version y14 on, main changes): // '**' marks versions sent as entries to Fred A H. // Y14d: get_polygon_areas() got its final form: middle_area is // now directly computed from max_area and min_area and no // more from some vmExp-directed smoothing of it. //** Y14h: several optimisations (inlining of some computations) // Y14z: YPolygon::points is now a c-style array, no more a std::vector. // Y15: PROBA was set to 80. MAX_EXP at the beginning to 4 and // N_RANDOM_TRYS to 20. Speed is 1.5 - 2.5 times faster now... // An inner rand() was written. It didn't improve speed on my // computer but may be on Fred's... Polygon::get_area () was // rewritten. // Y15b rewrote get_area again ;-) // Y15f: replaced 'typedef long double Scalar' by 'typedef double Scalar' // speedup estimated 25x to 100x - Fred's hardware suspected ;-) // Y15g-Y15j: miscellaneous optimisations by inlining. // Y15L: removed n_polygon comparison from beaten_best_score. // Y16,Y17,Y18: cleaned up dead code and comments we don't want // published ;-) // Y20: new overall_main. In second phase the few more promising // patterns are all tuned. // Y20b: introduced minimal improvement TUNING_EPS // otherwise we get stuck in (almost) infinite loops due to // equivalent situations getting different scores - and Yalta // thinks he's improving the score when the score actually stays // equal. //** Y20e: OUR FINAL ENTRY // the program stops when all current patterns have reached their // best possible integer score. // Y20x: "cleaned-up" version for publication. // The only modification that is meant to impact on the compiled // program is the added clean-up of MainSystems at the very end of // overall_main. This fixes a memory leak without changing the // output. //--------------------------------------------------------------------------- //-- general constants -- #define NUM_POTM_LINES 10 #define MAX_POLYGONS 68 #define WIDTH 100 #define AREA Scalar(WIDTH*WIDTH) const int TRIVIAL_SCORE = 277; // TRIVIAL_SCORE: // score that can always be achieved by using the default solution (Build277) //-- algorithm settings -- #define FOUR_LINES #define START_EXP 2 #define EXP_UPDATE ((vmExp + 1)) // how the exp updates #define PROBA 80 #define TUNING_EPS (1E-7) // minimum score difference that is considered an improvement //-- variable algorithm settings -- int MAX_EXP = 4; int MAX_SHAKE_COUNT = 0; // how many times to shake when //stuck at a given exp int N_RANDOM_TRYS = 20; // this should not be set too big since no time // checking is done inside that loop //--------------------------------------------------------------------------- // Compiler- or environment- specific stuff. // Borland: this program compiles (at least) with C++ Builder 1.0 // Microsoft Visual C++ ? #ifdef _MSC_VER // Microsoft template instanciation policy requires some operators to // be defined even though we don't actually use them... so: #define MSCVER_PSEUDO(CLASS, OP) \ inline bool operator OP (const CLASS &, const CLASS &) \ { return false; } #else #define MSCVER_PSEUDO(CLASS, OP) #endif //--------------------------------------------------------------------------- #include #include #include #include #include #include // for std::sort #include "stdlib.h" // for memcpy - talk of C++ programming ;-) //--------------------------------------------------------------------------- // Debug stuff: //#define TEST_CONSOLE // TEST_CONSOLE: this can be defined along with POTM_ENTRY // but will be left undefined for the official POTM entry, // in order to gain some time. (not a big deal...) int y_verbosity; #ifdef TEST_CONSOLE # define SECURE # define Message(IMPORTANCE, STREAMED_CONTENT) \ { if (IMPORTANCE <= y_verbosity) \ cout << '[' << IMPORTANCE << "] " << STREAMED_CONTENT << endl; } # define Error(STREAMED_CONTENT) \ { cerr << STREAMED_CONTENT << endl; } #else # define Message(IMPORTANCE, STREAMED_CONTENT) # define Error(STREAMED_CONTENT) #endif #ifdef SECURE # define Y_ASSERT(p) { if(!(p)) Error("Assertion failed: " << #p); } #else # define Y_ASSERT(p) #endif //------------------------------------------------------------------------ // TIME CONTROL //------------------------------------------------------------------------ #if ! defined(__BORLANDC__) && ! defined(_MSC_VER) // UNIX WORLD: #include // for the TMS structure int mytime100() { int seconds; static struct tms TMS; times(&TMS); // add the elapsed system and user times return TMS.tms_stime + TMS.tms_utime; } inline void init_clock() {} #else // MICROSOFT WINDOWS WORLD: #include // for clock() static int clock0 = 0; int mytime100() { int diff = clock() - clock0; return diff / 10; } inline void init_clock() { clock0 = clock(); } #endif // Why 569.0 ? Because we are afraid of a score tie... better be // slightly "faster" than our more dangerous competitors ! bool timeout(double delay = 569.0) // delay is in seconds... { Message(3, "timeout ? time=" << (mytime100() / 100.0)); #if defined(Y_BCB_INTERFACE) return y_bcb_stop(); #else return (mytime100() > 100*delay); #endif } //------------------------------------------------------------------------ typedef double Scalar; /* We were horribly surprised by the unexpected slowness of one of our latest Yalta entries on Fred's machine. It was about 25 to 100 times slower than expected with no obvious reason. The fault was 'typedef long double Scalar'. Apparently Fred's CPU does not handle 'long double' well... */ //[Y8] calculate x^(2^p) Scalar power2 (Scalar x, int p) { for (; p > 0; p--) x *= x; return x; } #define IFLOOR(scalar) ((int) floor(scalar)) int GCD (int a, int b, int &p__, int &q__) { // Greatest Common Divisor; by definition GCD(x,0) == x == GCD(0,x) // also finds p__ and q__ so that |a*q__ - b*p__| == |GCD(a,b)| // For the tranquillity of my mind, // operands must be positive because integers division is not // standardly defined on negative integers // (and most of the times, they choose the bad definition IMNSHO) if (a < 0) a = -a; if (b < 0) b = -b; p__ = 0; q__ = 1; int p_ = 1, q_ = 0, p, q; while (b != 0) { int tmp = a / b; p = tmp * p_ + p__; q = tmp * q_ + q__; tmp = a % b; a = b; b = tmp; p__ = p_; p_ = p; q__ = q_; q_ = q; } return a; } // [Y5M] database for GCD. ///////////////////// // G C D _ D B ///////////////////// class GCD_db_ { struct GCD_db_entry { int gcd; int p__, q__; } *_db; int _maxA, _maxB; public: GCD_db_ (int maxA = WIDTH, int maxB = WIDTH) : _maxA(maxA), _maxB(maxB), _db(NULL) { Message (1, "Building GCD database."); build_db (); } ~GCD_db_ () { delete _db; } void build_db () { if (!(_db = new GCD_db_entry[(_maxA+1)*(_maxB+1)])) { Y_ASSERT (_db!=NULL); return; } for (int a = 0; a <= _maxA; a++) for (int b = 0; b <= _maxB; b++) { GCD_db_entry *tmp = &_db[a * (_maxA + 1) + b]; tmp->gcd = GCD (a, b, tmp->p__, tmp->q__); } } int get (int a, int b, int &p__, int &q__) { //[Y5M] see GCD (...) a = abs (a); b = abs (b); #ifdef SECURE Y_ASSERT (_db != NULL); if (a > _maxA || b > _maxB) { Error ("a > _maxA || b > _maxB"); return -1; } #endif GCD_db_entry *tmp = &_db[a * (_maxA + 1) + b]; p__ = tmp->p__; q__ = tmp->q__; return tmp->gcd; } } GCD_db; class Segment; ///////////////////// // G V E C T O R ///////////////////// class GVector { // geometric vector public: Scalar x, y; GVector () { } GVector (const Scalar & _x, const Scalar & _y) : x(_x), y(_y) { } GVector (const GVector & o) : x(o.x), y(o.y) { } //---- basic point operations GVector & operator = (const GVector & o) { x = o.x; y = o.y;return *this; } bool operator == (const GVector & o) const { return x == o.x && y == o.y; } #if defined(__BORLANDC__) || defined(_MSC_VER) // Yalta5f: added _MSC_VER test bool operator != (const GVector & o) const { return ! operator== (o); } #endif //---- vectorial operations GVector operator + (const GVector & o) const { return GVector(x + o.x, y + o.y); } GVector operator - (const GVector & o) const { return GVector(x - o.x, y - o.y); } GVector operator * (const Scalar & k) const { return GVector(x * k, y * k); } GVector & operator += (const GVector & o) { x += o.x; y += o.y; return *this; } GVector & operator -= (const GVector & o) { x -= o.x; y -= o.y; return *this; } // scalar product : Scalar operator * (const GVector & o) const { return x * o.x + y * o.y; } // module of vectorial product : Scalar operator ^ (const GVector & o) const { return x * o.y - y * o.x; } void rand_slide () //[yalta10] { Scalar x1 = x + 2*(rand () % 2) - 1; Scalar y1 = y + 2*(rand () % 2) - 1; const int proba_coeff = 4; // probability to change is only 1/proba_coeff: // too low proba_coeff leads to bad behaviour ! if (x1 >= 0 && x1 <= WIDTH && (rand () < RAND_MAX / proba_coeff)) x = x1; if (y1 >= 0 && y1 <= WIDTH && (rand () < RAND_MAX / proba_coeff)) y = y1; } bool lays_in (const Segment & rect) const; }; typedef GVector Point; MSCVER_PSEUDO(GVector, <); ////////////////////// // S E G M E N T ////////////////////// class Segment { // It is a base class for Line. public: GVector p, q; Segment () { } Segment (const GVector & _p, const GVector & _q) : p(_p), q(_q) { #ifdef SECURE if (p == q) cerr << "undefined line or segment" << endl; #endif } Segment (const Segment & _seg) : p(_seg.p), q(_seg.q) { } bool line_contains(const Point & pt) const { return ((p - pt) ^ (p - q)) == 0; } // Gets the intersection point of two lines. // It is assumed that the intersection exists. If it doesn't the function // will format your c: drive... Point operator % (const Segment & l); // see also assign_intersection }; typedef Segment Rect; inline bool GVector::lays_in (const Rect & rect = Segment (GVector (0,0), GVector (WIDTH,WIDTH))) const { if (x >= rect.p.x && x <= rect.q.x && y >= rect.p.y && y <= rect.q.y) return true; else return false; } ////////////////////////// // L I N E ////////////////////////// class Line : public Segment { // "Line" is a segment with extended information that MainSystem manipulates public: Segment _save; Segment _closeLines[8]; int _nCloseLines; int _index, _indexToBest; Line () : Segment () { } // if given two points which the line passes through Line (const Point & _p, const Point & _q) : Segment (_p, _q), _nCloseLines(0), _index(-1), _indexToBest(-1) { } Line (const Segment & seg) : Segment (seg), _nCloseLines(0), _index(-1), _indexToBest(-1) { } Line & operator = (const Segment & o) { p = o.p; q = o.q; return *this; } void save () { _save.p = p; _save.q = q; } void restore () { *this = _save; } void calc_close_lines (); bool become_next_close () { if (++_index >= _nCloseLines) return false; *this = _closeLines[_index]; return true; } void become_random_close () { *this = _closeLines[rand() % _nCloseLines]; } void reset () { _index = -1; _indexToBest = -1; } void mark_as_best_close () { _indexToBest = _index; } void become_best_close () { if (_indexToBest >= 0) *this = _closeLines[_indexToBest]; } }; template void y_assign(std::vector & dest, const std::vector & org) // [Y14b] { const int siz = org.size(); dest.resize(siz); for (int i = 0; i < siz; ++ i) dest[i] = org[i]; } typedef std::vector Pattern; // [Y14b] MSCVER_PSEUDO(Segment, <); MSCVER_PSEUDO(Segment, ==); istream & operator >> (istream & is, GVector & gv) { is >> gv.x >> gv.y; return is; } istream & operator >> (istream & is, Segment & line) { Point p, q; is >> p >> q; line = Segment(p, q); return is; } ostream & operator << (ostream & os, const GVector & gv) { return os << gv.x << ' ' << gv.y; } ostream & operator << (ostream & os, const Segment & s) { return os << s.p << ' ' << s.q; } ///////////////////////// // P O L Y G O N ///////////////////////// class YPolygon { public: Point* points; // Y15c int n_points; // number of points // Previously points was a std::vector. This was replaced for optimisation // purposes: we're not sure Fred's compiler performs the optimisations that // make std::vector efficient enough. (read: as efficient as possible, // specially in split()). Scalar area; YPolygon () { points = new Point[NUM_POTM_LINES + 5]; //Y15c n_points = 0; } ~YPolygon () { delete[] points; } void operator = (const YPolygon & o) { n_points = o.n_points; memcpy(points, o.points, n_points * sizeof(Point)); area = o.area; } void assign_rectangle (const Rect & rect) { points[0] = Point(rect.p.x, rect.p.y); points[1] = Point(rect.q.x, rect.p.y); points[2] = Point(rect.q.x, rect.q.y); points[3] = Point(rect.p.x, rect.q.y); n_points = 4; get_area(); // we would feel bad if we forgot it ;-) } Scalar get_area (); // Splits the polygon into two by line and stores the second polygon in pol // The areas of each polygons automatically calculated. // returns true if the polygon is split into two non-empty parts. bool split (const Segment & line, YPolygon & pol); private: YPolygon(const YPolygon &); // forbids the use of copy constructor }; // if Fred's compiler won't inline it, _we_ have to inline it: // WARNING: arguments 'SEGM', 'P' and 'Q' are evaluated several times #define Y_ASSIGN_SEGM(SEGM, X0,Y0, X1,Y1) \ { SEGM.p.x = X0; SEGM.p.y = Y0; SEGM.q.x = X1; SEGM.q.y = Y1; } #define Y_ASSIGN_SEGM_P(SEGM, P, Q) \ { SEGM.p.x = P.x; SEGM.p.y = P.y; SEGM.q.x = Q.x; SEGM.q.y = Q.y; } inline void Line::calc_close_lines () { GVector r(q - p); Point pLeft, pRight, qLeft, qRight; // checking for some special cases // (these special cases make the function look ugly, but I didn't find // another way to make it efficient) if (r.x == 0) { // vertical p.y = 0; q.y = WIDTH; if (p.x == 0) { // the left border _nCloseLines = 3; Y_ASSIGN_SEGM(_closeLines[0], 0,0, 1,WIDTH); Y_ASSIGN_SEGM(_closeLines[1], 1,0, 0,WIDTH); Y_ASSIGN_SEGM(_closeLines[2], 1,0, 1,WIDTH); return; } else if (p.x == WIDTH) { // the right border _nCloseLines = 3; Y_ASSIGN_SEGM(_closeLines[0], WIDTH-1,0, WIDTH, WIDTH); Y_ASSIGN_SEGM(_closeLines[1], WIDTH, 0, WIDTH-1,WIDTH); Y_ASSIGN_SEGM(_closeLines[2], WIDTH-1,0, WIDTH-1,WIDTH); return; } pLeft = pRight = p; qLeft = qRight = q; pLeft.x -= 1; pRight.x += 1; qLeft.x -= 1; qRight.x += 1; } else if (r.y == 0) { // horizontal p.x = 0; q.x = WIDTH; if (p.y == 0) { // the bottom border _nCloseLines = 3; Y_ASSIGN_SEGM(_closeLines[0], 0,0, WIDTH,1); Y_ASSIGN_SEGM(_closeLines[1], 0,1, WIDTH,0); Y_ASSIGN_SEGM(_closeLines[2], 0,1, WIDTH,1); return; } else if (p.y == WIDTH) { // the top border _nCloseLines = 3; Y_ASSIGN_SEGM(_closeLines[0], 0,WIDTH-1, WIDTH,WIDTH); Y_ASSIGN_SEGM(_closeLines[1], 0,WIDTH, WIDTH,WIDTH-1); Y_ASSIGN_SEGM(_closeLines[2], 0,WIDTH-1, WIDTH,WIDTH-1); return; } pLeft = pRight = p; qLeft = qRight = q; pLeft.y -= 1; pRight.y += 1; qLeft.y -= 1; qRight.y += 1; } else { int dx, dy; int gcd = GCD_db.get ((int)r.x, (int)r.y, dx, dy); // extending the line to first points outside the border r.x /= gcd; r.y /= gcd; do { q.x += r.x; q.y += r.y; }while (q.lays_in()); do { p.x -= r.x; p.y -= r.y; }while (p.lays_in()); // finding pLeft, pRight, qLeft, qRight // It doesn't matter what side we consider _right_ and what _left_ ;) if (r.x < 0) dx = -dx; if (r.y < 0) dy = -dy; Point dr(dx, dy); //Y15h pLeft.x = p.x + dx; pLeft.y = p.y + dy; if (! pLeft.lays_in ()) pLeft += r; p += r; pRight.x = p.x - dx; pRight.y = p.y - dy; if (! pRight.lays_in ()) pRight += r; qRight.x = q.x - dx; qRight.y = q.y - dy; if (! qRight.lays_in ()) qRight -= r; q -= r; qLeft.x = q.x + dx; qLeft.y = q.y + dy; if (! qLeft.lays_in ()) qLeft -= r; } Y_ASSIGN_SEGM_P(_closeLines[0], p, qLeft); Y_ASSIGN_SEGM_P(_closeLines[1], p, qRight); Y_ASSIGN_SEGM_P(_closeLines[2], pLeft, q); Y_ASSIGN_SEGM_P(_closeLines[3], pRight, q); // perhaps next four (two, three) lines are not necessary Y_ASSIGN_SEGM_P(_closeLines[4], pLeft, qRight); Y_ASSIGN_SEGM_P(_closeLines[5], pRight, qLeft); _nCloseLines = 6; if (pLeft != qLeft) { // Warning ! don't change _nCloseLines in call to macro ! Y_ASSIGN_SEGM_P(_closeLines[_nCloseLines], pLeft, qLeft); ++ _nCloseLines; } if (pRight != qRight) { // Warning ! don't change _nCloseLines in call to macro ! Y_ASSIGN_SEGM_P(_closeLines[_nCloseLines], pRight, qRight); ++ _nCloseLines; } } //[faster intersection function adapted from old Segment::operator % // for YPolygon::split] void assign_intersection( Point & inters, const Point & p, const Point & q, const Segment & l ) { Scalar a1, b1, c1, a2, b2, c2, det; a1 = q.y - p.y; b1 = p.x - q.x; c1 = q.y * p.x - q.x * p.y; a2 = l.q.y - l.p.y; b2 = l.p.x - l.q.x; c2 = l.q.y * l.p.x - l.q.x * l.p.y; det = a1 * b2 - b1 * a2; inters.x = (c1 * b2 - b1 * c2) / det, inters.y = (a1 * c2 - c1 * a2) / det; } inline Point Segment::operator % (const Segment & l) { Point result; assign_intersection(result, p,q,l); return result; } inline Scalar YPolygon::get_area () { area = 0; if (n_points <= 2) return area; //[Y15b] mind the loop ! i0 starts on last point. Point* i1 = points; Point* iEnd = i1 + n_points; Point* i0 = iEnd - 1; for ( ; i1 < iEnd; i0 = i1, ++ i1) { // you may write 'i0=i1++' above is you wish ;-) area += (i1->x - i0->x) * (i1->y + i0->y); // the increment is twice the (signed) area under the segment // this is smaller, hence more precise than (*i0) ^ (*i1). // since we don't call 'operator ^' is is also faster. } if (area < 0) area = - area; area /= 2; return area; } inline bool YPolygon::split (const Segment & line, YPolygon & pol) { #define ERR_INTERS2 Error("Horror ! more than two intersections !") Point *pi; Point *pi_prev = & points[n_points - 1]; Point* const pi_end_minus_one = & points[n_points - 1]; //Y14z //Point line_r = line.q - line.q; Point line_r(line.q.x - line.p.x, line.q.y - line.p.y); Scalar e_last = (pi_prev->x - line.p.x) * line_r.y - (pi_prev->y - line.p.y) * line_r.x; Scalar e1, e2; int i, j = 0; // inter[2] show where we should break the points array. It may be // maximum 2 intersections (though it can be 1) // corner[2] indicates whether the line lays on the corner... // inter_p[2] are the intersection points int inter[2], corner[2] = { 0, 0 }; Point inter_p[2]; e1 = e_last; for (i = 0, pi = points; pi < pi_end_minus_one; pi++, i++) { //inlined computation of e2: e2 = (*pi - line.p) ^ line_r; e2 = (pi->x - line.p.x) * line_r.y - (pi->y - line.p.y) * line_r.x; if (e2 * e1 < 0) { // it MAY currently happen that j == 2 here (more than 2 // intersections) because of floating point imprecision. So... if (j >= 2) { ERR_INTERS2; return false; } assign_intersection(inter_p[j], *pi_prev, *pi, line); inter[j] = i; ++ j; } else if (e2 == 0) { if (j >= 2) { ERR_INTERS2; return false; } inter_p[j] = *pi; corner[j] = 1; inter[j] = i; ++ j; } e1 = e2; pi_prev = pi; } // This is for speeding up a little... if (e_last * e1 < 0) { if (j >= 2) { ERR_INTERS2; return false; } //[~Y15g] inter_p[j] = Segment (*pi_prev, *pi) % line; assign_intersection(inter_p[j], *pi_prev, *pi, line); //Y15g inter[j++] = i; } else if (e_last == 0) { if (j >= 2) { ERR_INTERS2; return false; } inter_p[j] = *pi; corner[j] = 1; inter[j++] = i; } Y_ASSERT(j <= 2); // je me repete... if (j != 2) return false; // no intersections //pi = points.begin () + inter[0]; pi = & points[inter[0]]; //-- Forming the new polygon // in [] brackets you have the std::vector equivalent code Point* const newPtsBegin = pol.points; Point* newPtsEnd = newPtsBegin; //[ if (!corner[0]) pol.points.push_back (inter_p[0]); ] if (!corner[0]) { memcpy(newPtsEnd, inter_p, sizeof(Point)); ++ newPtsEnd; } //[pol.points.insert (pol.points.end (), pi, points.begin () + inter[1]);] int numNewMidPts = inter[1] - inter[0]; memcpy(newPtsEnd, pi, numNewMidPts * sizeof(Point)); newPtsEnd += numNewMidPts; //[ pol.points.push_back (inter_p[1]); ] memcpy(newPtsEnd, inter_p + 1, sizeof(Point)); ++ newPtsEnd; // update pol size: pol.n_points = newPtsEnd - newPtsBegin; //-- Modifying the old polygon {{{ //This replaces: // points.erase (pi, points.begin () + inter[1] + corner[1]); // points.insert (pi, inter_p, inter_p + 2); // two intersection points char tail[(NUM_POTM_LINES + 5) * sizeof(Point)]; //[Y15i eeeeeek !!! awful ! horrible ! and yet I wrote it !] const int tail_begin = inter[1] + corner[1]; const int tail_length = n_points - tail_begin; if (tail_length > 0) memcpy(tail, & points[tail_begin], tail_length * sizeof(Point)); memcpy(pi, inter_p, 2 * sizeof(Point)); if (tail_length > 0) memcpy(pi + 2, tail, tail_length * sizeof(Point)); n_points = (pi - & points[0]) + 2 + tail_length; }}} // calculating the areas Scalar old_area = area; get_area (); pol.area = old_area - area; return true; // everything is ok.. } ////////////////////////////// // M A I N S Y S T E M ////////////////////////////// //$mainsystem class MainSystem { public: Segment problem_line; std::vector lines; // Number 2 means that we have two somewhat independent parts, that are // formed by the problem_line. // first[] - the polygons that are formed only by problem_line // polygons [] [] - the polygons formed by all lines on each side of // the problem_line // n_polygons [] - number of polygons on each side // This division makes it easy to calculate the mean area for each part, // which was needed by earlier version of the mechanism. YPolygon first [ 2 ]; YPolygon polygons [ 2 ] [ MAX_POLYGONS ]; int n_polygons [ 2 ]; // Local best pattern (for local MainSystem) //////////////////////////// Pattern bestof; // Scalar bestof_score; // int bestof_npolygons; // //////////////////////////// int min_score; //Y20e: minimum possible score !! Scalar max_area, min_area; // area_diff[0] is score diff, area_diff[1] is sqdiff... Scalar area_diff[2]; enum { vmSqDiff = 0, vmMaxDiff = 1 } _variation_mode; int vmExp; public: MainSystem (const Rect & border, const Segment & _problem_line, const std::vector & _lines) : problem_line(_problem_line), bestof_score(TRIVIAL_SCORE), bestof_npolygons(0) { y_assign(lines, _lines); bestof = _lines; sqMode (); n_polygons[0] = n_polygons[1] = 0; // prepare the information that will not change while tuning first[0].assign_rectangle (border); first[0].split (problem_line, first[1]); //evaluate score: I need it anyway update_polygons(); get_polygon_areas(); //Y20e Scalar min_float_score = fabs(first[0].area / n_polygons[0] - first[1].area / n_polygons[1]); min_score = IFLOOR(min_float_score - TUNING_EPS); //'TUNING_EPS' because I'm definitely paranoid. } void sqMode () { _variation_mode = vmSqDiff; vmExp = START_EXP; Message (2, "Entering Sq mode! " << "sc=" << area_diff[1] //<< " xsc=" << area_diff[0] << " exponent: " << vmExp << " time: " << mytime100()/100.0); } void maxMode () { _variation_mode = vmMaxDiff; Message (2, "Entering Max mode! " << "sc=" << area_diff[1] //<< " xsc=" << area_diff[0] << " time: " << mytime100()/100.0); } void update_polygons (); void get_polygon_areas (); int get_POTM_score() const { return IFLOOR(area_diff[vmMaxDiff]); } int get_n_polygons () const { return n_polygons[0] + n_polygons[1]; } Scalar get_variation () { update_polygons (); get_polygon_areas (); return area_diff[_variation_mode]; } int tune (); bool random_tune (Scalar, int); // Y20: shake() must (have) compute(d) get_variation before leaving void shake () { //[yalta10] a bit of noise (but not breaking the topology) Line *li; for (li = lines.begin (); li != lines.end (); li++) { li->save (); li->p.rand_slide (); li->q.rand_slide (); } int old_pols = get_n_polygons (); Scalar old_score = area_diff[1]; get_variation (); // this will roughly check for topology saving but should be // done more accurately if (old_pols != get_n_polygons () || area_diff[1]-old_score > 50) { for (li = lines.begin (); li != lines.end (); li++) li->restore (); get_variation (); // added Y20 - a big hammer for a small problem } } void beaten_best_score () { //[yalta10] check for our main aim ;-) //[y15L] removed get_n_polygons() check: was too complicated: // (0) things will go faster without this test ;-) // (1) patterns are not supposed to change. so num of polygons // is to stay constant. // (2) even if they change, it's unlikely that we'll miss a high // score because of that. It's unlikely that two distinct patterns // will yield the same high score. if (area_diff[1] < bestof_score) { bestof_score = area_diff[1]; bestof_npolygons = get_n_polygons (); y_assign(bestof, lines); // [Y14b] replaces "bestof = lines" Message (2, "Latest pattern yields best score so far: " << bestof_score); } } void set_to_best () { y_assign(lines, bestof); } }; struct BetterMainSys { // this class is needed by std::sort for sorting the MainSystems... bool operator() (const MainSystem* a, const MainSystem* b) const { return a->area_diff[1] < b->area_diff[1]; } // 'operator()' returns true if and only if a is better than b. }; void MainSystem::update_polygons () { polygons[0][0] = first[0]; polygons[1][0] = first[1]; n_polygons[0] = n_polygons[1] = 1; Line *li; YPolygon *pi, *old_pi_end; for (li = lines.begin (); li != lines.end (); li++) { for (int part = 0; part < 2; part++) { old_pi_end = polygons[part] + n_polygons[part]; for (pi = polygons[part]; pi < old_pi_end; pi++) if (pi->split (*li, polygons[part][n_polygons[part]])) n_polygons[part]++; } } } //$get_polygon_areas void MainSystem::get_polygon_areas () { min_area = AREA; max_area = 0.0; const Scalar am = Scalar (WIDTH * WIDTH) / (n_polygons[0] + n_polygons[1]); YPolygon *pi, *pi_end; Scalar diff_bound = 0; int count = 0; for (int part = 0; part < 2; part++) { pi = polygons[part]; pi_end = pi + n_polygons[part]; for (; pi < pi_end; pi++) { ++ count; if (pi->area > max_area) max_area = pi->area; if (pi->area < min_area) min_area = pi->area; } } if (_variation_mode != vmMaxDiff && min_area < max_area) // otherwise this would fail { Y_ASSERT(vmExp >= 1); // if vmExp==0, 'fabs' must be reintroduced below. const Scalar middle = (max_area + min_area) / 2.0; const Scalar scale = (max_area - min_area) / 2.0; Scalar exp_score = 0; for (int part = 0; part < 2; part++) { pi = polygons[part]; pi_end = pi + n_polygons[part]; for (; pi < pi_end; pi++) exp_score += power2(/*fabs*/(pi->area - middle)/scale, vmExp); // first argument of power2 is at most 1.0 (absolute value): // no more risk of overflowing. // since vmExp > 1, first argument of power2 can be negative, // result will stay positive (if using pow(), we should perhaps // leave fabs()). } exp_score = scale * pow(exp_score, 1.0 / (1 <save (); li->calc_close_lines (); li->reset (); var3 = initial_variation; while (li->become_next_close ()) { var1 = get_variation (); if (var1 < var3 - TUNING_EPS) { //Y20d: added TUNING_EPS var3 = var1; li->mark_as_best_close (); if (var1 < var0 - TUNING_EPS) { //Y20d: added TUNING_EPS var0 = var1; best_line = li; } } } li->restore (); //li->become_best_close (); } if (best_line) { // if the system is not stuck // move the lines to their best close lines... for (li = lines.begin (); li != lines.end (); li++) li->become_best_close (); // did we really improve the solution ? Scalar var0 = get_variation(); if (var0 < initial_variation - TUNING_EPS) return 0; // yes: go for it for (li = lines.begin (); li != lines.end (); li++) { li->restore (); if (get_variation () < initial_variation - TUNING_EPS) return 0; li->become_best_close (); } // un-move lines (all lines have been saved recently) for (li = lines.begin (); li != lines.end (); li++) li->restore (); Message(2, "needed to move one line only"); best_line->become_best_close(); get_variation(); //Y20: this update is now needed return 0; } if (shake_count < MAX_SHAKE_COUNT) { shake_count++; get_variation (); Message(2, "Stuck at " << area_diff[1] << "(" << area_diff[0] << ") shaking... "); shake (); //Y20: shake() updated area_diff[] return 0; }else shake_count = 0; if (_variation_mode == vmSqDiff) { vmExp = EXP_UPDATE; if (vmExp > MAX_EXP) { maxMode (); get_variation (); //Y20. perhaps needless (already done ?) } else { get_variation (); Message(2, "Stuck at " << area_diff[1] << "(" << area_diff[0] << ") new exp: " << vmExp); //set_to_best (); } return 0; } // we give up tuning: reset to best pattern we found. set_to_best (); get_variation (); return 1; } // Tries to find a way out of current situation randomly... // returns false if not found // Y20: random_tune() must (have) compute(d) area_diff[] for the pattern // that is defined when returning. bool MainSystem::random_tune (Scalar best_variation, int num_trys) { Message (3, "random_tune(" << best_variation << "," << num_trys << ") begins at " << mytime100()/100.0); for (Line* li = lines.begin (); li != lines.end (); li++) { li->calc_close_lines (); li->save (); } bool found = false; Scalar score; int count; for (count = 0; count < num_trys && /*[Y14]*/! found; ++ count) { //--- changing position: const int proba_moving_line = PROBA; //in % of moving a given line for (Line* li = lines.begin (); li != lines.end (); li++) { if (rand() % 100 < proba_moving_line) li->become_random_close(); } if ((score = get_variation()) < best_variation - TUNING_EPS) { best_variation = score; Message (3, "Random way found! ;-)... xsc="<< area_diff[0] << " sc=" << area_diff[1]); found = true; // yes, we found it!... } else for (Line* li = lines.begin(); li != lines.end(); ++ li) li->restore(); } if (! found) get_variation(); // expensive way to restore old area_diff[] Message (3, "random_tune(" << best_variation << "," << num_trys << ") ends at " << mytime100()/100.0 << " after " << (count) << " step(s): " << (found ? "success" : "failure") ); return found; } //------------------------------------------------------------------------ // I N I T I A L L I N E S //------------------------------------------------------------------------ #ifdef TEST_CONSOLE double BPS; // best possible score double EXS; // expected score #endif class InitialLinesIterator; class ProtoSystem { public: ProtoSystem() : // scores set to zero for security: expectedScore(0), bestPossibleScore(0), // parameters are set to zero by default: insideParallels(0), outsideParallels(0), secants(0), parallelsToSecants(0) {} // [FvdP] should we use "memset" ? ;-) ProtoSystem(const ProtoSystem & o) { memcpy(this, &o, sizeof(ProtoSystem)); } // [FvdP] lazier, ... but, for such a class, safer ! (hmm...) //-- named constructors: void buildPQR(const InitialLinesIterator & init, int insideP, int outsideP, int secants); void buildSideGrid(const InitialLinesIterator & init, int parallels, int gauches); // (anonymous constructors are sometimes good, but sometimes evil !) //-- data members // normally these things would be "private:" but the POTM lets me develop // bad habits :-) //-- evaluation info: double expectedScore; // approximate ! double bestPossibleScore; // if lines could bend... (ask Paul Banta ;-) //-- number of initial lines of each kind: int insideParallels; int outsideParallels; int secants; int parallelsToSecants; }; struct WorseProtos { // this class is needed by std::sort for sorting the Protos... bool operator() (const ProtoSystem* a, const ProtoSystem* b) const { return a->expectedScore > b->expectedScore; } // 'operator()' returns true if and only if a is worse than b. }; //--------------------------------------------------------------------------- class InitialLinesIterator { public: InitialLinesIterator(const Segment & FredsLine, double firstArea, double secondArea); // areas must be the areas of pieces split by the line (in any order) ~InitialLinesIterator(); // current score to beat: void putScoreBound(double sc) { int intsc = IFLOOR(sc); if (intsc < _maxScore) _maxScore = intsc; } MainSystem* next() { //--- skip solutions that can't possibly beat the best score so far // !!! remember the solution are NOT ordered // w.r.t. bestPossibleScore, but w.r.t. expectedScore ! while (! _protos.empty() && _protos.back()->bestPossibleScore >= _maxScore) { delete _protos.back(); _protos.pop_back(); } //--- no solution ? if (_protos.empty()) return 0; //--- build and return MainSystem #ifdef TEST_CONSOLE BPS = _protos.back ()->bestPossibleScore; EXS = _protos.back ()->expectedScore; #endif MainSystem* result = makeMainSystemFrom(*_protos.back()); delete _protos.back(); _protos.pop_back(); return result; } private://methods void init_constants(const Segment & FredsLine, double firstArea, double secondArea); // void output_transfo(Segment & line); // transform 'normalized' point coordinates into original coordinates void backTransform(Point & pt) const; void do_top_down(GVector & point) const { point.y = 100 - point.y; } void do_right_left(GVector & point) const { point.x = 100 - point.x; } void do_central(GVector & pt) const { do_right_left(pt); do_top_down(pt); } void do_diagonal(GVector & point) const { std::swap(point.x, point.y); } void addLineBundle(int numLines, const Point & start0, const Point & start1, const Point & end0, const Point & end1, std::vector & lines) const; void receive(ProtoSystem* proto); void generate_PQR_Protos(); void generate_SideGrid_Protos(); MainSystem* makeMainSystemFrom(const ProtoSystem & proto) const; public: //data members //---- CONSTANTS defined by the constructor ---- Segment _fredsLine; // NOT normalized: the very original first cut. Segment _line; // normalized ! double _smallerArea; double _biggerArea; // description of the normalization transformation: // normalization is applied in the given order: bool _rightleft; // makes slope negative (or null). bool _central; // makes origin belong to smallest piece. bool _diagonal; // makes slope >= -1 // left intersection of the (normalized) line with the square // is (0, _leftY) // right intersection if (_rightX, _rightY) // with either _rightY==0 or _rightX==100 // and we have anyway _rightX >= _leftY ... double _leftY; double _rightX; double _rightY; inline bool cutsTriangle() const { return _rightY==0; } // : for the sake of clarity //---- VARIABLES that control the iteration ---- std::vector _protos; int _maxScore; // current score to beat }; //--------------------------------------------------------------------------- /* NORMALIZATION: (see also above InitialLinesIterator data members description) InitialLinesIterator::_line is such that: (1) (0,0) is contained in the smaller piece; equivalently, the line separates (0,0) from the center (50,50) (if the center is on the line, we don't care.) (2) the slope p=dy/dx of the line is such that -1 <= p <= 0. */ //--------------------------------------------------------------------------- void InitialLinesIterator:: init_constants(const Segment & line, double firstArea, double secondArea) { //---- normalize the line ---- // HINT: the following trick is used: // a and b have same sign and none of them is zero <===> (a*b > 0) _fredsLine = line; _line = line; //- - - - _rightleft = ((_line.q.x - _line.p.x) * (_line.q.y - _line.p.y) > 0); // true iff line climbs from left to right // (but is not vertical or horiz.) if (_rightleft) { do_right_left(_line.p); do_right_left(_line.q); } //- - - - GVector origin(0,0); GVector center(50,50); GVector lineV(_line.q - _line.p); GVector lineOrtho(lineV.y, - lineV.x); _central = ( ((_line.p - origin) * lineOrtho) // "- origin" could be removed. * ((_line.p - center) * lineOrtho) > 0 ); // topdown is true if and only if // center and origin lie on the same side of the original 'line' // (and none of them lies on the line) if (_central) { do_central(_line.p); do_central(_line.q); } //- - - - _diagonal = fabs(_line.q.y - _line.p.y) > fabs(_line.q.x - _line.p.x); if (_diagonal) { do_diagonal(_line.p); do_diagonal(_line.q); } //---- other line constants ---- lineV = _line.q - _line.p; // update !!! double a,b,c; // aX + bY = c a = lineV.y; b = - lineV.x; c = a * _line.p.x + b * _line.p.y; Y_ASSERT(b != 0); // line cannot be vertical _leftY = c / b; _rightY = (c - 100*a) / b; _rightX = 100; if (_rightY < 0) { _rightY = 0; Y_ASSERT(a != 0); // line cannot be horiz _rightX = c / a; Y_ASSERT(_rightX <= 100.0); } Y_ASSERT(_leftY >= 0 && _leftY <= 100); Y_ASSERT(_leftY <= _rightX); Y_ASSERT(_leftY >= _rightY); // line goes down... //---- constants linked with areas ---- _smallerArea = firstArea; _biggerArea = secondArea; if (_smallerArea > _biggerArea) std::swap(_smallerArea, _biggerArea); } //--------------------------------------------------------------------------- void InitialLinesIterator::backTransform(Point & pt) const { if (_diagonal) do_diagonal(pt); if (_central) do_central(pt); if (_rightleft) do_right_left(pt); } //--------------------------------------------------------------------------- // MainSystem: // (*) best possible score for the pattern // (*) approx. expected score for the pattern //NB. the terminology: "parallel", "orthogonal", "gauche" is not // mathematically correct; they're just a hint about what these lines // are for. inline int Interpol (double r, double from, double to) { return IFLOOR(0.5 + from + (to - from) * r); } inline Point Interpol (double r, Point from, Point to) { return Point(Interpol(r, from.x, to.x), Interpol(r, from.y, to.y)); } void InitialLinesIterator:: addLineBundle(int numLines, const Point & start0, const Point & start1, const Point & end0, const Point & end1, std::vector & lines) const { for (int i = 0; i < numLines; ++ i) { double ratio = double(i+1) / double(numLines+1); Point start(Interpol(ratio, start0.x, start1.x), Interpol(ratio, start0.y, start1.y)); Point end (Interpol(ratio, end0.x, end1.x), Interpol(ratio, end0.y, end1.y)); lines.push_back(Segment(start, end)); } } MainSystem* InitialLinesIterator::makeMainSystemFrom(const ProtoSystem & proto) const { /* +-E----F---G | | A = leftIntersection | | B = leftInsideSecants A | C = rightInsideSecants |\_ | D = rightIntersection | \_ | E = leftOutsideSecants B \_ | F = topSplitPt | \ | G = farCorner +---C---D--H H = Point(100, _rightY) E-----F----G | | | | | | A\________ | | \DH | | | | B----------C */ //-- line points Point leftIntersection(0, _leftY); Point rightIntersection(_rightX, _rightY); //-- inside points Point leftInsideSecants; Point rightInsideSecants; leftInsideSecants = Point(0, _leftY / 2); rightInsideSecants = Point(_rightX / 2, 0); //(there is a unused variant of this code in yalta15) //--outside points Point leftOutsideSecants(0, 100); if (_leftY > 60) leftOutsideSecants = Point(_leftY - 60, 100); const int secantsAndParallels = proto.secants + proto.parallelsToSecants; double topSplitRatio = 0.5; if (secantsAndParallels) topSplitRatio = double(proto.secants) / double(proto.secants + proto.parallelsToSecants); int topSplit = Interpol(topSplitRatio, leftOutsideSecants.x, 100); Point topSplitPt = Point(topSplit, 100); Point farCorner(100,100); //--- make list of lines std::vector lines; // point on top line: on the left come the "secants", // on the right come the "parallels to secants" addLineBundle(proto.parallelsToSecants, rightIntersection, Point(100, _rightY), // the above two points coincide if cutsTriangle()==false. topSplitPt, farCorner, lines); addLineBundle(proto.outsideParallels, // "parallels" in the big piece leftIntersection, leftOutsideSecants, Point(100, _rightY), farCorner, lines); // : there's no competition with another bundle of lines, hence the // extremities do not need specific computation. addLineBundle(proto.secants, leftInsideSecants, rightInsideSecants, leftOutsideSecants, topSplitPt, lines); addLineBundle(proto.insideParallels, leftIntersection, leftInsideSecants, rightIntersection, rightInsideSecants, lines); //--- transform lines --- for (int i = 0; i < lines.size(); ++ i) { backTransform(lines[i].p); backTransform(lines[i].q); } //--- make main system from lines --- return new MainSystem(Rect(Point(0,0),Point(WIDTH,WIDTH)), _fredsLine, lines); } // in what follows: // 'outMean' is the mean size of 'outside' pieces, that is pieces from the // biggest initial piece. // 'inMean' is the mean size of 'inside' pieces, that is pieces from the // smaller initial piece. // Sometimes (e.g. for buildPQR) not all cuts are taken into account for // outMean and inMean. void ProtoSystem:: buildPQR(const InitialLinesIterator & init, int insideP, int outsideP, int secants_) { const double smallArea = init._smallerArea; insideParallels = insideP; outsideParallels = outsideP; secants = secants_; double inMean = smallArea / (1 + insideP); double outMean = (AREA - smallArea) / (1 + outsideP); bestPossibleScore = fabs(inMean - outMean) / (1 + secants); // it often occurred to me that I forgot the 'f' in 'fabs'... // such bugs are of the kind that makes you crazy ! expectedScore = bestPossibleScore; // malus when secants_ > 1, // (tries to) correspond(s) to the grid distortion: if (secants_ > 1) expectedScore = bestPossibleScore + fabs(init._leftY - init._rightY); } void ProtoSystem:: buildSideGrid(const InitialLinesIterator & init, int parallels, int nonSecants) { outsideParallels = parallels; parallelsToSecants = nonSecants; int numOutsidePieces = (1 + parallels) * (1 + nonSecants); double outMean = (AREA - init._smallerArea) / numOutsidePieces; bestPossibleScore = fabs(init._smallerArea - outMean); expectedScore = bestPossibleScore; if (parallels > 0 && nonSecants > 0) expectedScore += (init._smallerArea / numOutsidePieces); // malus is not really coherent... minimal for parallels==0 or secants==0 // then maximal for parallels==1 or secants==1... something's wrong ! } //-------------------------------------------------------------------- void InitialLinesIterator::receive(ProtoSystem* proto) { if (proto->bestPossibleScore < TRIVIAL_SCORE) _protos.push_back(proto); else delete proto; } void InitialLinesIterator::generate_PQR_Protos() { for (int sum_pq = 0; sum_pq <= NUM_POTM_LINES; ++ sum_pq) { double ideal_p = (sum_pq + 2) * (_smallerArea / AREA) - 1.0; int fork[2] = { IFLOOR(ideal_p), (int) ceil(ideal_p) }; std::vector p; if (fork[0] >= 0) p.push_back(fork[0]); if (fork[1] != fork[0] && fork[1] >= 0) p.push_back(fork[1]); if (fork[1] < 0) p.push_back(0); // 'fork[1] < 0' is an awful situation, but even then // PQR patterns can still be useful (probably with p=0, q=5, r=5). for (int i = 0; i < p.size(); ++ i) { for (int r = 0; r <= NUM_POTM_LINES - sum_pq; ++ r) { ProtoSystem* proto = new ProtoSystem; proto->buildPQR(*this, p[i], sum_pq - p[i], r); this->receive(proto); } } }//end for sum_pq } void InitialLinesIterator::generate_SideGrid_Protos() { // currently generates only protos with 'proto->secants == 0' // but higher 'secants' numbers provide a quite obvious generalisation. if (! cutsTriangle()) return; // side grids are hopeless in this case... (really ?) // Let's take it easy ;-) for (int sum_pq = 1; sum_pq <= NUM_POTM_LINES; ++ sum_pq) for (int p = 0; p <= sum_pq / 2; ++ p) { // p [#non-secants] <= q [#parallels] int q = sum_pq - p; ProtoSystem* proto = new ProtoSystem; proto->buildSideGrid(*this, q, p); this->receive(proto); } } InitialLinesIterator:: InitialLinesIterator(const Segment & FredsLine, double firstArea, double secondArea) { init_constants(FredsLine, firstArea, secondArea); _maxScore = TRIVIAL_SCORE; generate_PQR_Protos(); generate_SideGrid_Protos(); // sort _protos by decreasing (i.e. better-getting) expectedScores : // we'll extract Protos from the end, so the best ones must go there ! std::sort(_protos.begin(), _protos.end(), WorseProtos()); } InitialLinesIterator::~InitialLinesIterator() { for (int i = 0; i < _protos.size(); ++ i) delete _protos[i]; } void tuning_main(const Segment & problem_line, MainSystem &); void overall_main (const Segment & problem_line); //------------------------------------------------------------------------ // M A I N //------------------------------------------------------------------------ void Build277(const Segment & the_line, std::vector & lines) { // build a solution that will score <= 277 whatever the problem line... // this solution was found by purely mathematical means (pen & pencil) // (see note below) int sol[40] = { 16, 2, 17, 74, 33, 35, 34, 80, 49, 10, 51, 90, 66, 20, 67, 65, 83, 26, 84, 98, 26, 17, 98, 16, 20, 34, 65, 33, 10, 51, 90, 49, 35, 67, 80, 66, 2, 84, 74, 83 }; lines.resize(0); for (int i = 0; i < 40; i += 4) { Point a(sol[i],sol[i+1]); Point b(sol[i+2],sol[i+3]); if (! (the_line.line_contains(a) && the_line.line_contains(b)) ) lines.push_back(Segment(a,b)); } } /* Note on the solution hardcoded in 'Build277': If floating point coordinates were allowed, the obvious 5x5 grid would split the square in pieces of equal areas 277.777... But since it's not allowed, we have to move the lines while keeping the areas as equal as possible. I wondered if there existed a "direction" in which to move the lines of the ideal 5x5 grid so that the first derivative of each area is zero. Indeed, there is one (and only one !) for each rectangular NxM grid: define f(t) = t * (100 - t); then given a small coefficient eps, move the lines as follows: vertical lines: (x,0) to (x,100) becomes (x + eps*f(x), 0) to (x - eps*f(x), 100) horizontal lines: (0,y) to (100,y) becomes (0, y - eps*f(y)) to (100, y + eps*f(y)) The final step was to find a value of eps such that all lines pass through integer coordinates. The "Build277" solution is based on the smallest possible such value (which can be found without computer computations). Note that there is no guarantee that the _optimal_ distorted 5x5 grid lies in the given direction from the ideal 5x5 grid. */ void tuning_main(const Segment &, //unused parameter 'problem_line', MainSystem & ms) { ms.sqMode (); for (;;) { if (timeout()) { ms.set_to_best(); ms.get_variation(); // done just after the loop break; } if (ms.tune ()) //[Y14]: note that this calls get_variation() { // tuning ended... break; } //[~Y14: moved out of loop] ms.get_variation (); #ifdef TEST_CONSOLE Message (3, "Score: " << (ms.max_area - ms.min_area) << "; area_sqdiff: " << (ms.area_diff[0]) << "; N polygons: " << (ms.n_polygons[1] + ms.n_polygons[0])); #endif }//end of tuning loop #ifdef TEST_CONSOLE //ms->get_variation (); if (y_verbosity >= 1) { cout << "[1] Final results for the latest pattern:" << endl; cout << "[1] area_sqdiff: " << ms.area_diff[0] << endl; cout << "[1] Score: " << (ms.max_area - ms.min_area) << endl; cout << "[1] N polygons: " << ms.get_n_polygons () << endl; cout << "[1] Lines:" << endl; for (int i = 0; i < ms.lines.size(); ++ i) cout << "[1] " << ms.lines[i] << endl; } #endif } void overall_main (const Segment & problem_line) { init_clock(); std::vector systems; // list of all current systems. //----- 0th phase: "trivial" solution pattern277: Pattern pattern277; Build277(problem_line, pattern277); systems.push_back(new MainSystem(Rect (Point(0,0), Point(WIDTH,WIDTH) ), problem_line, pattern277 ) ); MainSystem* const system277 = systems[0]; //----- 1st phase: roughly evaluating all patterns // given by InitialLinesIterator : //remember the following values are set when these variables are defined: // MAX_EXP = 4; // MAX_SHAKE_COUNT = 0; // N_RANDOM_TRYS = 20; InitialLinesIterator init(problem_line, system277->first[0].get_area(), system277->first[1].get_area()); init.putScoreBound(system277->get_POTM_score()); // FvdP: currently, InitialLinesIterator::InitialLinesIterator blindly // builds a number of ProtoSystems. In later versions we should give // him 'bestof_score' as constructor argument so that he'll avoid // building many of them. (...but is it useful ? the only gain would // be a memory gain) while (! timeout(450.0)) //Y20e: added timeout. { MainSystem* ms = init.next(); if (ms == 0) break; // no more initial mainsystems #ifdef TEST_CONSOLE Message (1, "Now = " << mytime100()/100.0); Message (1, "Now tuning this pattern (" << ms->get_n_polygons() << " polygons, BPS=" << BPS << ", EXS=" << EXS << "):"); for (int i = 0; i < ms->lines.size(); ++ i) Message (2, ms->lines[i]); if (ms->lines.empty()) Message (2, "(empty pattern !)"); #endif tuning_main(problem_line, *ms); // ms->set_to_best(); init.putScoreBound(ms->get_POTM_score()); systems.push_back(ms); }//end of overall loop //----- 2nd phase: re-tuning "good enough" patterns from 1st phase Message (1, "Now = " << mytime100()/100.0); Message (1, "Now second phase: tuning best patterns till the end"); MAX_EXP = 7; //[Yalta13, I tried 10 but that seems needless...] MAX_SHAKE_COUNT = 4; N_RANDOM_TRYS = 200; double threshold = 5; // [Y20c]: instead of 10.0; double decay = 0.3; // [Y20c]: instead of 0.5 while (! timeout()) { int i; // for non-standard Microsoft Visual C++ 5 ... //--- 2A: eliminating not-good-enough patterns double best_score = AREA+1; // floating point score, not integer for (i = 0; i < systems.size(); ++ i) if (systems[i]->get_POTM_score() < best_score) best_score = systems[i]->area_diff[1]; double worst_accepted_score = best_score + threshold + TUNING_EPS; threshold *= decay; // next threshold will be smaller... int best_int_score = IFLOOR(best_score + TUNING_EPS); //Y20e /*Design warning: since for some i, worst_accepted_score >= systems[i]->get_POTM_score() we are sure that at least one MainSystem remains. This would not be true if best_score was replaced by floor(best_score) so beware ! _However_ if tamed, this effect can be interesting. */ int iRead, iWrite; for (iRead = 0, iWrite = 0; iRead < systems.size(); ++ iRead) { Scalar score = systems[iRead]->area_diff[1]; if (systems[iRead]->area_diff[1] > worst_accepted_score) delete systems[iRead]; // not good enough else systems[iWrite++] = systems[iRead]; } Y_ASSERT(iWrite > 0); systems.resize(iWrite); Message (2, "Best score = " << best_score << "; limit = " << worst_accepted_score); Message (2, "There remain " << iWrite << " different pattern(s)"); //--- 2B: one tuning round for each pattern we kept: // [Y20e] this is a last-minute quick hack: bool all_frozen = true; for (i = 0; i < systems.size() && ! timeout(); ++ i) if (systems[i]->get_POTM_score() > systems[i]->min_score) { all_frozen = false; break; } if (all_frozen) break; // no pattern can still improve -> we stop ! // [Y20c] we begin with the more promising ones... std::sort(systems.begin(), systems.end(), BetterMainSys()); for (i = 0; i < systems.size() && ! timeout(); ++ i) { MainSystem & ms = *systems[i]; // current main system #ifdef TEST_CONSOLE Message (2, "Now = " << mytime100()/100.0); Message (2, "Now tuning best pattern #" << (i+1) << "/" << systems.size()); for (int i = 0; i < ms.lines.size(); ++ i) Message (2, ms.lines[i]); if (ms.lines.empty()) Message (2, "(empty pattern !)"); Message (2, "(" << ms.get_n_polygons() << " polygons, score = " << ms.area_diff[1] << ")"); #endif tuning_main(problem_line, ms); // ms.set_to_best (); }//end 2nd phase sub-loop (for i < systems.size()) }//end 2nd phase loop (while ! timeout()) //----- finally we select the best score double final_best_score = AREA+1; int final_system_index = -1; for (int i = 0; i < systems.size(); ++ i) { if (systems[i]->get_POTM_score() < final_best_score) { final_system_index = i; final_best_score = systems[i]->get_POTM_score(); } } MainSystem* best = systems[final_system_index]; #ifdef TEST_CONSOLE Message (1, "My final choice after " << (double) mytime100 () / 100 << " seconds:"); Message (1, "Score: " << (best->get_POTM_score())); Message (1, "N polygons: " << best->get_n_polygons()); #endif for (i = 0; i < best->lines.size(); ++ i) cout << best->lines[i] << endl; if (best->lines.empty()) cout << "0 0 0 100" << endl; // special case: best solution found has zero lines... but we must // provide a line: a border will do (it _is_ allowed by the rules !) // NB. if the original line splits the square in equal parts, a better // line would be the original line rotated 90 degrees. //----- we should delete remaining mainsystems here... // Y20x: the following lines were added _after_ the deadline. // they don't change the outcome of the program. for (i = 0; i < systems.size(); ++ i) delete systems[i]; } int main(int argc, char *argv[]) { Segment problem_line; std::vector lines; y_verbosity = -1; srand (time(NULL)); // this is for not to get used to specific seed... //-- verbosity flags if (argc > 1 && argv[1][0] == 'v') { const char* vptr = argv[1]; while (*vptr++ == 'v') ++ y_verbosity; -- argc; ++ argv; } const bool potm_conditions = (argc==5); if (potm_conditions) { problem_line = Segment(Point(atoi(argv[1]),atoi(argv[2])), Point(atoi(argv[3]),atoi(argv[4])) ); } else { //[Y14h]-[Y14z] this modification is needed for some of FvdP's tests // (e.g. because C++Builder 1.0 does not define arguments to send to // a console program :-((( ) problem_line = Segment(Point(3,38),Point(99,87)); cout << "Warning: wrong number of arguments; using last system test" << endl; y_verbosity = 2; //[Y18] I left this for the interested reader... /** cout << "Warning: wrong number of arguments; line read from stdin" << endl; cin >> problem_line; // lines.resize(0); // [FvdP: not needed after default constructor] Segment line; while (!(cin >> line).eof ()) lines.push_back (line); **/ } Message(1, "version: " << Y_VERSION << "; build: " << __DATE__); if (lines.empty()) overall_main(problem_line); else { MainSystem ms (Rect (Point(0,0), Point(WIDTH,WIDTH)), problem_line, lines); tuning_main(problem_line, ms); } return 0; }