C Programming Tutorial: Using Stacks and Trees to Solve a Ship Layout Problem

Introduction: Navigating the New Ship Layout

Imagine you're the captain of a newly repaired spaceship. The repair crew has rearranged the interior, and you need to figure out how many rooms can be used as sleeping quarters and the total distance from those rooms to the main entrance. In programming terms, this is a classic problem that combines stacks and trees in C. In this tutorial, we'll walk through the solution step by step, using the input format from the assignment: a list of room IDs ending with -1. We'll build a tree, track parent-child relationships, and compute the required outputs efficiently.

This problem is similar to analyzing a social network where you want to find leaf nodes (users with no followers) and their distance from a central hub. Or think of it like a video game map where you need to find all dead ends and how far they are from the starting point.

Understanding the Input and Output

The input is a series of integers, each on its own line, terminated by -1. These integers represent the order in which an employee visited rooms. The employee starts at the main entrance (the last ID before -1) and walks each corridor exactly twice. The graph is a tree: there is exactly one path between any two rooms.

We need to output two integers: the number of possible sleeping quarters and the sum of distances (in corridors) from each quarter to the main entrance. A quarter is a room that has no children—meaning no other room must pass through it to reach the entrance.

Key Data Structures: Stack and Tree

We'll use a stack to track the path from the main entrance to the current room. The stack's size at any point gives the depth (distance) of the current room. We'll also store for each room:

parent: the room visited just before it (toward the entrance)
depth: distance from the main entrance
children count: number of rooms that have this room as parent

Since room IDs are integers, we can use a hash map or a simple array if IDs are bounded. For simplicity, we'll assume IDs fit in a reasonable range and use arrays indexed by ID. Alternatively, use a dynamic data structure like a linked list.

Algorithm Overview

Read the input IDs until -1.
Initialize arrays for parent, depth, and children count (set to -1, 0, 0).
Use a stack (array with top pointer) to simulate the traversal.
For each ID:
- If the stack is empty (first room), push it with depth 0.
- Else, check the top of the stack:
  - If the top is the parent of the current ID (i.e., the current ID is a child), set parent[current] = top, depth[current] = depth[top] + 1, increment children count of top, and push current.
  - If the top is the current ID itself (returning to a room), pop the stack (leave the room).
  - Otherwise, the current ID is a sibling or other; this case shouldn't happen in a valid traversal, but we can handle by popping until we find the parent.
After processing all IDs, iterate over all rooms that were visited. A room is a quarter if it has no children (children count == 0) and it is not the entrance. Sum the depths of such rooms, and count them.
Output the count and sum.

Step-by-Step Example

Let's trace the first sample input:

Main entrance is 1. Start with stack empty.

Read 1: Stack empty, push 1 (depth 0). Stack: [1]
Read 3: Top is 1. 3 is not 1, so set parent[3]=1, depth[3]=1, children[1]++, push 3. Stack: [1,3]
Read 1: Top is 3. 1 is not 3, but 1 is the parent of 3 (since parent[3]=1). So we pop 3 (leaving room 3). Stack: [1]
Read 10: Top is 1. 10 is not 1, set parent[10]=1, depth[10]=1, children[1]++, push 10. Stack: [1,10]
Read 4: Top is 10. 4 not 10, parent[4]=10, depth[4]=2, children[10]++, push 4. Stack: [1,10,4]
Read 8: Top is 4. 8 not 4, parent[8]=4, depth[8]=3, children[4]++, push 8. Stack: [1,10,4,8]
Read 4: Top is 8. 4 is parent of 8? parent[8]=4, so pop 8. Stack: [1,10,4]
Read 10: Top is 4. 10 is parent of 4? parent[4]=10, so pop 4. Stack: [1,10]
Read 1: Top is 10. 1 is parent of 10? parent[10]=1, so pop 10. Stack: [1]
Read 5: Top is 1. 5 not 1, parent[5]=1, depth[5]=1, children[1]++, push 5. Stack: [1,5]
Read 1: Top is 5. 1 is parent of 5, so pop 5. Stack: [1]
Read -1: End of input.

Now rooms visited: 1,3,4,5,8,10. Children counts: 1 has children 3,10,5 → children[1]=3; 10 has child 4 → children[10]=1; 4 has child 8 → children[4]=1; 3,5,8 have 0 children. Quarters are rooms with no children and not entrance: 3,5,8. Depths: depth[3]=1, depth[5]=1, depth[8]=3. Sum = 5. Output: 3 5.

Implementation Details in C

We'll write a C program that reads from stdin and writes to stdout. Use a stack implemented as an array with an integer top. Since we don't know the maximum number of rooms, we can allocate dynamic arrays or use a large fixed size (e.g., 10000). For simplicity, we'll assume IDs are positive and less than 1000. We'll use arrays of size 1000 for parent, depth, children. Initialize parent to -1 (unvisited).

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

