Interesting Programming Puzzle

[DavidSnider]

You're in a Mars Lander.
The planets gravity pulls you towards it at 3.711 m/s². (So at T(1) with 0 thrust your vertical velocity is -3.711).
Your lander has 4 thrust settings: 0 m/s², 1 m/s², 2 m/s², 3 m/s², 4 m/s².
Each of these use 0, 1, 2, 3 and 4 units of fuel per second respectively.
Your lander starts at a height of 2500 meters.
You can read your altitude, speed and adjust your thrust settings once every second.
The ground is at 100m.
Your vertical landing speed needs to be between 0 and 40m/s.
For each time step what is the optimal amount of thrust to conserve fuel and still hit the ground at an acceptable speed?

(mass and rotation and other pesky real world things not contained in the problem do not apply)

https://www.codingame.com/ if you want to try this out.

 

[Borg]

I looked at the simple intro but I didn't create an account to see the game that you're referring to. Are there multiple games that you can code?

 

[Vanadium 50]

Why is this hard? And why is it a programming problem?

You want to minimize fuel, so you want to minimize the time spent with Mars accelerating you. That happens when you don't fire at all until the last minute, and that's when you go full blast. (Which is the only setting where you are actually slowing down) That point is best calculated with pencil and paper.

 

[Jarvis323]

(Which is the only setting where you are actually slowing down)

This is not generally true. The time steps and fuel choices are discrete. The first time step when you use your thrusters, it may be more efficient to not use full throttle.

Even if you could solve a general instance of this by hand, with an arbitrary discretization, faster than I can blink, it would still be better job for a computer.

 

[Khashishi]

Ah, the problem statement above didn't mention discrete time steps.

 

[Jarvis323]

You can read your altitude, speed and adjust your thrust settings once every second.

 

[mfb]

This is not generally true. The time steps and fuel choices are discrete. The first time step when you use your thrusters, it may be more efficient to not use full throttle.

Even if you could solve a general instance of this by hand, with an arbitrary discretization, faster than I can blink, it would still be better job for a computer.

This gives seven cases to investigate: reduce thrust for the last second by 1 to 3 steps, or reduce thrust for the first thrusting period by 1 to 3 steps, or go for a setting of 4 over the whole period. Write down a formula that calculates impact speed depending on those cases, plug those cases in, see what you get. A 1-line program executed 7 times. A few more lines if you want to loop over those cases in the program.

Actually solving this program would need some clarification how exactly the time steps work. With a proper integration, or with some discrete integration method? In the latter case, what happens for the last step that gets interrupted by the impact?

 

[DavidSnider]

I looked at the simple intro but I didn't create an account to see the game that you're referring to. Are there multiple games that you can code?

Yes, there are many.

 

[Vanadium 50]

That's true; I hadn't considered that this is discrete. However, if you go down that path you have to consider that the computer itself uses discrete math and will have rounding errors that also need to be considered and programmed around.

In a continuous universe, you fall for 9.58 seconds, and then blast away for the remainder of the flight (123 seconds) and hit just under the magic 40 m/s. (10.04 seconds give you a soft landing). In the discrete universe, I'd need to know a lot more about how the discretization process is done. (Are you taking values at the beginning of the time step or the middle, or something else)

 

[Jarvis323]

That's true; I hadn't considered that this is discrete. However, if you go down that path you have to consider that the computer itself uses discrete math and will have rounding errors that also need to be considered and programmed around.

In a continuous universe, you fall for 9.58 seconds, and then blast away for the remainder of the flight (123 seconds) and hit just under the magic 40 m/s. (10.04 seconds give you a soft landing). In the discrete universe, I'd need to know a lot more about how the discretization process is done. (Are you taking values at the beginning of the time step or the middle, or something else)

In that case, the best time to start the thrusters would be at t=9 seconds. You are only allowed to change the thruster setting at 1 second intervals.

 

[DavidSnider]

How do you calculate at what time to hit the thrusters?
Values are taken at the beginning of the timestep.

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
* Auto-generated code below aims at helping you parse
* the standard input according to the problem statement.
**/
class Player
{
    static void Main(string[] args)
    {
        string[] inputs;
        int surfaceN = int.Parse(Console.ReadLine()); // the number of points used to draw the surface of Mars.
        for (int i = 0; i < surfaceN; i++)
        {
            inputs = Console.ReadLine().Split(' ');
            int landX = int.Parse(inputs[0]); // X coordinate of a surface point. (0 to 6999)
            int landY = int.Parse(inputs[1]); // Y coordinate of a surface point. By linking all the points together in a sequential fashion, you form the surface of Mars.
        }
        int lastSpeed = 0;
        decimal time=0;
    
        while (true)
        {
            inputs = Console.ReadLine().Split(' ');
            int X = int.Parse(inputs[0]);
            int Y = int.Parse(inputs[1]);
            int hSpeed = int.Parse(inputs[2]); // the horizontal speed (in m/s), can be negative.
            int vSpeed = int.Parse(inputs[3]); // the vertical speed (in m/s), can be negative.
            int fuel = int.Parse(inputs[4]); // the quantity of remaining fuel in liters.
            int rotate = int.Parse(inputs[5]); // the rotation angle in degrees (-90 to 90).
            int power = int.Parse(inputs[6]); // the thrust power (0 to 4).
        
            time++;
            if(time > 12) {
                power = 4;
            }
            if(time > 59) {
                power = 3;
            }

            Console.WriteLine("0 " + power);
        
        }
    }
}

