Mars Lander Optimization for CodinGame (https://www.codingame.com/ide/puzzle/mars-lander)

mars_lander_optimization.dart

import 'dart:io';
import 'dart:math';
import 'dart:collection';

Line marsGround;
State marsLanderInitState;

// todo set you hostname for debugging
List<String> localHosts = [];

final log              = true;
final elitism          = true;
final generationsCount = 12;
final populationSize   = 24;
final genomeSize       = 1440;

var uniformRate        = .5;
var mutationRate       = .06;
var selectionRatio     = .4;

var GRAVITY            = acceleration(0.0, -3.711);
int maxX               = 6999;
int minX               = 0;

Queue emulatedSyncQueue = new Queue.from('''
6
0 100
1000 500
1500 100
3000 100
5000 1500
6999 1000
2500 2500 0 0 500 0 0'''.split("\n").toList());

void main()
{
  marsGround                 = codingGameGroundInputsToLine();
  marsLanderInitState        = codingGameLanderInitialState();
  GenomesAndResult bestChimp = findBestChimp(
      createMarsLander2FromGenome,
      marsLander2Fitness
  );

  bestChimp.result.trajectory..removeAt(0);

  stderr.writeln('# Commands: ${bestChimp.result.trajectory.length}');

  for (var i = 0; i < bestChimp.result.trajectory.length; i++) {
    stderr.writeln('Executing state: ${bestChimp.result.trajectory[i]}');
    stderr.writeln('Times: ${bestChimp.result.trajectory[i].time.sec.toInt()}');
    for(var j = 0; j < bestChimp.result.trajectory[i].time.sec.toInt(); j++) {
      print(bestChimp.result.trajectory[i]);
    }
  }
}

Lander createMarsLander2FromGenome(List<List<Gene>> genomes)
{
  var previousPower = 0,
      previousAngle = 0,
      previousSec  = 1,
      ret = new List<ControlCmd>();

  for (int i = 1; i < genomes[0].length + 1; i++) {
    var tmpPower = new Random().nextBool()
                   ? previousPower + genomes[0][i - 1].asInt(1)
                   : previousPower - genomes[0][i - 1].asInt(1),
        power = coerceAtLeast(0, coerceAtMost(4, tmpPower));

    var tmpAngle = new Random().nextBool()
                   ? previousAngle + genomes[1][i - 1].asInt(15)
                   : previousAngle - genomes[1][i - 1].asInt(15),
        angle = coerceAtLeast(-15, coerceAtMost(15, tmpAngle));

    var tmpSec = //previousSec - genomes[2][i - 1].asInt(9),
    new Random().nextBool()
                   ? previousSec + genomes[2][i - 1].asInt(9)
                   : previousSec - genomes[2][i - 1].asInt(9),
          sec = coerceAtLeast(1, coerceAtMost(10, tmpSec)).toDouble();

    ret.add(new ControlCmd(power, angle, new Time(sec)));
    previousPower = power;
  }

  return new Lander(marsLanderInitState, ret, marsGround);
}

double marsLander2Fitness(Lander lander)
{
  double fitness = double.NEGATIVE_INFINITY;

  switch (lander.flyState) {
    case FlyState.Landed:
      fitness = lander.trajectory.last.fuel.toDouble();

      break;
    case FlyState.Flying:
      var negPosY    = -lander.trajectory.last.position.y,
          landZoneY  = marsGround.landingZone.first.y,
          fitnessY   = negPosY + landZoneY,
          landZoneX1 = marsGround.landingZone.first.x,
          landZoneX2 = marsGround.landingZone.second.x,
          landerX    = lander.trajectory.last.position.x,
          xSpeed     = lander.trajectory.last.speed.xSpeed,
          fitnessX   = landerX < landZoneX1
                        ? landerX - landZoneX1 + xSpeed
                        : landerX > landZoneX2
                          ? landZoneX2 - landerX - xSpeed
                          : 0;

      fitness = fitnessY + fitnessX;

      break;
    case FlyState.Crashed:
      var last        = lander.trajectory.last,
          ySpeedTmp   = last.speed.ySpeed,
          ySpeed      = ySpeedTmp < 0 ? ySpeedTmp : -ySpeedTmp,
          landZoneY   = marsGround.landingZone.first.y,
          landerY     = last.position.y,
          fitnessY    = landerY > landZoneY ? landZoneY - landerY : landerY - landZoneY,

          xSpeed      = last.speed.xSpeed,
          landZoneX1  = marsGround.landingZone.first.x,
          landZoneX2  = marsGround.landingZone.second.x,
          landerX     = last.position.x,
          fitnessX    = landerX < landZoneX1
                        ? landerX - landZoneX1 + xSpeed
                        : landerX > landZoneX2
                          ? landZoneX2 - landerX - xSpeed
                          : -xSpeed.abs() + 20;

      fitnessY = fitnessY + ySpeed + 40;
      fitness  = fitnessY + fitnessX;

      break;
  }

  return fitness;
}

Lander createMarsLander1FromGenome(List<List<Gene>> genomes)
{
  var previousPower = 0,
      ret = new List<ControlCmd>();

  for (int i = 1; i < genomes[0].length + 1; i++) {
//    var tmpPower = new Random().nextBool()
//                   ? previousPower + genome[i - 1].asInt(1)
//                   : previousPower - genome[i - 1].asInt(1),
    var tmpPower = previousPower + genomes[0][i - 1].asInt(1),
        power = coerceAtMost(4, tmpPower);
    ret.add(new ControlCmd(power, 0));
    previousPower = power;
  }

  return new Lander(marsLanderInitState, ret, marsGround);
}

double marsLander1Fitness(Lander lander)
{
  double fitness = double.NEGATIVE_INFINITY;

  switch (lander.flyState) {
    case FlyState.Landed:
      fitness = lander.trajectory.last.fuel.toDouble();

      break;
    case FlyState.Flying:
      var negPosY   = -lander.trajectory.last.position.y,
          landZoneY = marsGround.landingZone.first.y;

      fitness = negPosY + landZoneY;

      break;
    case FlyState.Crashed:
      var last = lander.trajectory.last,
          pos1 = marsGround.landingZone.first.y,
          pos2 = last.position.y,
          pos3 = last.speed.ySpeed + 40;

      fitness = pos1 - pos2 + pos3;

      break;
  }

  return fitness;
}

GenomesAndResult findBestChimp(Function create, Function fitness)
{
  List<GenomesAndResult> population = new List<GenomesAndResult>(populationSize);

  for (var i = 0; i < populationSize; i++)
  {
    population[i] = new GenomesAndResult(
        [
          buildGenome(genomeSize),
          buildGenome(genomeSize),
          buildGenome(genomeSize)
        ],
        create);
  }

  population..sort((a, b) => (fitness(b.result) - fitness(a.result)).toInt());

  logFitness(population, fitness);

  var chimpsFewGenerationsLater =
  new List(generationsCount).fold(population, (pop, next)
  {
    var nextGen = buildNextGeneration(pop, create)..sort((a, b) =>
    (fitness(b.result) - fitness(a.result)).toInt());

    logFitness(nextGen, fitness);

    return nextGen;
  });

  return chimpsFewGenerationsLater.first;
}

class Point
{

  double x;
  double y;

  Point(this.x, this.y);

  Point operator +(Vector vector) => new Point(x + vector.dx, y + vector.dy);

  Vector operator -(Point point) => new Vector(x - point.x, y - point.y);

  double distanceTo(Point point) => (point - this).length;
}

class Vector
{

  double dx;
  double dy;

  double get length => sqrt(dx * dx + dy * dy);

  Vector(this.dx, this.dy);

  Vector operator +(Vector vector) =>
      new Vector(dx + vector.dx, dy + vector.dy);

  Vector operator *(double times) => new Vector(dx * times, dy * times);

  Vector rotate(Angle angle) => new Vector(
      dx * cos(angle.rad) - dy * sin(angle.rad),
      dx * sin(angle.rad) + dy * cos(angle.rad));
}

class Angle
{
  double _rad;

  num get rad => toDegrees(_rad);

  Angle(this._rad);
}

class Line
{

  List<Point> points;

  Line(List<Point> points) {
    if (points.length < 2) {
      throw new Exception('Should have 2 points at minimum.');
    }

    this.points = points;
  }

  operator >(Point point) {
    var distance = (_getYforX(point.x) - point.y).toInt();
    return distance >= 0 ? true : false;
  }

  isHorizontalAtX(double x)
  {
    Pair segment = _getSegmentFor(x);

    if (segment == null) {
      return false;
    }

    return segment.first.y == segment.second.y;
  }

  Pair _getSegmentFor(double x)
  {
    var p1 = points.firstWhere((p1) {
      var isP1 = p1.x <= x,
          p2 = points.elementAt(points.indexOf(p1) + 1),
          isP2 = x <= p2.x;
      return isP1 && isP2;
    });

    var p2 = points.elementAt(points.indexOf(p1) + 1);

    return new Pair(p1, p2);
  }

  double _getYforX(double x)
  {
    Pair segment = _getSegmentFor(x);

    if (segment == null) {
      return 0.0;
    }

    return segment.first.y +
           (x - segment.first.x) * (segment.second.y - segment.first.y) /
           (segment.second.x - segment.first.x);
  }

  Pair get landingZone {
    Pair pair;

    for (var i = 0; i < points.length - 1; i++) {
      if (points[i].y == points[i + 1].y) {
        pair = new Pair(points[i], points[i + 1]);
      }
    }

    return pair;
  }
}

class Pair
{
  var first;
  var second;

  Pair(this.first, this.second);

  toString() => '${first} ${second}';

  toList() => [first, second];
}

class Gene
{
  double random;

  Gene([random]) {
    if (random == null || !random is double)
    {
      this.random = new Random().nextDouble();
    }
    else
    {
      this.random = random;
    }
  }

  asInt(int max) => (random * (max + 1)).toInt();
}

class GenomesAndResult
{
  List<List<Gene>> genomes;
  var result;

  GenomesAndResult(List<List<Gene>> genomes, Function create)
  {
    this.genomes = genomes;
    this.result = create(genomes);
  }
}

class ControlCmd
{
  int power;
  int angle;
  Time time = new Time(1.0);

  ControlCmd([this.power = 0, this.angle = 0, this.time]);
}

class State
{
  int fuel;
  int power;
  int angle;
  Particule particule;
  Time time;

  State(this.fuel, this.power, this.angle, this.particule, [this.time]);

  Point get position => particule.position;

  Speed get speed => particule.speed;

  State computeNextState(ControlCmd cmd, [Time time])
  {
    if (time == null)
    {
      time = new Time(1.0);
    }

    var tmpNewAngle = coerceAtMost(15, coerceAtLeast(-15, cmd.angle - angle)),
        newAngle = angle + tmpNewAngle,
        tmpNewPower = coerceAtLeast(-1, coerceAtMost(1, cmd.power - power)),
        newPower = power + tmpNewPower,
        thrustAcceleration = new Acceleration(
            (new Vector(0.0, 1.0) * newPower.toDouble()).rotate(
                intToAngle(newAngle))),
        acceleration = GRAVITY + thrustAcceleration,
        newParticule = particule.accelerate(acceleration, time),
        newFuel = fuel - newPower * time.sec.toInt();

    return new State(newFuel, newPower, newAngle, newParticule, time);
  }

  toString() => '$angle $power';
}

enum FlyState
{
  Landed,
  Crashed,
  Flying
}

class Lander
{
  State initState;
  List<ControlCmd> cmds;
  Line ground;

  List<State> trajectory = [];
  var flyState           = FlyState.Flying;

  Lander(initState, cmds, ground)
  {
    this.initState = initState;
    this.cmds      = cmds;
    this.ground    = ground;

    trajectory.add(initState);

    computeTrajectory();
  }

  void computeTrajectory()
  {
    for (var i = 0; i < cmds.length; i++)
    {
      var nextState = trajectory[i].computeNextState(cmds[i], cmds[i].time);

      trajectory.add(nextState);

      if (evaluateOutside(nextState)) return;
      if (evaluateHitTheGround(nextState)) return;
      if (evaluateNoFuel(nextState)) return;
    }
  }

  bool evaluateOutside(State state)
  {
    if (state.position.x > maxX || state.position.x < minX)
    {
      flyState = FlyState.Crashed;

      return true;
    }

    return false;
  }

  bool evaluateHitTheGround(State nextState)
  {
    if (ground > nextState.position)
    {
      if (nextState.angle == 0
          && nextState.speed.ySpeed > -40
          && nextState.speed.xSpeed.abs() <= 20
          && ground.isHorizontalAtX(nextState.position.x))
      {
        flyState = FlyState.Landed;
      }
      else
      {
        flyState = FlyState.Crashed;
      }

      return true;
    }

    return false;
  }

  bool evaluateNoFuel(State nextState)
  {
    if (nextState.fuel <= 0)
    {
      flyState = FlyState.Crashed;

      return true;
    }

    return false;
  }
}

class Time
{
  final double sec;

  Time(this.sec);
}

class Speed
{
  Vector direction;

  double get xSpeed => direction.dx;
  double get ySpeed => direction.dy;

  Speed(this.direction);

  operator +(Speed speed) => new Speed(direction + speed.direction);

  toString() => "(${xSpeed.toStringAsFixed(2)}, ${ySpeed.toStringAsFixed(2)})";
}

class Acceleration
{

  Vector vector;

  Acceleration(this.vector);

  operator *(Time time) => new Speed(vector * time.sec);

  operator +(Acceleration acceleration) =>
      new Acceleration(vector + acceleration.vector);

}

class Particule
{
  Point position;
  Speed speed;

  Particule(this.position, this.speed);

  Particule accelerate(Acceleration acceleration, Time time)
  {
    Speed newSpeed = speed + acceleration * time;
    Point newPosition = position +
                        speed.direction * time.sec +
                        acceleration.vector * time.sec * time.sec * 0.5;

    return new Particule(newPosition, newSpeed);
  }

  toString() =>
      " x=${position.x.toStringAsFixed(2)} y=${position.y.toStringAsFixed(
          2)} speed=${speed}";
}

