Airplane fuel-efficiency

[itsme86]

Just for fun I figured I'd solve the problem outlined here

Here's my solution:

#include <stdio.h>
#include <stdlib.h>

#define VCRUISE   400
#define AOPT       30
#define GPHOPT   2000
#define GPHEXTRA   10
#define CLIMBCOST  50

double tailwind(int altitude, int tail20, int tail40)
{
  double windinc;

  windinc = ((double)tail40 - tail20) / 20;
  altitude -= 20;

  return tail20 + windinc * altitude;
}

int climbcost(int climb)
{
  return climb * CLIMBCOST;
}

double planespeed(double tailwind)
{
  return VCRUISE + tailwind;
}

double legtime(int tailwind, int leglen)
{
  return leglen / planespeed(tailwind);
}

int fuelconsumphour(int altitude)
{
  int altdiff;

  altdiff = AOPT - altitude;
  if(altdiff < 0)
     altdiff = -altdiff;

  return GPHOPT + (GPHEXTRA * altdiff);
}

double fuelconsumpleg(int altitude, double ltime)
{
  return climbcost(altitude) + fuelconsumphour(altitude) * ltime;
}

int main(void)
{
  struct
  {
    int altitude;
    double fuelcost;
  } legs[10];
  char buf[4096];
  int nflights, nlegs;
  int leglen, tail20, tail40;
  int altitude;
  double wind, legfuel, flightfuel, ltime;
  int i, j;

  fgets(buf, sizeof(buf), stdin);
  nflights = atoi(buf);

  for(i = 0;i < nflights;++i)
  {
    fgets(buf, sizeof(buf), stdin);
    nlegs = atoi(buf);

    for(j = 0;j < nlegs;++j)
    {
      fgets(buf, sizeof(buf), stdin);
      sscanf(buf, "%d %d %d", &leglen, &tail20, &tail40);

      for(altitude = 20;altitude <= 40;++altitude)
      {
        wind = tailwind(altitude, tail20, tail40);
        ltime = legtime(wind, leglen);
        legfuel = fuelconsumpleg(altitude, ltime);

        if(altitude == 20 || legfuel < legs[j].fuelcost)
        {
          legs[j].altitude = altitude;
          legs[j].fuelcost = legfuel;
        }
      }
    }

    printf("Flight %d: ", i+1);
    for(flightfuel = 0, j = 0;j < nlegs;++j)
    {
      printf("%d ", legs[j].altitude);
      flightfuel += legs[j].fuelcost;
    }
    printf("%.0f\n", flightfuel);
  }

  return 0;
}

For their test data I get this:

Flight 1: 35 20 15235
Flight 2: 20 30 30 26002

instead of what they get:

Flight 1: 35 30 13985
Flight 2: 20 30 40 23983

I can't seem to find what I'm doing wrong. I blame the fact that it's Monday. I tried some debugging. I threw a printf() in the middle of the altitude loop, but it looks right and the calculations add up. I'm beginning to think I'm misunderstanding the instructions, but I can't find my fault there either.

Anyone see what I'm missing?

[Dave Evans]

Just for fun I figured I'd solve the problem outlined here


For their test data I get this:

Flight 1: 35 20 15235
Flight 2: 20 30 30 26002

instead of what they get:

Flight 1: 35 30 13985
Flight 2: 20 30 40 23983

I can't seem to find what I'm doing wrong. I blame the fact that it's Monday. I tried some debugging. I threw a printf() in the middle of the altitude loop, but it looks right and the calculations add up. I'm beginning to think I'm misunderstanding the instructions, but I can't find my fault there either.

Anyone see what I'm missing?

Maybe each leg starts at the altitude of the previous leg (that is, the individual legs represent course changes or other corrections, not new landings and takeoffs).

Look at flight #1:

At the end of leg 1, the plane is at 35,000 feet. Since this is above the optimum altitude, and there is no penalty for going down to the optimum altitude (and there is no tailwind for the second leg), it is "obvious" that the best altitude for leg #2 is 30,000 ft. Your program calculates the climb penalty for leg 2 from 0 feet altitude , not from the altitude at the end of leg 1.

Worth considering?

Regards,

Dave

[pianorain]