This code saves more fuel in the game than just hitting power 4 at timestep 12. Power 4 at timestep 13 crashes. It also seems that your position is rounded to the nearest meter after each step.

 

[mfb]

That code does not save fuel. With the simple "take the values from the start" calculation approach, the lander is at height 112m after 64 seconds, moving downwards with 37.5 m/s. We apply the final 3 m/s burn and land at 75 m and 38.2 m/s. Sum of thrust values: 203.

Start burning after 14 steps and keep full thrust: after 59 seconds we are at 110 m moving downwards by 38.9 m/s. Throttle to 3 to land the following second - 71 m and 39.66 m/s. Sum of thrust values: 183 (184 without final throttling).
Start burning after 14 steps, but apply just 3 thrust the first second, no throttling at the end: same fuel consumption, landing speed increases to 39.95 but stays within the limit.
Reducing thrust further would does not work, therefore testing those three cases is already sufficient to find the optimal solution.

I didn't round any values (well, at the 15th digit or whatever excel does).

 

[DavidSnider]

That code does not save fuel. With the simple "take the values from the start" calculation approach, the lander is at height 112m after 64 seconds, moving downwards with 37.5 m/s. We apply the final 3 m/s burn and land at 75 m and 38.2 m/s. Sum of thrust values: 203.

Start burning after 14 steps and keep full thrust: after 59 seconds we are at 110 m moving downwards by 38.9 m/s. Throttle to 3 to land the following second - 71 m and 39.66 m/s. Sum of thrust values: 183 (184 without final throttling).
Start burning after 14 steps, but apply just 3 thrust the first second, no throttling at the end: same fuel consumption, landing speed increases to 39.95 but stays within the limit.
Reducing thrust further would does not work, therefore testing those three cases is already sufficient to find the optimal solution.

I didn't round any values (well, at the 15th digit or whatever excel does).

I've already tested this in the game. My code lands with 310 fuel. If I remove the power=3 block it lands with 306 fuel.

 

[Vanadium 50]

In that case, the best time to start the thrusters would be at t=9 seconds.

No, t=10. If you hit at t=9. you are moving too fast. If you like, you need to fire between 9.6 and 10.4 seconds. At 10 seconds, you land. At 9.6 you hit the maximum velocity. At 10.4 you start moving up again, and then when you fall you again hit at the maximum.

 

[Jarvis323]

Here is my solution, not sure if it is correct. It's just brute force, making some naive assumptions, like that thrust should only increase with time, not decrease. And I'm not sure that the moment of impact calculation is quite right. It says to apply a thrust of 4 at t=15, and uses 180 fuel units.

#include <iostream>
#include <vector>
#include <cmath>

double naiveFindDt( double p0, double p1, double v0, double A, double lowGuess, double highGuess ) {
  
    double diff = 9999;
    while( 1 ) {
      
        double guess = lowGuess + ( highGuess - lowGuess ) / 2.0;
        double result = p0 + v0*guess + .5*A*guess*guess;
        diff = result - p1;

        if( std::abs( diff ) > .00001  ) {
            return guess;
        }
        else if( diff > 0 ) {
            highGuess = guess;
        }
        else {
            lowGuess = guess;
        }
    }
}

double solve
(
    const double GE,
    const double AG,
    const double LV,
    double elevation,
    const std::vector< int > & thrustOptions,
    double fuelUsed,
    double v_y,
    int thrust,
    int t
)
{
    double next = elevation + ( v_y + .5*( AG + thrust ) );
    if( next < GE )
    {
        double dt = naiveFindDt( elevation, GE, v_y, AG+thrust, 0, 1 );
        double landingVelocity = v_y + .5*( AG + thrust )*dt;
        if( landingVelocity >= LV )
        {
            std::cout << "landed at t=" << t+1 << std::endl;
            std::cout << "used " << fuelUsed+thrust << " units of fuel " << std::endl;
            std::cout << "velocity on impact was " << v_y + ( AG + thrust )*dt << std::endl;
            return fuelUsed + thrust;
        }

        else return -1;
    }

    double result;

    for( int i = thrust; i < thrustOptions.size(); ++i )
    {
        if ( ( result = solve(
                            GE,
                            AG,
                            LV,
                            elevation + v_y + .5 * ( AG + thrustOptions[ i ] ),
                            thrustOptions,
                            fuelUsed + thrustOptions[ i ],
                            v_y + AG + thrustOptions[ i ],
                            thrustOptions[ i ],
                            t+1
        ) ) >= 0  )
        {
            if( thrustOptions[ i ] > thrust )
            {
                std::cout << "set thrust to " << i << " at t=" << t+1 << std::endl;
            }
            return result;
        }
    }

    return -1;
}

