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

## 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.

it 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 = 'A'; // first track name   name = '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); //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); //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;     name = name;     name = 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, "nop"))     op = 0;   else if (string_equal(tokens, "acc"))     op = 1;   else if (string_equal(tokens, "jmp"))     op = 2;   // parse the integer argument   int *arg = parse_int(tokens, 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); @*/; ```