fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define TRUE 1
  5. #define FALSE 0
  6. #define QUEUE_SIZE 256
  7. #define HEAD (QUEUE_SIZE - 1)
  8. #define TAIL (QUEUE_SIZE - 2)
  9. #define MODULUS (HEAD < TAIL ? HEAD : TAIL)
  10. #define INCREMENT(x) x = (x + 1) % MODULUS
  11. typedef unsigned short baboon;
  12. enum direction { EAST, WEST }; 
  13. enum list_type { FORWARD, BACKWARD, STARVATION }; 
  14. baboon **lists; 
  15. unsigned short num_cycles; 
  16. char *input = "EEWEWWWEWEEEWEE"; 
  17. unsigned short default_crossing_time = 3; 
  18. unsigned short current_direction; 
  19. unsigned short use_starvation_queue = FALSE; 
  20. int main(int argc, char **argv);
  21. void initialize();
  22. int lists_are_empty();
  23. void add_baboon(int cycle);
  24. void run_one_cycle();
  25. void check_for_swap();
  26. void swap(void *first, void *second);
  27. int main (int argc, char **argv) {
  28. 	initialize();
  29. 	int cycle = 0;
  30. 	while ((cycle <= num_cycles) || !lists_are_empty()) {
  31. 		printf("Cycle %3d: ", cycle + 1);
  32. 		add_baboon(cycle);
  33. 		run_one_cycle();
  34. 		check_for_swap();
  35. 		printf("\n");
  36. 		cycle++;
  37. 	}
  38. 	return (0);
  39. }
  40. void add_baboon(int cycle) {
  41. 	if (cycle >= num_cycles)
  42. 		return;
  43. 	int list, tail, crossing_time = default_crossing_time;
  44. 	unsigned short direction = input[cycle] == 'E' ? EAST : WEST;
  45. 	if (direction == current_direction) {
  46. 		if (use_starvation_queue) {
  47. 			list = STARVATION;
  48. 		} else {
  49. 			list = FORWARD;
  50. 		}
  51. 	} else {
  52. 		list = BACKWARD;
  53. 		#ifdef STARVATION
  54. 		use_starvation_queue = TRUE;
  55. 		#endif
  56. 	}
  57. 	tail = lists[list][TAIL];
  58. 	if (lists[list][HEAD] != lists[list][TAIL]) {
  59. 		int previous = (lists[list][TAIL] - 1) % MODULUS;
  60. 		printf("previous: %d", previous);
  61. 		printf("previous_time: %d", lists[list][previous]);
  62. 		crossing_time = lists[list][previous] >= crossing_time ? 
  63. 				lists[list][previous] + 1 : crossing_time;
  64. 		printf("crossing_time: %d", crossing_time);
  65. 	}
  66. 	lists[list][tail] = crossing_time;
  67. 	INCREMENT(lists[list][TAIL]);
  68. }
  69. void run_one_cycle() {
  70. 	baboon start, end, head;
  71. 	start = head = lists[FORWARD][HEAD];
  72. 	end = lists[FORWARD][TAIL];
  73. 	while (start != end) {
  74. 		lists[FORWARD][start]--;
  75. 		INCREMENT(start);
  76. 	}
  77. 	if (lists[FORWARD][head] == 0) {
  78. 		printf("%c", current_direction == EAST ? 'E' : 'W');
  79. 		INCREMENT(lists[FORWARD][HEAD]);
  80. 	} else {
  81. 		printf("-");
  82. 	}
  83. }
  84. void check_for_swap() {
  85. 	if (lists[FORWARD][HEAD] == lists[FORWARD][TAIL]) {
  86. 		lists[FORWARD][HEAD] = lists[FORWARD][TAIL] = 0;
  87. 		baboon *temp = lists[FORWARD];
  88. 		lists[FORWARD] = lists[BACKWARD];
  89. 		lists[BACKWARD] = temp;
  90. 		current_direction = !current_direction;
  91. 		if (use_starvation_queue) {
  92. 			temp = lists[BACKWARD];
  93. 			lists[BACKWARD] = lists[STARVATION];
  94. 			lists[STARVATION] = temp;
  95. 			use_starvation_queue = FALSE; // ***STARVATION SEMAPHORE P***
  96. 		}
  97. 	}
  98. }
  99. void initialize() {
  100. 	int i;
  101. 	lists = (baboon **) calloc(STARVATION + 1, sizeof(baboon*));
  102. 	for (i = 0; i <= STARVATION; i++)
  103. 		lists[i] = (baboon *) calloc(QUEUE_SIZE, sizeof(baboon));
  104. 	num_cycles = strlen(input);
  105. 	current_direction = input[0] == 'E' ? EAST : WEST;
  106. }
  107.  
  108. int lists_are_empty() {
  109. 	return (lists[FORWARD][HEAD] == lists[FORWARD][TAIL] && 
  110. 			lists[BACKWARD][HEAD] == lists[BACKWARD][TAIL] && 
  111. 			lists[STARVATION][HEAD] == lists[STARVATION][TAIL]);
  112. }
  113.  
  114. void swap(void *first, void *second) {
  115. 	void *swap = first;
  116. 	first = second;
  117. 	second = swap;
  118. }
  119.  
Success #stdin #stdout 0.01s 5304KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Cycle   1: -
Cycle   2: previous: 0previous_time: 2crossing_time: 3-
Cycle   3: E
Cycle   4: previous: 1previous_time: 1crossing_time: 3E
Cycle   5: previous: 0previous_time: 3crossing_time: 4-
Cycle   6: previous: 1previous_time: 4crossing_time: 5E
Cycle   7: previous: 2previous_time: 5crossing_time: 6-
Cycle   8: -
Cycle   9: previous: 3previous_time: 4crossing_time: 5W
Cycle  10: previous: 0previous_time: 3crossing_time: 4W
Cycle  11: previous: 1previous_time: 4crossing_time: 5W
Cycle  12: previous: 2previous_time: 5crossing_time: 6W
Cycle  13: previous: 4previous_time: 1crossing_time: 3W
Cycle  14: previous: 3previous_time: 6crossing_time: 7-
Cycle  15: previous: 4previous_time: 7crossing_time: 8W
Cycle  16: -
Cycle  17: -
Cycle  18: E
Cycle  19: E
Cycle  20: E
Cycle  21: E
Cycle  22: E
Cycle  23: E
https://ideone.com/iu1ypv
language:
C (gcc 8.3)
created:
11 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!