daily pastebin goal
26%
SHARE
TWEET

Untitled

a guest Feb 13th, 2018 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "myUtils.h"
  5. #include "myHT.h"
  6.  
  7. typedef struct item_t i_t;
  8. typedef struct set_t s_t;
  9.  
  10. int comb_r(s_t *workers, s_t *firms, int current, int N);
  11. int checkStability(s_t *w, s_t *f, int N);
  12. void loadFile(FILE *input, s_t **workers, s_t **firms, int *n);
  13. void printAssignments(s_t *workers, int N);
  14. void freeSet(s_t *s, int N);
  15. void freeItem(i_t *i, int N);
  16. s_t *setInit(int N);
  17. i_t *itemInit(char *name, int N);
  18.  
  19. struct item_t {
  20.     char *name;
  21.     s_t *preferences;
  22.     i_t *assigned;
  23. };
  24.  
  25. struct set_t {
  26.     i_t **table;
  27.     ht_t *ht;
  28. };
  29.  
  30. int main(int argc, char **argv) {
  31.     int N;
  32.     s_t *workers, *firms;
  33.     FILE *input;
  34.  
  35.     if (argc != 2) {
  36.         printf("Expected 1 argument: prgm.exe <filename>\n");
  37.         exit(EXIT_FAILURE);
  38.     }
  39.  
  40.     input = fopenOrDie(argv[1], "r");
  41.     loadFile(input, &workers, &firms, &N);
  42.     fclose(input);
  43.  
  44.     if (comb_r(workers, firms, 0, N))printAssignments(workers, N);
  45.     else printf("No solution found.\n");
  46.  
  47.     freeSet(workers, N);
  48.     freeSet(firms, N);
  49.  
  50.     return 0;
  51. }
  52.  
  53. int comb_r(s_t *workers, s_t *firms, int current, int N) {
  54.     int i;
  55.  
  56.     if (current == N) {
  57.         if (checkStability(workers, firms, N))return 1;
  58.         return 0;
  59.     }
  60.  
  61.     for (i = 0; i < N; i++) {
  62.         if (firms->table[i]->assigned == NULL) {
  63.             workers->table[current]->assigned = firms->table[i];
  64.             firms->table[i]->assigned = workers->table[current];
  65.             if (comb_r(workers, firms, current + 1, N))return 1;
  66.             firms->table[i]->assigned = NULL;
  67.         }
  68.     }
  69.  
  70.     return 0;
  71. }
  72.  
  73. int checkStability(s_t *w, s_t *f, int N) {
  74.     int i, j, act_w, act_f;
  75.  
  76.     for (i = 0; i < N; i++) {
  77.         act_w = HTfind(w->table[i]->preferences->ht, w->table[i]->assigned->name);
  78.         for (j = 0; j < N; j++) {
  79.             act_f = HTfind(f->table[j]->preferences->ht, f->table[j]->assigned->name);
  80.             if (HTfind(w->table[i]->preferences->ht, f->table[j]->name) < act_w
  81.                 && HTfind(f->table[j]->preferences->ht, w->table[i]->name) < act_f)
  82.                 return 0;
  83.         }
  84.     }
  85.  
  86.     return 1;
  87. }
  88.  
  89. void loadFile(FILE *input, s_t **workers, s_t **firms, int *n) {
  90.     s_t *w, *f;
  91.     int i, j, k = 0, pos, N;
  92.     char name[20 + 1];
  93.  
  94.     fscanf(input, "%d", &N);
  95.  
  96.     w = setInit(N);
  97.     f = setInit(N);
  98.  
  99.     for (i = 0; i < N; i++) {
  100.         fscanf(input, "%s", name);
  101.         w->table[i] = itemInit(name, N);
  102.         HTinsert(w->ht, name, i);
  103.         w->table[i]->preferences = setInit(N);
  104.         for (j = 0; j < N; j++) {
  105.             fscanf(input, "%s", name);
  106.             pos = HTfind(f->ht, name);
  107.             if (pos == -1) {
  108.                 f->table[k] = itemInit(name, N);
  109.                 HTinsert(f->ht, name, k++);
  110.                 pos = k;
  111.             }
  112.             w->table[i]->preferences->table[j] = f->table[pos];
  113.             HTinsert(w->table[i]->preferences->ht, name, j);
  114.         }
  115.     }
  116.  
  117.     for (i = 0; i < N; i++) {
  118.         fscanf(input, "%s", name);
  119.         pos = HTfind(f->ht, name);
  120.         for (j = 0; j < N; j++) {
  121.             fscanf(input, "%s", name);
  122.             f->table[pos]->preferences->table[j] = w->table[HTfind(w->ht, name)];
  123.             HTinsert(f->table[pos]->preferences->ht, name, j);
  124.         }
  125.     }
  126.  
  127.     *n = N;
  128.     *workers = w;
  129.     *firms = f;
  130. }
  131.  
  132. void printAssignments(s_t *workers, int N) {
  133.     int i;
  134.     for (i = 0; i < N; i++)printf("%s %s\n", workers->table[i]->name, workers->table[i]->assigned->name);
  135. }
  136.  
  137. void freeSet(s_t *s, int N) {
  138.     int i;
  139.     for (i = 0; i < N; i++)freeItem(s->table[i], N);
  140.     HTfree(s->ht);
  141.     free(s);
  142. }
  143.  
  144. void freeItem(i_t *i, int N) {
  145.     free(i->name);
  146.     free(i->preferences);
  147.     free(i);
  148. }
  149.  
  150. s_t *setInit(int N) {
  151.     s_t *set;
  152.     set = (s_t *) allocateOrDie(sizeof(s_t));
  153.     set->table = (i_t **) allocateOrDie(sizeof(i_t *) * N);
  154.     set->ht = HTinit(N);
  155.     return set;
  156. }
  157.  
  158. i_t *itemInit(char *name, int N) {
  159.     i_t *item;
  160.     item = (i_t *) allocateOrDie(sizeof(i_t));
  161.     item->name = strdup(name);
  162.     if (item->name == NULL)exit(EXIT_FAILURE);
  163.     item->assigned = NULL;
  164.     item->preferences = setInit(N);
  165.     return item;
  166. }
RAW Paste Data
Top