List<Gene> buildGenome(int size)
{
  var genome = new List<Gene>(size);

  for (var i = 0; i < size; i++) {
    genome[i] = new Gene();
  }

  return genome;
}

List<GenomesAndResult> buildNextGeneration(
    List<GenomesAndResult> population,
    Function create
    )
{
  var newPop = new List<GenomesAndResult>.from(population),
      elitismOffset = elitism == true ? 1 : 0;

  for (var i = elitismOffset; i < population.length; i++)
  {
    var genomes1 = select(population).genomes,
        genomes2 = select(population).genomes,
        genomes   = new List(genomes1.length);

    for (var j = 0; j < genomes1.length; j++) {
      var genome = crossover(genomes1[j], genomes2[j]);
      genome = mutate(genome);
      genomes[j] = genome;
    }

    newPop[i] = new GenomesAndResult(genomes, create);
  }

  return newPop;
}

GenomesAndResult select(List<GenomesAndResult> population)
{
  for (var i = 0; i < population.length; i++)
  {
    if (new Random().nextDouble() <=
        selectionRatio * (population.length - i) / population.length) {
      return population[i];
    }
  }

  return population.first;
}

List<Gene> crossover(List<Gene>genome1, List<Gene> genome2)
{
  var genome = new List<Gene>(genome1.length);

  for (var i = 0; i < genome1.length; i++) {
    if (new Random().nextDouble() <= uniformRate)
    {
      genome[i] = genome1[i];
    }
    else
    {
      genome[i] = genome2[i];
    }
  }

  return genome;
}

