Skip to content

Instantly share code, notes, and snippets.

@lucarinelli
Last active January 30, 2018 17:26
Show Gist options
  • Save lucarinelli/e227da8dd19f7ffe422591d1f2bbee77 to your computer and use it in GitHub Desktop.
Save lucarinelli/e227da8dd19f7ffe422591d1f2bbee77 to your computer and use it in GitHub Desktop.
20180129
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "myUtils.h"
#include "myHT.h"
typedef struct item_t i_t;
typedef struct set_t s_t;
int comb_r(s_t *workers, s_t *firms, int current, int N);
int checkStability(s_t *w, s_t *f, int N);
void loadFile(FILE *input, s_t **workers, s_t **firms, int *n);
void printAssignments(s_t *workers, int N);
void freeSet(s_t *s, int N);
void freeItem(i_t *i, int N);
s_t *setInit(int N);
i_t *itemInit(char *name, int N);
struct item_t {
char *name;
s_t *preferences;
i_t *assigned;
};
struct set_t {
i_t **table;
ht_t *ht;
};
int main(int argc, char **argv) {
int N;
s_t *workers, *firms;
FILE *input;
if (argc != 2) {
printf("Expected 1 argument: prgm.exe <filename>\n");
exit(EXIT_FAILURE);
}
input = fopenOrDie(argv[1], "r");
loadFile(input, &workers, &firms, &N);
fclose(input);
if (comb_r(workers, firms, 0, N))printAssignments(workers, N);
else printf("No solution found.\n");
freeSet(workers, N);
freeSet(firms, N);
return 0;
}
int comb_r(s_t *workers, s_t *firms, int current, int N) {
int i;
if (current == N) {
if (checkStability(workers, firms, N))return 1;
return 0;
}
for (i = 0; i < N; i++) {
if (firms->table[i]->assigned == NULL) {
workers->table[current]->assigned = firms->table[i];
firms->table[i]->assigned = workers->table[current];
if (comb_r(workers, firms, current + 1, N))return 1;
firms->table[i]->assigned = NULL;
}
}
return 0;
}
int checkStability(s_t *w, s_t *f, int N) {
int i, j, act_w, act_f;
for (i = 0; i < N; i++) {
act_w = HTfind(w->table[i]->preferences->ht, w->table[i]->assigned->name);
for (j = 0; j < N; j++) {
act_f = HTfind(f->table[j]->preferences->ht, f->table[j]->assigned->name);
if (HTfind(w->table[i]->preferences->ht, f->table[j]->name) < act_w
&& HTfind(f->table[j]->preferences->ht, w->table[i]->name) < act_f)
return 0;
}
}
return 1;
}
void loadFile(FILE *input, s_t **workers, s_t **firms, int *n) {
s_t *w, *f;
int i, j, k = 0, pos, N;
char name[20 + 1];
fscanf(input, "%d", &N);
w = setInit(N);
f = setInit(N);
for (i = 0; i < N; i++) {
fscanf(input, "%s", name);
w->table[i] = itemInit(name, N);
HTinsert(w->ht, name, i);
w->table[i]->preferences = setInit(N);
for (j = 0; j < N; j++) {
fscanf(input, "%s", name);
pos = HTfind(f->ht, name);
if (pos == -1) {
f->table[k] = itemInit(name, N);
HTinsert(f->ht, name, k++);
pos = k;
}
w->table[i]->preferences->table[j] = f->table[pos];
HTinsert(w->table[i]->preferences->ht, name, j);
}
}
for (i = 0; i < N; i++) {
fscanf(input, "%s", name);
pos = HTfind(f->ht, name);
for (j = 0; j < N; j++) {
fscanf(input, "%s", name);
f->table[pos]->preferences->table[j] = w->table[HTfind(w->ht, name)];
HTinsert(f->table[pos]->preferences->ht, name, j);
}
}
*n = N;
*workers = w;
*firms = f;
}
void printAssignments(s_t *workers, int N) {
int i;
for (i = 0; i < N; i++)printf("%s %s\n", workers->table[i]->name, workers->table[i]->assigned->name);
}
void freeSet(s_t *s, int N) {
int i;
for (i = 0; i < N; i++)freeItem(s->table[i], N);
HTfree(s->ht);
free(s);
}
void freeItem(i_t *i, int N) {
free(i->name);
free(i->preferences);
free(i);
}
s_t *setInit(int N) {
s_t *set;
set = (s_t *) allocateOrDie(sizeof(s_t));
set->table = (i_t **) allocateOrDie(sizeof(i_t *) * N);
set->ht = HTinit(N);
return set;
}
i_t *itemInit(char *name, int N) {
i_t *item;
item = (i_t *) allocateOrDie(sizeof(i_t));
item->name = strdup(name);
if (item->name == NULL)exit(EXIT_FAILURE);
item->assigned = NULL;
item->preferences = setInit(N);
return item;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment