Created
May 7, 2017 03:12
-
-
Save ronlobo/62c4ff566e4ecb97b427a28b56340366 to your computer and use it in GitHub Desktop.
Mars Lander Optimization for CodinGame (https://www.codingame.com/ide/puzzle/mars-lander)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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()); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment