Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Interesting Programming Puzzle

  1. Jan 14, 2016 #1

    DavidSnider

    User Avatar
    Gold Member

    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.
     
    Last edited: Jan 14, 2016
  2. jcsd
  3. Jan 15, 2016 #2

    Borg

    User Avatar
    Science Advisor
    Gold Member

    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?
     
  4. Jan 15, 2016 #3

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    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.
     
  5. Jan 15, 2016 #4
    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.
     
  6. Jan 15, 2016 #5
    Ah, the problem statement above didn't mention discrete time steps.
     
  7. Jan 15, 2016 #6
     
  8. Jan 15, 2016 #7

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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?
     
  9. Jan 15, 2016 #8

    DavidSnider

    User Avatar
    Gold Member

    Yes, there are many.
     
  10. Jan 15, 2016 #9

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    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)
     
  11. Jan 15, 2016 #10
    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.
     
  12. Jan 15, 2016 #11

    DavidSnider

    User Avatar
    Gold Member

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

    Code (Text):

    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.
     
  13. Jan 15, 2016 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    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).
     
  14. Jan 15, 2016 #13

    DavidSnider

    User Avatar
    Gold Member

    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.
     
  15. Jan 15, 2016 #14

    Vanadium 50

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor

    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.
     
  16. Jan 15, 2016 #15
    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.
    Code (C):

    #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 ]
                         );
    }
     
    Code (Text):

    landed at t=59
    used 180 units of fuel
    velocity on impact was -39.0935
    set thrust to 4 at t=15
     
     
  17. Jan 15, 2016 #16

    DavidSnider

    User Avatar
    Gold Member

    Velocity on impact should be between 0 and 40 not -40.
     
  18. Jan 15, 2016 #17
    -40 in this output means 40 m/s towards the planet. This is not right?
     
  19. Jan 15, 2016 #18

    DavidSnider

    User Avatar
    Gold Member

    No, it should be away from the planet.
     
  20. Jan 15, 2016 #19

    DavidSnider

    User Avatar
    Gold Member

    Ooops. I'm wrong. The original problem said:
    • vertical speed must be limited ( ≤ 40m/s in absolute value)
    My mistake
     
  21. Jan 15, 2016 #20
    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?

    Code (C):

    #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 ]
                         );
    }
     
    Code (Text):

    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
     
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Interesting Programming Puzzle
Loading...