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:
- The shunting locomotive can only move the foremost wagon from one track to another.
- Only the wagon number of the foremost wagon on a track can be read. Wagons behind them can not be seen.
- 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:
- 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.
- The shunting operations that your algorithm performs must be output to the terminal.
- Format your output so that you can read per line which wagon number (w) from a Track (x) is moved to another track (y) :
- Move (w) from (x) to (y)
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.
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 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); @*/;