I'd have to agree with Dave on this one. After making a few changes to your code, I came up with some numbers that looked closer to their sample output. I don't think I'm calculating anything incorrectly, though.

//changes
int climbcost(int climb)
{
    return (climb > 0 ? climb * CLIMBCOST : 0);
}

double fuelconsumpleg(int start_altitude, int end_altitude, double ltime)
{
  return climbcost(end_altitude - start_altitude) + fuelconsumphour(end_altitude) * ltime;
}

//in main
//...snip
      for(altitude = 20;altitude <= 40;++altitude)
      {
        wind = tailwind(altitude, tail20, tail40);
        ltime = legtime((int)wind, leglen);

        //first leg is from altitude 0, subsequent legs are from previous leg altitude
        legfuel = fuelconsumpleg((j == 0 ? 0 : legs[j-1].altitude), altitude, ltime);

        if(altitude == 20 || legfuel < legs[j].fuelcost)
        {
          legs[j].altitude = altitude;
          legs[j].fuelcost = legfuel;
        }
      }
//...snip

//input
2
2
1500 -50 50
1000 0 0
3
1000 50 0
2000 0 20
1800 50 100

//Output
Flight 1: 35 30 13985
Flight 2: 20 30 30 23502

It looks like a better route than the one the sample output suggests, but I could have made a logical error in calculation.

[itsme86]

Brilliant! Thank you. With the new calculations it almost works correctly. Flight 2 is still a bit off, but I can probably find the problem now.

EDIT: pianorain, I get the exact same output with mine.

[pianorain]

After a bit of modification, it's simple to check their output and see that it's the incorrect answer.

int main(void)
{
  struct
  {
    int altitude;
    double fuelcost;
  } legs[10];
  char buf[4096];
  int nflights, nlegs;
  int leglen, tail20, tail40;
  int altitude;
  double wind, legfuel, flightfuel, ltime;
  int i, j;

  fgets(buf, sizeof(buf), stdin);
  nflights = atoi(buf);

  for(i = 0;i < nflights;++i)
  {
    fgets(buf, sizeof(buf), stdin);
    nlegs = atoi(buf);

    for(j = 0;j < nlegs;++j)
    {
      fgets(buf, sizeof(buf), stdin);
      sscanf(buf, "%d %d %d %d", &leglen, &tail20, &tail40, &altitude);

        wind = tailwind(altitude, tail20, tail40);
        ltime = legtime((int)wind, leglen);
        legfuel = fuelconsumpleg((j == 0 ? 0 : legs[j-1].altitude), altitude, ltime);

          legs[j].altitude = altitude;
          legs[j].fuelcost = legfuel;
    }

    printf("Flight %d: ", i+1);
    for(flightfuel = 0, j = 0;j < nlegs;++j)
    {
      printf("%d ", legs[j].altitude);
      flightfuel += legs[j].fuelcost;
    }
    printf("%.0f\n", flightfuel);
  }

  return 0;
}

//input
2
3
1000 50 0 20
2000 0 20 30
1800 50 100 30
3
1000 50 0 20
2000 0 20 30
1800 50 100 40

//output
Flight 1: 20 30 30 23502
Flight 2: 20 30 40 23983

As you can see, itsme86, your program generates the correct answer. The sample output on the site is incorrect.

[itsme86]

That's the conclusion I'm drawing also. Thanks for your help!

[Dave Evans]

After a bit of modification, it's simple to check their output and see that it's the incorrect answer.

As you can see, itsme86, your program generates the correct answer. The sample output on the site is incorrect.

That's real teamwork!.

I "reverse-engineered" the first flight results to deduce one possibility for an algorithm adjustment. I noticed that my answer for flight 2 was demonstrably better than the published result, but didn't try to figure out what happened there.

Then pianorain "reverse-engineered" the results for flight 2 to make an adjustment in the input data.

As I learned in a lab that I took about a thousand years ago: "If you know the right answer, you can get the right answer."

Back in those days the phrase "reverse-engineering" was not in my lexicon; we called it "dry-labbing".

(By the way --- since the creator of the problem also created the posted solution, I have to wonder: is there another way to intrepret the problem statement to come up with the posted solution with the given input data? Maybe someone should ask...)

Regards,

Dave