· 6 years ago · May 28, 2019, 07:12 AM
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4#include <limits.h> //To compare long numbers with INT_MAX to prevent overflow
5#include <time.h> //To provide not so bad seed for random
6#include <errno.h> //Overflow flag
7#include <ctype.h> //isdigit, isalpha, isalnum functions
8#include <stdarg.h> //For variadic functions
9
10/*
11 * The task is being solved by genetic algorithm.
12 *
13 * Population - set of individuals
14 * Individual - one particular solution. Individual consists of genes
15 * Gene - one distribution for a particular course
16 *
17 * The idea is to generate a random population and try to improve it in the next generation.
18 * BEST_FIT_PERCENTAGE of individuals goes to the new population directly
19 * The population is being reproducted by crossing GOOD_FIT_PERCENTAGE of individuals
20 * The child's genes are the mixes of parent's. As a result, program finds available best distribution in a
21 * reasonable amount of time
22 */
23
24/////////////////////////////////Constants, types/////////////////////////////////
25
26typedef unsigned long long ull;
27
28///Input Constants///
29#define MAXN 50
30#define MAXN_LENGTH 2
31//"DaniilManakovskiyOutput<MAXN_LENGTH chars for number>.txt\0 -
32#define FILENAME_SIZE (28 + MAXN_LENGTH)
33#define MAX_ENTRY_SIZE 32
34#define MAX_ENTRY_COUNT 32
35size_t MAX_BUFFER_SIZE = MAX_ENTRY_SIZE * MAX_ENTRY_COUNT;
36#define ID_SIZE 5
37
38///Hash Table Constants///
39#define MAX_LOAD_FACTOR 0.75
40char *sep = " "; // separator between first and last names
41
42///Evolution Constants///
43#define POPULATION_SIZE 1000
44#define EVOLUTION_STEPS 1000
45#define BEST_FIT_PERCENTAGE 0.1
46#define GOOD_FIT_PERCENTAGE 0.2
47#define MUTATION_PROBABILITY 0.1
48#define TAKE_SECOND_PARENT_GENE (1 - (MUTATION_PROBABILITY))
49#define TAKE_FIRST_PARENT_GENE ((TAKE_SECOND_PARENT_GENE)/2)
50#define BEST_COUNT (int)(POPULATION_SIZE*BEST_FIT_PERCENTAGE)
51#define CROSSING_PARENTS_COUNT (int)(POPULATION_SIZE * GOOD_FIT_PERCENTAGE)
52#define MAX_STEPS_WITHOUT_IMPROVEMENT 25
53
54///Error Penalties///
55#define COURSE_NOT_RUN 20
56
57#define PROFESSOR_UNASSIGNED 10
58#define PROFESSOR_WRONG_SUBJECT 5
59#define PROFESSOR_LACKING_CLASS 5
60
61#define TA_LACKING_CLASS 2
62
63#define STUDENT_LACKING_CLASS 1
64
65///Constraints///
66#define TA_MAX_CLASS 4
67#define PROFESSOR_MAX_TRAINED_COURSES_TEACHING 2
68//hardcoded that Professor can teach only 1 untrained course
69
70///Utility Constants///
71#define True 1
72#define False 0
73
74#define PROF_DELIMITER "P"
75#define TA_DELIMITER "T"
76#define STUDENT_DELIMITER "S"
77
78
79/////////////////////////////////Data structures/////////////////////////////////
80///Linked List///
81typedef struct node {
82 void *data;
83 struct node *next, *prev;
84} Node;
85
86typedef struct list {
87 int cursor_position;
88 int size;
89 Node *head;
90 Node *tail;
91 Node *cursor;
92} List;
93
94
95Node *getNodeFromList(List *list, int ind);
96
97void *getFromList(List *list, int ind);
98
99void printList(List *list, int n, void (*print_function)(void *));
100
101void freeList(List *list, void (*destructor)(void *));
102
103void freeListSaveData(List *list);
104
105// functions for different representation of void* in list nodes
106
107void printStudent(void *s);
108
109void printTAGenetic(void *taG);
110
111void pushBack(List *list, void *data);
112
113void initList(List *list);
114
115char /*Bool*/ isInList(List *list, void *data, int (*key_cmp)(void *, void *));
116
117void removeFromList(List *list, int index);
118
119int findIndex(List *list, void *key, int (*cmp)(void *, void *));
120
121void removeByKey(List *list, void *key, int (*cmp)(void *, void *));
122
123///Hash Map///
124typedef struct hash_node {
125 char *key;
126 void *value;
127 struct hash_node *next;
128 struct hash_node *prev;
129} HashNode;
130
131typedef struct {
132 HashNode *head;
133 HashNode *tail;
134} HashList;
135
136typedef struct {
137 HashList *datalist;
138 size_t size, capacity;
139
140 int (*key_comparator)(void *, void *);
141 /* 1: key1 > key2
142 * 0: key1 = key2 actually, only this is needed (!!!)
143 * -1 key1 < key2
144 */
145} HashTable;
146
147ull hash(const void *data);
148
149void free_hash_entry(HashNode *node);
150
151void init_datalist(HashList *datalist, size_t capacity);
152
153void hash_table_init(HashTable *table, size_t capacity,
154 int (*key_cmp)(void *, void *));
155
156void insert(HashTable *table, char *key, void *value);
157
158void free_hash_table(HashTable *table);
159
160void rehash(HashTable *table);
161
162void *get_el(HashTable *table, char *key);
163
164void remove_el(HashTable *table, char *key);
165
166//WARNING! Returns a pointer to actual node in table
167HashNode *find_node(HashTable *table, char *key);
168
169
170/////////////////////////////////Data structures/////////////////////////////////
171typedef enum Status {
172 COURSE, PROFESSOR, TA, STUDENT
173} status;
174
175///BASIC DATA STRUCTURES///
176
177typedef struct subject {
178 char *name;
179 int required_labs;
180 int allowed_students;
181 int selectedCount; //how many student selected this course
182 List *required_by;
183} Subject;
184
185
186//TA and Prof are both faculty, but TA can be assigned only to those courses that he/she can teach
187typedef struct faculty {
188 char *fullname;
189 ull hash;
190 List *trained_for; // array for strings - names of courses
191} Faculty;
192
193typedef struct student {
194 char *name;
195 char *ID;
196 List *lacking_courses;
197} Student;
198
199
200///Genetic data structures///
201typedef struct prof {
202 Faculty *professor;
203 char /*Bool*/ isDoingWrongSubject;
204 char /*Bool*/ isBusy;
205 List *courses_teaching; // what courses prof teaches
206} ProfessorGenetic;
207
208typedef struct ta {
209 Faculty *TA;
210 List *courses_teaching; // what courses prof teaches
211} TAGenetic;
212
213typedef struct course {
214 Subject *subject;
215 ProfessorGenetic *prof;
216 List *TAs;
217} CourseGenetic;
218
219typedef struct individ {
220 CourseGenetic *schedule; //list of courses
221 List *allprofs;
222 List *professors;
223 List *allTAs;
224 List *TAs;
225 int error;
226} Individual;
227
228/////////////////////////////////functions on DTs and constructors/////////////////////////////////
229///Constructors//
230//All of them fills the fields of stuct, given pre-allocated pointer to the struct
231void new_subject(Subject *new, char *name, int labs, int students);
232
233void new_faculty(Faculty *new, char *fullname);
234
235void new_student(Student *new, char *fullname, char *ID);
236
237void new_professorGenetic(ProfessorGenetic *new, Faculty *prof);
238
239void new_TAGenetic(TAGenetic *new, Faculty *TA);
240
241void new_CourseGenetic(CourseGenetic *new, Subject *subject);
242
243
244///Destructors//
245void del_subject(Subject *subj);
246
247void del_faculty(Faculty *f);
248
249void del_student(Student *s);
250
251void del_Professor_genetic(ProfessorGenetic *prof);
252
253void del_TA_genetic(TAGenetic *ta);
254
255///ProfessorGenetic///
256char /*Bool*/ isAvailableProf(ProfessorGenetic *prof, CourseGenetic *course);
257
258void AssignToProf(ProfessorGenetic *prof, CourseGenetic *course);
259
260int errorProf(ProfessorGenetic *prof, char/*Bool*/ print);
261
262
263///TAGenetic///
264char /*Bool*/ isAvailableTA(TAGenetic *ta, CourseGenetic *course);
265
266int errorTA(TAGenetic *ta, char/*Bool*/ print);
267
268void AssignToTA(TAGenetic *ta, CourseGenetic *course);
269
270///CourseGenetic///
271int errorCourse(CourseGenetic *course, char/*Bool*/ print);
272
273char /*Bool*/ willRun(CourseGenetic *course);
274
275///Individual///
276int errorIndividual(Individual *individual, char /*Bool*/ print);
277
278int cmpIndividuals(Individual *i1, Individual *i2);
279
280/////////////////////////////////Functions used for solving/////////////////////////////////
281void printEmail();
282
283int parseInput(List *subjects, List *profs, List *TAs, List *students);
284
285int findMaximumInputFile();
286
287void generateInitialPopulation();
288
289void initializeChild(Individual *child, HashTable *TAbyName, HashTable *ProfbyName);
290
291void performEvolutionStep();
292
293void makeChild(Individual *child, Individual *first_parent, Individual *second_parent, HashTable *TAbyName,
294 HashTable *ProfbyName);
295
296void printReport(Individual *individual);
297/////////////////////////////////Input Validation/////////////////////////////////
298
299char /*Bool*/ checkID(char *id);
300
301char /*Bool*/ checkName(char *name);
302
303int findAllNumbers(char *str, int max_ints, long found_numbers[]);
304
305// Modified version of strtok from the standard library that does not skip the block
306// between 2 consecutive delimiters.
307// Retrieved from: https://stackoverflow.com/a/8706031
308char *strtok_single(char *str, char const *delims);
309
310/////////////////////////////////Generic macroses/////////////////////////////////
311
312#define isAvailable(X, Y) _Generic((X), \
313 ProfessorGenetic*: isAvailableProf, \
314 TAGenetic*: isAvailableTA\
315)(X, Y)
316
317#define AssignTo(X, Y) _Generic((X), \
318 ProfessorGenetic*: AssignToProf,\
319 TAGenetic*: AssignToTA\
320)(X, Y)
321
322#define error(X, i) _Generic((X), \
323 ProfessorGenetic*: errorProf,\
324 TAGenetic*: errorTA,\
325 CourseGenetic*: errorCourse,\
326 Individual*: errorIndividual\
327)(X, i)
328
329/////////////////////////////////Global variables/////////////////////////////////
330char *global_buffer;
331void *new_entity = NULL;
332HashTable *subjectByName = NULL;
333HashTable *professorPresence = NULL;
334HashTable *TAPresence = NULL;
335List *subjects = NULL;
336List *profs = NULL;
337List *tas = NULL;
338List *students = NULL;
339int input_status;
340
341List *student_ids = NULL;
342
343//During the evolution there is a lot of inserting/getting element from hashTables.
344//before invoking a call to hashTable, if the hash to key has already been calculated
345//it is being added to this variable, otherwise hash will be recalculated.
346ull precalculatedHash = -1;
347Individual *population = NULL;
348
349/////////////////////////////////Util functions/////////////////////////////////
350char /*Bool*/ isValid(const char *token) {
351 return token != NULL && (*token) != '\0';
352}
353
354// removes \n from global_buffer
355void trim() {
356 if (global_buffer[strlen(global_buffer) - 1] == '\n') global_buffer[strlen(global_buffer) - 1] = '\0';
357}
358
359//Comparator for different types in order to improve readability further
360int cmpStr(void *s1, void *s2) {
361 return strcmp((char *) s1, (char *) s2);
362}
363
364int cmpTA(TAGenetic *t1, TAGenetic *t2) {
365 return strcmp(t1->TA->fullname, t2->TA->fullname);
366}
367
368int cmpProf(ProfessorGenetic *p1, ProfessorGenetic *p2) {
369 return strcmp(p1->professor->fullname, p2->professor->fullname);
370}
371
372int cmpStudents(Student *s1, Student *s2) {
373 return strcmp(s1->name, s2->name) != 0 || strcmp(s1->ID, s2->ID) != 0;
374}
375
376void swap(void **pa, void **pb) {
377 void *pc;
378
379 pc = *pa;
380 *pa = *pb;
381 *pb = pc;
382}
383
384//Generates an array of shuffled links to original array. Used to add randomness into generating of first population
385CourseGenetic **shuffle(CourseGenetic *arr, int n) {
386 CourseGenetic **result = (CourseGenetic **) malloc(subjects->size * sizeof(CourseGenetic *));
387
388 for (int k = 0; k < n; ++k) {
389 result[k] = &(arr[k]);
390 }
391
392 for (int i = n - 1; i > 0; --i) {
393 int j = rand() % (i + 1);
394 swap((void **) &(result[i]), (void **) &(result[j]));
395 }
396
397 return result;
398}
399
400double randDouble() {
401 return (double) rand() / (double) RAND_MAX;
402}
403
404void getFullName(char *fullname, char *first_name, char *last_name) {
405 strcpy(fullname, first_name);
406 strcat(fullname, sep);
407 strcat(fullname, last_name);
408}
409
410// Free all n pointers
411void freeAll(int n, ...) {
412
413 va_list ptrs;
414 va_start(ptrs, n);
415
416 while (n-- > 0) {
417 void *p = va_arg(ptrs, void*);
418 free(p);
419 }
420 va_end(ptrs);
421}
422
423void introduce() {
424 printf("Sizeof(Node) = %ld\n", sizeof(Node));
425 printf("Sizeof(List) = %ld\n", sizeof(List));
426 printf("Sizeof(HashNode) = %ld\n", sizeof(HashNode));
427 printf("Sizeof(HashList) = %ld\n", sizeof(HashList));
428 printf("Sizeof(HashTable) = %ld\n", sizeof(HashTable));
429 printf("Sizeof(Subject) = %ld\n", sizeof(Subject));
430 printf("Sizeof(Faculty) = %ld\n", sizeof(Faculty));
431 printf("Sizeof(Student) = %ld\n", sizeof(Student));
432 printf("Sizeof(ProfessorGenetic) = %ld\n", sizeof(ProfessorGenetic));
433 printf("Sizeof(TAGenetic) = %ld\n", sizeof(TAGenetic));
434 printf("Sizeof(CourseGenetic) = %ld\n", sizeof(CourseGenetic));
435 printf("Sizeof(Individual) = %ld\n", sizeof(Individual));
436// printf("Sizeof() = %lld", sizeof());
437}
438
439int main() {
440// introduce();
441 size_t seed = 1555950238; //time(NULL);
442// fprintf(stderr, "%llu\n", seed);
443 srand(seed);
444 global_buffer = (char *) malloc(MAX_BUFFER_SIZE);
445 printEmail();
446
447 int max_test = findMaximumInputFile(); //Maximum found test in the current working directory (CWD)
448 char inputFile[FILENAME_SIZE];
449 char outputFile[FILENAME_SIZE];
450 for (int test = 1; test <= max_test; ++test) {
451
452 //writes to the buffer filename of the current input file
453 snprintf(inputFile, FILENAME_SIZE, "input%d.txt", test);
454 snprintf(outputFile, FILENAME_SIZE, "DaniilManakovskiyOutput%d.txt", test);
455 // if input file exist, solve the problem, otherwise print error
456 freopen(outputFile, "w", stdout); // since we know last existing file, we must generate all outputs before
457 if (freopen(inputFile, "r", stdin) != NULL) {
458// fprintf(stderr, "test: %d\n", test);
459
460 int current_result = -1;
461 int steps_without_improvement = 0;
462
463 //solve task for a particular input
464 subjects = malloc(sizeof(List));
465 profs = malloc(sizeof(List));
466 tas = malloc(sizeof(List));
467 students = malloc(sizeof(List));
468
469
470 initList(subjects);
471 initList(profs);
472 initList(tas);
473 initList(students);
474
475 subjectByName = (HashTable *) malloc(sizeof(HashTable));
476 hash_table_init(subjectByName, 5, cmpStr);
477
478 professorPresence = (HashTable *) malloc(sizeof(HashTable));
479 hash_table_init(professorPresence, 5, cmpStr);
480
481 TAPresence = (HashTable *) malloc(sizeof(HashTable));
482 hash_table_init(TAPresence, 5, cmpStr);
483
484 student_ids = malloc(sizeof(List));
485 initList(student_ids);
486
487 if (parseInput(subjects, profs, tas, students) != 0) {
488 printf("Invalid input.");
489 switch (input_status) {
490 case PROFESSOR:
491 case TA: {
492 del_faculty(new_entity);
493 free(new_entity);
494 break;
495 }
496 case STUDENT: {
497 del_student(new_entity);
498 free(new_entity);
499 break;
500 }
501 default: {
502 }
503 }
504
505 freeList(subjects, (void (*)(void *)) del_subject);
506 freeList(profs, (void (*)(void *)) del_faculty);
507 freeList(tas, (void (*)(void *)) del_faculty);
508 freeList(students, (void (*)(void *)) del_student);
509 freeList(student_ids, NULL);
510 free_hash_table(TAPresence);
511 free_hash_table(professorPresence);
512 free_hash_table(subjectByName);
513 continue;
514 }
515 freeList(student_ids, NULL);
516
517 free_hash_table(TAPresence);
518 free_hash_table(professorPresence);
519 free_hash_table(subjectByName);
520
521 // Input finished. Starting solving - generate random population
522 generateInitialPopulation();
523
524
525 for (int step = 0; step < EVOLUTION_STEPS; ++step) {
526 performEvolutionStep();
527
528// fprintf(stderr, "%d - %d\n", step, population[0].error);
529
530 /*
531 * in order to reduce time consuming, evolution stops after MAX_STEPS_WITHOUT_IMPROVEMENT steps if the
532 * best result has not been improved or if badness points = 0 - there is no way to find better answer
533 */
534 if (population[0].error == current_result) {
535 ++steps_without_improvement;
536 } else {
537 current_result = population[0].error;
538 steps_without_improvement = 0;
539 }
540
541 if (steps_without_improvement == MAX_STEPS_WITHOUT_IMPROVEMENT || current_result == 0) {
542// printf("%d\n", current_result);
543 break;
544 }
545 }
546 //////////////////////////////// All evolution steps done///////////////////////////////////////////////////
547 printReport(&population[0]);
548
549
550//Population free start
551 for (int l = 0; l < POPULATION_SIZE; ++l) {
552 freeListSaveData(population[l].TAs);
553
554 freeListSaveData(population[l].professors);
555
556 freeList(population[l].allprofs, (void (*)(void *)) del_Professor_genetic);
557 freeList(population[l].allTAs, (void (*)(void *)) del_TA_genetic);
558
559 for (int i = 0; i < subjects->size; ++i) {
560 freeListSaveData(population[l].schedule[i].TAs);
561 }
562 free(population[l].schedule);
563 }
564 free(population);
565//population free end
566
567 freeList(subjects, (void (*)(void *)) del_subject);
568 freeList(profs, (void (*)(void *)) del_faculty);
569 freeList(tas, (void (*)(void *)) del_faculty);
570 freeList(students, (void (*)(void *)) del_student);
571 } else {
572 printf("Invalid input.");
573 }
574 }
575 free(global_buffer);
576 return 0;
577}
578
579void printEmail() {
580 FILE *email = fopen("DaniilManakovskiyEmail.txt", "w");
581 fprintf(email, "d.manakovskiy@innopolis.university");
582 fclose(email);
583}
584
585//Calculates how many tests are to pass
586int findMaximumInputFile() {
587 char num[FILENAME_SIZE];
588 for (int test = MAXN; test >= 1; --test) {
589 //writes to the buffer filename of the current input file
590 snprintf(num, FILENAME_SIZE, "input%d.txt", test);
591 FILE *file;
592 if ((file = fopen(num, "r"))) {
593 fclose(file);
594 return test;
595 }
596 }
597 return 0;
598}
599
600void generateInitialPopulation() {
601 // generate intial random population
602 population = (Individual *) malloc(POPULATION_SIZE * sizeof(Individual));
603
604 for (int i = 0; i < POPULATION_SIZE; ++i) {
605
606 //List of all professors and TAs in order to perform easy memory cleaning
607 List *allProfs = malloc(sizeof(List));
608 initList(allProfs);
609
610 List *allTA = malloc(sizeof(List));
611 initList(allTA);
612
613 //Pools contain objects of professor/ta that are available to any course
614 List *profPool = malloc(sizeof(List));
615 initList(profPool);
616
617 List *taPool = malloc(sizeof(List));
618 initList(taPool);
619
620 for (int j = 0; j < profs->size; ++j) {
621 ProfessorGenetic *new = malloc(sizeof(ProfessorGenetic));
622 new_professorGenetic(new, (Faculty *) getFromList(profs, j));
623 pushBack(profPool, new);
624 pushBack(allProfs, new);
625 }
626
627
628 for (int j = 0; j < tas->size; ++j) {
629 TAGenetic *new = malloc(sizeof(TAGenetic));
630 new_TAGenetic(new, (Faculty *) getFromList(tas, j));
631 pushBack(allTA, new);
632 pushBack(taPool, new);
633 }
634
635 CourseGenetic *courses = (CourseGenetic *) malloc(subjects->size * sizeof(CourseGenetic));
636 for (int j = 0; j < subjects->size; ++j) {
637 new_CourseGenetic(&(courses[j]), (Subject *) getFromList(subjects, j));
638 }
639
640 /* since all individuals have the same order of courses in schedule, we have to shuffle all courses to
641 * add some randomness into professor/ta distribution
642 */
643 CourseGenetic **shuffled_courses = shuffle(courses, subjects->size);
644 for (int j = 0; j < subjects->size; ++j) {
645 // if there is any available prof, try assign him/her to the course
646 if (profPool->size == 0) {
647 break;
648 }
649
650 int randomInd = rand() % profPool->size;
651
652 ProfessorGenetic *prof = getFromList(profPool, randomInd);
653
654 if (isAvailable(prof, shuffled_courses[j]) == False) {
655 continue;
656 }
657
658 AssignTo(prof, shuffled_courses[j]);
659 if (prof->isBusy) {
660 removeFromList(profPool, randomInd);
661 }
662 }
663
664 // All professors assigned, perform the same assignment for TAs
665 for (int j = 0; j < subjects->size; ++j) {
666 //Construct a list of TAs that now can teach current course
667 List *availableTA = malloc(sizeof(List));
668 initList(availableTA);
669 for (int k = 0; k < taPool->size; ++k) {
670 TAGenetic *ta = getFromList(taPool, k);
671
672 if (isAvailable(ta, shuffled_courses[j])) {
673 pushBack(availableTA, ta);
674 }
675 }
676
677 //For each lab try to assign a TA
678 for (int l = 0; l < shuffled_courses[j]->subject->required_labs; ++l) {
679 if (availableTA->size == 0) {
680 break;
681 }
682
683 int randomInd = rand() % availableTA->size;
684 TAGenetic *ta = getFromList(availableTA, randomInd);
685
686 AssignTo(ta, shuffled_courses[j]);
687
688 if (ta->courses_teaching->size == TA_MAX_CLASS) {
689 removeFromList(availableTA, randomInd);
690 removeByKey(taPool, ta, (int (*)(void *, void *)) cmpTA);
691 }
692
693 }
694 freeListSaveData(availableTA);
695 }
696
697 population[i].allprofs = allProfs;
698 population[i].schedule = courses;
699 population[i].professors = profPool;
700 population[i].allTAs = allTA;
701 population[i].TAs = taPool;
702 population[i].error = error(&(population[i]), False);
703 free(shuffled_courses);
704 }
705
706 //Sort all individuals by badness
707 qsort(population, POPULATION_SIZE, sizeof(Individual), (__compar_fn_t) cmpIndividuals);
708}
709
710void initializeChild(Individual *child, HashTable *TAbyName, HashTable *ProfbyName) {
711 child->TAs = malloc(sizeof(List));
712 initList(child->TAs);
713
714 child->allTAs = malloc(sizeof(List));
715 initList(child->allTAs);
716
717 child->professors = malloc(sizeof(List));
718 initList(child->professors);
719
720 child->allprofs = malloc(sizeof(List));
721 initList(child->allprofs);
722
723 CourseGenetic *childSchedule = (CourseGenetic *) malloc(subjects->size * sizeof(CourseGenetic));
724 for (int j = 0; j < subjects->size; ++j) {
725 new_CourseGenetic(&(childSchedule[j]), (Subject *) getFromList(subjects, j));
726 }
727
728 for (int j = 0; j < tas->size; ++j) {
729 TAGenetic *new = malloc(sizeof(TAGenetic));
730 new_TAGenetic(new, (Faculty *) getFromList(tas, j));
731 pushBack(child->allTAs, new);
732 pushBack(child->TAs, new);
733 precalculatedHash = new->TA->hash;
734 insert(TAbyName, new->TA->fullname, new);
735 }
736
737 for (int j = 0; j < profs->size; ++j) {
738 ProfessorGenetic *new = malloc(sizeof(ProfessorGenetic));
739
740 new_professorGenetic(new, (Faculty *) getFromList(profs, j));
741
742 pushBack(child->professors, new);
743 pushBack(child->allprofs, new);
744 precalculatedHash = new->professor->hash;
745 insert(ProfbyName, new->professor->fullname, new);
746 }
747
748 child->schedule = childSchedule;
749}
750
751void performEvolutionStep() {
752 // At each evolution step we should create new population, based on good individual of the current one
753 Individual *new_population = (Individual *) malloc(POPULATION_SIZE * sizeof(Individual));
754
755 //Some percentage of best individuals go to the next generation directly
756 for (int i = 0; i < BEST_COUNT; ++i) {
757 memcpy(&(new_population[i]), &(population[i]), sizeof(Individual));
758 }
759
760 //Other part of population must be reproducted from CROSSING_PARENTS_COUNT best individuals
761
762 for (int child_no = 0; child_no < POPULATION_SIZE - BEST_COUNT; ++child_no) {
763 Individual first_parent = population[rand() % CROSSING_PARENTS_COUNT];
764 Individual second_parent = population[rand() % CROSSING_PARENTS_COUNT];
765
766 // Maps TA's Fullname -> object into child
767 HashTable *TAbyName = malloc(sizeof(HashTable));
768 hash_table_init(TAbyName, (int) (tas->size * 1.5), cmpStr);
769
770 // Maps Professor's Fullname -> object into child
771 HashTable *ProfbyName = malloc(sizeof(HashTable));
772 hash_table_init(ProfbyName, (int) (profs->size * 1.5), cmpStr);
773
774 Individual *child = malloc(sizeof(Individual));
775 initializeChild(child, TAbyName, ProfbyName);
776
777 makeChild(child, &first_parent, &second_parent, TAbyName, ProfbyName);
778
779 free_hash_table(ProfbyName);
780 free_hash_table(TAbyName);
781
782 child->error = error(child, False);
783 new_population[BEST_COUNT + child_no] = *child;
784 free(child); // этот объект и объект выше - разные, но внутри ссылки одинаковые.
785 }
786
787 //free all population from the inside
788 for (int l = BEST_COUNT; l < POPULATION_SIZE; ++l) {
789 freeListSaveData(population[l].TAs);
790 freeListSaveData(population[l].professors);
791
792 freeList(population[l].allprofs, (void (*)(void *)) del_Professor_genetic);
793 freeList(population[l].allTAs, (void (*)(void *)) del_TA_genetic);
794
795 for (int i = 0; i < subjects->size; ++i) {
796 freeListSaveData(population[l].schedule[i].TAs);
797 }
798 free(population[l].schedule);
799 }
800 free(population);
801
802
803 population = new_population;
804 qsort(population, POPULATION_SIZE, sizeof(Individual), (__compar_fn_t) cmpIndividuals);
805}
806
807
808void makeChild(Individual *child, Individual *first_parent, Individual *second_parent, HashTable *TAbyName,
809 HashTable *ProfbyName) {
810 /*
811 * For each course add available assistants from the first parent, append from the second, if need add from
812 * the current pool.
813 * Since in 2 parents TA distribution is likely to be different, the resulting distribution will be some new,
814 * unlikely seen before one
815 */
816 for (int i = 0; i < subjects->size; ++i) {
817 CourseGenetic *course = &(child->schedule[i]);
818
819 List *sourceAssistants = first_parent->schedule[i].TAs;
820
821 List *availableAssistants = malloc(sizeof(List));
822 initList(availableAssistants);
823
824 for (int k = 0; k < sourceAssistants->size; ++k) {
825 TAGenetic *sourceTA = getFromList(sourceAssistants, k);
826 precalculatedHash = sourceTA->TA->hash;
827 TAGenetic *ta = get_el(TAbyName,
828 sourceTA->TA->fullname);
829 if (ta != NULL && isAvailable(ta, course)) {
830 pushBack(availableAssistants, ta);
831 }
832 }
833
834 for (int j = 0; j < course->subject->required_labs; ++j) {
835 // try to find an available ta from the first parent
836
837 if (availableAssistants->size != 0) {
838 int randomInd = rand() % availableAssistants->size;
839 TAGenetic *ta = getFromList(availableAssistants, randomInd);
840
841 AssignTo(ta, course);
842
843 removeByKey(availableAssistants, ta, (int (*)(void *, void *)) cmpTA);
844 if (ta->courses_teaching->size == TA_MAX_CLASS) {
845 removeByKey(child->TAs, ta, (int (*)(void *, void *)) cmpTA);
846 remove_el(TAbyName,
847 ta->TA->fullname); // раньше удаляло целиком объект с ключом - ТА
848 }
849 continue;
850 }
851
852 //try to find an available TA from the second parent
853 freeListSaveData(availableAssistants);
854 availableAssistants = malloc(sizeof(List));
855 initList(availableAssistants);
856 sourceAssistants = second_parent->schedule[i].TAs;
857
858 for (int k = 0; k < sourceAssistants->size; ++k) {
859 TAGenetic *sourceTA = getFromList(sourceAssistants, k);
860 precalculatedHash = sourceTA->TA->hash;
861 TAGenetic *ta = get_el(TAbyName,
862 sourceTA->TA->fullname);
863 if (ta != NULL && isAvailable(ta, course)) {
864 pushBack(availableAssistants, ta);
865 }
866 }
867
868 if (availableAssistants->size != 0) {
869 int randomInd = rand() % availableAssistants->size;
870 TAGenetic *ta = getFromList(availableAssistants, randomInd);
871
872 AssignTo(ta, course);
873
874 removeByKey(availableAssistants, ta, (int (*)(void *, void *)) cmpTA);
875 if (ta->courses_teaching->size == TA_MAX_CLASS) {
876 removeByKey(child->TAs, ta, (int (*)(void *, void *)) cmpTA);
877 remove_el(TAbyName, ta->TA->fullname);
878 }
879 continue;
880 }
881
882 //If there is any TA, pick random
883 if (child->TAs->size == 0)
884 continue;
885 int randomInd = rand() % child->TAs->size;
886 TAGenetic *ta = getFromList(child->TAs, randomInd);
887 if (isAvailable(ta, course)) {
888 AssignTo(ta, course);
889
890 if (ta->courses_teaching->size == TA_MAX_CLASS) {
891 removeByKey(child->TAs, ta, (int (*)(void *, void *)) cmpTA);
892 remove_el(TAbyName, ta->TA->fullname);
893 }
894 }
895 }
896 freeListSaveData(availableAssistants);
897
898 /*
899 * For that moment TA distribution is finished.
900 * With some chance choose what parent will give its professor, or mutation will happen
901 */
902 if (child->professors->size == 0) continue;
903
904 double probability = randDouble();
905 Individual *emitter = NULL;
906 if (probability < TAKE_FIRST_PARENT_GENE) {
907 emitter = first_parent;
908 } else if (probability < TAKE_SECOND_PARENT_GENE) {
909 emitter = second_parent;
910 }
911
912
913 if (emitter == NULL) { // do mutation -> try to assign random prof
914 int randomInd = rand() % child->professors->size;
915 ProfessorGenetic *prof = getFromList(child->professors, randomInd);
916 if (isAvailable(prof, course)) {
917 AssignTo(prof, course);
918
919 if (prof->isBusy) {
920 removeByKey(child->professors, prof, (int (*)(void *, void *)) cmpProf);
921 remove_el(ProfbyName, prof->professor->fullname);
922 }
923 }
924
925 continue;
926 }
927
928 // If parent was chosen, find corresponding prof from child and try to assign it, otherwise do mutation
929 ProfessorGenetic *parentProf = emitter->schedule[i].prof;
930 if (parentProf == NULL) {
931 continue;
932 } else {
933 precalculatedHash = parentProf->professor->hash;
934 ProfessorGenetic *childProf = get_el(ProfbyName, parentProf->professor->fullname);
935 if (childProf == NULL) {
936 if (child->professors->size == 0) continue;
937
938 int randomInd = rand() % child->professors->size;
939 childProf = getFromList(child->professors, randomInd);
940
941 }
942
943 if (isAvailable(childProf, course)) {
944 AssignTo(childProf, course);
945 if (childProf->isBusy) {
946 removeByKey(child->professors, childProf, (int (*)(void *, void *)) cmpProf);
947 remove_el(ProfbyName, childProf->professor->fullname);
948 }
949
950 }
951
952 }
953 }
954}
955
956//print a report for given individual
957void printReport(Individual *individual) {
958 for (int subj = 0; subj < subjects->size; ++subj) {
959 if (willRun(&(individual->schedule[subj]))) {
960 printf("%s\n%s\n",
961 individual->schedule[subj].subject->name,
962 individual->schedule[subj].prof->professor->fullname
963 );
964 printList(individual->schedule[subj].TAs, -1, printTAGenetic);
965 printList(individual->schedule[subj].subject->required_by,
966 individual->schedule[subj].subject->allowed_students,
967 printStudent);
968 printf("\n");
969 }
970 }
971 error(individual, True);
972 printf("Total score is %d.", individual->error);
973}
974
975int parseInput(List *subjects, List *profs, List *TAs, List *students) {
976
977 //get last symbol of the file. If it is a newline - immediately break
978 char last_char = 't'; // in case the file is empty.
979 fseek(stdin, -1, SEEK_END);
980 scanf("%c", &last_char);
981 if (last_char == *"\n")
982 return 111;
983 fseek(stdin, SEEK_SET, 0);
984
985
986 input_status = COURSE;
987 //reading subjects, until "P" is met
988 while (getline(&global_buffer, &MAX_BUFFER_SIZE, stdin) != -1 && strcmp(global_buffer, "P\n") != 0) {
989
990// trim();
991
992 char *course_name = (char *) calloc(MAX_ENTRY_SIZE, sizeof(char));
993 int labs_required, students_allowed, course_name_end_pos = 0;
994 char *cursor = global_buffer;
995
996 //read letters as much as possible
997 while (isalpha(global_buffer[course_name_end_pos])) {
998 ++course_name_end_pos;
999 ++cursor;
1000 }
1001 strncpy(course_name, global_buffer, course_name_end_pos);
1002 // if non-letter char met, it must be a space followed by a digit
1003 if (!(*cursor == ' ' && isdigit(*(cursor + 1)))) {
1004 free(course_name);
1005 return 10;
1006 }
1007 // If name does not satisfy given contraints
1008 if (checkName(course_name) == False) {
1009 free(course_name);
1010 return 20;
1011 }
1012
1013 ++cursor;
1014 long nums[2];
1015 // if 2 number have not been found or they overflowed or found more than 2 - error
1016 if (findAllNumbers(cursor, 2, nums) != 0) {
1017 free(course_name);
1018 return 30;
1019 }
1020
1021 labs_required = nums[0];
1022 students_allowed = nums[1];
1023 // if information about course contains negative numbers (it must be handled above, but for any case)
1024 // or zeroes
1025 if (labs_required <= 0 || students_allowed <= 0) {
1026 free(course_name);
1027 return 35;
1028 }
1029
1030 //If some course was introduced twice
1031 if (get_el(subjectByName, course_name) != NULL) {
1032 free(course_name);
1033 return 36;
1034 }
1035
1036 Subject *n = (Subject *) malloc(sizeof(Subject));
1037 new_subject(n, course_name, labs_required, students_allowed);
1038 pushBack(subjects, n);
1039 insert(subjectByName, course_name, n);
1040 free(course_name);
1041
1042
1043 }
1044 //EOF right after course block is unacceptable
1045 if (strcmp(global_buffer, "P\n") != 0)
1046 return 40;
1047
1048 input_status = PROFESSOR; // what group is being read
1049
1050 while (getline(&global_buffer, &MAX_BUFFER_SIZE, stdin) != -1) {
1051 trim();
1052 // Performs changing of group of people Profs -> TAs
1053 if (strcmp(global_buffer, TA_DELIMITER) == 0) {
1054 if (input_status == PROFESSOR) {
1055 input_status = TA;
1056 continue;
1057 } else {
1058 return 41;
1059 }
1060 }
1061 // TAs -> Students
1062 if (strcmp(global_buffer, STUDENT_DELIMITER) == 0) {
1063 if (input_status == TA) {
1064 input_status = STUDENT;
1065 continue;
1066 } else {
1067 return 42;
1068 }
1069 }
1070
1071 //If before the newline/EOF character there is a non-letter symbol - input is incorrect
1072 if (!isalpha(global_buffer[strlen(global_buffer) - 1])) {
1073 return 39;
1074 }
1075
1076 // tokenize given string by spaces
1077 // the format is always like {fullname} {surname} <{ID}> {List of subjects}
1078 char *token = strtok_single(global_buffer, " ");
1079 if (!isValid(token)) { // token is invalid is it is NULL (the string ended) or "\0" (delimiter repeated)
1080 return 43;
1081 }
1082
1083 char *name = strdup(token);
1084 if (checkName(name) == False) {
1085 free(name);
1086 return 443;
1087 }
1088
1089
1090 token = strtok_single(NULL, " ");
1091 if (!isValid(token)) {
1092 free(name);
1093 return 44;
1094 }
1095
1096 char *surname = strdup(token);
1097 if (checkName(surname) == False) {
1098 freeAll(2, name, surname);
1099 return 445;
1100 }
1101
1102 token = strtok_single(NULL, " ");
1103 if (!isValid(token)) {
1104 freeAll(2, name, surname);
1105 return 45;
1106 }
1107
1108 char *fullname = (char *) malloc((2 + strlen(name) + strlen(surname)) * sizeof(char));
1109 getFullName(fullname, name, surname);
1110 switch (input_status) {
1111 //check if professor/TA is unique
1112 case PROFESSOR: {
1113 if (get_el(professorPresence, fullname) != NULL) {
1114 freeAll(3, name, surname, fullname);
1115 return 447;
1116 }
1117 break;
1118 }
1119
1120 case TA: {
1121 if (get_el(TAPresence, fullname) != NULL) {
1122 freeAll(3, name, surname, fullname);
1123 return 448;
1124 }
1125 break;
1126 }
1127
1128 default: {
1129 }
1130 }
1131
1132 List *head = malloc(sizeof(List));
1133 initList(head);
1134 int len = 0;
1135
1136
1137 char *student_id = NULL;
1138 if (input_status == STUDENT) {
1139
1140 if (!checkID(token)) {
1141 freeList(head, NULL);
1142 freeAll(3, name, surname, fullname);
1143 return 447;
1144 }
1145
1146 if (isInList(student_ids, token, cmpStr) == True){ // If id is not unique
1147 freeList(head, NULL);
1148 freeAll(3, name, surname, fullname);
1149 return 448;
1150 }
1151
1152 student_id = strdup(token);
1153 pushBack(student_ids, strdup(student_id));
1154 token = strtok_single(NULL, " ");
1155 if (!isValid(token)) {
1156 freeList(head, NULL);
1157 freeAll(4, name, surname, fullname, student_id);
1158 return 46;
1159 }
1160 }
1161
1162
1163 if (input_status == STUDENT) {
1164 new_entity = (Student *) malloc(sizeof(Student));
1165 new_student(new_entity, fullname, student_id);
1166 } else {
1167 new_entity = (Faculty *) malloc(sizeof(Faculty));
1168 new_faculty(new_entity, fullname);
1169 }
1170
1171
1172 while (token != NULL) {
1173 if (!isValid(token)) {
1174 freeList(head, NULL);
1175 freeAll(3, name, surname, fullname);
1176 if (input_status == STUDENT)
1177 free(student_id);
1178 return 47;
1179 }
1180 //uncomment this to revert changes
1181 //Checks whether new token is unique in the list
1182 if (isInList(head, token, (int (*)(void *, void *)) strcmp) == True) {
1183 freeList(head, NULL);
1184 freeAll(3, name, surname, fullname);
1185 if (input_status == STUDENT)
1186 free(student_id);
1187 return 447;
1188 }
1189 char *tmp = malloc(strlen(token) + 1);
1190 strcpy(tmp, token);
1191 pushBack(head, tmp);
1192
1193 //Comment block above and uncomment this to revert last assignment change
1194// if (input_status != STUDENT) {
1195// char *tmp = malloc(strlen(token) + 1);
1196// strcpy(tmp, token);
1197// pushBack(head, tmp);
1198// }
1199 len++;
1200
1201 Subject *subj = get_el(subjectByName, token);
1202 if (subj == NULL) {
1203 freeList(head, NULL);
1204 freeAll(3, name, surname, fullname);
1205 if (input_status == STUDENT)
1206 free(student_id);
1207 return 48; // Found a course_name that doesn't exists
1208 }
1209
1210 // if list of required courses for student started
1211 if (input_status == STUDENT) {
1212 if (!isInList(subj->required_by, new_entity, (int (*)(void *, void *)) cmpStudents))
1213 pushBack(subj->required_by, new_entity);
1214 subj->selectedCount++;
1215 }
1216 token = strtok_single(NULL, " ");
1217
1218 }
1219
1220
1221 switch (input_status) {
1222 case PROFESSOR: {
1223 ((Faculty *) new_entity)->trained_for = head;
1224 pushBack(profs, new_entity);
1225 precalculatedHash = ((Faculty *) new_entity)->hash;
1226 insert(professorPresence, fullname, new_entity);
1227 break;
1228 }
1229 case TA: {
1230 ((Faculty *) new_entity)->trained_for = head;
1231 pushBack(TAs, new_entity);
1232 precalculatedHash = ((Faculty *) new_entity)->hash;
1233 insert(TAPresence, fullname, new_entity);
1234 break;
1235 }
1236 case STUDENT: {
1237 freeList(head, NULL);
1238 pushBack(students, new_entity);
1239 break;
1240 }
1241 default: {
1242 }
1243 }
1244
1245 new_entity = NULL;
1246 freeAll(4, name, surname, token, fullname);
1247 if (input_status == STUDENT) free(student_id);
1248
1249 }
1250
1251 //
1252 if (input_status != STUDENT) {
1253
1254 return 50;
1255 }
1256
1257 return 0;
1258}
1259
1260/////////////////////////////////Input Validation/////////////////////////////////
1261int findAllNumbers(char *str, int max_ints, long found_numbers[]) {
1262 if (isdigit(str[0]) == 0) {
1263 return 1;
1264 }
1265 if (str[0] == '0' && isdigit(str[1])) return 1;
1266
1267 char *p = calloc(strlen(str) + 1, sizeof(char));
1268 char *cleaner = p;
1269 int found_number_count = 0;
1270 strcpy(p, str);
1271 char *end;
1272
1273 // strtol returns long, cast to integer behaves unexpectedly with numbers X:
1274 // MAX_INT <= X <= MAX_LONG, but working fine with longs
1275 for (long i = strtol(p, &end, 10); p != end; i = strtol(p, &end, 10)) {
1276 found_number_count++;
1277 // strtol sets errno to ERANGE in case of overflow
1278 if (errno == ERANGE) {
1279 errno = 0;
1280 free(cleaner);
1281// freeIfPossible(p);
1282 return 1;
1283 }
1284 if (i > INT_MAX) {
1285 free(cleaner);
1286 return 1;
1287 }
1288 if (found_number_count > max_ints) {
1289 // if at some moment it findes more numbers, than
1290 // expected, terminates
1291 free(cleaner);
1292 return 1;
1293 }
1294
1295 found_numbers[found_number_count - 1] = i;
1296 p = end;
1297 // p is pointing to the first symbol after the last read number
1298
1299 // if we did not read all number, we have to check
1300 // spaces and leading zeroes between them
1301 // If all numbers are read, then after the loop
1302 // last symbol will be checked
1303 if (found_number_count < max_ints) {
1304 // problem cases:
1305 // there is not a number after 1 delimiter
1306 if (!isdigit(p[1])) {
1307 free(cleaner);
1308 return 1;
1309 } else {
1310 // there is a leading zero
1311 if (p[1] == '0' && isdigit(p[2])) {
1312 free(cleaner);
1313 return 1;
1314 }
1315 }
1316 // The delimiter must be a space
1317 if (*p != ' ') {
1318 free(cleaner);
1319 return 1;
1320 }
1321 }
1322
1323 // printf("%d %d %d\n", p[0], p[1],
1324 // (found_number_count == max_ints) ? 1 : 0);
1325 }
1326 // p points to the first char after the last found number
1327 // if flag is_end set, then it supposed to be null terminator, otherwise
1328 // line feed
1329 // printf("String ended with: |%d|\n", *p);
1330 if (*p != '\n') {
1331 free(cleaner);
1332 return 1;
1333 }
1334 free(cleaner);
1335 return (found_number_count == max_ints) ? 0 : 1;
1336}
1337
1338
1339char /*Bool*/ checkID(char *id) {
1340 if (id != NULL) {
1341 if (strlen(id) != ID_SIZE)
1342 return False;
1343 for (int i = 0; i < ID_SIZE; ++i) {
1344 if (isalnum(id[i]) == 0) {
1345 return False;
1346 }
1347 }
1348 return True;
1349 }
1350 return False;
1351}
1352
1353char /*Bool*/ checkName(char *name) {
1354 if (name != NULL) {
1355 for (int i = 0; i < strlen(name); ++i) {
1356 if (isalpha(name[i]) == 0 && name[i] != ' ') {
1357 return False;
1358 }
1359 }
1360 if (strcmp(name, PROF_DELIMITER) == 0 ||
1361 strcmp(name, STUDENT_DELIMITER) == 0 ||
1362 strcmp(name, TA_DELIMITER) == 0) {
1363 return False;
1364 }
1365 return True;
1366 }
1367 return False;
1368}
1369
1370char *strtok_single(char *str, char const *delims) {
1371 static char *src = NULL;
1372 char *p, *ret = 0;
1373
1374 if (str != NULL)
1375 src = str;
1376
1377 if (src == NULL)
1378 return NULL;
1379
1380 if ((p = strpbrk(src, delims)) != NULL) {
1381 *p = 0;
1382 ret = src;
1383 src = ++p;
1384
1385 } else if (*src) {
1386 ret = src;
1387 src = NULL;
1388 }
1389
1390 return ret;
1391}
1392
1393/////////////////////////////////Data structures/////////////////////////////////
1394///Linked List///
1395
1396void removeFromList(List *list, int index) {
1397 Node *tmp = getNodeFromList(list, index);
1398 if (tmp != NULL) {
1399 list->size--;
1400
1401 if (list->size == 0) {
1402 list->head = NULL;
1403 list->tail = NULL;
1404 list->cursor = NULL;
1405 list->cursor_position = 0;
1406 free(tmp);
1407 return;
1408 }
1409
1410 if (tmp == list->head) {
1411 list->head = tmp->next;
1412 list->head->prev = NULL;
1413 list->cursor = list->head;
1414 list->cursor_position = 0;
1415 free(tmp);
1416 return;
1417 }
1418
1419 if (tmp == list->tail) {
1420 list->tail = tmp->prev;
1421 list->tail->next = NULL;
1422 list->cursor = list->tail;
1423 list->cursor_position = list->size - 1;
1424 free(tmp);
1425 return;
1426 }
1427
1428 tmp->prev->next = tmp->next;
1429 tmp->next->prev = tmp->prev;
1430 --list->cursor_position;
1431 list->cursor = list->cursor->prev;
1432 free(tmp);
1433 }
1434}
1435
1436void removeByKey(List *list, void *key, int (*cmp)(void *, void *)) {
1437 int ind = findIndex(list, key, cmp);
1438 if (ind == -1)
1439 return;
1440 removeFromList(list, ind);
1441}
1442
1443int findIndex(List *list, void *key, int (*cmp)(void *, void *)) {
1444
1445 for (int i = 0; i < list->size; ++i) {
1446 if (cmp(key, getFromList(list, i)) == 0) {
1447 return i;
1448 }
1449 }
1450
1451 return -1;
1452}
1453
1454Node *getNodeFromList(List *list, int ind) {
1455 while (ind < 0) {
1456 ind += list->size;
1457 }
1458 if (ind >= list->size) {
1459 return NULL;
1460 }
1461 int diff = ind - list->cursor_position; // if positive, go right, else - left
1462
1463 if (ind < abs(diff)) {
1464 diff = ind;
1465 list->cursor = list->head;
1466 } else if (list->size - ind - 1 < abs(diff)) {
1467 diff = ind - (list->size - 1);
1468 list->cursor = list->tail;
1469 }
1470
1471 while (diff != 0) {
1472 if (diff < 0) {
1473 list->cursor = list->cursor->prev;
1474 ++diff;
1475 } else {
1476 list->cursor = list->cursor->next;
1477 --diff;
1478 }
1479 }
1480 list->cursor_position = ind;
1481 return list->cursor;
1482}
1483
1484void *getFromList(List *list, int ind) {
1485 Node *res = getNodeFromList(list, ind);
1486 return (res != NULL) ? res->data : NULL;
1487}
1488
1489void printStudent(void *s) {
1490 Student *st = (Student *) (s);
1491 printf("%s %s\n", st->name, st->ID);
1492}
1493
1494void printTAGenetic(void *taG) {
1495 TAGenetic *ta = (TAGenetic *) taG;
1496 printf("%s\n", ta->TA->fullname);
1497
1498}
1499
1500void pushBack(List *list, void *data) {
1501 Node *new_node = (Node *) malloc(sizeof(Node));
1502
1503 new_node->data = data;
1504
1505 if (list->head == NULL) { // no elements were introduced
1506 list->head = new_node;
1507 list->tail = new_node;
1508 list->cursor = new_node;
1509 list->cursor_position = 0;
1510 new_node->prev = NULL;
1511 new_node->next = NULL;
1512
1513 } else {
1514 list->tail->next = new_node;
1515 new_node->prev = list->tail;
1516 new_node->next = NULL;
1517 list->tail = new_node;
1518 }
1519 ++(list->size);
1520
1521}
1522
1523void initList(List *list) {
1524 list->head = NULL;
1525 list->tail = NULL;
1526 list->cursor = NULL;
1527 list->cursor_position = 0;
1528 list->size = 0;
1529}
1530
1531void printList(List *list, int n, void (*print_function)(void *)) {
1532 int printed = 0;
1533 Node *node = list->head;
1534 while (node != NULL && printed != n) {
1535 (*print_function)(node->data);
1536 node = node->next;
1537 ++printed;
1538 }
1539}
1540
1541void freeList(List *list, void (*destructor)(void *)) {
1542 if (list != NULL) {
1543 Node *node = list->head;
1544 Node *next;
1545 while (node != NULL) {
1546 next = node->next;
1547 if (destructor != NULL)
1548 destructor(node->data);
1549 free(node->data);
1550 node->prev = NULL;
1551 node->next = NULL;
1552 free(node);
1553 node = next;
1554 }
1555 free(list);
1556 }
1557}
1558
1559void freeListSaveData(List *list) {
1560 Node *node = list->head;
1561 Node *next;
1562 while (node != NULL) {
1563 next = node->next;
1564 node->prev = NULL;
1565 node->next = NULL;
1566 free(node);
1567 node = next;
1568 }
1569 free(list);
1570}
1571
1572char /*Bool*/ isInList(List *list, void *data, int (*key_cmp)(void *, void *)) {
1573 for (int i = 0; i < list->size; ++i) {
1574 if (key_cmp(data, getFromList(list, i)) == 0) {
1575 return True;
1576 }
1577 }
1578 return False;
1579}
1580
1581///Hash Map///
1582//Source: http://www.cse.yorku.ca/~oz/hash.html
1583ull hash(const void *data) {
1584 ull result = 5381;
1585 char *i = (char *) data;
1586 int c;
1587
1588 while ((c = *i++))
1589 result = ((result << 5U) + result) + c;
1590
1591 return result;
1592}
1593
1594void free_hash_entry(HashNode *node) {
1595 if (node != NULL) {
1596 free(node->key);
1597 }
1598}
1599
1600
1601void
1602hash_table_init(HashTable *table, size_t capacity, int (*key_cmp)(void *, void *)) {
1603 table->capacity = capacity;
1604 table->datalist = (HashList *) malloc(capacity * sizeof(HashList));
1605 table->key_comparator = key_cmp;
1606 table->size = 0;
1607 init_datalist(table->datalist, capacity);
1608}
1609
1610void insert(HashTable *table, char *key, void *value) {
1611 ull index = ((precalculatedHash == -1) ? hash(key) : precalculatedHash) % table->capacity;
1612 precalculatedHash = -1;
1613 HashNode *node = (table->datalist[index]).head;
1614
1615 HashNode *item = (HashNode *) malloc(sizeof(HashNode));
1616
1617 item->next = NULL;
1618 item->prev = NULL;
1619 item->key = strdup(key);
1620 item->value = value;
1621
1622 if (node == NULL) {
1623 // definetely no item
1624 (table->datalist)[index].head = item;
1625 (table->datalist)[index].tail = item;
1626 table->size++;
1627 } else {
1628 // iterate over the list. If needed node is not present - add to the
1629 // list
1630 while (node != NULL) {
1631 if (table->key_comparator(node->key, key) == 0) {
1632 node->value = value;
1633 free_hash_entry(item);
1634 free(item);
1635 break;
1636 }
1637 node = node->next;
1638 }
1639 if (node == NULL) {
1640 (table->datalist)[index].tail->next = item;
1641 item->prev = (table->datalist)[index].tail;
1642 (table->datalist)[index].tail = item;
1643 table->size++;
1644 }
1645
1646 }
1647
1648
1649 double load_factor = (1.0 * table->size) / table->capacity;
1650 if (load_factor >= MAX_LOAD_FACTOR) {
1651 rehash(table);
1652 }
1653}
1654
1655void free_hash_table(HashTable *table) {
1656 if (table != NULL) {
1657 HashNode *node = NULL;
1658 HashNode *next = NULL;
1659 for (int i = 0; i < table->capacity; ++i) {
1660 node = table->datalist[i].head;
1661 while (node != NULL) {
1662 free(node->key);
1663 next = node->next;
1664 free(node);
1665 node = next;
1666 }
1667 }
1668 freeAll(2, table->datalist, table);
1669 }
1670}
1671
1672void rehash(HashTable *table) {
1673// fprintf(stderr, "REHASH!\n");
1674 HashList *old = table->datalist;
1675 HashTable *temp = malloc(sizeof(HashTable));
1676 hash_table_init(temp, 2 * table->capacity, table->key_comparator);
1677
1678 HashNode *list = NULL;
1679 HashNode *next = NULL;
1680
1681 for (int i = 0; i < table->capacity; ++i) {
1682 list = old[i].head;
1683 // if hash_list contains anything, insert it into a new ht
1684 while (list != NULL) {
1685 insert(temp, list->key, list->value);
1686 free(list->key);
1687 next = list->next;
1688 free(list);
1689 list = next;
1690 }
1691 }
1692 table->capacity *= 2;
1693 free(table->datalist);
1694 table->datalist = temp->datalist;
1695 free(temp);
1696}
1697
1698
1699void init_datalist(HashList *datalist, size_t capacity) {
1700 for (size_t i = 0; i < capacity; i++) {
1701 datalist[i].head = NULL;
1702 datalist[i].tail = NULL;
1703 }
1704}
1705
1706//WARNING! Returns a pointer to actual node in table
1707HashNode *find_node(HashTable *table, char *key) {
1708 HashNode *node = table->datalist[((precalculatedHash == -1) ? hash(key) : precalculatedHash) %
1709 table->capacity].head;
1710 precalculatedHash = -1;
1711 while (node != NULL) {
1712 if (table->key_comparator(key, node->key) == 0) {
1713 return node;
1714 }
1715 node = node->next;
1716 }
1717 return NULL;
1718}
1719
1720void *get_el(HashTable *table, char *key) {
1721 HashNode *tmp = find_node(table, key);
1722 return (tmp != NULL) ? tmp->value : NULL;
1723}
1724
1725void remove_el(HashTable *table, char *key) {
1726 HashNode *tmp = find_node(table, key);
1727 if (tmp != NULL) {
1728 size_t index = hash(key) % table->capacity;
1729 if (tmp->next != NULL && tmp->prev != NULL) {
1730 tmp->prev->next = tmp->next;
1731 tmp->next->prev = tmp->prev;
1732
1733 } else if (tmp->prev != NULL) {
1734 tmp->prev->next = NULL;
1735 table->datalist[index].tail = tmp->prev;
1736 } else if (tmp->next != NULL) {
1737 tmp->next->prev = NULL;
1738 table->datalist[index].head = tmp->next;
1739 } else {
1740 table->datalist[index].tail = NULL;
1741 table->datalist[index].head = NULL;
1742 }
1743 freeAll(2, tmp->key, tmp);
1744 }
1745}
1746
1747
1748///Constructors//
1749void new_subject(Subject *new, char *name, int labs, int students) {
1750 if (new == NULL)
1751 return;
1752 new->name = malloc(strlen(name) + 1);
1753 strcpy(new->name, name);
1754 new->required_labs = labs;
1755 new->allowed_students = students;
1756 new->required_by = malloc(sizeof(List));
1757 initList(new->required_by);
1758}
1759
1760void new_faculty(Faculty *new, char *fullname) {
1761 if (new == NULL)
1762 return;
1763 new->fullname = strdup(fullname);
1764 new->hash = hash(fullname);
1765 new->trained_for = NULL;
1766}
1767
1768void new_student(Student *new, char *fullname, char *ID) {
1769 if (new == NULL)
1770 return;
1771 new->name = strdup(fullname);
1772 new->ID = malloc(ID_SIZE + 1); // ID_SIZE chars + \0
1773 strcpy(new->ID, ID);
1774 new->lacking_courses = malloc(sizeof(List));
1775 initList(new->lacking_courses);
1776}
1777
1778void new_professorGenetic(ProfessorGenetic *new, Faculty *prof) {
1779 new->professor = prof;
1780 new->isDoingWrongSubject = False;
1781 new->isBusy = False;
1782 new->courses_teaching = malloc(sizeof(List));
1783 initList(new->courses_teaching);
1784
1785}
1786
1787void new_TAGenetic(TAGenetic *new, Faculty *TA) {
1788 new->TA = TA;
1789 new->courses_teaching = malloc(sizeof(List));
1790 initList(new->courses_teaching);
1791}
1792
1793void new_CourseGenetic(CourseGenetic *new, Subject *subject) {
1794 new->prof = NULL;
1795 new->subject = subject;
1796 new->TAs = malloc(sizeof(List));
1797 initList(new->TAs);
1798}
1799
1800
1801///Destructors//
1802void del_subject(Subject *subj) {
1803 freeListSaveData(subj->required_by);
1804 free(subj->name);
1805}
1806
1807void del_faculty(Faculty *f) {
1808 if (f != NULL) {
1809 freeList(f->trained_for, NULL);
1810 free(f->fullname);
1811 }
1812}
1813
1814void del_student(Student *s) {
1815 if (s != NULL) {
1816 freeListSaveData(s->lacking_courses);
1817 freeAll(2, s->name, s->ID);
1818 }
1819}
1820
1821void del_Professor_genetic(ProfessorGenetic *prof) {
1822 freeListSaveData(prof->courses_teaching);
1823}
1824
1825void del_TA_genetic(TAGenetic *ta) {
1826 freeListSaveData(ta->courses_teaching);
1827}
1828
1829///Functions on DT///
1830///ProfessorGenetic///
1831char /*Bool*/ isAvailableProf(ProfessorGenetic *prof, CourseGenetic *course) {
1832 if (prof->courses_teaching->size == 0) {
1833 return True;
1834 }
1835
1836 if (prof->courses_teaching->size == 1) {
1837 return !prof->isDoingWrongSubject &&
1838 isInList(prof->professor->trained_for, course->subject->name, cmpStr);
1839 }
1840
1841 return False;
1842}
1843
1844void AssignToProf(ProfessorGenetic *prof, CourseGenetic *course) {
1845 pushBack(prof->courses_teaching, course);
1846
1847 if (isInList(prof->professor->trained_for, course->subject->name, cmpStr) == False) {
1848 prof->isDoingWrongSubject = True;
1849 }
1850
1851 course->prof = prof;
1852
1853 if (prof->isDoingWrongSubject || prof->courses_teaching->size == PROFESSOR_MAX_TRAINED_COURSES_TEACHING) {
1854 prof->isBusy = True;
1855 }
1856}
1857
1858int errorProf(ProfessorGenetic *prof, char/*Bool*/ print) {
1859 int run_course_count = 0;
1860 for (int i = 0; i < prof->courses_teaching->size; ++i) {
1861 if (willRun(getFromList(prof->courses_teaching, i))) {
1862 ++run_course_count;
1863 }
1864 }
1865
1866 if (run_course_count == 0) {
1867 if (print) {
1868 printf("%s is unassigned.\n", prof->professor->fullname);
1869 }
1870 return PROFESSOR_UNASSIGNED;
1871 }
1872 if (prof->isDoingWrongSubject == True) {
1873 if (print) {
1874 printf("%s is not trained for %s.\n", prof->professor->fullname,
1875 ((CourseGenetic *) (getFromList(prof->courses_teaching, 0)))->subject->name);
1876 }
1877 return PROFESSOR_WRONG_SUBJECT;
1878 }
1879 if (run_course_count == 1) {
1880 if (print) {
1881 printf("%s is lacking class.\n", prof->professor->fullname);
1882 }
1883 return PROFESSOR_LACKING_CLASS;
1884 }
1885
1886 return 0;
1887}
1888
1889///TAGenetic///
1890char /*Bool*/ isAvailableTA(TAGenetic *ta, CourseGenetic *course) {
1891 return ta->courses_teaching->size < TA_MAX_CLASS && isInList(ta->TA->trained_for, course->subject->name, cmpStr);
1892}
1893
1894void AssignToTA(TAGenetic *ta, CourseGenetic *course) {
1895 pushBack(course->TAs, ta);
1896
1897 pushBack(ta->courses_teaching, course);
1898}
1899
1900int errorTA(TAGenetic *ta, char/*Bool*/ print) {
1901 int run_course_count = 0;
1902 for (int i = 0; i < ta->courses_teaching->size; ++i) {
1903 if (willRun(getFromList(ta->courses_teaching, i))) {
1904 ++run_course_count;
1905 }
1906 }
1907 if (print && (TA_MAX_CLASS - run_course_count) > 0) {
1908 printf("%s is lacking %d lab(s).\n", ta->TA->fullname, TA_MAX_CLASS - run_course_count);
1909 }
1910 return (TA_MAX_CLASS - run_course_count) * TA_LACKING_CLASS;
1911}
1912
1913///CourseGenetic///
1914int errorCourse(CourseGenetic *course, char/*Bool*/ print) {
1915 if (willRun(course)) {
1916 int lacking_students = course->subject->required_by->size - course->subject->allowed_students;
1917 if (print && lacking_students > 0) {
1918 for (int i = course->subject->allowed_students; i < course->subject->required_by->size; ++i) {
1919 Student *student = getFromList(course->subject->required_by, i);
1920 pushBack(student->lacking_courses, course);
1921
1922 }
1923 }
1924 return (lacking_students > 0) ? lacking_students * STUDENT_LACKING_CLASS : 0;
1925 } else {
1926 if (print) {
1927 printf("%s cannot be run.\n", course->subject->name);
1928 for (int i = 0; i < course->subject->required_by->size; ++i) {
1929 Student *student = getFromList(course->subject->required_by, i);
1930 pushBack(student->lacking_courses, course);
1931 }
1932 }
1933 return course->subject->required_by->size * STUDENT_LACKING_CLASS + COURSE_NOT_RUN;
1934 }
1935}
1936
1937char /*Bool*/ willRun(CourseGenetic *course) {
1938 return (course->prof != NULL && course->TAs->size == course->subject->required_labs) ?
1939 True : False;
1940}
1941
1942///Individual///
1943int errorIndividual(Individual *individual, char /*Bool*/ print) {
1944 int overall_error = 0;
1945 int subj = 0;
1946 int prof = 0;
1947 int ta = 0;
1948 for (int i = 0; i < subjects->size; ++i) {
1949 subj += error(&(individual->schedule[i]), print);
1950 }
1951
1952 for (int i = 0; i < individual->allprofs->size; ++i) {
1953 prof += error((ProfessorGenetic *) (getFromList(individual->allprofs, i)), print);
1954 }
1955
1956 for (int i = 0; i < individual->allTAs->size; ++i) {
1957 ta += error((TAGenetic *) (getFromList(individual->allTAs, i)), print);
1958 }
1959
1960 if (print) {
1961 for (int i = 0; i < students->size; ++i) {
1962 Student *student = getFromList(students, i);
1963 for (int j = 0; j < student->lacking_courses->size; ++j) {
1964 CourseGenetic *lacking = getFromList(student->lacking_courses, j);
1965 printf("%s is lacking %s.\n", student->name, lacking->subject->name);
1966 }
1967 }
1968 }
1969
1970 overall_error = subj + prof + ta;
1971 return overall_error;
1972}
1973
1974int cmpIndividuals(Individual *i1, Individual *i2) {
1975 return i1->error - i2->error;
1976}