int main()
{

    std::vector< int > thrustOptions( 5 );
    for ( int i = 0; i < 5; ++i )
    {
        thrustOptions[i] = i;
    }

    double minFuel = solve(
                         100,
                         -3.711,
                         -40,
                         2500,
                         thrustOptions,
                         0,
                         0,
                         0,
                         thrustOptions[ 0 ]
                     );
}

landed at t=59
used 180 units of fuel
velocity on impact was -39.0935
set thrust to 4 at t=15

 

[DavidSnider]

landed at t=59
used 180 units of fuel
velocity on impact was -39.0935
set thrust to 4 at t=15

Velocity on impact should be between 0 and 40 not -40.

 

[Jarvis323]

Velocity on impact should be between 0 and 40 not -40.

-40 in this output means 40 m/s towards the planet. This is not right?

 

[DavidSnider]

-40 in this output means 40 m/s towards the planet. This is not right?

No, it should be away from the planet.

 

[DavidSnider]

No, it should be away from the planet.

Ooops. I'm wrong. The original problem said:

• vertical speed must be limited ( ≤ 40m/s in absolute value)

My mistake

 

[Jarvis323]

I think it's almost correct now, but I'm getting a slightly different result than mfb. Are you sure it doesn't work to use only one unit of thrust on the last time step?

#include <iostream>
#include <vector>
#include <cmath>

double naiveFindDt( double p0, double p1, double v0, double A, double lowGuess, double highGuess ) {
    
    double diff = 9999;
    while( 1 ) {
        
        double guess = lowGuess + ( highGuess - lowGuess ) / 2.0;
        double result = p0 + v0*guess + .5*A*guess*guess;
        diff = result - p1; 

        if( std::abs( diff ) > .0000001  ) {
            return guess;
        }
        else if( diff > 0 ) {
            highGuess = guess;
        }
        else {
            lowGuess = guess;
        }
    }
}

double solve
(
    const double GE,
    const double AG,
    const double LV,
    double elevation,
    double lastElevation,
    double lastVelocity,
    const std::vector< int > & thrustOptions,
    double fuelUsed,
    double v_y,
    int thrust,
    int t
)
{
    for( int i = 0; i < thrustOptions.size(); ++i ) {
        double adjusted = lastElevation + ( lastVelocity + .5*( AG + thrustOptions[ i ] ) );
        if( adjusted < GE )
        {
            double dt = naiveFindDt( lastElevation, GE, lastVelocity, AG + thrustOptions[ i ], 0, 1 ); 
            double landingVelocity = lastVelocity + .5*( AG + thrustOptions[ i ]  )*dt;
            if( landingVelocity >= LV )
            {
                if( thrustOptions[i] != thrust ) {
                    std::cout << "set thrust to " << thrustOptions[i] << " at t=" << t << std::endl; 
                }
                std::cout << "landed at t=" << t+dt << std::endl; 
                std::cout << "used " << fuelUsed+thrustOptions[ i ]-thrust  << " units of fuel " << std::endl;              
                std::cout << "velocity on impact was " << landingVelocity << std::endl;
                return fuelUsed + thrustOptions[ i ] - thrust;
            }
            else if( thrustOptions[ i ] >= thrust ) {
                return -1;
            }
        }
    }

    double result;

    for( int i = thrust; i < thrustOptions.size(); ++i )
    {
        if ( ( result = solve(
                            GE,
                            AG,
                            LV,
                            elevation + v_y + .5 * ( AG + thrust ),
                            elevation,
                            v_y,
                            thrustOptions,
                            fuelUsed + thrustOptions[ i ],
                            v_y + AG + thrust,
                            thrustOptions[ i ],
                            t+1
        ) ) >= 0  )
        {
            if( thrustOptions[ i ] > thrust )
            {
                std::cout << "set thrust to " << i << " at t=" << t+1 << std::endl;
            }
            return result;
        }
    }

    return -1;
}

int main()
{

    std::vector< int > thrustOptions( 5 );
    for ( int i = 0; i < 5; ++i )
    {
        thrustOptions[i] = i;
    }

    double minFuel = solve(
                         100,
                         -3.711,
                         -40,
                         2500,
                         2500,
                         0,
                         thrustOptions,
                         0,
                         0,
                         0,
                         thrustOptions[ 0 ]
                     );
}

set thrust to 1 at t=59
landed at t=59.5
used 181 units of fuel 
velocity on impact was -39.9157
set thrust to 4 at t=14

 

[mfb]

No, it should be away from the planet.

You cannot land while moving away from the planet, unless you are in some cave-like structure.

I think it's almost correct now, but I'm getting a slightly different result than mfb. Are you sure it doesn't work to use only one unit of thrust on the last time step?

I'm not sure about the integration scheme, so +- 1 second is possible. Anyway, we save a lot of fuel compared to DavidSnider's solution. Yes, that solution needs more fuel if you replace all "3" by "4" but the saving occurs if you combine this change with the later onset of thrust.