greedy

/* VERY hardcoded version */

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define LINE_LENGTH 256 // line from input file
#define N 5 // number of cities (matrix size)

static int matrix_oriented[N][N] =
  { {-1, 174, 315, 634, 544},
    {174, -1, 152, -1, 595},
    {315, 152, -1, 393, -1},
    {634, 544, 393, -1, -1},
    {544, 595, -1, 388, -1}};

void setBit (unsigned char *byte, int pos){
  *byte = *byte | (1 << pos);
}

void clearBit (unsigned char *byte, int pos){
  *byte = *byte & (~1 << pos);
}

// returns 0 or something other than 0
int getBit (unsigned char byte, int pos){
  return byte & (1 << pos);
}

// from @startingPoint to all the other cities without visiting any twice
// returns total cost
unsigned greedy_oriented(int startingPoint){
  int i = startingPoint, j = 0;
  int holdJ, path[N] = { startingPoint }, count = 1;
  int cost = 0;
  unsigned char citiesVisited = 0; // 1 byte: least-significant bit for Timisoara,
  // most-significant bit for Bucuresti. Bit is 0 if city hasn't been visited yet
  setBit(&citiesVisited, startingPoint);
  while (citiesVisited != 0xFF){
    int minimum = INT_MAX;
    while (j < N){
      if (matrix_oriented[i][j] >= 0 && matrix_oriented[i][j] < minimum
      && (getBit(citiesVisited, j) == 0)){
    minimum = matrix_oriented[i][j];
    printf("minimum = %d\n",minimum);
    holdJ = j;
      }
    }

    j = 0;
    if (minimum == INT_MAX){
      printf("no solution\n");
      return cost;
    }

    cost += minimum;
    path[count] = holdJ;
    count++;
    setBit(&citiesVisited, holdJ);
    i = holdJ;
  }
  return cost;
}

/*void read(FILE * inputFile){
  char line[LINE_LENGTH];
  char *temp;
  unsigned i = 0, j = 0;
  fgets(line, LINE_LENGTH, inputFile); // ignoring first line
  fgets(line, LINE_LENGTH, inputFile); // ignoring second line
  fgets(line, LINE_LENGTH, inputFile);
  // parsing data now
  // while (line){
    temp = strtok(line, "|");
    while (temp){
      temp = strtok(NULL, "|");
      sscanf(temp, "%d", &matrix[i][j]);
      j++;
      printf("%d ", matrix[i][j]);
      //printf("%s",temp);
    }
    putchar('\n');
    /*fgets(line, LINE_LENGTH, inputFile);
    if(line == NULL) printf("line NULL\n");
    }*/ /*
}*/

int main(int argc, char **argv){
  /*FILE * in = fopen(argv[1], "r");
  if (in == NULL){
    printf("error opening file\nplease specify the file name or its absolute path"
       " as the first input parameter, thanks.\n");
    return -1;
  }
  read(in);
  fclose(in);*/
  greedy_oriented(1);
  return 0;
}