List<Gene> mutate(List<Gene> genome)
{
  for (var i = 0; i < genome.length; i++)
  {
    if (new Random().nextDouble() <= mutationRate)
    {
      genome[i] = new Gene();
    }
  }

  return genome;
}

void logFitness(List<GenomesAndResult> population, Function fitness)
{
  if (log) {
    var msg = '';

    for (var i = 0; i < population.length; i++) {
      msg += fitness(population[i].result).toInt().toString().padRight(5) + ' ';
    }

    stderr.writeln(msg);
  }
}

num toRadians(num degrees) => degrees * PI / 180.0;

num toDegrees(num radians) => radians * 180.0 / PI;

int coerceAtLeast(int minimumValue, int checkValue) =>
    checkValue < minimumValue ? minimumValue : checkValue;

int coerceAtMost(int maximumValue, int checkValue) =>
    checkValue > maximumValue ? maximumValue : checkValue;

Angle intToAngle(int integer) => new Angle(toRadians(integer.toDouble()));

Speed speed(double xSpeed, double ySpeed) => new Speed(new Vector(xSpeed, ySpeed));

Acceleration acceleration(double xAcc, double yAcc) =>
    new Acceleration(new Vector(xAcc, yAcc));

Particule particule(double x, double y, Speed s) =>
    new Particule(new Point(x, y), s);

