pandp.c

#include <stdio.h>
#include <math.h>

#define FILE_NAME_LENGTH 25

struct pub {
    int cost;
    int reward;
    int x;
    int y;
};

/**
    Function to sort pubs ascendingly based on cost. Uses insertion sort.
*/
void sortPubs(struct pub pubs[], int n) {
    int i, j, key;
    for (i = 1; i < n; i++) {
        key = pubs[i].cost;
        int r = pubs[i].reward, x = pubs[i].x, y = pubs[i].y;
        j = i - 1;
        while (j >= 0 && pubs[j].cost > key) {
            // move higher costs to the right
            // following lines equivalent to pubs[j + 1] = pubs[j];
            pubs[j + 1].cost = pubs[j].cost;
            pubs[j + 1].reward = pubs[j].reward;
            pubs[j + 1].x = pubs[j].x;
            pubs[j + 1].y = pubs[j].y;
            j--;
        }
        // insert key to correct place
        // following lines equivalent to pubs[j + 1] = pubs[i];
        pubs[j + 1].cost = key;
        pubs[j + 1].reward = r;
        pubs[j + 1].x = x;
        pubs[j + 1].y = y;
    }
}


int main() {
    // open file
    char file_name[FILE_NAME_LENGTH];
    printf("What is the name of the game description file?\n");
    scanf("%s%*c", file_name);
    FILE *inp = fopen(file_name, "r");

    // scan N and M first
    int N, M;
    fscanf(inp, "%d %d%*c", &N, &M);
    struct pub pubs[N];
    // read all pubs
    for (int i = 0; i < N; i++) {
        struct pub p;
        fscanf(inp, "%d %d %d %d%*c", &(p.cost), &(p.reward), &(p.x), &(p.y));
        pubs[i] = p;
    }
    fclose(inp);

    // sort ascendingly on cost
    sortPubs(pubs, N);

    // initialize accumulative/state variables
    int tavern_count = 0;
    int profit = 0;
    int last_x = 0;
    int last_y = 0;
    double distance = 0;

    // loop until...
    while (1) {
        struct pub p = pubs[tavern_count];
        if (M + profit >= p.cost) {
            // we can afford this
            tavern_count++;
            profit += p.reward - p.cost;
            // distance formula
            distance += sqrt(pow(p.x - last_x, 2) + pow(p.y - last_y, 2));
            // set new position
            last_x = p.x;
            last_y = p.y;
        } else {
            // we cannot afford
            break;
        }
    }

    printf("You will travel %f miles and build %d taverns for a profit of $%d.", distance, tavern_count, profit);
    return 0;
}