1 /*
2 (C) 2001 by Argonne National Laboratory.
3 See COPYRIGHT in top-level directory.
4 */
5 #define LOGGING
6 #include "mpi.h"
7 #ifdef USE_GRAPHICS
8 #define MPE_GRAPHICS
9 #include "mpe.h"
10 #endif
11 #include <stdio.h>
12 #include <math.h>
13
14 /* Numeric type representing a guess: double or unsigned long */
15 typedef double GUESST;
16 /* corresponding MPI type */
17 #define MPI_GUESST MPI_DOUBLE
18 /* 1 for GUESST=unsigned, 0 for DOUBLE */
19 #define GUESST_INTEGRAL 0
20
21 #if GUESS_INTEGRAL
22 #define MAX_GUESST 4294967295.0 /* 2^32 - 1 */
23 #else
24 #define MAX_GUESST 18014398509481984.0 /* 2^54 - 1 */
25 #endif
26
27 /* message tags */
28 #define GUESS 0
29 #define GUESS_LENGTH columns+2
30 /* guess[0], ..., guess[columns-1], row_num, guesses_done */
31 #define ACCEPTED 1
32 #define ACCEPTED_LENGTH 2
33 /* bulls, cows */
34 #define NEW_INFO 2
35 #define NEW_INFO_LENGTH columns+3
36 /* bulls, cows, guess[0],..., guess[columns-1], source*/
37 #define EXIT 3
38 #define EXIT_LENGTH 0
39 #define WON 4
40 #define WON_LENGTH 0
41 #define TASK 5
42 #define TASK_LENGTH 2
43 /* task_start, task_size */
44 #define TASK_REQ 6
45 #define TASK_REQ_LENGTH 0
46 #define FINISHED 7
47 #define FINISHED_LENGTH 1
48 #define MAX_MSG_LENGTH NEW_INFO_LENGTH
49
50 /* further internal tags */
51 #define REJECTED 5
52 #define PROGRESS 6
53
54
55 #ifdef USE_GRAPHICS
56 /* data for graphics */
57 #define HDIST 35
58 #define VDIST 50
59 #define ROWS 16
60 #define RADIUS 10
61 #define SCORE_RADIUS 3
62 #define SCORE_VDIST 8
63 #define SCORE_HDIST 8
64 #define SCORE_ROWS 4
65 #define SCORE_COLS 4
66 #define SCORE_WIDTH SCORE_COLS*SCORE_HDIST
67 #define WORKER_WIDTH 10
68 #define WORKER_HEIGHT 10
69 #define WORKER_HDIST 20
70 #define COLOURSCALE_WIDTH 20
71 #define COLOURSCALE_HDIST 30
72 #define SUCCESS_HEIGHT 4
73
74 /* Maps slave numbers 1, ..., numprocs-1 to MPE colours */
75 #define WorkerColour(N) N+1 /* To exclude black which is 1 */
76
77 /* Maps peg colours 0, ..., colours-1 to MPE colours */
78 #define PegColour(N) N+2
79
80 #endif /* USE_GRAPHICS */
81
82 /* max size of the mastermind board */
83 #ifdef USE_GRAPHICS
84 /* limitations of the graphics: */
85 #define MAXCOLS SCORE_ROWS*SCORE_COLS
86 #define MAXCOLOURS 14 /* black and white excluded from the 16 allowed colours*/
87 #else
88 #define MAXCOLS 20
89 #define MAXCOLOURS 100
90 #endif
91 #define MAXGUESSES 500
92
93 #define MAXTASKS 1000
94 #define MIN_TASK_SIZE 20
95
96 #define MASTER_RANK 0
97 #define NO_COLOUR -1 /* different from any valid peg colour */
98
99 /* global variables */
100 int numprocs;
101 int myid;
102 int colours, columns, numtasks;
103 GUESST guesses_done;
104 GUESST search_space_size;
105
106 int guess[MAXCOLS+2];
107 int secret[MAXCOLS];
108
109 /* DATA STRUCTURES */
110
111 /* the structure of the board (should better be a struct!)
112 board[i][0] [1] [2] ... [columns+1] [columns+2]
113 ----------- ----- --------- ---------------- -----------
114 bulls, cows, guess[0], ..., guess[columns-1], source (worker num)
115
116 */
117 int board[MAXGUESSES][MAXCOLS+3];
118 int sources[MAXGUESSES]; /* who does the guess come from */
119
120
121 typedef struct task
122 {
123 struct task *next;
124 struct task *previous;
125 int guess[MAXCOLS+2];
126 GUESST guess_number;
127 GUESST guesses_remaining;
128 } TASKT;
129
130 TASKT *free_tasks, *curr_task;
131
132 #define CURR_GUESS (curr_task->guess)
133 #define Check_Arg(Var, Txt, Low, High) \
134 if (Var > High || Var < Low)\
135 {\
136 if (myid == 0)\
137 printf("%s: %d, should be between %d and %d. Exiting.\n",\
138 Txt, Var, Low, High);\
139 MPI_Finalize();\
140 return;\
141 }
142
143 TASKT task_storage[MAXTASKS];
144
145 GUESST initial_tasks[MAXTASKS*2];
146
147 int next_row;
148 int freq_counter;
149 #define FREQUENCY 500
150
151 #ifdef USE_GRAPHICS
152 int height, width, left_col_width;
153 MPE_XGraph handle;
154 #endif
155
156 extern GUESST next_guess();
157
main(argc,argv)158 main(argc, argv)
159 int argc;
160 char *argv[];
161 {
162
163 MPI_Init(&argc, &argv);
164 MPI_Comm_size(MPI_COMM_WORLD, &numprocs);
165 MPI_Comm_rank(MPI_COMM_WORLD, &myid);
166
167
168 #ifdef LOGGING
169 MPE_Init_log();
170 MPE_Stop_log();
171 if (myid == 0) {
172 MPE_Describe_state(1, 2, "Send", "green:light_gray");
173 MPE_Describe_state(3, 4, "Admin", "blue:gray3");
174 MPE_Describe_state(5, 6, "Receive", "red:vlines3");
175 }
176 #endif
177
178
179 #ifndef INTERACTIVE
180 if (argc < 3)
181 {
182 if (myid == 0)
183 fprintf(stderr, "usage: %s colours columns [tasks]\n", argv[0]);
184 exit(1);
185 }
186
187 colours = atoi(argv[1]);
188 columns = atoi(argv[2]);
189
190 if (argc == 3)
191 numtasks = 997;
192 else
193 numtasks = atoi(argv[3]);
194
195 Check_Arg(colours, "Colours", 2, MAXCOLOURS);
196 Check_Arg(columns, "Columns", 2, MAXCOLS);
197 Check_Arg(numtasks,"Tasks", 1, MAXTASKS);
198 #endif
199
200 #ifdef USE_GRAPHICS
201 Check_Arg(numprocs, "Processors", 2, ROWS+1);
202 #endif
203
204 if (myid == 0)
205 master();
206 else
207 slave();
208
209
210 #ifdef LOGGING
211 MPE_Finish_log("gmm.log");
212 #endif
213
214
215 #ifdef USE_GRAPHICS
216 MPE_Close_graphics(&handle);
217 #endif
218 MPI_Finalize();
219 }
220
slave()221 slave()
222 {
223 int done;
224 GUESST skipped;
225 MPI_Status status;
226 int i, j, k, flag, count, colour;
227 int col_to_change;
228 int numslaves = numprocs-1;
229
230 guesses_done = 0;
231 next_row = 0;
232 initialize_mm();
233
234
235 #ifdef LOGGING
236 MPE_Start_log();
237 MPE_Log_event(3,0,"");
238 #endif
239
240 MPI_Recv(initial_tasks, MAXTASKS*2, MPI_GUESST,
241 MASTER_RANK, TASK, MPI_COMM_WORLD, &status);
242
243 #ifdef LOGGING
244 MPE_Log_event(4,0,"");
245 #endif
246
247
248 MPI_Get_count(&status, MPI_GUESST, &count);
249 count /= 2;
250
251 /* Get initial tasks */
252
253 for (i=0, j=0; i< count; i++, j+=2)
254 {
255 GUESST guessnum = initial_tasks[j];
256 task_storage[i].guess_number = guessnum;
257 task_storage[i].guesses_remaining = initial_tasks[j+1];
258 task_storage[i].previous = &task_storage[i-1];
259 task_storage[i].next = &task_storage[i+1];
260
261 for (k=columns-1; k>=0; k--)
262 {
263 #if GUESST_INTEGRAL
264 task_storage[i].guess[k] = guessnum % colours;
265 guessnum /= colours;
266 #else
267 colour = (int) fmod(guessnum, (double) colours);
268 task_storage[i].guess[k] = colour;
269 guessnum = floor(((guessnum-colour)/(double)colours)+.1);
270 #endif
271 }
272 }
273
274 task_storage[count-1].next = &task_storage[0];
275 task_storage[0].previous = &task_storage[count-1];
276 curr_task = &task_storage[0];
277
278 #ifdef DEBUG
279 for (i=0; i<count;i++)
280 {
281 printf("Task_storage[%d] (0x%x) = (num=%d, rem=%d, prev=0x%x, next=0x%x)\n",
282 i, &task_storage[i], task_storage[i].guess_number,
283 task_storage[i].guesses_remaining,
284 task_storage[i].previous,
285 task_storage[i].next);
286 }
287 #endif
288
289 init_free_task_storage(count);
290
291 #ifdef PRINTING
292 trace_guess("STARTING: ", "\n");
293 #endif
294 freq_counter = FREQUENCY;
295
296 done = 0;
297
298
299 while(!done)
300 {
301 if (freq_counter-- == 0)
302 {
303 #ifdef USE_GRAPHICS
304 draw_guess(myid-1, 1, CURR_GUESS, myid);
305 draw_progress(myid-1, PROGRESS, 0);
306 MPE_Update(handle);
307 #endif
308 while (1)
309 {
310 MPI_Iprobe(0, MPI_ANY_TAG, MPI_COMM_WORLD, &flag, &status);
311 if (flag == 1)
312 {
313 if (status.MPI_TAG == EXIT)
314 {
315 MPI_Recv(NULL, EXIT_LENGTH, MPI_INT, MASTER_RANK,
316 EXIT, MPI_COMM_WORLD, &status);
317 done = 1;
318 break;
319 }
320 else if (status.MPI_TAG == NEW_INFO)
321 {
322 MPI_Recv(&board[next_row][0], NEW_INFO_LENGTH, MPI_INT,
323 MASTER_RANK, NEW_INFO, MPI_COMM_WORLD, &status);
324 #ifdef USE_GRAPHICS
325 draw_progress(myid-1, NEW_INFO,
326 board[next_row][columns+2]);
327 MPE_Update(handle);
328 #endif
329 #ifdef PRINTING
330 printf("%2d: NEW INFO, row num: %d\n", myid, next_row);
331 #endif
332 next_row++;
333 }
334 else
335 break;
336 }
337 else
338 break;
339 }
340
341 freq_counter=FREQUENCY;
342 }
343
344 if (guess_consistent(&col_to_change))
345 {
346 #ifdef DEBUG
347 trace_guess("sending: ", "\n");
348 #endif
349 CURR_GUESS[columns] = next_row;
350 CURR_GUESS[columns+1] =
351 (int)(guesses_done/search_space_size*numslaves*100);
352 #ifdef LOGGING
353 MPE_Log_event(1,0,"");
354 #endif
355 MPI_Send(CURR_GUESS, GUESS_LENGTH, MPI_INT, MASTER_RANK,
356 GUESS, MPI_COMM_WORLD);
357 #ifdef LOGGING
358 MPE_Log_event(2,0,"");
359 MPE_Log_event(5,0,"");
360 #endif
361 MPI_Recv(&board[next_row][0], MAX_MSG_LENGTH, MPI_INT, MASTER_RANK,
362 MPI_ANY_TAG, MPI_COMM_WORLD, &status);
363 #ifdef LOGGING
364 MPE_Log_event(6,0,"");
365 #endif
366 switch (status.MPI_TAG)
367 {
368 case EXIT:
369 done = 1;
370 break;
371 case WON:
372 done = 1;
373 #ifdef USE_GRAPHICS
374 draw_progress(myid-1, ACCEPTED, 0);
375 MPE_Update(handle);
376 #endif
377 break;
378 case ACCEPTED:
379 #ifdef USE_GRAPHICS
380 draw_progress(myid-1, ACCEPTED, 0);
381 MPE_Update(handle);
382 #endif
383 for (i=0; i<columns; i++)
384 board[next_row][i+2] = CURR_GUESS[i];
385 next_row++;
386 next_guess(columns-1);
387 (curr_task->guess_number)++;
388 guesses_done++;
389 if ((--curr_task->guesses_remaining)<=0)
390 current_chunk_done(&done);
391 break;
392 case NEW_INFO:
393 #ifdef USE_GRAPHICS
394 draw_progress(myid-1, REJECTED,
395 board[next_row][columns+2]);
396 MPE_Update(handle);
397 #endif
398 #ifdef PRINTING
399 printf("%2d: NEW INFO, row num: %d\n", myid, next_row);
400 #endif
401 next_row++;
402
403 break;
404 default:
405 fprintf(stderr,"slave %d received invalid type %d\n",
406 myid, status.MPI_TAG);
407 done = 1;
408 }
409 }
410 else
411 {
412 #ifdef DEBUG
413 trace_guess("inconsis: ", ", ");
414 printf("col_to_change = %d\n", col_to_change);
415 #endif
416 skipped = next_guess(col_to_change);
417 if ((curr_task->guesses_remaining-=skipped) > 0)
418 {
419 guesses_done+=skipped;
420 curr_task->guess_number+=skipped;
421 }
422 else
423 {
424 guesses_done+=(curr_task->guesses_remaining+skipped);
425 current_chunk_done(&done);
426 }
427 }
428 if (!done)
429 curr_task = curr_task->next;
430 }
431
432 #ifdef PRINTING
433 trace_guess("LAST: ", "\n");
434 #endif
435
436
437 #ifdef USE_GRAPHICS
438 draw_guess(myid-1, 1, CURR_GUESS, myid);
439 draw_progress(myid-1, PROGRESS, 0);
440 MPE_Update(handle);
441 #endif
442
443 count = (int)(guesses_done/search_space_size*numslaves*100);
444
445 #ifdef LOGGING
446 MPE_Log_event(3,0,"");
447 #endif
448 MPI_Send(&count, FINISHED_LENGTH, MPI_INT, MASTER_RANK,
449 FINISHED, MPI_COMM_WORLD);
450 #ifdef LOGGING
451 MPE_Log_event(4,0,"");
452 #endif
453 }
454
current_chunk_done(done)455 current_chunk_done(done)
456 int *done;
457 {
458 TASKT *tmp;
459 if (curr_task->next == curr_task)
460 {
461 /* run out of work */
462 *done = 1;
463 }
464 else
465 {
466 curr_task->next->previous = curr_task->previous;
467 curr_task->previous->next = curr_task->next;
468 tmp = curr_task->previous;
469 add_to_free_list(curr_task);
470 curr_task = tmp;
471 }
472 }
473
master()474 master()
475 {
476 int row_num, source, worker, bulls, cows, done_pcnt, i, j;
477 int numslaves = numprocs-1;
478 int slaves_active;
479 int game_over = 0;
480 double starttime, endtime;
481 MPI_Status status;
482 GUESST tsk, last_guess, task_size, task_step;
483 GUESST task_info[TASK_LENGTH];
484
485 #ifdef INTERACTIVE
486 while (1)
487 {
488
489 while (1)
490 {
491 printf("Number of colours: ");
492 fflush(stdout);
493 i = scanf("%d", &colours);
494 while(getchar() != 10);
495 if ( i > 0 && colours > 1 && colours <= MAXCOLOURS )
496 break;
497 printf("This should be a number between 2 and %d\n", MAXCOLOURS);
498 }
499
500 while (1)
501 {
502 printf("Number of columns: ");
503 fflush(stdout);
504 i = scanf("%d", &columns);
505 while(getchar() != 10);
506 if (i > 0 && columns > 1 && columns <=MAXCOLS )
507 break;
508 else
509 printf("This should be a number between 2 and %d\n", MAXCOLS);
510 }
511
512 if (pow((double)colours, (double)columns) < MAX_GUESST)
513 break;
514 else
515 printf("colours ^ columns too big (should be < %f)\n", MAX_GUESST);
516 }
517 while (1)
518 {
519 printf("Number of tasks: ");
520 fflush(stdout);
521 i = scanf("%d", &numtasks);
522 while(getchar() != 10);
523 if (i > 0 && numtasks > 1 && numtasks <=MAXTASKS )
524 break;
525 else
526 printf("This should be a number between 2 and %d\n", MAXTASKS);
527 }
528 #endif
529
530 slaves_active = numslaves;
531 get_secret();
532 initialize_mm(0);
533
534 /* initial distribution of tasks */
535
536 task_size = search_space_size/numtasks;
537 if (task_size < MIN_TASK_SIZE)
538 task_size = MIN_TASK_SIZE;
539 task_step = numslaves*task_size;
540
541 #ifdef LOGGING
542 MPE_Start_log();
543 #endif
544
545 for (worker = 1; worker <= numslaves; worker++)
546 {
547 j=0;
548 for (tsk = (worker-1)*task_size; tsk<search_space_size; tsk+=task_step)
549 {
550 initial_tasks[j] = tsk;
551 if (tsk+task_size<=search_space_size)
552 initial_tasks[j+1] = task_size;
553 else
554 initial_tasks[j+1] = search_space_size-tsk;
555 j+=2;
556 }
557
558 #ifdef LOGGING
559 MPE_Log_event(3,0,"");
560 #endif
561 MPI_Send(initial_tasks, j, MPI_GUESST,
562 worker, TASK, MPI_COMM_WORLD);
563 #ifdef LOGGING
564 MPE_Log_event(4,0,"");
565 #endif
566 }
567
568 starttime = MPI_Wtime();
569
570
571 while(!game_over)
572 {
573
574 #ifdef LOGGING
575 MPE_Log_event(5,0,"");
576 #endif
577 MPI_Recv(guess, MAX_MSG_LENGTH, MPI_INT, MPI_ANY_SOURCE,
578 MPI_ANY_TAG, MPI_COMM_WORLD, &status);
579 #ifdef LOGGING
580 MPE_Log_event(6,0,"");
581 #endif
582 source = status.MPI_SOURCE;
583 switch (status.MPI_TAG)
584 {
585 case FINISHED:
586 printf("Slave %d finished at%8.3f, %2d%%(s%d)\n",
587 source, MPI_Wtime()-starttime, guess[0], source);
588 slaves_active--;
589 break;
590 case GUESS:
591 row_num = guess[columns];
592 done_pcnt = guess[columns+1];
593 if (row_num == next_row)
594 {
595 eval_guess(guess, secret, &bulls, &cows);
596
597 board[next_row][0] = bulls;
598 board[next_row][1] = cows;
599 for (i=0; i<columns; i++)
600 board[next_row][i+2] = guess[i];
601
602 /* printf("%2d: %3d. ", source, next_row); */
603 printf("%3d. ", next_row+1);
604 print_guess("", guess);
605 printf("(%2db %2dc)%8.3fs, %2d%%(s%d)\n",
606 bulls, cows, MPI_Wtime()-starttime,
607 done_pcnt, source);
608 if (bulls == columns) /* game over */
609 {
610 for (i = 1; i <= numslaves; i++)
611 MPI_Send(NULL, EXIT_LENGTH, MPI_INT, i,
612 (i==source?WON:EXIT), MPI_COMM_WORLD);
613 game_over = 1;
614 }
615 else
616 {
617 for (i = 1; i <= numslaves; i++)
618 {
619 #ifdef LOGGING
620 MPE_Log_event(1,0,"");
621 #endif
622 if (i == source)
623 MPI_Send(&board[next_row][0], ACCEPTED_LENGTH, MPI_INT,
624 source, ACCEPTED, MPI_COMM_WORLD);
625 else
626 {
627 board[row_num][columns+2] = source;
628 MPI_Send(&board[row_num][0], NEW_INFO_LENGTH,
629 MPI_INT, i, NEW_INFO, MPI_COMM_WORLD);
630 }
631 #ifdef LOGGING
632 MPE_Log_event(2,0,"");
633 #endif
634 }
635 }
636 #ifdef USE_GRAPHICS
637 sources[next_row] = source;
638 if (next_row < ROWS)
639 {
640 draw_guess(next_row, 0, guess, source);
641 draw_score(next_row, bulls, cows);
642 }
643 else /* scroll */
644 for (i = next_row-ROWS+1, j = 0; i <=next_row; i++, j++)
645 {
646 draw_guess(j, 0, &board[i][2], sources[i]);
647 draw_score(j, board[i][0], board[i][1]);
648 }
649 MPE_Update(handle);
650 #endif
651 if (++next_row >= MAXGUESSES)
652 {
653 printf("Mastermind board overflow, aborting\n");
654 for (i = 1; i <= numslaves; i++)
655 MPI_Send(NULL, EXIT_LENGTH, MPI_INT, i, EXIT,
656 MPI_COMM_WORLD);
657 game_over = 1;
658 }
659
660 }
661 break;
662 default:
663 fprintf(stderr,"master received invalid type %d\n",
664 status.MPI_TAG);
665 }
666 }
667 endtime = MPI_Wtime();
668 printf("MM for %2d slaves, %2d colours, %2d columns: %8.3fs, %2d guesses\n",
669 numslaves, colours, columns, endtime - starttime, next_row);
670
671 while(slaves_active)
672 {
673 #ifdef LOGGING
674 MPE_Log_event(3,0,"");
675 #endif
676 MPI_Recv(guess, MAX_MSG_LENGTH, MPI_INT, MPI_ANY_SOURCE,
677 MPI_ANY_TAG, MPI_COMM_WORLD, &status);
678 #ifdef LOGGING
679 MPE_Log_event(4,0,"");
680 #endif
681 source = status.MPI_SOURCE;
682 switch (status.MPI_TAG)
683 {
684 case FINISHED:
685 printf("Slave %d finished at%8.3f, %2d%%(s%d)\n",
686 source, MPI_Wtime()-starttime, guess[0], source);
687 slaves_active--;
688 break;
689 case GUESS:
690 break;
691 default:
692 fprintf(stderr,"master received invalid type %d\n",
693 status.MPI_TAG);
694 }
695 }
696
697 #ifdef USE_GRAPHICS
698 /* just testing */
699 MPE_Draw_string (handle, 15, 15, MPE_BLACK, "Hello, world!" );
700 /* */
701
702 printf("Any key to exit\n");
703 scanf("%c",&i);
704 #endif
705 }
706
next_guess(col)707 GUESST next_guess(col)
708 int col;
709 {
710 int i;
711 GUESST pos = 1, cnt = 0;
712 for (i = columns-1; i>=col+1; i--)
713 {
714 cnt += CURR_GUESS[i]*pos;
715 CURR_GUESS[i] = 0;
716 pos *= colours;
717 }
718
719 for (i = col; i>=0; i--)
720 if (CURR_GUESS[i] < colours-1)
721 {
722 CURR_GUESS[i]++;
723 break;
724 }
725 else /* CURR_GUESS[i] == colours-1 */
726 CURR_GUESS[i] = 0;
727
728 return pos - cnt;
729 }
730
731
eval_guess(guess,code,bulls,cows)732 eval_guess(guess, code, bulls, cows)
733 int guess[], code[];
734 int *bulls, *cows;
735 {
736 int i,j;
737 int tmp[MAXCOLS];
738
739 for (i=0; i<columns; i++)
740 tmp[i] = guess[i];
741
742 *bulls = 0;
743 *cows = 0;
744 for (i=0; i<columns; i++)
745 if (guess[i] == code[i])
746 (*bulls)++;
747 for (i=0; i<columns; i++)
748 for (j=0; j<columns; j++)
749 if (code[i] == tmp[j])
750 {
751 (*cows)++;
752 tmp[j] = -1; /* nonexistent colour */
753 break;
754 }
755 *cows -= *bulls;
756 }
757
758 /*
759 col is initially set to 'columns', i.e. the column after the last one
760 (columns being numbered from 0 to columns-1).
761
762 When an inconsistency with a row of the board is found, col is set to
763 the column where the inconsistency is detected.
764
765 After an inconsistency has been found, we still keep checking the board,
766 so that further rows of the board can cause col to move leftwards (I
767 don't know if this pays off, perhaps worth profiling).
768
769 If all rows tested and col still points to 'columns', than the guess is
770 found to be consistent with the board.
771
772 Otherwise the guess is inconsistent and col is returned as the leftmost
773 col_to_change.
774
775 */
776
guess_consistent(col_to_change)777 guess_consistent(col_to_change)
778 int *col_to_change;
779 {
780 int bulls, bullscows, col, row, peg;
781 int *board_row;
782 int i,j;
783 int tmp[MAXCOLS];
784
785 col = columns;
786
787 for (row = 0; row < next_row; row++)
788 {
789 board_row = &board[row][2];
790 bulls = board[row][0];
791 bullscows = board[row][1]+bulls;
792
793 for (i=0; i<columns; i++)
794 tmp[i] = board_row[i];
795
796 for (i=0; i < col; i++)
797 {
798 if (CURR_GUESS[i] == board_row[i]) /* bull */
799 {
800 if ((bulls--) <= 0) /* too many bulls */
801 break;
802 }
803 j = 0;
804 peg = CURR_GUESS[i];
805 while ( j < columns && peg != tmp[j])
806 j++;
807 if (j < columns ) /* bull or cow */
808 if (bullscows-- <= 0) /* too many bulls or cows */
809 break;
810 else
811 tmp[j] = NO_COLOUR;
812 if (bullscows >= columns-i) /* too few bulls of cows */
813 break;
814 }
815 col = i;
816 }
817
818 if (col == columns)
819 return 1;
820
821 *col_to_change = col;
822 return 0;
823 }
824
print_guess(text,guess)825 print_guess(text, guess)
826 char *text;
827 int guess[];
828 {
829 int i;
830
831 printf("%s", text);
832 for (i=0; i<columns; i++)
833 {
834 printf("%2d ", guess[i]);
835 }
836 }
837
838 #ifdef USE_GRAPHICS
draw_guess(row,col,guess,id)839 draw_guess(row, col, guess, id)
840 int row, col, id;
841 int guess[];
842 {
843 int i;
844 int hpos = left_col_width*col+HDIST+WORKER_HDIST;
845 int vpos = (row+2)*VDIST;
846
847 MPE_Fill_rectangle(handle, hpos-(HDIST-2*RADIUS+WORKER_WIDTH),
848 (int)(vpos-WORKER_HEIGHT/2), WORKER_WIDTH, WORKER_HEIGHT,
849 WorkerColour(id));
850
851 for (i=0; i<columns; i++)
852 {
853 MPE_Fill_circle( handle, hpos, vpos, RADIUS, PegColour(guess[i]) );
854 hpos += HDIST;
855 }
856 }
857
draw_score(row,bulls,cows)858 draw_score(row, bulls, cows)
859 int row, bulls, cows;
860 {
861 int r,c, i;
862 int vpos = (row+2)*VDIST-RADIUS+SCORE_RADIUS;
863 int hpos = left_col_width-HDIST-SCORE_WIDTH;
864
865 for (r=0; r<SCORE_ROWS; r++)
866 for (c=0; c<SCORE_COLS; c++)
867 {
868 i = SCORE_COLS*r+c;
869 if (i < bulls)
870 MPE_Fill_circle( handle, hpos+SCORE_HDIST*c,
871 vpos+SCORE_VDIST*r, SCORE_RADIUS, MPE_BLACK);
872 else if (i < bulls+cows)
873 MPE_Draw_circle( handle, hpos+SCORE_HDIST*c,
874 vpos+SCORE_VDIST*r, SCORE_RADIUS, MPE_BLACK);
875 else
876 break;
877 }
878 }
879
draw_progress(row,type,source)880 draw_progress(row, type, source)
881 int row, type, source;
882 {
883 int hpos = left_col_width+HDIST+WORKER_HDIST-RADIUS;
884 int vpos = (row+2)*VDIST+2*RADIUS;
885 int length;
886
887 length = (int)((((double) guesses_done)/search_space_size)
888 * ((columns-1)*HDIST+2*RADIUS));
889
890 MPE_Draw_line(handle, hpos, vpos, hpos+length, vpos, MPE_BLACK);
891
892 switch (type)
893 {
894 case PROGRESS:
895 break;
896 case ACCEPTED:
897 MPE_Draw_line(handle, hpos+length, vpos, hpos+length,
898 vpos-2*SUCCESS_HEIGHT, WorkerColour(myid));
899 break;
900 case REJECTED:
901 MPE_Draw_line(handle, hpos+length, vpos, hpos+length,
902 vpos+SUCCESS_HEIGHT, MPE_BLACK);
903 case NEW_INFO:
904 MPE_Draw_line(handle, hpos+length, vpos, hpos+length,
905 vpos-SUCCESS_HEIGHT, WorkerColour(source));
906 break;
907 }
908 }
909
910 #endif
911
get_secret()912 get_secret()
913 {
914 int i;
915
916 for (i=0; i<columns; i++)
917 if (i<colours)
918 secret[i] = colours-1-i;
919 else
920 secret[i] = 0;
921 }
922
int_power(n,m)923 GUESST int_power(n, m)
924 int n,m;
925 {
926 int i;
927 GUESST pw = 1;
928
929 for (i=0; i<m; i++)
930 pw*=n;
931
932 return pw;
933 }
934
initialize_mm()935 initialize_mm()
936 {
937 int right_col_width, colourscale_width, i;
938
939 MPI_Bcast(&colours, 1, MPI_INT, 0, MPI_COMM_WORLD);
940 MPI_Bcast(&columns, 1, MPI_INT, 0, MPI_COMM_WORLD);
941
942 search_space_size = int_power(colours, columns);
943
944 #ifdef USE_GRAPHICS
945 left_col_width = WORKER_HDIST+(columns+2)*HDIST+SCORE_WIDTH;
946 right_col_width = (columns+1)*HDIST;
947 colourscale_width = (colours+2)*COLOURSCALE_HDIST;
948 if (right_col_width < colourscale_width)
949 right_col_width = colourscale_width;
950 width = left_col_width+WORKER_HDIST+right_col_width;
951 height = (ROWS+2)*VDIST - VDIST/2;
952
953 MPE_Open_graphics( &handle, MPI_COMM_WORLD, (char*)0,
954 -1, -1, width, height, MPE_GRAPH_INDEPDENT);
955
956 if (myid > 0)
957 return;
958
959 for (i=0; i<columns; i++)
960 {
961 MPE_Fill_circle( handle, HDIST*(i+1)+WORKER_HDIST,
962 (int)(0.6*VDIST), RADIUS, PegColour(secret[i]) );
963 }
964 for (i=0; i<colours; i++)
965 {
966 MPE_Fill_rectangle(handle, left_col_width+HDIST+WORKER_HDIST-RADIUS
967 +i*COLOURSCALE_HDIST, (int)(0.6*VDIST)-RADIUS,
968 COLOURSCALE_WIDTH, 2*RADIUS,
969 PegColour(i));
970 }
971 MPE_Draw_line(handle, 0, (int)(1.3*VDIST), width, (int)(1.3*VDIST),
972 MPE_BLACK);
973 MPE_Draw_line(handle, 0, (int)(1.4*VDIST), width, (int)(1.4*VDIST),
974 MPE_BLACK);
975 MPE_Draw_line(handle, (int)(left_col_width-0.3*HDIST), 0,
976 (int)(left_col_width-0.3*HDIST), height,
977 MPE_BLACK);
978 MPE_Draw_line(handle, (int)(left_col_width-0.4*HDIST), 0,
979 (int)(left_col_width-0.4*HDIST), height,
980 MPE_BLACK);
981 #endif
982 }
983
trace_guess(txt1,txt2)984 trace_guess(txt1, txt2)
985 char *txt1, *txt2;
986 {
987 printf("%2d: ", myid);
988 print_guess(txt1, CURR_GUESS);
989 printf(", guesses_done = %d%s", guesses_done, txt2);
990 }
991
init_free_task_storage(used)992 init_free_task_storage(used)
993 int used;
994 {
995 int i;
996
997 if (used<MAXTASKS)
998 {
999 for (i=used; i < MAXTASKS-1; i++)
1000 {
1001 task_storage[i].next = &task_storage[i+1];
1002 task_storage[i+1].previous = &task_storage[i];
1003 }
1004
1005 task_storage[MAXTASKS-1].next = NULL;
1006 task_storage[used].previous = NULL;
1007 free_tasks = &task_storage[used];
1008 }
1009 else
1010 free_tasks = NULL;
1011 }
1012
add_to_free_list(task)1013 add_to_free_list(task)
1014 TASKT *task;
1015 {
1016 task->next = free_tasks;
1017 task->previous = NULL;
1018 free_tasks->previous = task;
1019 free_tasks = task;
1020 }
1021