# Shunting Problem C Language Assignment Solution, Train Problem Solution, C Program Assignment Solution.

June 28, 2024
Sarah Williams
C
Sarah is a skilled C programmer with a bachelor's degree in computer science and over 600 completed orders. Specializing in data structure implementation, she delivers meticulously crafted solutions that leverage arrays, linked lists, trees, and hash tables for effective mapping operations.
Key Topics
• Instructions
• Requirements and Specifications
Tip of the day
News

## Instructions

Objective

Write a C program to solve the shunting problem in C language.

## Requirements and Specifications

Task 1: Shunting of wagons [10 points] (Submission: shunting. cO, elements.cO, stack. h0, stack. (cO)

At the main station in Tübingen the track image from Figure 1a is shown. On track A are numbered.

Wagons which must be so manoeuvred that they ascend on track C according to their numbers sorted.

When manoeuvring, the following must be considered:

1. The shunting locomotive can only move the foremost wagon from one track to another.
2. Only the wagon number of the foremost wagon on a track can be read. Wagons behind them can not be seen.
1. Writes a shunt function that shunt any number of wagons in any order, under Be- respect of rules (a) and (b), transported from track A to C. On track C, the wagons must be sorted in ascending order. It can be assumed that at the beginning all wagons are on track A. shunt should work something like this:
1. Transport wagons from A to C until one of the wagons to be transported has reached a Number which is greater than the frontmost wagon on track C. In this case, the Wagon of track C temporarily housed on siding B. This process is repeated for a long time, with the exception of track A, there are no more wagons.
2. Check if tracks A and B are empty. If so, all wagons on track C are in ascendingOrder accommodated. Otherwise repeat step I., where now the rollers of track A and B are interchanged.

Note: Consider appropriate data structures and help functions that will help you to implement shunt- mentate. So your choice of data structures sets the signature of shunt. But it applies: used mandatory three stacks to represent the three tracks.

1. The shunting operations that your algorithm performs must be output to the terminal.
2. Format your output so that you can read per line which wagon number (w) from a Track (x) is moved to another track (y) :
3. Move (w) from (x) to (y)

For the example in Figure 1, the first four shunting operations of the algorithm would look like this:

Move 5 from A to C

Move 2 from A to C

Move 1 from A to C

Move 1 from C to B

Provide a main function that constructs at least the example train from Figure 1 and then its Shunting.

Screenshots of output

Source Code

```#use #use "elem-int.c0" #use void shunt(stack A, stack B, stack C) { char [] name = alloc_array(char, 2); name[0] = 'A'; // first track name name[1] = 'B'; // second track name while (!stack_is_empty(A) || !stack_is_empty(B)) { // move elements from A to C while(!stack_is_empty(A)) { elem x = stack_top(A); // get wagon from A // if there are wagons in C and wagon in A > wagon in C if (stack_is_empty(C) || x <= stack_top(C)) { x = stack_pop(A); // remove wagon from A print("Move "); printint(x); print(" from "); printchar(name[0]); //current track used as A print(" to C"); print("\n"); stack_push(C, x); // save in C } else { x = stack_pop(C); // remove wagon from C print("Move "); printint(x); print(" from C to "); printchar(name[1]); //current track used as B print("\n"); stack_push(B, x); // save in B } } // swap stacks A and B stack temp = A; A = B; B = temp; // swap stack names char ctemp = name[0]; name[0] = name[1]; name[1] = ctemp; } } int main() { stack A = stack_new(); stack B = stack_new(); stack C = stack_new(); // save elements in inverse order stack_push(A, 3); stack_push(A, 7); stack_push(A, 6); stack_push(A, 4); stack_push(A, 1); stack_push(A, 2); stack_push(A, 5); // shunt elements in A to C shunt(A, B, C); return 0; } Stack.c /* Stacks (LIFO) implementation */ /* stack are specific lists */ struct list { elem elem; struct list* next; }; typedef struct list* list; /* stack implementation (top/bottom pointers) */ struct stack { list top; list bottom; }; /* can we reach `to' if we start traversing from `from'? */ /* NB: endless iteration in presence of cycles! */ bool reachable(list from, list to) { for (list walk = from; walk != to; walk = walk->next) if (walk == NULL) return false; return true; } /* check the data structure invariant for stack s: bottom is reachable from top */ bool is_stack(stack s) /*@ requires s != NULL; @*/ { return s->top != NULL && s->bottom != NULL && reachable(s->top, s->bottom); } /* create a new empty stack */ stack stack_new() /*@ ensures is_stack(\result); @*/ /*@ ensures stack_is_empty(\result); @*/ { list top = alloc(struct list); /* elem/next remain at their defaults */ stack s = alloc(struct stack); s->top = top; s->bottom = top; return s; } /* does s contain elements? */ bool stack_is_empty(stack s) /*@ requires is_stack(s); @*/ { return s->top == s->bottom; } /* push e onto the top of stack s */ stack stack_push(stack s, elem e) /*@ requires is_stack(s); @*/ /*@ ensures is_stack(\result); @*/ /*@ ensures !stack_is_empty(\result); @*/ /*@ ensures stack_top(\result) == e; @*/ // !! HAS TO BE CHANGED { list top = alloc(struct list); top->elem = e; top->next = s->top; s->top = top; return s; } /* remove and return element at stack top */ elem stack_pop(stack s) /*@ requires is_stack(s); @*/ /*@ requires !stack_is_empty(s); @*/ /*@ ensures is_stack(s); @*/ { elem e = s->top->elem; /* /!\ side effect on s */ s->top = s->top->next; /* s->top now unreachable: garbage collect */ return e; } /* inspect element at stack top */ elem stack_top(stack s) /*@ requires is_stack(s); @*/ /*@ requires !stack_is_empty(s); @*/ /*@ ensures is_stack(s); @*/ { return s->top->elem; } Stack .h /* Stacks (LIFO) interface */ /* element type */ #use // !! HAS TO BE CHANGED !! //typedef string elem; /* the abstract stack type */ struct stack; typedef struct stack* stack; /* operations */ bool stack_is_empty(stack s) /* does s contain elements? */ /*@ requires s != NULL; @*/; stack stack_new() /* create new empty stack */ /*@ ensures \result != NULL && stack_is_empty(\result); @*/; elem stack_pop(stack s) /* remove element at top of s */ /*@ requires s != NULL && !stack_is_empty(s); @*/; elem stack_top(stack s) /* inspect element at top of s */ /*@ requires s != NULL && !stack_is_empty(s); @*/; stack stack_push(stack s, elem e) /* place element e on top of s */ /*@ requires s != NULL; @*/ /*@ ensures !stack_is_empty(\result); @*/ /*@ ensures stack_top(\result) == e; @*/; // !! HAS TO BE CHANGED Hash-int /* Use a cuckoo hash table to maintain a set of integers */ #use typedef int* entry; /* (pointer to) hash table entry */ typedef int key; /* entries are their own keys */ int hash(key k) { return k; } bool key_equal(key k1, key k2) { return k1 == k2; } key entry_key(entry e) /*@ requires e != NULL; @*/ { return *e; /* the element *is* the key */ } string entry_string(entry e) /*@ requires e != NULL; @*/ { return string_fromint(*e); } Hash.c /* Hash table implementation (separate chaining) */ #use /* separate chaining maintains a list in each bucket */ struct list { entry elem; /* an entry in the chain */ struct list* next; /* next entry in chain */ }; typedef struct list* list; /* the hash table itself */ struct ht { int capacity; /* hash table capacity */ list[] buckets; /* array of chains (or: "buckets") */ /* invariant: \length(buckets) == capacity */ }; /* check whether all entries in chain share the common hash value i */ bool is_chain(list chain, int i, int c) { for (; chain != NULL; chain = chain->next) if (hash(entry_key(chain->elem)) % c != i) return false; return true; } /* check whether ht is a valid hash table (all entries must be chains) */ bool is_ht(ht h) /*@ requires h != NULL; @*/ /*@ requires h->capacity > 0 && \length(h->buckets) == h->capacity; @*/ { for (int i = 0; i < h->capacity; i++) if (!is_chain(h->buckets[i], i, h->capacity)) return false; return true; } /* create a new hash table with capacity c */ ht ht_new(int c) /*@ requires c > 0; @*/ /*@ ensures is_ht(\result); @*/ { ht h = alloc(struct ht); h->capacity = c; h->buckets = alloc_array(list, c); return h; } /* search for entry with key k in hash table ht (returns NULL if key k not present in table) */ entry ht_search(ht h, key k) /*@ requires is_ht(h); @*/ /*@ ensures is_ht(h); @*/ { int b = hash(k) % h->capacity; for (list chain = h->buckets[b]; chain != NULL; chain = chain->next) if (key_equal(entry_key(chain->elem), k)) return chain->elem; return NULL; } /* insert new entry e into hash table ht */ void ht_insert(ht h, entry e) /*@ requires is_ht(h); @*/ /*@ requires e != NULL; @*/ /*@ ensures is_ht(h); @*/ { list head = alloc(struct list); key k = entry_key(e); int b = hash(k) % h->capacity; head->elem = e; head->next = h->buckets[b]; h->buckets[b] = head; } /* debugging only: print hash table */ void printht(ht h) /*@ requires is_ht(h); @*/ { list l; for (int i = 0; i < h->capacity; i++) { printf("%d\t| ", i); l = h->buckets[i]; printchar('['); if (l != NULL) { print(entry_string(l->elem)); for (l = l->next; l != NULL; l = l->next) { printchar(','); print(entry_string(l->elem)); } } println("]"); } } Interpreter .c #use #use #use #use #use #use "hash-int.c0" #use struct instruction { int op; // operation 0 = nop, 1 = acc, 2 = jmp int arg; // argument }; typedef struct instruction* instruction; struct program { instruction [] instructions; // instructions in program int instruction_count; // number of instructions in program }; typedef struct program* program; // Create new instruction and return it instruction instruction_new(int op, int arg) /*@ requires 0 <= op && op <= 2; @*/ { // allocate structure instruction inst = alloc(struct instruction); // fill in data inst->op = op; inst->arg = arg; return inst; // return allocated structure } // Parse the given line and create a new instruction instruction parse_instruction(string line) { string [] tokens = parse_tokens(line); assert(num_tokens(line) == 2); int op = -1; // convert string to operation number if (string_equal(tokens[0], "nop")) op = 0; else if (string_equal(tokens[0], "acc")) op = 1; else if (string_equal(tokens[0], "jmp")) op = 2; // parse the integer argument int *arg = parse_int(tokens[1], 10); assert(arg != NULL); return instruction_new(op, *arg); } // Load a program from the input file and return it program load_program(string input) { // create program program prog = alloc(struct program); file_t file = file_read(input); // read file assert(file != NULL); // check file was opened // read all lines in file into a queue queue q = queue_new(); // create queue prog->instruction_count = 0; // no instructions initially while (!file_eof(file)) { // read line and save in queue queue_enq(q, file_readline(file)); // increment instruction count prog->instruction_count++; } file_close(file); // close the file // create instruction array prog->instructions = alloc_array // parse all instructions for (int i = 0; i < prog->instruction_count; i++) prog->instructions[i] = parse_instruction(queue_deq(q)); return prog; } // Interpret the given program and return the resulting acccumulator value int interpret(program p) { int acc = 0; // initial value in accumulator int ip = 0; // position in program // create a new hash table for the instruction pointer ht table = ht_new(p->instruction_count); bool halt = false; while (!halt) // repeat until we need to halt /*@ loop_invariant ip >= 0 && ip <= p->instruction_count; @*/ { // load instruction instruction inst = p->instructions[ip]; // if repeated instruction if (ht_search(table, ip) != NULL) halt = true; // halt program else { entry e = alloc(int); *e = ip; ht_insert(table, e); // insert ip in hash table // if this is the instruction before the last one if (ip == p->instruction_count - 1) halt = true; // halt program if (inst->op == 0) // nop { ip++; // simply advance to next instruction } else if (inst->op == 1) // acc { acc = acc + inst->arg; // add argument to acc ip++; // advance to next instruction } else // inst->op == 2, that is, jmp { ip = ip + inst->arg; // jump to argument position after ip } } } return acc; } int main() { // load program program p = load_program("puzzle.aoc"); // interpret program int acc = interpret(p); // print the result in the accumulator print("Accumulator: "); printint(acc); print("\n"); return 0; } Queue .c /* Queues (FIFO) */ /* Queue implementation below */ /* queues are specific lists */ struct qlist { qelem elem; struct qlist* next; }; typedef struct qlist* qlist; /* queue implementation (head/back pointers) */ struct queue { qlist head; qlist back; }; /* can we reach `to' if we start traversing from `from'? */ /* NB: endless iteration in presence of cycles! */ bool reachable(qlist from, qlist to) { for (qlist walk = from; walk != to; walk = walk->next) if (walk == NULL) return false; return true; } /* check the data structure invariant for queue q: back is reachable from head */ bool is_queue(queue q) /*@ requires q != NULL; @*/ { return q->head != NULL && q->back != NULL && reachable(q->head, q->back); } /* create a new empty queue */ queue queue_new() /*@ ensures is_queue(\result); @*/ /*@ ensures queue_is_empty(\result); @*/ { qlist end = alloc(struct qlist); /* fields remain at default/NULL */ queue q = alloc(struct queue); q->head = end; q->back = end; return q; } /* does q contain elements? */ bool queue_is_empty(queue q) /*@ requires is_queue(q); @*/ { return q->head == q->back; } /* place element e at the back of q */ void queue_enq(queue q, qelem e) /*@ requires is_queue(q); @*/ /*@ ensures is_queue(q); @*/ /*@ ensures !queue_is_empty(q); @*/ { qlist end = alloc(struct qlist); q->back->elem = e; q->back->next = end; q->back = end; } /* remove and return element at head of q */ qelem queue_deq(queue q) /*@ requires is_queue(q); @*/ /*@ requires !queue_is_empty(q); @*/ /*@ ensures is_queue(q); @*/ { qelem e = q->head->elem; q->head = q->head->next; return e; } Queue .h /* Queues (FIFO) interface */ /* the abstract queue type */ struct queue; typedef struct queue* queue; /* element type */ typedef string qelem; /* operations */ bool queue_is_empty(queue q) /* does q contain elements? */ /*@ requires q != NULL; @*/; queue queue_new() /* create new empty queue */ /*@ ensures \result != NULL && queue_is_empty(\result); @*/; void queue_enq(queue q, qelem e) /* place element e at back of q */ /*@ requires q != NULL; @*/ /*@ ensures !queue_is_empty(q); @*/; qelem queue_deq(queue q) /* remove element at head of q */ /*@ requires q != NULL && !queue_is_empty(q); @*/; ```

## Related Samples

Visit our C Assignments Sample Section to find outstanding solutions designed for students facing C programming challenges. From fundamental programs to intricate algorithms, these samples highlight our expertise in providing top-notch programming assistance. Enhance your understanding and excel in C assignments with our comprehensive examples!