Line codingGameGroundInputsToLine()
{
  List inputs;
  var points   = new List<Point>(),
      surfaceN = int.parse(readString());

  for (int i = 0; i < surfaceN; i++)
  {
    inputs       = readString().split(' ');
    double landX = int.parse(inputs[0]).toDouble();
    double landY = int.parse(inputs[1]).toDouble();

    points.add(new Point(landX, landY));
  }

  return new Line(points);
}

State codingGameLanderInitialState()
{
  List inputs   = readString().split(' ');
  double X      = double.parse(inputs[0]);
  double Y      = double.parse(inputs[1]);
  double hSpeed = double.parse(inputs[2]);
  double vSpeed = double.parse(inputs[3]);
  int fuel      = int.parse(inputs[4]);
  int rotate    = int.parse(inputs[5]);
  int power     = int.parse(inputs[6]);

  return new State(fuel, power, rotate, particule(X, Y, speed(hSpeed, vSpeed)));
}

String getHostName() => Platform.localHostname;

bool isLocalHost() => localHosts.contains(getHostName());

bool isDebug() => isLocalHost();

String readEmulatedSync() => emulatedSyncQueue.removeFirst();

String readLineSync() {
  String line = stdin.readLineSync();
  if(isDebug()) stderr.writeln(line);
  return line;
}

String readString() => isLocalHost()
                       ? readEmulatedSync()
                       : readLineSync();

int readInt() => int.parse(readString());