TopCoder Open 2008 Finals solution

//
// Copyright (c) 2010 Tuomas Pelkonen, tuomaspelkonen.com
//
// Permission is hereby granted, free of charge, to any person
// obtaining a copy of this software and associated documentation
// files (the "Software"), to deal in the Software without
// restriction, including without limitation the rights to use,
// copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the
// Software is furnished to do so, subject to the following
// conditions:
//
// The above copyright notice and this permission notice shall be
// included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
// OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
// HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
// WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
// OTHER DEALINGS IN THE SOFTWARE.
//

#include <vector>
#include <string>
#include <sys/time.h>
#include <math.h>
#include <assert.h>

using namespace std;
struct timeval start_tv;

double max_acc;
double friction;
double air;

struct Waypoint
{
  double x;
  double y;
};

vector<Waypoint> waypoints;

double get_elapsed()
{
  struct timeval tv;

  gettimeofday(&tv, NULL);

  return (tv.tv_sec - start_tv.tv_sec) +
    (tv.tv_usec - start_tv.tv_usec) / 1000000.0;
}

#define PI 3.14159265

double angle_diff(double a1, double a2)
{
  double diff = a1 - a2;

  if (diff > PI)
    diff -= 2 * PI;

  if (diff < -PI)
    diff += 2 * PI;

  return diff;
}

#define ABS(x) ((x) < 0 ? -(x) : (x))

double get_distance(double x, double y)
{
  return sqrt(x * x + y * y);
}

double angle(double x, double y)
{
  if (x > -0.0001 && x < 0.0001)
    {
      if (y > 0)
        return PI / 2;
      else
        return -PI / 2;
    }

  if (x >= 0 && y >= 0)
    return atan(y / x);
  if (x < 0 && y >= 0)
    return PI + atan(y / x);
  if (x < 0 && y < 0)
    return -PI + atan(y / x);
  if (x >= 0 && y < 0)
    return atan(y / x);
}

int loop_count = 0;

int init(double _friction, double _air, double _maxacc,
         vector<double> wx, vector<double> wy)
{
  int i;

#if 0
  fprintf(stderr, "INIT %.2f %.2f %.2f\n", _friction, _air, _maxacc);
#endif

  gettimeofday(&start_tv, NULL);

  friction = _friction;
  air = _air;
  max_acc = _maxacc - 0.00001;

  for (i = 0; i < (int)wx.size(); i++)
    {
      Waypoint wp;

      wp.x = wx[i];
      wp.y = wy[i];

      waypoints.push_back(wp);
    }

  loop_count = 0;

  return 0;
}

void get_target(double x, double y, int wp, double *tx, double *ty)
{
  int i;

  if (wp == waypoints.size() - 1)
    {
      *tx = waypoints[wp].x;
      *ty = waypoints[wp].y;
      return;
    }

  int next_wp = wp + 1;

  for (i = wp + 1; i < waypoints.size(); i++)
    {
      if (get_distance(waypoints[wp].x - waypoints[i].x,
                       waypoints[wp].y - waypoints[i].y) > 1000.0)
        {
          next_wp = i;
          break;
        }
    }

  double min_dist = 1000000.0;
  for (i = 0; i < 100; i++)
    {
      double angle = i / 100.0 * 2 * PI;
      double x1 = cos(angle) * 800.0 + waypoints[wp].x;
      double y1 = sin(angle) * 800.0 + waypoints[wp].y;

      double dist = get_distance(x1 - x, y1 - y) +
        get_distance(waypoints[next_wp].x - x1, waypoints[next_wp].y - y1);

      if (dist < min_dist)
        {
          *tx = x1;
          *ty = y1;
          min_dist = dist;
        }
    }

}

vector<double> step(double x, double y, double dx, double dy,
                    double alpha, int wp)
{
  vector<double> ret;

  double speed = get_distance(dx, dy);

  double direction = angle(dx, dy);

  Waypoint target;
  get_target(x, y, wp, &target.x, &target.y);

  double goal = angle(target.x - x, target.y - y);
  double diff = angle_diff(goal, alpha);

  double acc = 0.0;
  double turn = 0.0;
  double dist = get_distance(target.x - x, target.y - y);

  double steps = dist / speed;

  turn = diff / steps * 1.75;
  double max_turn = 0.005;

  if (turn > max_turn)
    {
      acc = -max_acc;
      turn = 0.005;
    }
  else if (turn < -max_turn)
    {
      acc = -max_acc;
      turn = -0.005;
    }
  else
    {
      acc = max_acc;
    }

  ret.push_back(acc);
  ret.push_back(turn);

#if 0
  if (loop_count % 1000 == 0)
    {
      fprintf(stderr, "%.2f %.2f\n", ret[0], ret[1]);
      fflush(stderr);
    }
#endif

  loop_count++;

  return ret;
}  

class CarRace
{
public:
  int init(double friction, double air, double maxacc,
           vector<double> wx, vector<double> wy)
  {
    return ::init(friction, air, maxacc, wx, wy);
  }

  vector<double> step(double x, double y, double dx, double dy,
                      double alpha, int wp)
  {
    return ::step(x, y, dx, dy, alpha, wp);
  }

};
  • Share/Bookmark

Trackbacks / Pingbacks

  1. What happened in Vegas '08 | Rants and Apps

Leave a Reply