#define MAX_ID 1000

int main() {
    int stack[MAX_ID];
    int top = -1;
    int parent[MAX_ID];
    int depth[MAX_ID];
    int children[MAX_ID];
    int visited[MAX_ID] = {0}; // track which IDs appear
    int id, entrance;

    // Initialize arrays
    for (int i = 0; i < MAX_ID; i++) {
        parent[i] = -1;
        depth[i] = 0;
        children[i] = 0;
    }

    // Read input
    while (scanf("%d", &id) == 1 && id != -1) {
        visited[id] = 1;
        if (top == -1) {
            // First room is entrance
            stack[++top] = id;
            depth[id] = 0;
            parent[id] = -1;
        } else {
            int top_id = stack[top];
            if (top_id == id) {
                // Returning to parent, pop
                top--;
            } else if (parent[top_id] == id) {
                // Current id is the parent of top_id, so we are going back to parent
                // Pop top_id
                top--;
            } else {
                // New child
                parent[id] = top_id;
                depth[id] = depth[top_id] + 1;
                children[top_id]++;
                stack[++top] = id;
            }
        }
    }

    // Find entrance: the last ID before -1 (we stored it as the first pushed? Actually we can track separately)
    // Better: store entrance as the first ID read.
    // But in sample, entrance is last before -1. So we need to read all IDs into an array first.
    // For simplicity, we'll adjust: read all IDs into an array, then process.
    // However, the above loop processes on the fly. We need to know entrance before processing.
    // Let's restructure: read all IDs into a list, then process.
    // We'll rewrite below.

    return 0;
}

Complete Corrected Implementation

To correctly handle the entrance being the last ID before -1, we should first read all IDs into an array, then process. Here's a complete program:

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

#define MAX_IDS 10000
#define MAX_ID_VAL 10000

int main() {
    int ids[MAX_IDS];
    int n = 0;
    int id;
    while (scanf("%d", &id) == 1 && id != -1) {
        ids[n++] = id;
    }
    if (n == 0) return 0;
    int entrance = ids[n-1]; // last ID is entrance

    int parent[MAX_ID_VAL];
    int depth[MAX_ID_VAL];
    int children[MAX_ID_VAL];
    int visited[MAX_ID_VAL] = {0};

    for (int i = 0; i < MAX_ID_VAL; i++) {
        parent[i] = -1;
        depth[i] = 0;
        children[i] = 0;
    }

    int stack[MAX_IDS];
    int top = -1;

    // Process each ID
    for (int i = 0; i < n; i++) {
        int current = ids[i];
        visited[current] = 1;
        if (top == -1) {
            stack[++top] = current;
            depth[current] = 0;
            parent[current] = -1;
        } else {
            int top_id = stack[top];
            if (top_id == current) {
                // leaving room: pop
                top--;
            } else if (parent[top_id] == current) {
                // going back to parent
                top--;
            } else {
                // new child
                parent[current] = top_id;
                depth[current] = depth[top_id] + 1;
                children[top_id]++;
                stack[++top] = current;
            }
        }
    }

    int quarter_count = 0;
    int total_distance = 0;
    for (int i = 0; i < MAX_ID_VAL; i++) {
        if (visited[i] && i != entrance && children[i] == 0) {
            quarter_count++;
            total_distance += depth[i];
        }
    }

    printf("%d %d\n", quarter_count, total_distance);
    return 0;
}

Testing with Samples

Compile with: gcc -std=gnu11 -lm program.c -o program. Run and provide sample input:

echo -e "1\n3\n1\n10\n4\n8\n4\n10\n1\n5\n1\n-1" | ./program

Output: 3 5. Second sample:

echo -e "8\n2\n4\n5\n4\n6\n4\n2\n8\n-1" | ./program

Output: 2 6.

Time and Space Complexity

We process each ID once, O(N) where N is the number of IDs. Space is O(max ID value) for arrays, which is acceptable for typical constraints.

Common Pitfalls

Not initializing arrays properly: parent must be -1 for unvisited rooms.
Confusing the entrance: the last ID before -1 is the entrance, not the first.
Forgetting that a room can be visited multiple times; we must handle returning to parent correctly.
Using recursion could cause stack overflow; iterative stack is safer.

Conclusion

By using a stack to simulate the traversal and a tree structure to track parent-child relationships, we efficiently compute the number of possible sleeping quarters and their total distance from the entrance. This approach is not only useful for this assignment but also for any problem involving tree construction from a depth-first traversal. Just like navigating a new social media feature or a video game dungeon, understanding the underlying structure is key. Happy coding!