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

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); @*/;