Be make – Developer Tools Exercise with Solution

Do make's job. You are given the time each file last changed (a bigger time is newer) and the rules, already in build order. For each rule, the target must be rebuilt if any of its prerequisites is newer than it. A rebuilt target's time becomes now, and then now goes up by 1. now starts at one more than the largest time in the input.

Input

The first line has f (1 ≤ f ≤ 50), the number of files. Each of the next f lines has a file name (up to 20 characters, no spaces) and its time (0 to 1000). The next line has r (1 ≤ r ≤ 50), the number of rules. Each rule is one line: the target, the number of prerequisites k (1 ≤ k ≤ 10), and the k prerequisite names. Every name in a rule is one of the files.

Output

For each rule, in order: rebuild TARGET or TARGET is up to date.

Examples

Example 1 · Input

6
main.c 5
stack.c 9
stack.h 2
main.o 6
stack.o 7
app 8
3
main.o 2 main.c stack.h
stack.o 2 stack.c stack.h
app 2 main.o stack.o

Expected output

main.o is up to date
rebuild stack.o
rebuild app

Example 2 · Input

2
hello.c 1
hello 2
1
hello 1 hello.c

Expected output

hello is up to date

Hints

Hint 1

Store the file names and times in arrays; find a file by comparing names with strcmp.

Hint 2

A target is rebuilt if any prerequisite has a bigger time than it.

Hint 3

A rebuilt target gets the time now, and now goes up by one each time. now starts one above the largest time read.

Solution

Show one correct solution (try it yourself first)

#include <stdio.h>
#include <string.h>

char names[50][21];
int times[50];
int f;

int find(const char *name) {
    for (int i = 0; i < f; i++)
        if (strcmp(names[i], name) == 0) return i;
    return -1;
}

int main(void) {
    int r, now = 0;
    scanf("%d", &f);
    for (int i = 0; i < f; i++) {
        scanf("%20s %d", names[i], &times[i]);
        if (times[i] >= now) now = times[i] + 1;
    }
    scanf("%d", &r);
    for (int i = 0; i < r; i++) {
        char target[21], dep[21];
        int k, stale = 0;
        scanf("%20s %d", target, &k);
        int t = find(target);
        for (int j = 0; j < k; j++) {
            scanf("%20s", dep);
            if (times[find(dep)] > times[t]) stale = 1;
        }
        if (stale) {
            printf("rebuild %s\n", target);
            times[t] = now++;
        } else {
            printf("%s is up to date\n", target);
        }
    }
    return 0;
}

Lesson: Building with make →