### Problem 1: Constraint Satisfaction (50 points)

Solution by James Abbatiello :
To build : gcc hw3.c -o hw3

hw3.c

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

#define MAX_PROCS 64

typedef struct bin_s
{
bool same;
bool not_same;
int not_proc1;
int not_proc2;
} bin_t;

{
int id;
int length;
bool allow_proc[MAX_PROCS];
int proc;
int saved_proc;

int nproc;
int least_cost = INT_MAX;
int proc_costs[MAX_PROCS];

/* get a line from the console and strip off the trailing \n if present */
char *mygets(char *s, int size)
{
char *ret, *p;
ret = fgets(s, size, stdin);
if ((p = strchr(s, '\n'))) *p = '\0';
return ret;
}

int mygeti()
{
char buff[256];
mygets(buff, sizeof(buff));
return (atoi(buff));
}

/* prompts for a nonnegative integer from the user */
int prompt_int(char *prompt)
{
int ret;
for (;;)
{
printf("%s", prompt);
ret = mygeti();
if (ret > 0)
break;
}
return ret;
}

/* gets information about the problem from the user */
void get_problem_info(void)
{
char buff[256], *tok;
int i, j;

for (i = 0; i < ntasks; i++)
{
for (j = 0; j < MAX_PROCS; j++)
for (j = 0; j < ntasks; j++)
{
}

}

printf("\n");
nproc = prompt_int("number of processors: ");
for (i = 1; i <= nproc; i++)
{
sprintf(buff, "\tcost of processor %d (in dollars per sec.): ", i);
proc_costs[i] = prompt_int(buff);
}

printf("\n");

printf("\nunary constraints:\n");
for (i = 0; i < ntasks; i++)
{
int first_constraint = 0;
mygets(buff, sizeof(buff));
if (!*buff || strcmp(buff, "none") == 0)
continue;
tok = strtok(buff, ", ");
while (tok)
{
if (tok[0] == 'p' && first_constraint != 2)
{
int proc = atoi(tok + 1);
if (proc >= 0)
{
if (first_constraint == 0)
for (j = 0; j < nproc; j++)
first_constraint = 1;
}
else
printf("warning: invalid constraint: %s\n", tok);
}
else if (tok[0] == '!' && tok[1] == 'p' && first_constraint != 1)
{
int proc = atoi(tok + 2);
if (proc >= 0)
{
first_constraint = 2;
}
else
printf("warning: invalid constraint: %s\n", tok);
}
else
printf("warning: invalid constraint: %s\n", tok);
tok = strtok(NULL, ", ");
}
}

printf("\nbinary constraints:\n");
for (i = 0; i < ntasks; i++)
{
for (;;)
{
mygets(buff, sizeof(buff));
if (!*buff || strcmp(buff, "none") == 0)
break;
tok = strtok(buff, ": ");
if (!tok || tok[0] != 't' || (task = atoi(tok + 1) - 1) <= 0)
{
printf("warning: invalid constraint: %s\n", tok);
continue;
}
tok = strtok(NULL, ": ");
if (!tok)
{
printf("warning: lack of constraint\n");
continue;
}
if (strcmp(tok, "same") == 0)
{
}
else if (strcmp(tok, "!same") == 0)
{
}
else if ((tok[0] == '!' && tok[1] == '(' && tok[2] == 'p'))
{
}
else
printf("warning: invalid constraint: %s\n", tok);
}
}

}

/* compare routine used for sorting tasks
* longer tasks come before shorter ones */
int task_compar(const void *a, const void *b)
{
const task_t *ta = a, *tb = b;

if (ta->length > tb->length)
return -1;
if (ta->length < tb->length)
return 1;
return 0;
}

/* time used by processes already scheduled on p */
{
int i, ret = 0;
for (i = 0; i < after_task; i++)
{
}
return ret;
}

/* print out the assignment found */
void print_assignment(void)
{
int p, i, offset;

printf("\n");
for (p = 1; p <= nproc; p++)
{
printf("processor %d: ", p);
i = 0;
offset = 0;
for (i = 0; i < ntasks; i++)
{
}
printf("\n");
}
printf("\n");
}

/* find the cost of a given assignment */
int cost_assignment(void)
{
int i, cost = 0;
for (i = 0; i < ntasks; i++)

return cost;
}

{
int p, i, t;

/* recursive base case
* if this assignment is cheaper than any so far, save it */
{
int cost;
if ((cost = cost_assignment()) < least_cost)
{
least_cost = cost;
for (i = 0; i < ntasks; i++)
}
return;
}

/* look for processor to schedule this task on */
for (p = 1; p <= nproc; p++)
{
/* unary constraints */
continue;

continue;

/* binary constraints */
for (i = 0; i < first_task; i++)
{
break;

break;

break;
}
continue;

/* schedule this task on this processor */

/* recurse */
}

/* out of options */
return;
}

int main(void)
{
get_problem_info();

/* sort tasks using the heuristic:
* longer tasks get assigned before shorter ones */

find_assignment(0);

if (least_cost != INT_MAX)
print_assignment();   /* found one */
else
printf("no assignment possible\n");

return 0;
}

Script :

Case 1 :

length of task 1 (in sec.): 7
length of task 2 (in sec.): 8
length of task 3 (in sec.): 6
length of task 4 (in sec.): 7
length of task 5 (in sec.): 9

number of processors: 3
cost of processor 1 (in dollars per sec.): 1
cost of processor 2 (in dollars per sec.): 1
cost of processor 3 (in dollars per sec.): 1

unary constraints:
t1: !p1
t2: p2
t3: !p3
t4: none
t5: p1

binary constraints:
t1: t2: !same
t1: none
t2: none
t3: t4: same
t3: none
t4: none
t5: none

processor 1: t5
processor 2: t1 t4 t3
processor 3: t2

Case 2 :

length of task 1 (in sec.): 9
length of task 2 (in sec.): 8
length of task 3 (in sec.): 9
length of task 4 (in sec.): 8
length of task 5 (in sec.): 9

number of processors: 3
cost of processor 1 (in dollars per sec.): 1
cost of processor 2 (in dollars per sec.): 1
cost of processor 3 (in dollars per sec.): 1

unary constraints:
t1: p1
t2: p2
t3: !p2
t4: p3
t5: none

binary constraints:
t1: t5: !same
t1: none
t2: none
t3: t5: same
t3: none
t4: t3: same
t4: none
t5: none
no assignment possible