I have been able to read in from file and then add up the 1,2,3,4,5 route. I am having
trouble permuting the 2d array and then adding up.. I know what I want to do... it's just
not working ideally... and then I'm also getting syntax warnings on the permute function.
Requirements:
Your C program should consist of the single file, X.c (or whatever
you decide to call your program.)
Your program will read an input file (from stdin) which includes
an unspecified number of command lines which describe the graph to
be constructed. The input (file) will contain two types of commands,
and each command will be included on a single line of the file. The
commands are:
c W
a X Y Z
for Create a node and Add an edge between two nodes. The symbols
W,X,Y,Z all stand for "arbitrary" integers. Each "city" will be
"named" with a distinct integer, specifically the one included in
the "c" command. In the "a" command (add an edge) the edge should
be From X To Y, with Cost Z. To make the program a bit easier,
all the "Create" commands will precede any "Add" commands in the input
file. If you wish you can assume an upper limit of 20 cities, "named"
0-19, for this version of the program. You may also assume that the
"names" of the nodes will be consecutive integers starting at 1.
Note that this is the same format that was specified (and used) in
Part 1. (Ok, I said for Part 1 that you needed to support up to 20
cities, and I'd like you to do that again, but we won't test your
program for more than 13, because otherwise, it would take too long
(if your program actually DOES generate all legal tours that is.)
Code:
#include <stdio.h>
//prototypes
void permute(int);
void swap(int *,int*);
int noofpermutations();
int addup(int);
//global variables
int between[20+1][20+1], cities;
int minimumCost = 0;
int initCost = 0;
int main() {
char action;
int i = 1, j = 1;
int ch;
while ((ch = getchar()) != EOF) {
scanf("\n%c", &action);
if (action == 'c') {
scanf(" %d", &cities);
}
if (action == 'a') {
scanf(" %d", &i);
scanf(" %d", &j);
scanf(" %d", &between[i][j]);
}
}
int start = (cities - (cities-1));
for(i = 1; i < cities; i++) //add up the total cost
{
initCost += between[i][i+1];
}
initCost += between[start][cities];
permute(start);
printf("The shortest tour is "); //print statement
for(i = 1; i < cities+1; i++)
{
printf(" %d", i);
}
printf(" %d", start);
printf(" and costs only %d\n", minimumCost);
return 0;
}
int noofpermutations(int cities)
{
int permutations = 1, x;
for( x = 1; x <= cities; x++)
permutations = permutations * x;
return permutations;
}
void swap(int *p1,int *p2)
{ int temp;
temp = *p1;
*p1 = *p2;
*p2 = temp;
}
int addup(int start)
{
int i, totalCost = 0;
for(i = 1; i < cities; i++) //add up the total cost
{
totalCost += between[i][i+1];
}
totalCost += between[start][cities];
if (totalCost < initCost) {
return totalCost;
} else {
return initCost;
}
}
// FIGURE OUT PERMUTATION FOR 2D ARRAYS BLAHBLAHBLAH GRRRRRRR
void permute(int start)
{
int y, count = 0;
while( count < noofpermutations(cities))
{
for( y = 0; y < cities-1; y++)
{
swap( &between[y], &between[y+1]);
addup(cities);
count++;
}
swap(&between[0],&between[1]);
count++;
for(y = cities - 1; y > 0; y--)
{
swap( &between[y], &between[y-1]);
count++;
}
swap( &between[cities-1], &between[cities-2] );
count++;
}
}