Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
2nd International KNOBELN Contest (part2/2)
0 views
Skip to first unread message
Lutz Prechelt
Mar 24, 1994, 2:12:04 PM3/24/94
to
#! /bin/sh
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: knobellib.c knobeln.c knobeln.cr
# Wrapped by prechelt@Sofia on Thu Mar 24 19:28:01 1994
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'knobellib.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'knobellib.c'\"
else
echo shar: Extracting \"'knobellib.c'\" \(3552 characters\)
sed "s/^X//" >'knobellib.c' <<'END_OF_FILE'
X/*************************************************************************
XFile : knobellib.c: Library for Knobeln strategies
XAutor : Lutz Prechelt, Karlsruhe, Germany (prec...@ira.uka.de)
XDate : 94/03/05
XLanguage: Kernighan/Ritchie C
X**************************************************************************/
X
X/*
X
X Library for strategy programs in the Knobeln-Contest
X ------------------------------------------------------
X
XThis file is functionally equivalent (but not necessarily identical) to
Xwhat your strategy will be linked with in the contest.
XYou must compile it with
X
X cc -c knobellib.c
X
X(or the like) and can then create an executable version "strat" of your
Xstrategy (supposed it is in a file called "strat.c") with something
Xlike
X
X cc -o strat strat.c knobellib.o
X
XYou must not use any include files in strat.c
XYou must not call any functions that are neither local to strat.c nor
Xdefined in the interface of this library, or otherwise your program
Xwill not compile when the contest is run.
X
XThis module is written to compile on BSD-UNIX systems. For other
Xsystems modifications might be necessary.
XIn particular, if your system does not have random()/srandom() you may
Xwant to try rand()/srand() instead.
X
X
X
XThe interface of the library is:
X
Xint init_random ()
X Initializes the random number generator in some not reproducible
X way. Returns 0.
X
Xint log2 (int number)
X Returns the biggest integer that is smaller or equal to the
X base 2 logarithm of the positive <number>.
X
Xint next_random (int low, int high)
X Returns a random number in the range [low...high]
X Preconditions: -32767 <= low <= high <= 32767 and
X (high - low) <= 32767
X
Xint make_throw (int my_throw)
X Outputs my_throw on stdout
X (i.e. transmits your own throw to the referee program), then
X reads your partners throw from stdin and returns it.
X
Xint count_points (int throw1, int throw2, int *points1, int *points2);
X Increases *points1 by log2(throw1), if throw1 wins against throw2, or
X increases *points2 by log2(throw2), if throw2 wins against throw1.
X Returns 0 if nobody wins, 1 if throw1 wins and 2 if throw2 wins.
X
X************************************************************************/
X
X
X#include <stdio.h> /* to define NULL and stdout */
X
Xint init_random ()
X{
X /* If getpid() is not available on your system, just replace it by 0 */
X srandom ((int)(time(NULL) ^ getpid()));
X return (0);
X}
X
X
Xint log2 (number)
X register int number;
X{
X register int i = 0;
X while(number >>= 1)
X i++;
X return i;
X}
X
X
Xint next_random (low, high)
X int low, high;
X{
X /* return 0 if preconditions not met */
X /* Use random() random number generator */
X if (low < -32767 || high > 32767 || low > high ||
X (int)((long)high - (long)low) > 32767)
X return (0);
X return ((int)(random() % (long)(high - low + 1)) + low);
X}
X
X
Xint make_throw (my_throw)
X int my_throw;
X{
X int your_throw, r;
X printf ("%d\n", my_throw); fflush (stdout);
X r = scanf ("%d", &your_throw);
X if (r == EOF) /* terminate program on end of file */
X exit (0);
X return (your_throw);
X}
X
X
Xint count_points (throw1, throw2, points1, points2)
X int throw1, throw2,
X *points1, *points2;
X{
X if (throw1 == throw2) { /* nobody wins */
X return (0);
X }
X if ((throw1 > throw2 && !(throw1 > 2*throw2)) || /* throw1 wins with bigger */
X (2*throw1 < throw2)) { /* throw1 wins with smaller number */
X *points1 += log2 (throw1);
X return (1);
X }
X /* otherwise throw2 wins: */
X *points2 += log2 (throw2);
X return (2);
X}
END_OF_FILE
if test 3552 -ne `wc -c <'knobellib.c'`; then
echo shar: \"'knobellib.c'\" unpacked with wrong size!
fi
# end of 'knobellib.c'
fi
if test -f 'knobeln.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'knobeln.c'\"
else
echo shar: Extracting \"'knobeln.c'\" \(24048 characters\)
sed "s/^X//" >'knobeln.c' <<'END_OF_FILE'
X
X/*************************************************************************
XProject : KNOBELN
XModule : Conductor and referee for one game
XAuthor : Lutz Prechelt, Karlsruhe
XDate : 25.09.93
XEnvironment: SUN-OS 4.1, ANSI-C (gcc), C-Refine
XRCS : $Id$
X**************************************************************************/
X
X#if 0
X
Xusage: knobeln first second [L a b k maxcpu maxmem show_interval]
X
XConducts a game of Knobeln with L throws in the interval a..b
Xminimum sequence length is k, opponent strategies are 'first' and 'second'.
XThe strategies are Unix programs, who on every throw write one number
Xtextually to stdout and then read one from stdin. Each number is ended
Xwith a newline character. Each module is allowed to use at most maxcpu
Xseconds of cpu time and maxmem kilobytes process size (SIZE field of ps).
XThe intermediate result is shown after every show_interval throws.
XFor the default values see the #define std_... below.
X
XThis program transduces the numbers thrown between the opponents,
Xchecks for the rules and computes the result.
X
X
XMethod:
X-------
XThe program creates two pipes for each opponent program.
XThe opponent programs are started via fork and exec.
XThe timeout, cputime, and space limitations are checked by a routine
Xthat is invoked by a timer alarm and reads from 'popen("ps -ux")'
XThe scanning of the ps output is critical to portability, i.e.
Xyou may need to adjust get_process_info() for a different kind of Unix.
X
XOutput:
X-------
XThe program writes three files:
X the protocol the compact protocol, and the bulletin.
XThe protocol looks like this:
X------------------------------------------------------------------------
X1000-throw KNOBELN (interval 1...12288, minimum sequence length 8)
XPlayer 1: "fribyte"
XPlayer 2: "GrandPrix"
X 1: 1 6700 -> 0 : 0
X 2: 3349 10714 -> 11 : 0
X 3: 5356 11412 -> 23 : 0
X 4: 5705 12006 -> 35 : 0
X.... (here are the lines for the other throws)
X999: 12288 12288 -> 7870 : 1112
X1000: 12288 12288 -> 7870 : 1112
X
XGame ended normally.
XResult:
X "fribyte": 7870 points
X "GrandPrix": 1112 points
X------------------------------------------------------------------------
XThe corresponding short protocol looks like this:
X
X1 6700
X3349 10714
X5356 11412
X5705 12006
X.... (here are the lines for the other throws)
X12288 12288
X12288 12288
X------------------------------------------------------------------------
XThe bulletin is a one-line file and has one of the following forms:
X
Xteam_name_1 : team_name_2 -> 345 : 536
Xteam_name_1 : team_name_2 -> Failure of player 1
Xteam_name_1 : team_name_2 -> Failure of player 2
Xteam_name_1 : team_name_2 -> Failure of both players
X
X#endif
X
X/*************************************************************************/
X/***** USES **************************************************************/
X/*************************************************************************/
X
X#include <assert.h>
X#include <stdio.h>
X#include <signal.h>
X
X
X/*************************************************************************/
X/***** PRIVATE Constants, Types, Variables, Functions ******************/
X/*************************************************************************/
X
Xtypedef enum {false, true} bool;
X
X#define shortprotocolfilename "knobeln.prot"
X#define protocolfilename "knobeln.protocol"
X#define bulletinfilename "knobeln.bulletin"
X
X#define std_L 1000
X#define std_a 1
X#define std_b 12288
X#define std_k 8
X#define std_maxcpu 60
X#define std_maxmem 1024
X
X#define alarm_interval 10 /* check processes all ... seconds */
X
X
X#define p_read 0
X#define p_write 1
X#define _first 0
X#define _second 1
X#define _nobody -1
X/* example to[_first][p_write] is the file descriptor used by the parent
X process to write to the 'first' subprocess
X*/
X
Xstatic char *name[2]; /* the strategies' names */
Xstatic int a, b, L, k; /* the game parameters */
Xstatic int maxcpu, maxmem; /* the runtime restrictions */
Xstatic int display_interval;
Xstatic bool display_on_alarm;
Xstatic FILE *protocol, /* the protocol file */
X *prot, /* the short-protocol file */
X *bulletin; /* the result file */
Xstatic int result[2], /* current points */
X current[2]; /* last numbers thrown */
Xstatic int from[2][2],
X to[2][2]; /* the pipes */
Xstatic int process_id[2] =
X { -1, -1 }; /* the child processes */
Xstatic int throw_nr, /* number of current throw */
X old_throw_nr = 0, /* throw_nr at last alarm */
X next_to_throw; /* which player's turn it is */
X
X
X/* Signal handling and process handling:*/
Xvoid alarm_catcher();
Xvoid kill_child_processes ();
Xvoid terminate_abnormally (int status);
Xvoid terminate_by_signal ();
Xvoid terminate_normally ();
Xvoid watch (const int pids[2], char *name[2], int maxcpu, int maxmem,
X int throw_nr, int old_throw_nr);
Xvoid get_process_info (const int pids[2], bool still_living[2],
X int cpu[2], int mem[2]);
X
X/* help functions: */
Xvoid display ();
Xint log2 (int n);
Xint read_int (int fd, const char *name);
X
X/* game conductor: */
Xvoid play (int to[2][2], int from[2][2], char *name[2],
X FILE *protocol, FILE *prot,
X int result[2], int a, int b, int L, int k,
X int maxcpu, int maxmem, int display_interval);
X
X/* main: */
Xint main (int argc, char *argv[]);
X
X/*************************************************************************/
X/***** IMPLEMENTATION of private Functions *******************************/
X/*************************************************************************/
X
Xvoid alarm_catcher()
X{
X /* handler for SIGALARM */
X watch (process_id, name, maxcpu, maxmem, throw_nr, old_throw_nr);
X old_throw_nr = throw_nr;
X if (display_on_alarm)
X display ();
X alarm (alarm_interval);
X}
X
Xvoid kill_child_processes ()
X{
X int i, result;
X for (i = _first; i <= _second; i++) {
X if ((
X process_id[i])
X > 0) {
X result = kill ((
X process_id[i])
X , SIGKILL);
X /* fprintf (stderr, "kill -9 %d --> %d ", `this_process, result); */
X }
X }
X}
X
X
Xvoid terminate_abnormally (int exit_status)
X{
X /* actions to perform on termination because of error */
X alarm (0);
X kill_child_processes();
X exit (exit_status);
X}
X
X
Xvoid terminate_by_signal ()
X{
X /* actions to perform when interrupt signal is catched */
X fprintf (stderr, "\nSignal catched. \n");
X alarm (0);
X kill_child_processes();
X exit (1);
X}
X
X
Xvoid terminate_normally ()
X{
X /* actions to perform when normal end of program is reached */
X alarm (0);
X kill_child_processes();
X exit (0);
X}
X
X
Xvoid watch (const int process_id[2], char *name[2],
X int maxcpu, int maxmem, int throw_nr, int old_throw_nr)
X{
X /* This function is activated from the timer alarm catcher.
X It checks, whether the child processes identified by process_id are
X still alive, have consumed not more than maxcpu seconds cputime and
X don't use more than maxmem kilobytes of memory.
X It also checks whether the game has made any progress since the
X last alarm by comparing throw_nr with old_throw_nr. If no progress
X was made, the blame is put on next_player_to_throw which is
X either _first or _second.
X */
X bool still_living[2], failure[2];
X int cpu[2], mem[2];
X int i;
X failure[_first] = failure[_second] = false;
X get_process_info (process_id, still_living, cpu, mem);
X for (i = _first; i <= _second; i++) {
X if (!still_living[i])
X { /* process_terminated_prematurely (Level 1) */
X fprintf (protocol, "\nProcess \"%s\" terminated prematurely.", name[i]);
X fprintf (prot, "\nProcess \"%s\" terminated prematurely.", name[i]);
X fprintf (stderr, "\nProcess \"%s\" terminated prematurely.", name[i]);
X failure[i] = true;
X }
X else {
X if (mem[i] > maxmem)
X { /* process_too_large (Level 1) */
X fprintf (protocol, "\nProcess \"%s\" uses too much memory: %d kb",
X name[i], mem[i]);
X fprintf (prot, "\nProcess \"%s\" uses too much memory: %d kb",
X name[i], mem[i]);
X fprintf (stderr, "\nProcess \"%s\" uses too much memory: %d kb\n",
X name[i], mem[i]);
X failure[i] = true;
X }
X if (cpu[i] > maxcpu)
X { /* process_used_too_much_time (Level 1) */
X fprintf (protocol, "\nProcess \"%s\" used too much CPU time", name[i]);
X fprintf (prot, "\nProcess \"%s\" used too much CPU time", name[i]);
X fprintf (stderr, "\nProcess \"%s\" used too much CPU time\n", name[i]);
X failure[i] = true;
X }
X }
X }
X if (throw_nr == old_throw_nr)
X ; /* we catch this case via cputime check. Processes can't stop! */
X if (failure[_first] || failure[_second])
X { /* write_bulletin_and_terminate (Level 1) */
X char *message = "";
X if (failure[_first] && failure[_second])
X message = "Failure of both players";
X else if (failure[_first])
X message = "Failure of player 1";
X else if (failure[_second])
X message = "Failure of player 2";
X fprintf (protocol, "\nGame ended unnormally: %s\n", message);
X fprintf (prot, "\nGame ended unnormally: %s\n", message);
X fprintf (bulletin, "%-30s : %30s -> %s\n",
X name[_first], name[_second], message);
X terminate_normally();
X }
X}
X
X
Xvoid get_process_info (const int process_id[2], bool still_living[2],
X int cpu[2], int mem[2])
X{
X /* uses 'popen ("ps -ux")' to get information about the child processes.
X returns in still_living, whether they still exist, and if yes, returns
X in maxmem how many kilobytes their SIZE is and how many seconds of
X CPU time they have consumed.
X */
X FILE *ps = popen ("ps -ux", "r");
X char lbuf[(
X 200)
X ]; /* line buffer */
X int nr_of_processes_found = 0;
X { /* discard_header_line (Level 1) */
X fgets (lbuf, (
X 200)
X , ps);
X }
X still_living[_first] = false;
X still_living[_second] = false;
X while (!feof (ps) && nr_of_processes_found < 2)
X { /* examine_next_line (Level 1) */
X /* Outputformat of 'ps -ux' (SUN-4, Sun-OS 4.1):
X#USER____ PID__ CP.U ME.M SZ__ RSS_ TT STAT START TIME__ COMMAND________
X prechelt 12945 11.8 2.9 180 420 p4 R 08:15 0:00 ps -u
X 0 1 2 3 4 5 6
X 0123456789012345678901234567890123456789012345678901234567890123456789
X ^ $ ^ $ ^ $ ^ $^ $^ $ ^$ ^ $ ^ $^ $ ^
X */
X char ccc[20]; /* a few chars from lbuf */
X int index;
X int pid;
X char STAT; /* first char of STAT field */
X int SZ, /* value of SZ field */
X RSS, /* value of RSS field */
X TIME; /* value of TIME field in seconds for form mmm:mm*/
X fscanf (ps, "%s %d", ccc, &pid); /* read username and process id */
X fgets (lbuf, (
X 200)
X , ps); /* read rest of line, starting at column `offset */
X if (pid != process_id[_first] && pid != process_id[_second])
X goto examine_next_line_1;
X nr_of_processes_found++;
X index = (pid == process_id[_first]) ? _first : _second;
X fprintf (stdout, "#%s", lbuf);
X { /* get_SZ (Level 2) */
X strncpy (ccc, lbuf - (
X 14)
X + (
X 24)
X , (
X 5)
X );
X ccc[(
X 5)
X ] = 0; /* put null terminator behind */
X SZ = atoi (ccc);
X }
X { /* get_RSS (Level 2) */
X strncpy (ccc, lbuf - (
X 14)
X + (
X 29)
X , (
X 5)
X );
X ccc[(
X 5)
X ] = 0; /* put null terminator behind */
X RSS = atoi (ccc);
X }
X { /* get_STAT (Level 2) */
X STAT = lbuf[-(
X 14)
X + (
X 38)
X ];
X }
X { /* get_TIME (Level 2) */
X if ((
X lbuf[(
X 52)
X - (
X 14)
X ] == ':')
X ) {
X strncpy (ccc, lbuf - (
X 14)
X + (
X 49)
X , (
X 3)
X );
X ccc[(
X 3)
X ] = 0; /* put null terminator behind */
X TIME = 60 * atoi (ccc);
X strncpy (ccc, lbuf - (
X 14)
X + (
X 53)
X , (
X 2)
X );
X ccc[(
X 2)
X ] = 0; /* put null terminator behind */
X TIME += atoi (ccc);
X }
X else {
X TIME = 3600 + 1; /* see test at `get options in main() */
X }
X }
X { /* interpret_values (Level 2) */
X assert (STAT >= 'A' && STAT <= 'Z');
X still_living[index] = (STAT != (
X 'Z')
X );
X cpu[index] = TIME;
X mem[index] = SZ;
X }
Xexamine_next_line_1: ;
X }
X pclose (ps);
X}
X
X
Xvoid display ()
X{
X fprintf (stdout, "%7d: %8d %8d --> %6d : %d\n", throw_nr,
X current[_first], current[_second],
X result[_first], result[_second]);
X}
X
X
Xint log2 (int n)
X{
X /* returns the floor part of logarithmus dualis of n.
X n has to be positive, but is not checked.
X */
X int result = 0;
X while (n > 1) {
X n >>= 1;
X result++;
X }
X return (result);
X}
X
X
Xint read_int (int fd, const char *name)
X{
X /* Reads characterwise from file descriptor fd. This reading must
X deliver a single integer.
X If no integer is found, complains about strategy 'name' breaking
X the rules and exits.
X */
X int result = 0;
X int sign = 1;
X char c;
X for (;;) {
X read (fd, &c, 1);
X if (c == ' ')
X { /* handle_blanks (Level 1) */
X if (result == 0)
X ; /* ignore leading spaces */
X else /* trailing spaces */
X return (sign*result);
X }
X else if (c == '\n')
X return (sign*result);
X else if (c == '-')
X sign *= -1;
X else if (c >= '0' && c <= '9')
X result = 10*result + c - '0';
X else
X { /* complain_loudly (Level 1) */
X fprintf (stderr, "\n>>> \"%s\" %s '%c' (code %d). Game aborted <<<\n",
X name, "transfers illegal character", c, (int)c);
X terminate_abnormally (2);
X }
X }
X}
X
X
Xvoid play (int to[2][2], int from[2][2], char *name[2],
X FILE *protocol, FILE *prot,
X int result[2], int a, int b, int L, int k,
X int maxcpu, int maxmem, int display_interval)
X{
X /* conducts a game between the two strategies accessible via the pipe pairs
X <to> and <from> having the names accessible in <name>.
X A protocol is written on FILE <protocol>, a short protocol on <prot>.
X The results are returned in <result> which is initialized with zeroes
X at the beginning.
X The game is of length L, in the interval a..b, with
X minimum sequence length k
X */
X int sequence_length[2]; /* current sequence lengths */
X int last[2]; /* previous values of current */
X bool failure[2];
X { /* init (Level 1) */
X int i;
X for (i = _first; i <= _second; i++) {
X result[i] = 0;
X sequence_length[i] = 0;
X last[i] = -1;
X failure[i] = false;
X }
X }
X { /* show_start_message (Level 1) */
X char buffer[200];
X sprintf (buffer, "\n%d-throw KNOBELN (interval %d...%d, %s%d)",
X L, a, b, "minimum sequence length ", k);
X fprintf (stdout, "%s", buffer);
X fprintf (protocol, "%s", buffer);
X fprintf (prot, "%s", buffer);
X sprintf (buffer, "\nPlayer 1: \"%s\"\nPlayer 2: \"%s\"\n",
X name[_first], name[_second]);
X fprintf (stdout, "%s", buffer);
X fprintf (protocol, "%s", buffer);
X fprintf (prot, "%s", buffer);
X }
X { /* perform_throws (Level 1) */
X for (throw_nr = 1; throw_nr <= L && (
X !failure[_first] && !failure[_second]);
X throw_nr++) {
X { /* make_throw (Level 2) */
X int i;
X for (i = _first; i <= _second; i++) {
X next_to_throw = i;
X current[i] = read_int (from[i][p_read], name[i]);
X }
X next_to_throw = _nobody;
X }
X { /* protocol_throw (Level 2) */
X fprintf (protocol, "%3d: %5d %5d", throw_nr,
X current[_first], current[_second]);
X fprintf (prot, "%d %d\n", current[_first], current[_second]);
X }
X { /* check_rules (Level 2) */
X int i;
X for (i = _first; i <= _second; i++)
X if ((
X current[i] < a || current[i] > b)
X )
X { /* complain_for_interval (Level 3) */
X fprintf (stderr, "\n>>> \"%s\" throws illegal number %d. Game aborted <<<\n",
X name[i], current[i]);
X fprintf (protocol, "\n\"%s\" throws illegal number %d.\n",
X name[i], current[i]);
X fprintf (prot, "\n\"%s\" throws illegal number %d.\n",
X name[i], current[i]);
X failure[i] = true;
X }
X else if ((
X sequence_length[i] < k && current[i] < last[i])
X )
X { /* complain_for_sequence_length (Level 3) */
X fprintf (stderr,
X "\n>>> \"%s\" throws %d after %d\n but has only %d %s <<<\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.\n Game aborted");
X fprintf (protocol,
X "\n\"%s\" throws %d after %d\n but has only %d %s\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.");
X fprintf (prot,
X "\n\"%s\" throws %d after %d\n but has only %d %s\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.");
X failure[i] = true;
X }
X }
X if ((
X !failure[_first] && !failure[_second])
X ) {
X { /* count_throw (Level 2) */
X int i;
X for (i = _first; i <= _second; i++)
X if (((
X /* the following expression is a bit of a hack !!! */
X current[i] > current[(i+1)%2] &&
X 2*current[(i+1)%2] >= current[i])
X || (
X /* the following expression is a bit of a hack !!! */
X 2*current[i] < current[(i+1)%2]))
X )
X result[i] += log2 (current[i]);
X }
X { /* update_remaining_variables (Level 2) */
X int i;
X for (i = _first; i <= _second; i++) {
X if (current[i] < last[i])
X sequence_length[i] = 0;
X sequence_length[i]++;
X last[i] = current[i];
X }
X }
X { /* protocol_result (Level 2) */
X fprintf (protocol, " -> %4d : %d\n", result[_first], result[_second]);
X if (throw_nr % display_interval == 0)
X display ();
X }
X { /* broadcast_last_throw (Level 2) */
X /* hands the last number thrown by first to second and vice versa */
X char buffer[100];
X sprintf (buffer, "%d\n", current[_first]);
X write (to[_second][p_write], buffer, strlen (buffer));
X sprintf (buffer, "%d\n", current[_second]);
X write (to[_first][p_write], buffer, strlen (buffer));
X }
X }
X }
X }
X alarm (0);
X { /* write_bulletin (Level 1) */
X if ((
X !failure[_first] && !failure[_second])
X ) {
X fprintf (protocol, "\nGame ended normally.");
X fprintf (protocol, "\nResult:\n \"%s\": %d points\n \"%s\": %d points\n",
X name[_first], result[_first], name[_second], result[_second]);
X fprintf (prot, "\nResult:\n \"%s\": %d points\n \"%s\": %d points\n",
X name[_first], result[_first], name[_second], result[_second]);
X fprintf (bulletin, "%-30s : %30s -> %5d : %d\n",
X name[_first], name[_second], result[_first], result[_second]);
X }
X else {
X char *message = "";
X if (failure[_first] && failure[_second])
X message = "Failure of both players";
X else if (failure[_first])
X message = "Failure of player 1";
X else if (failure[_second])
X message = "Failure of player 2";
X fprintf (protocol, "\nGame ended abnormally. %s\n", message);
X fprintf (prot, "\nGame ended abnormally. %s\n", message);
X fprintf (bulletin, "%-30s : %30s -> %s\n",
X name[_first], name[_second], message);
X }
X }
X}
X
X/*************************************************************************/
X/***** IMPLEMENTATION of visible Functions *******************************/
X/*************************************************************************/
X
X
Xint main (argc, argv)
X int argc;
X char *argv[];
X{
X { /* get_and_check_arguments (Level 1) */
X if (argc < 3 || argc > 10) {
X fprintf (stderr, (
X "usage: knobeln first second [L a b k maxcpu maxmem show_interval]\n")
X );
X fprintf (stderr, " e.g. knobeln maria thorsten 500 1 6000 10 30 \n");
X fprintf (stderr, " optional args can be left out one by one from end\n");
X exit (1);
X }
X name[_first] = argv[1];
X name[_second] = argv[2];
X L = argc > 3 ? atoi (argv[3]) : std_L;
X a = argc > 4 ? atoi (argv[4]) : std_a;
X b = argc > 5 ? atoi (argv[5]) : std_b;
X k = argc > 6 ? atoi (argv[6]) : std_k;
X maxcpu = argc > 7 ? atoi (argv[7]) : std_maxcpu;
X maxmem = argc > 8 ? atoi (argv[8]) : std_maxmem;
X display_interval = argc > 9 ? atoi (argv[9]) : L/10;
X if (display_interval < 0) {
X display_interval = -display_interval;
X display_on_alarm = true;
X }
X else
X display_on_alarm = false;
X if (a <= 0 || b <= a || b > 100000000) {
X fprintf (stderr, "\nmust be 0 < a < b <= 1e8\n");
X exit (1);
X }
X if (k <= 1 || L/10 <= k || L > 1000000) {
X fprintf (stderr, "\nmust be 1 < k < L/10 <= 1e5\n");
X exit (1);
X }
X if (maxcpu >= 3600) { /* see get_process_info(): `get TIME */
X fprintf (stderr, "\nmust be maxcpu < 3600\n");
X exit (1);
X }
X }
X { /* open_protocol (Level 1) */
X protocol = fopen (protocolfilename, "w");
X if (protocol == NULL) {
X perror (protocolfilename);
X exit (1);
X }
X setbuffer (protocol, 0, 0); /* no buffering */
X prot = fopen (shortprotocolfilename, "w");
X if (prot == NULL) {
X perror (shortprotocolfilename);
X exit (1);
X }
X setbuffer (prot, 0, 0); /* no buffering */
X bulletin = fopen (bulletinfilename, "w");
X if (bulletin == NULL) {
X perror (bulletinfilename);
X exit (1);
X }
X }
X { /* install_signal_catchers (Level 1) */
X signal (SIGALRM, alarm_catcher);
X signal (SIGINT, terminate_by_signal);
X }
X { /* create_subprocesses_and_make_redirections (Level 1) */
X pipe (from[_first]);
X pipe (to[_first]);
X pipe (from[_second]);
X pipe (to[_second]);
X { /* do_forks (Level 2) */
X process_id[_first] = fork();
X if (process_id[_first] == -1) {
X perror ("fork first");
X terminate_abnormally (1);
X }
X else if (process_id[_first] == 0) { /* first child process */
X dup2 (from[_first][p_write], 1); /* redirect first's stdout */
X /* dup2 (from[_first][p_write], 2);*/ /* redirect first's stderr */
X dup2 (to[_first][p_read], 0); /* redirect first's stdin */
X execl(name[_first], name[_first], (char*)0); /* start first subprocess */
X /* execl returns only on failure: */
X perror ("execl first");
X write (1, "#", 1); /* send illegal character to stop game */
X exit (1);
X }
X else /* parent process */
X { /* do_second_fork (Level 3) */
X process_id[_second] = fork();
X if (process_id[_second] == -1) {
X perror ("fork second");
X terminate_abnormally (1);
X }
X else if (process_id[_second] == 0) { /* first child process */
X dup2 (from[_second][p_write], 1); /* redirect second's stdout */
X /* dup2 (from[_second][p_write], 2); */ /* redirect second's stderr */
X dup2 (to[_second][p_read], 0); /* redirect second's stdin */
X execl(name[_second], name[_second], (char*)0); /* start second subprocess */
X /* execl returns only on failure: */
X perror ("execl second");
X write (1, "#", 1); /* send illegal character to stop game */
X exit (1);
X }
X else { /* parent process */
X ; /* nothing */
X }
X }
X }
X /* only the parent process can ever come to this point */
X }
X alarm (alarm_interval);
X play (to, from, name, protocol, prot, result, a, b, L, k,
X maxcpu, maxmem, display_interval);
X terminate_normally ();
X}
X
X
END_OF_FILE
if test 24048 -ne `wc -c <'knobeln.c'`; then
echo shar: \"'knobeln.c'\" unpacked with wrong size!
fi
# end of 'knobeln.c'
fi
if test -f 'knobeln.cr' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'knobeln.cr'\"
else
echo shar: Extracting \"'knobeln.cr'\" \(23854 characters\)
sed "s/^X//" >'knobeln.cr' <<'END_OF_FILE'
X/*************************************************************************
XProject : KNOBELN
XModule : Conductor and referee for one game
XAuthor : Lutz Prechelt, Karlsruhe
XDate : 94/03/05
XEnvironment: SUN-OS 4.1, ANSI-C (gcc), C-Refine 3.0
XRCS : $Id$
X**************************************************************************/
X
X#if 0
X
X[[ This program is written using C-Refine 3.0, which is available for anonymous
X ftp from ftp.ira.uka.de in /pub/gnu/crefine.3.0.tar.Z (93 kB)
X or from any comp.sources.reviewed archive (appeared as v02i013 to v02i19
X on comp.sources.reviewed on 15 Jul 92)
X]]
X
X
Xusage: knobeln first second [L a b k maxcpu maxmem show_interval]
X
XConducts a game of Knobeln with L throws in the interval a..b
Xminimum sequence length is k, opponent strategies are 'first' and 'second'.
XThe strategies are Unix programs, who on every throw write one number
Xtextually to stdout and then read one from stdin. Each number is ended
Xwith a newline character. Each module is allowed to use at most maxcpu
Xseconds of cpu time and maxmem kilobytes process size (SIZE field of ps).
XThe intermediate result is shown after every show_interval throws.
XFor the default values see the #define std_... below.
X
XThis program transduces the numbers thrown between the opponents,
Xchecks for the rules and computes the result.
X
X
XMethod:
X-------
XThe program creates two pipes for each opponent program.
XThe opponent programs are started via fork and exec.
XThe timeout, cputime, and space limitations are checked by a routine
Xthat is invoked by a timer alarm and reads from 'popen("ps -ux")'
XThe scanning of the ps output is critical to portability, i.e.
Xyou may need to adjust get_process_info() for a different kind of Unix.
X
XOutput:
X-------
XThe program writes three files:
X the protocol the compact protocol, and the bulletin.
XThe protocol looks roughly like this:
X------------------------------------------------------------------------
X# 1000-throw KNOBELN (interval 1...12288, minimum sequence length 8)
X# Player 1: "fribyte"
X# Player 2: "GrandPrix"
X 1: 1 6700 -> 0 : 0
X 2: 3349 10714 -> 11 : 0
X 3: 5356 11412 -> 23 : 0
X 4: 5705 12006 -> 35 : 0
X.... (here are the lines for the other throws)
X999: 12288 12288 -> 7870 : 1112
X1000: 12288 12288 -> 7870 : 1112
X
X# Game ended normally.
X# Result:
X# "fribyte": 7870 points
X# "GrandPrix": 1112 points
X------------------------------------------------------------------------
XThe corresponding short protocol looks roughly like this:
X------------------------------------------------------------------------
X# fribyte GrandPrix
X1 6700
X3349 10714
X5356 11412
X5705 12006
X.... (here are the lines for the other throws)
X12288 12288
X12288 12288
X# Game ended normally.
X------------------------------------------------------------------------
XThe bulletin is a one-line file and has one of the following forms:
X------------------------------------------------------------------------
Xteam_name_1 : team_name_2 -> 345 : 536
Xteam_name_1 : team_name_2 -> Failure of player 1
Xteam_name_1 : team_name_2 -> Failure of player 2
Xteam_name_1 : team_name_2 -> Failure of both players
X------------------------------------------------------------------------
X
X#endif
X
X/*************************************************************************/
X
X#include <assert.h>
X#include <stdio.h>
X#include <signal.h>
X
X
Xtypedef enum {false, true} bool;
X
X#define shortprotocolfilename "knobeln.prot"
X#define protocolfilename "knobeln.protocol"
X#define bulletinfilename "knobeln.bulletin"
X
X#define std_L 1000
X#define std_a 1
X#define std_b 12288
X#define std_k 8
X#define std_maxcpu 30
X#define std_maxmem 1024
X
X#define alarm_interval 10 /* check processes all ... seconds */
X
X
X#define p_read 0
X#define p_write 1
X#define _first 0
X#define _second 1
X#define _nobody -1
X/* example to[_first][p_write] is the file descriptor used by the parent
X process to write to the 'first' subprocess
X*/
X
Xstatic char *name[2]; /* the strategies' names */
Xstatic int a, b, L, k; /* the game parameters */
Xstatic int maxcpu, maxmem; /* the runtime restrictions */
Xstatic int display_interval;
Xstatic bool display_on_alarm;
Xstatic FILE *protocol, /* the protocol file */
X *prot, /* the short-protocol file */
X *bulletin; /* the result file */
Xstatic int result[2], /* current points */
X current[2]; /* last numbers thrown */
Xstatic int from[2][2],
X to[2][2]; /* the pipes */
Xstatic int process_id[2] =
X { -1, -1 }; /* the child processes */
Xstatic int throw_nr, /* number of current throw */
X old_throw_nr = 0, /* throw_nr at last alarm */
X next_to_throw; /* which player's turn it is */
X
X#if __STDC__
X#define A(a) a
X#else
X#define A(a) ()
X#endif
X
X/* Signal handling and process handling:*/
Xvoid alarm_catcher();
Xvoid kill_child_processes ();
Xvoid terminate_abnormally A((int status));
Xvoid terminate_by_signal ();
Xvoid terminate_normally ();
Xvoid watch A((int pids[2], char *name[2], int maxcpu, int maxmem,
X int throw_nr, int old_throw_nr));
Xvoid get_process_info A((int pids[2], bool still_living[2],
X int cpu[2], int mem[2]));
X
X/* help functions: */
Xvoid display ();
Xint log2 A((int n));
Xint read_int A((int fd, char *name));
X
X/* game conductor: */
Xvoid play A((int to[2][2], int from[2][2], char *name[2],
X FILE *protocol, FILE *prot,
X int result[2], int a, int b, int L, int k,
X int maxcpu, int maxmem, int display_interval));
X
X/* main: */
Xint main A((int argc, char *argv[]));
X
X/*************************************************************************/
X
Xvoid alarm_catcher()
X{
X /* handler for SIGALARM */
X watch (process_id, name, maxcpu, maxmem, throw_nr, old_throw_nr);
X old_throw_nr = throw_nr;
X if (display_on_alarm)
X display ();
X alarm (alarm_interval);
X}
X
Xvoid kill_child_processes ()
X{
X int i, result;
X for (i = _first; i <= _second; i++) {
X if (`this process > 0) {
X result = kill (`this process, SIGKILL);
X /* fprintf (stderr, "kill -9 %d --> %d ", `this_process, result); */
X }
X }
X
X`this process:
X process_id[i]
X
X}
X
X
Xvoid terminate_abnormally (exit_status)
X int exit_status;
X{
X /* actions to perform on termination because of error */
X alarm (0);
X kill_child_processes();
X exit (exit_status);
X}
X
X
Xvoid terminate_by_signal ()
X{
X /* actions to perform when interrupt signal is catched */
X fprintf (stderr, "\nSignal catched. \n");
X alarm (0);
X kill_child_processes();
X exit (1);
X}
X
X
Xvoid terminate_normally ()
X{
X /* actions to perform when normal end of program is reached */
X alarm (0);
X kill_child_processes();
X exit (0);
X}
X
X
Xvoid watch (process_id, name, maxcpu, maxmem, throw_nr, old_throw_nr)
X int process_id[2];
X char *name[2];
X int maxcpu, maxmem;
X int throw_nr, old_throw_nr;
X{
X /* This function is activated from the timer alarm catcher.
X It checks, whether the child processes identified by process_id are
X still alive, have consumed not more than maxcpu seconds cputime and
X don't use more than maxmem kilobytes of memory.
X It also checks whether the game has made any progress since the
X last alarm by comparing throw_nr with old_throw_nr. If no progress
X was made, the blame is put on next_player_to_throw which is
X either _first or _second.
X */
X bool still_living[2], failure[2];
X int cpu[2], mem[2];
X int i;
X failure[_first] = failure[_second] = false;
X get_process_info (process_id, still_living, cpu, mem);
X for (i = _first; i <= _second; i++) {
X if (!still_living[i])
X `process terminated prematurely;
X else {
X if (mem[i] > maxmem)
X `process too large;
X if (cpu[i] > maxcpu)
X `process used too much time;
X }
X }
X if (throw_nr == old_throw_nr)
X ; /* we catch this case via cputime check. Processes can't stop! */
X if (failure[_first] || failure[_second])
X `write bulletin and terminate;
X
X`process terminated prematurely:
X fprintf (protocol, "\n# Process \"%s\" terminated prematurely.", name[i]);
X fprintf (prot, "\n# Process \"%s\" terminated prematurely.", name[i]);
X fprintf (stderr, "\nProcess \"%s\" terminated prematurely.", name[i]);
X failure[i] = true;
X
X`process too large:
X fprintf (protocol, "\n# Process \"%s\" uses too much memory: %d kb",
X name[i], mem[i]);
X fprintf (prot, "\n# Process \"%s\" uses too much memory: %d kb",
X name[i], mem[i]);
X fprintf (stderr, "\nProcess \"%s\" uses too much memory: %d kb\n",
X name[i], mem[i]);
X failure[i] = true;
X
X`process used too much time:
X fprintf (protocol, "\n# Process \"%s\" used too much CPU time", name[i]);
X fprintf (prot, "\n# Process \"%s\" used too much CPU time", name[i]);
X fprintf (stderr, "\nProcess \"%s\" used too much CPU time\n", name[i]);
X failure[i] = true;
X
X`write bulletin and terminate:
X char *message = "";
X if (failure[_first] && failure[_second])
X message = "Failure of both players";
X else if (failure[_first])
X message = "Failure of player 1";
X else if (failure[_second])
X message = "Failure of player 2";
X fprintf (protocol, "\n# Game ended unnormally: %s\n", message);
X fprintf (prot, "\n# Game ended unnormally: %s\n", message);
X fprintf (bulletin, "%-30s : %30s -> %s\n",
X name[_first], name[_second], message);
X terminate_normally();
X
X}
X
X
Xvoid get_process_info (process_id, still_living, cpu, mem)
X int process_id[2];
X bool still_living[2];
X int cpu[2], mem[2];
X{
X /* uses 'popen ("ps -ux")' to get information about the child processes.
X returns in still_living, whether they still exist, and if yes, returns
X in maxmem how many kilobytes their SIZE is and how many seconds of
X CPU time they have consumed.
X */
X FILE *ps = popen ("ps -ux", "r");
X char lbuf[`N]; /* line buffer */
X int nr_of_processes_found = 0;
X `discard header line;
X still_living[_first] = false;
X still_living[_second] = false;
X while (!feof (ps) && nr_of_processes_found < 2)
X `examine next line;
X pclose (ps);
X
X`discard header line:
X fgets (lbuf, `N, ps);
X
X`examine next line:
X /* Outputformat of 'ps -ux' (SUN-4, Sun-OS 4.1):
X #USER____ PID__ CP.U ME.M SZ__ RSS_ TT STAT START TIME__ COMMAND________
X prechelt 12945 11.8 2.9 180 420 p4 R 08:15 0:00 ps -u
X 0 1 2 3 4 5 6
X 0123456789012345678901234567890123456789012345678901234567890123456789
X ^ $ ^ $ ^ $ ^ $^ $^ $ ^$ ^ $ ^ $^ $ ^
X */
X char ccc[20]; /* a few chars from lbuf */
X int index;
X int pid;
X char STAT; /* first char of STAT field */
X int SZ, /* value of SZ field */
X RSS, /* value of RSS field */
X TIME; /* value of TIME field in seconds for form mmm:mm*/
X fscanf (ps, "%s %d", ccc, &pid); /* read username and process id */
X fgets (lbuf, `N, ps); /* read rest of line, starting at column `offset */
X if (pid != process_id[_first] && pid != process_id[_second])
X leave `examine next line;
X nr_of_processes_found++;
X index = (pid == process_id[_first]) ? _first : _second;
X fprintf (stdout, "#%s", lbuf);
X `get SZ;
X `get RSS;
X `get STAT;
X `get TIME;
X `interpret values;
X
X`get SZ:
X strncpy (ccc, lbuf - `offset + `SZpos, `SZlen);
X ccc[`SZlen] = 0; /* put null terminator behind */
X SZ = atoi (ccc);
X
X`get RSS:
X strncpy (ccc, lbuf - `offset + `RSSpos, `RSSlen);
X ccc[`RSSlen] = 0; /* put null terminator behind */
X RSS = atoi (ccc);
X
X`get STAT:
X STAT = lbuf[-`offset + `STATpos];
X
X`get TIME:
X if (`is minutes and seconds format) {
X strncpy (ccc, lbuf - `offset + `TIMEminpos, `TIMEminlen);
X ccc[`TIMEminlen] = 0; /* put null terminator behind */
X TIME = 60 * atoi (ccc);
X strncpy (ccc, lbuf - `offset + `TIMEsecpos, `TIMEseclen);
X ccc[`TIMEseclen] = 0; /* put null terminator behind */
X TIME += atoi (ccc);
X }
X else {
X TIME = 3600 + 1; /* see test at `get options in main() */
X }
X
X`is minutes and seconds format:
X lbuf[`TIMEcolonpos - `offset] == ':'
X
X`interpret values:
X assert (STAT >= 'A' && STAT <= 'Z');
X still_living[index] = (STAT != `zombie);
X cpu[index] = TIME;
X mem[index] = SZ;
X
X`N: 200
X`offset: 14
X`SZpos: 24
X`SZlen: 5
X`RSSpos: 29
X`RSSlen: 5
X`STATpos: 38
X`TIMEminpos: 49
X`TIMEminlen: 3
X`TIMEsecpos: 53
X`TIMEseclen: 2
X`TIMEcolonpos: 52
X`zombie: 'Z'
X
X}
X
X
Xvoid display ()
X{
X fprintf (stdout, "%7d: %8d %8d --> %6d : %d\n", throw_nr,
X current[_first], current[_second],
X result[_first], result[_second]);
X}
X
X
Xint log2 (n)
X int n;
X{
X /* returns the floor part of logarithmus dualis of n.
X n has to be positive, but is not checked.
X */
X int result = 0;
X while (n > 1) {
X n >>= 1;
X result++;
X }
X return (result);
X}
X
X
Xint read_int (fd, name)
X int fd;
X char *name;
X{
X /* Reads characterwise from file descriptor fd. This reading must
X deliver a single integer.
X If no integer is found, complains about strategy 'name' breaking
X the rules and exits.
X */
X int result = 0;
X int sign = 1;
X char c;
X for (;;) {
X read (fd, &c, 1);
X if (c == ' ')
X `handle blanks;
X else if (c == '\n')
X return (sign*result);
X else if (c == '-')
X sign *= -1;
X else if (c >= '0' && c <= '9')
X result = 10*result + c - '0';
X else
X `complain loudly;
X }
X
X`handle blanks:
X if (result == 0)
X ; /* ignore leading spaces */
X else /* trailing spaces */
X return (sign*result);
X
X`complain loudly:
X fprintf (stderr, "\n>>> \"%s\" %s '%c' (code %d). Game aborted <<<\n",
X name, "transfers illegal character", c, (int)c);
X terminate_abnormally (2);
X
X}
X
X
Xvoid play (to, from, name, protocol, prot, result, a, b, L, k,
X maxcpu, maxmem, display_interval)
X int to[2][2], from[2][2]; /* file handles */
X char *name[2];
X FILE *protocol, *prot;
X int result[2];
X int a, b, L, k;
X int maxcpu, maxmem;
X int display_interval;
X{
X /* conducts a game between the two strategies accessible via the pipe pairs
X <to> and <from> having the names accessible in <name>.
X A protocol is written on FILE <protocol>, a short protocol on <prot>.
X The results are returned in <result> which is initialized with zeroes
X at the beginning.
X The game is of length L, in the interval a..b, with
X minimum sequence length k
X */
X int sequence_length[2]; /* current sequence lengths */
X int last[2]; /* previous values of current */
X bool failure[2];
X `init;
X `show start message;
X `perform throws;
X alarm (0);
X `write bulletin;
X
X`init:
X int i;
X for (i = _first; i <= _second; i++) {
X result[i] = 0;
X sequence_length[i] = 0;
X last[i] = -1;
X failure[i] = false;
X }
X
X`show start message:
X char buffer[200];
X sprintf (buffer, "\n# %d-throw KNOBELN (interval %d...%d, %s%d)",
X L, a, b, "minimum sequence length ", k);
X fprintf (stdout, "%s", buffer);
X fprintf (protocol, "%s", buffer);
X fprintf (prot, "%s", buffer);
X sprintf (buffer, "\n# Player 1: %s\n# Player 2: %s\n",
X name[_first], name[_second]);
X fprintf (stdout, "%s", buffer);
X fprintf (protocol, "%s", buffer);
X fprintf (prot, "\n# %s %s\n", name[_first], name[_second]);
X
X`perform throws:
X for (throw_nr = 1; throw_nr <= L && `no failure; throw_nr++) {
X `make throw;
X `protocol throw;
X `check rules;
X if (`no failure) {
X `count throw;
X `update remaining variables;
X `protocol result;
X `broadcast last throw;
X }
X }
X
X`no failure:
X !failure[_first] && !failure[_second]
X
X`make throw:
X int i;
X for (i = _first; i <= _second; i++) {
X next_to_throw = i;
X current[i] = read_int (from[i][p_read], name[i]);
X }
X next_to_throw = _nobody;
X
X`protocol throw:
X fprintf (protocol, "%4d: %5d %5d", throw_nr,
X current[_first], current[_second]);
X fprintf (prot, "%d %d\n", current[_first], current[_second]);
X
X`check rules:
X int i;
X for (i = _first; i <= _second; i++)
X if (`value is outside interval)
X `complain for interval;
X else if (`sequence is too short)
X `complain for sequence length;
X
X`value is outside interval:
X current[i] < a || current[i] > b
X
X`complain for interval:
X fprintf (stderr, "\n>>> \"%s\" throws illegal number %d. Game aborted <<<\n",
X name[i], current[i]);
X fprintf (protocol, "\n# \"%s\" throws illegal number %d.\n",
X name[i], current[i]);
X fprintf (prot, "\n# \"%s\" throws illegal number %d.\n",
X name[i], current[i]);
X failure[i] = true;
X
X`sequence is too short:
X sequence_length[i] < k && current[i] < last[i]
X
X`complain for sequence length:
X fprintf (stderr,
X "\n>>> \"%s\" throws %d after %d\n but has only %d %s <<<\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.\n Game aborted");
X fprintf (protocol,
X "\n# \"%s\" throws %d after %d\n but has only %d %s\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.");
X fprintf (prot,
X "\n# \"%s\" throws %d after %d\n but has only %d %s\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.");
X failure[i] = true;
X
X`count throw:
X int i;
X for (i = _first; i <= _second; i++)
X if (`player i has won the throw)
X result[i] += log2 (current[i]);
X
X`update remaining variables:
X int i;
X for (i = _first; i <= _second; i++) {
X if (current[i] < last[i])
X sequence_length[i] = 0;
X sequence_length[i]++;
X last[i] = current[i];
X }
X
X`player i has won the throw:
X `won with more points || `won with less points
X
X`won with more points:
X /* the following expression is a bit of a hack !!! */
X current[i] > current[(i+1)%2] &&
X 2*current[(i+1)%2] >= current[i]
X
X`won with less points:
X /* the following expression is a bit of a hack !!! */
X 2*current[i] < current[(i+1)%2]
X
X`protocol result:
X fprintf (protocol, " -> %4d : %d\n", result[_first], result[_second]);
X if (throw_nr % display_interval == 0)
X display ();
X
X`broadcast last throw:
X /* hands the last number thrown by first to second and vice versa */
X char buffer[100];
X sprintf (buffer, "%d\n", current[_first]);
X write (to[_second][p_write], buffer, strlen (buffer));
X sprintf (buffer, "%d\n", current[_second]);
X write (to[_first][p_write], buffer, strlen (buffer));
X
X`write bulletin:
X if (`no failure) {
X fprintf (protocol, "\n# Game ended normally.");
X fprintf (protocol, "\n# Result:\n# %s: %d points\n# %s: %d points\n",
X name[_first], result[_first], name[_second], result[_second]);
X fprintf (prot, "\n# Result:\n# %s: %d points\n# %s: %d points\n",
X name[_first], result[_first], name[_second], result[_second]);
X fprintf (bulletin, "%-30s : %30s -> %5d : %d\n",
X name[_first], name[_second], result[_first], result[_second]);
X }
X else {
X char *message = "";
X if (failure[_first] && failure[_second])
X message = "Failure of both players";
X else if (failure[_first])
X message = "Failure of player 1";
X else if (failure[_second])
X message = "Failure of player 2";
X fprintf (protocol, "\n# Game ended abnormally. %s\n", message);
X fprintf (prot, "\n# Game ended abnormally. %s\n", message);
X fprintf (bulletin, "%-30s : %30s -> %s\n",
X name[_first], name[_second], message);
X }
X
X}
X
X/*************************************************************************/
X
Xint main (argc, argv)
X int argc;
X char *argv[];
X{
X `get and check arguments;
X `open protocol;
X `install signal catchers;
X `create subprocesses and make redirections;
X alarm (alarm_interval);
X play (to, from, name, protocol, prot, result, a, b, L, k,
X maxcpu, maxmem, display_interval);
X terminate_normally ();
X
X`get and check arguments:
X if (argc < 3 || argc > 10) {
X fprintf (stderr, `usage string);
X fprintf (stderr, " e.g. knobeln maria thorsten 500 1 6000 10 30 \n");
X fprintf (stderr, " optional args can be left out one by one from end\n");
X exit (1);
X }
X name[_first] = argv[1];
X name[_second] = argv[2];
X L = argc > 3 ? atoi (argv[3]) : std_L;
X a = argc > 4 ? atoi (argv[4]) : std_a;
X b = argc > 5 ? atoi (argv[5]) : std_b;
X k = argc > 6 ? atoi (argv[6]) : std_k;
X maxcpu = argc > 7 ? atoi (argv[7]) : std_maxcpu;
X maxmem = argc > 8 ? atoi (argv[8]) : std_maxmem;
X display_interval = argc > 9 ? atoi (argv[9]) : L/10;
X if (display_interval < 0) {
X display_interval = -display_interval;
X display_on_alarm = true;
X }
X else
X display_on_alarm = false;
X if (a <= 0 || b <= a || b > 100000000) {
X fprintf (stderr, "\nmust be 0 < a < b <= 1e8\n");
X exit (1);
X }
X if (k <= 1 || L/10 <= k || L > 1000000) {
X fprintf (stderr, "\nmust be 1 < k < L/10 <= 1e5\n");
X exit (1);
X }
X if (maxcpu >= 3600) { /* see get_process_info(): `get TIME */
X fprintf (stderr, "\nmust be maxcpu < 3600\n");
X exit (1);
X }
X
X`usage string:
X "usage: knobeln first second [L a b k maxcpu maxmem show_interval]\n"
X
X`open protocol:
X protocol = fopen (protocolfilename, "w");
X if (protocol == NULL) {
X perror (protocolfilename);
X exit (1);
X }
X setbuffer (protocol, 0, 0); /* no buffering */
X prot = fopen (shortprotocolfilename, "w");
X if (prot == NULL) {
X perror (shortprotocolfilename);
X exit (1);
X }
X setbuffer (prot, 0, 0); /* no buffering */
X bulletin = fopen (bulletinfilename, "w");
X if (bulletin == NULL) {
X perror (bulletinfilename);
X exit (1);
X }
X
X`install signal catchers:
X signal (SIGALRM, alarm_catcher);
X signal (SIGINT, terminate_by_signal);
X
X`create subprocesses and make redirections:
X pipe (from[_first]);
X pipe (to[_first]);
X pipe (from[_second]);
X pipe (to[_second]);
X `do forks;
X /* only the parent process can ever come to this point */
X
X`do forks:
X process_id[_first] = fork();
X if (process_id[_first] == -1) {
X perror ("fork first");
X terminate_abnormally (1);
X }
X else if (process_id[_first] == 0) { /* first child process */
X dup2 (from[_first][p_write], 1); /* redirect first's stdout */
X /* dup2 (from[_first][p_write], 2);*/ /* redirect first's stderr */
X dup2 (to[_first][p_read], 0); /* redirect first's stdin */
X execl(name[_first], name[_first], (char*)0); /* start first subprocess */
X /* execl returns only on failure: */
X perror ("execl first");
X write (1, "#", 1); /* send illegal character to stop game */
X exit (1);
X }
X else /* parent process */
X `do second fork;
X
X`do second fork:
X process_id[_second] = fork();
X if (process_id[_second] == -1) {
X perror ("fork second");
X terminate_abnormally (1);
X }
X else if (process_id[_second] == 0) { /* first child process */
X dup2 (from[_second][p_write], 1); /* redirect second's stdout */
X /* dup2 (from[_second][p_write], 2); */ /* redirect second's stderr */
X dup2 (to[_second][p_read], 0); /* redirect second's stdin */
X execl(name[_second], name[_second], (char*)0); /* start second subprocess */
X /* execl returns only on failure: */
X perror ("execl second");
X write (1, "#", 1); /* send illegal character to stop game */
X exit (1);
X }
X else { /* parent process */
X ; /* nothing */
X }
X}
X
X
END_OF_FILE
if test 23854 -ne `wc -c <'knobeln.cr'`; then
echo shar: \"'knobeln.cr'\" unpacked with wrong size!
fi
# end of 'knobeln.cr'
fi
echo shar: End of shell archive.
exit 0
# This is a shell archive. Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file". To overwrite existing
# files, type "sh file -c". You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g.. If this archive is complete, you
# will see the following message at the end:
# "End of shell archive."
# Contents: knobellib.c knobeln.c knobeln.cr
# Wrapped by prechelt@Sofia on Thu Mar 24 19:28:01 1994
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'knobellib.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'knobellib.c'\"
else
echo shar: Extracting \"'knobellib.c'\" \(3552 characters\)
sed "s/^X//" >'knobellib.c' <<'END_OF_FILE'
X/*************************************************************************
XFile : knobellib.c: Library for Knobeln strategies
XAutor : Lutz Prechelt, Karlsruhe, Germany (prec...@ira.uka.de)
XDate : 94/03/05
XLanguage: Kernighan/Ritchie C
X**************************************************************************/
X
X/*
X
X Library for strategy programs in the Knobeln-Contest
X ------------------------------------------------------
X
XThis file is functionally equivalent (but not necessarily identical) to
Xwhat your strategy will be linked with in the contest.
XYou must compile it with
X
X cc -c knobellib.c
X
X(or the like) and can then create an executable version "strat" of your
Xstrategy (supposed it is in a file called "strat.c") with something
Xlike
X
X cc -o strat strat.c knobellib.o
X
XYou must not use any include files in strat.c
XYou must not call any functions that are neither local to strat.c nor
Xdefined in the interface of this library, or otherwise your program
Xwill not compile when the contest is run.
X
XThis module is written to compile on BSD-UNIX systems. For other
Xsystems modifications might be necessary.
XIn particular, if your system does not have random()/srandom() you may
Xwant to try rand()/srand() instead.
X
X
X
XThe interface of the library is:
X
Xint init_random ()
X Initializes the random number generator in some not reproducible
X way. Returns 0.
X
Xint log2 (int number)
X Returns the biggest integer that is smaller or equal to the
X base 2 logarithm of the positive <number>.
X
Xint next_random (int low, int high)
X Returns a random number in the range [low...high]
X Preconditions: -32767 <= low <= high <= 32767 and
X (high - low) <= 32767
X
Xint make_throw (int my_throw)
X Outputs my_throw on stdout
X (i.e. transmits your own throw to the referee program), then
X reads your partners throw from stdin and returns it.
X
Xint count_points (int throw1, int throw2, int *points1, int *points2);
X Increases *points1 by log2(throw1), if throw1 wins against throw2, or
X increases *points2 by log2(throw2), if throw2 wins against throw1.
X Returns 0 if nobody wins, 1 if throw1 wins and 2 if throw2 wins.
X
X************************************************************************/
X
X
X#include <stdio.h> /* to define NULL and stdout */
X
Xint init_random ()
X{
X /* If getpid() is not available on your system, just replace it by 0 */
X srandom ((int)(time(NULL) ^ getpid()));
X return (0);
X}
X
X
Xint log2 (number)
X register int number;
X{
X register int i = 0;
X while(number >>= 1)
X i++;
X return i;
X}
X
X
Xint next_random (low, high)
X int low, high;
X{
X /* return 0 if preconditions not met */
X /* Use random() random number generator */
X if (low < -32767 || high > 32767 || low > high ||
X (int)((long)high - (long)low) > 32767)
X return (0);
X return ((int)(random() % (long)(high - low + 1)) + low);
X}
X
X
Xint make_throw (my_throw)
X int my_throw;
X{
X int your_throw, r;
X printf ("%d\n", my_throw); fflush (stdout);
X r = scanf ("%d", &your_throw);
X if (r == EOF) /* terminate program on end of file */
X exit (0);
X return (your_throw);
X}
X
X
Xint count_points (throw1, throw2, points1, points2)
X int throw1, throw2,
X *points1, *points2;
X{
X if (throw1 == throw2) { /* nobody wins */
X return (0);
X }
X if ((throw1 > throw2 && !(throw1 > 2*throw2)) || /* throw1 wins with bigger */
X (2*throw1 < throw2)) { /* throw1 wins with smaller number */
X *points1 += log2 (throw1);
X return (1);
X }
X /* otherwise throw2 wins: */
X *points2 += log2 (throw2);
X return (2);
X}
END_OF_FILE
if test 3552 -ne `wc -c <'knobellib.c'`; then
echo shar: \"'knobellib.c'\" unpacked with wrong size!
fi
# end of 'knobellib.c'
fi
if test -f 'knobeln.c' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'knobeln.c'\"
else
echo shar: Extracting \"'knobeln.c'\" \(24048 characters\)
sed "s/^X//" >'knobeln.c' <<'END_OF_FILE'
X
X/*************************************************************************
XProject : KNOBELN
XModule : Conductor and referee for one game
XAuthor : Lutz Prechelt, Karlsruhe
XDate : 25.09.93
XEnvironment: SUN-OS 4.1, ANSI-C (gcc), C-Refine
XRCS : $Id$
X**************************************************************************/
X
X#if 0
X
Xusage: knobeln first second [L a b k maxcpu maxmem show_interval]
X
XConducts a game of Knobeln with L throws in the interval a..b
Xminimum sequence length is k, opponent strategies are 'first' and 'second'.
XThe strategies are Unix programs, who on every throw write one number
Xtextually to stdout and then read one from stdin. Each number is ended
Xwith a newline character. Each module is allowed to use at most maxcpu
Xseconds of cpu time and maxmem kilobytes process size (SIZE field of ps).
XThe intermediate result is shown after every show_interval throws.
XFor the default values see the #define std_... below.
X
XThis program transduces the numbers thrown between the opponents,
Xchecks for the rules and computes the result.
X
X
XMethod:
X-------
XThe program creates two pipes for each opponent program.
XThe opponent programs are started via fork and exec.
XThe timeout, cputime, and space limitations are checked by a routine
Xthat is invoked by a timer alarm and reads from 'popen("ps -ux")'
XThe scanning of the ps output is critical to portability, i.e.
Xyou may need to adjust get_process_info() for a different kind of Unix.
X
XOutput:
X-------
XThe program writes three files:
X the protocol the compact protocol, and the bulletin.
XThe protocol looks like this:
X------------------------------------------------------------------------
X1000-throw KNOBELN (interval 1...12288, minimum sequence length 8)
XPlayer 1: "fribyte"
XPlayer 2: "GrandPrix"
X 1: 1 6700 -> 0 : 0
X 2: 3349 10714 -> 11 : 0
X 3: 5356 11412 -> 23 : 0
X 4: 5705 12006 -> 35 : 0
X.... (here are the lines for the other throws)
X999: 12288 12288 -> 7870 : 1112
X1000: 12288 12288 -> 7870 : 1112
X
XGame ended normally.
XResult:
X "fribyte": 7870 points
X "GrandPrix": 1112 points
X------------------------------------------------------------------------
XThe corresponding short protocol looks like this:
X
X1 6700
X3349 10714
X5356 11412
X5705 12006
X.... (here are the lines for the other throws)
X12288 12288
X12288 12288
X------------------------------------------------------------------------
XThe bulletin is a one-line file and has one of the following forms:
X
Xteam_name_1 : team_name_2 -> 345 : 536
Xteam_name_1 : team_name_2 -> Failure of player 1
Xteam_name_1 : team_name_2 -> Failure of player 2
Xteam_name_1 : team_name_2 -> Failure of both players
X
X#endif
X
X/*************************************************************************/
X/***** USES **************************************************************/
X/*************************************************************************/
X
X#include <assert.h>
X#include <stdio.h>
X#include <signal.h>
X
X
X/*************************************************************************/
X/***** PRIVATE Constants, Types, Variables, Functions ******************/
X/*************************************************************************/
X
Xtypedef enum {false, true} bool;
X
X#define shortprotocolfilename "knobeln.prot"
X#define protocolfilename "knobeln.protocol"
X#define bulletinfilename "knobeln.bulletin"
X
X#define std_L 1000
X#define std_a 1
X#define std_b 12288
X#define std_k 8
X#define std_maxcpu 60
X#define std_maxmem 1024
X
X#define alarm_interval 10 /* check processes all ... seconds */
X
X
X#define p_read 0
X#define p_write 1
X#define _first 0
X#define _second 1
X#define _nobody -1
X/* example to[_first][p_write] is the file descriptor used by the parent
X process to write to the 'first' subprocess
X*/
X
Xstatic char *name[2]; /* the strategies' names */
Xstatic int a, b, L, k; /* the game parameters */
Xstatic int maxcpu, maxmem; /* the runtime restrictions */
Xstatic int display_interval;
Xstatic bool display_on_alarm;
Xstatic FILE *protocol, /* the protocol file */
X *prot, /* the short-protocol file */
X *bulletin; /* the result file */
Xstatic int result[2], /* current points */
X current[2]; /* last numbers thrown */
Xstatic int from[2][2],
X to[2][2]; /* the pipes */
Xstatic int process_id[2] =
X { -1, -1 }; /* the child processes */
Xstatic int throw_nr, /* number of current throw */
X old_throw_nr = 0, /* throw_nr at last alarm */
X next_to_throw; /* which player's turn it is */
X
X
X/* Signal handling and process handling:*/
Xvoid alarm_catcher();
Xvoid kill_child_processes ();
Xvoid terminate_abnormally (int status);
Xvoid terminate_by_signal ();
Xvoid terminate_normally ();
Xvoid watch (const int pids[2], char *name[2], int maxcpu, int maxmem,
X int throw_nr, int old_throw_nr);
Xvoid get_process_info (const int pids[2], bool still_living[2],
X int cpu[2], int mem[2]);
X
X/* help functions: */
Xvoid display ();
Xint log2 (int n);
Xint read_int (int fd, const char *name);
X
X/* game conductor: */
Xvoid play (int to[2][2], int from[2][2], char *name[2],
X FILE *protocol, FILE *prot,
X int result[2], int a, int b, int L, int k,
X int maxcpu, int maxmem, int display_interval);
X
X/* main: */
Xint main (int argc, char *argv[]);
X
X/*************************************************************************/
X/***** IMPLEMENTATION of private Functions *******************************/
X/*************************************************************************/
X
Xvoid alarm_catcher()
X{
X /* handler for SIGALARM */
X watch (process_id, name, maxcpu, maxmem, throw_nr, old_throw_nr);
X old_throw_nr = throw_nr;
X if (display_on_alarm)
X display ();
X alarm (alarm_interval);
X}
X
Xvoid kill_child_processes ()
X{
X int i, result;
X for (i = _first; i <= _second; i++) {
X if ((
X process_id[i])
X > 0) {
X result = kill ((
X process_id[i])
X , SIGKILL);
X /* fprintf (stderr, "kill -9 %d --> %d ", `this_process, result); */
X }
X }
X}
X
X
Xvoid terminate_abnormally (int exit_status)
X{
X /* actions to perform on termination because of error */
X alarm (0);
X kill_child_processes();
X exit (exit_status);
X}
X
X
Xvoid terminate_by_signal ()
X{
X /* actions to perform when interrupt signal is catched */
X fprintf (stderr, "\nSignal catched. \n");
X alarm (0);
X kill_child_processes();
X exit (1);
X}
X
X
Xvoid terminate_normally ()
X{
X /* actions to perform when normal end of program is reached */
X alarm (0);
X kill_child_processes();
X exit (0);
X}
X
X
Xvoid watch (const int process_id[2], char *name[2],
X int maxcpu, int maxmem, int throw_nr, int old_throw_nr)
X{
X /* This function is activated from the timer alarm catcher.
X It checks, whether the child processes identified by process_id are
X still alive, have consumed not more than maxcpu seconds cputime and
X don't use more than maxmem kilobytes of memory.
X It also checks whether the game has made any progress since the
X last alarm by comparing throw_nr with old_throw_nr. If no progress
X was made, the blame is put on next_player_to_throw which is
X either _first or _second.
X */
X bool still_living[2], failure[2];
X int cpu[2], mem[2];
X int i;
X failure[_first] = failure[_second] = false;
X get_process_info (process_id, still_living, cpu, mem);
X for (i = _first; i <= _second; i++) {
X if (!still_living[i])
X { /* process_terminated_prematurely (Level 1) */
X fprintf (protocol, "\nProcess \"%s\" terminated prematurely.", name[i]);
X fprintf (prot, "\nProcess \"%s\" terminated prematurely.", name[i]);
X fprintf (stderr, "\nProcess \"%s\" terminated prematurely.", name[i]);
X failure[i] = true;
X }
X else {
X if (mem[i] > maxmem)
X { /* process_too_large (Level 1) */
X fprintf (protocol, "\nProcess \"%s\" uses too much memory: %d kb",
X name[i], mem[i]);
X fprintf (prot, "\nProcess \"%s\" uses too much memory: %d kb",
X name[i], mem[i]);
X fprintf (stderr, "\nProcess \"%s\" uses too much memory: %d kb\n",
X name[i], mem[i]);
X failure[i] = true;
X }
X if (cpu[i] > maxcpu)
X { /* process_used_too_much_time (Level 1) */
X fprintf (protocol, "\nProcess \"%s\" used too much CPU time", name[i]);
X fprintf (prot, "\nProcess \"%s\" used too much CPU time", name[i]);
X fprintf (stderr, "\nProcess \"%s\" used too much CPU time\n", name[i]);
X failure[i] = true;
X }
X }
X }
X if (throw_nr == old_throw_nr)
X ; /* we catch this case via cputime check. Processes can't stop! */
X if (failure[_first] || failure[_second])
X { /* write_bulletin_and_terminate (Level 1) */
X char *message = "";
X if (failure[_first] && failure[_second])
X message = "Failure of both players";
X else if (failure[_first])
X message = "Failure of player 1";
X else if (failure[_second])
X message = "Failure of player 2";
X fprintf (protocol, "\nGame ended unnormally: %s\n", message);
X fprintf (prot, "\nGame ended unnormally: %s\n", message);
X fprintf (bulletin, "%-30s : %30s -> %s\n",
X name[_first], name[_second], message);
X terminate_normally();
X }
X}
X
X
Xvoid get_process_info (const int process_id[2], bool still_living[2],
X int cpu[2], int mem[2])
X{
X /* uses 'popen ("ps -ux")' to get information about the child processes.
X returns in still_living, whether they still exist, and if yes, returns
X in maxmem how many kilobytes their SIZE is and how many seconds of
X CPU time they have consumed.
X */
X FILE *ps = popen ("ps -ux", "r");
X char lbuf[(
X 200)
X ]; /* line buffer */
X int nr_of_processes_found = 0;
X { /* discard_header_line (Level 1) */
X fgets (lbuf, (
X 200)
X , ps);
X }
X still_living[_first] = false;
X still_living[_second] = false;
X while (!feof (ps) && nr_of_processes_found < 2)
X { /* examine_next_line (Level 1) */
X /* Outputformat of 'ps -ux' (SUN-4, Sun-OS 4.1):
X#USER____ PID__ CP.U ME.M SZ__ RSS_ TT STAT START TIME__ COMMAND________
X prechelt 12945 11.8 2.9 180 420 p4 R 08:15 0:00 ps -u
X 0 1 2 3 4 5 6
X 0123456789012345678901234567890123456789012345678901234567890123456789
X ^ $ ^ $ ^ $ ^ $^ $^ $ ^$ ^ $ ^ $^ $ ^
X */
X char ccc[20]; /* a few chars from lbuf */
X int index;
X int pid;
X char STAT; /* first char of STAT field */
X int SZ, /* value of SZ field */
X RSS, /* value of RSS field */
X TIME; /* value of TIME field in seconds for form mmm:mm*/
X fscanf (ps, "%s %d", ccc, &pid); /* read username and process id */
X fgets (lbuf, (
X 200)
X , ps); /* read rest of line, starting at column `offset */
X if (pid != process_id[_first] && pid != process_id[_second])
X goto examine_next_line_1;
X nr_of_processes_found++;
X index = (pid == process_id[_first]) ? _first : _second;
X fprintf (stdout, "#%s", lbuf);
X { /* get_SZ (Level 2) */
X strncpy (ccc, lbuf - (
X 14)
X + (
X 24)
X , (
X 5)
X );
X ccc[(
X 5)
X ] = 0; /* put null terminator behind */
X SZ = atoi (ccc);
X }
X { /* get_RSS (Level 2) */
X strncpy (ccc, lbuf - (
X 14)
X + (
X 29)
X , (
X 5)
X );
X ccc[(
X 5)
X ] = 0; /* put null terminator behind */
X RSS = atoi (ccc);
X }
X { /* get_STAT (Level 2) */
X STAT = lbuf[-(
X 14)
X + (
X 38)
X ];
X }
X { /* get_TIME (Level 2) */
X if ((
X lbuf[(
X 52)
X - (
X 14)
X ] == ':')
X ) {
X strncpy (ccc, lbuf - (
X 14)
X + (
X 49)
X , (
X 3)
X );
X ccc[(
X 3)
X ] = 0; /* put null terminator behind */
X TIME = 60 * atoi (ccc);
X strncpy (ccc, lbuf - (
X 14)
X + (
X 53)
X , (
X 2)
X );
X ccc[(
X 2)
X ] = 0; /* put null terminator behind */
X TIME += atoi (ccc);
X }
X else {
X TIME = 3600 + 1; /* see test at `get options in main() */
X }
X }
X { /* interpret_values (Level 2) */
X assert (STAT >= 'A' && STAT <= 'Z');
X still_living[index] = (STAT != (
X 'Z')
X );
X cpu[index] = TIME;
X mem[index] = SZ;
X }
Xexamine_next_line_1: ;
X }
X pclose (ps);
X}
X
X
Xvoid display ()
X{
X fprintf (stdout, "%7d: %8d %8d --> %6d : %d\n", throw_nr,
X current[_first], current[_second],
X result[_first], result[_second]);
X}
X
X
Xint log2 (int n)
X{
X /* returns the floor part of logarithmus dualis of n.
X n has to be positive, but is not checked.
X */
X int result = 0;
X while (n > 1) {
X n >>= 1;
X result++;
X }
X return (result);
X}
X
X
Xint read_int (int fd, const char *name)
X{
X /* Reads characterwise from file descriptor fd. This reading must
X deliver a single integer.
X If no integer is found, complains about strategy 'name' breaking
X the rules and exits.
X */
X int result = 0;
X int sign = 1;
X char c;
X for (;;) {
X read (fd, &c, 1);
X if (c == ' ')
X { /* handle_blanks (Level 1) */
X if (result == 0)
X ; /* ignore leading spaces */
X else /* trailing spaces */
X return (sign*result);
X }
X else if (c == '\n')
X return (sign*result);
X else if (c == '-')
X sign *= -1;
X else if (c >= '0' && c <= '9')
X result = 10*result + c - '0';
X else
X { /* complain_loudly (Level 1) */
X fprintf (stderr, "\n>>> \"%s\" %s '%c' (code %d). Game aborted <<<\n",
X name, "transfers illegal character", c, (int)c);
X terminate_abnormally (2);
X }
X }
X}
X
X
Xvoid play (int to[2][2], int from[2][2], char *name[2],
X FILE *protocol, FILE *prot,
X int result[2], int a, int b, int L, int k,
X int maxcpu, int maxmem, int display_interval)
X{
X /* conducts a game between the two strategies accessible via the pipe pairs
X <to> and <from> having the names accessible in <name>.
X A protocol is written on FILE <protocol>, a short protocol on <prot>.
X The results are returned in <result> which is initialized with zeroes
X at the beginning.
X The game is of length L, in the interval a..b, with
X minimum sequence length k
X */
X int sequence_length[2]; /* current sequence lengths */
X int last[2]; /* previous values of current */
X bool failure[2];
X { /* init (Level 1) */
X int i;
X for (i = _first; i <= _second; i++) {
X result[i] = 0;
X sequence_length[i] = 0;
X last[i] = -1;
X failure[i] = false;
X }
X }
X { /* show_start_message (Level 1) */
X char buffer[200];
X sprintf (buffer, "\n%d-throw KNOBELN (interval %d...%d, %s%d)",
X L, a, b, "minimum sequence length ", k);
X fprintf (stdout, "%s", buffer);
X fprintf (protocol, "%s", buffer);
X fprintf (prot, "%s", buffer);
X sprintf (buffer, "\nPlayer 1: \"%s\"\nPlayer 2: \"%s\"\n",
X name[_first], name[_second]);
X fprintf (stdout, "%s", buffer);
X fprintf (protocol, "%s", buffer);
X fprintf (prot, "%s", buffer);
X }
X { /* perform_throws (Level 1) */
X for (throw_nr = 1; throw_nr <= L && (
X !failure[_first] && !failure[_second]);
X throw_nr++) {
X { /* make_throw (Level 2) */
X int i;
X for (i = _first; i <= _second; i++) {
X next_to_throw = i;
X current[i] = read_int (from[i][p_read], name[i]);
X }
X next_to_throw = _nobody;
X }
X { /* protocol_throw (Level 2) */
X fprintf (protocol, "%3d: %5d %5d", throw_nr,
X current[_first], current[_second]);
X fprintf (prot, "%d %d\n", current[_first], current[_second]);
X }
X { /* check_rules (Level 2) */
X int i;
X for (i = _first; i <= _second; i++)
X if ((
X current[i] < a || current[i] > b)
X )
X { /* complain_for_interval (Level 3) */
X fprintf (stderr, "\n>>> \"%s\" throws illegal number %d. Game aborted <<<\n",
X name[i], current[i]);
X fprintf (protocol, "\n\"%s\" throws illegal number %d.\n",
X name[i], current[i]);
X fprintf (prot, "\n\"%s\" throws illegal number %d.\n",
X name[i], current[i]);
X failure[i] = true;
X }
X else if ((
X sequence_length[i] < k && current[i] < last[i])
X )
X { /* complain_for_sequence_length (Level 3) */
X fprintf (stderr,
X "\n>>> \"%s\" throws %d after %d\n but has only %d %s <<<\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.\n Game aborted");
X fprintf (protocol,
X "\n\"%s\" throws %d after %d\n but has only %d %s\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.");
X fprintf (prot,
X "\n\"%s\" throws %d after %d\n but has only %d %s\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.");
X failure[i] = true;
X }
X }
X if ((
X !failure[_first] && !failure[_second])
X ) {
X { /* count_throw (Level 2) */
X int i;
X for (i = _first; i <= _second; i++)
X if (((
X /* the following expression is a bit of a hack !!! */
X current[i] > current[(i+1)%2] &&
X 2*current[(i+1)%2] >= current[i])
X || (
X /* the following expression is a bit of a hack !!! */
X 2*current[i] < current[(i+1)%2]))
X )
X result[i] += log2 (current[i]);
X }
X { /* update_remaining_variables (Level 2) */
X int i;
X for (i = _first; i <= _second; i++) {
X if (current[i] < last[i])
X sequence_length[i] = 0;
X sequence_length[i]++;
X last[i] = current[i];
X }
X }
X { /* protocol_result (Level 2) */
X fprintf (protocol, " -> %4d : %d\n", result[_first], result[_second]);
X if (throw_nr % display_interval == 0)
X display ();
X }
X { /* broadcast_last_throw (Level 2) */
X /* hands the last number thrown by first to second and vice versa */
X char buffer[100];
X sprintf (buffer, "%d\n", current[_first]);
X write (to[_second][p_write], buffer, strlen (buffer));
X sprintf (buffer, "%d\n", current[_second]);
X write (to[_first][p_write], buffer, strlen (buffer));
X }
X }
X }
X }
X alarm (0);
X { /* write_bulletin (Level 1) */
X if ((
X !failure[_first] && !failure[_second])
X ) {
X fprintf (protocol, "\nGame ended normally.");
X fprintf (protocol, "\nResult:\n \"%s\": %d points\n \"%s\": %d points\n",
X name[_first], result[_first], name[_second], result[_second]);
X fprintf (prot, "\nResult:\n \"%s\": %d points\n \"%s\": %d points\n",
X name[_first], result[_first], name[_second], result[_second]);
X fprintf (bulletin, "%-30s : %30s -> %5d : %d\n",
X name[_first], name[_second], result[_first], result[_second]);
X }
X else {
X char *message = "";
X if (failure[_first] && failure[_second])
X message = "Failure of both players";
X else if (failure[_first])
X message = "Failure of player 1";
X else if (failure[_second])
X message = "Failure of player 2";
X fprintf (protocol, "\nGame ended abnormally. %s\n", message);
X fprintf (prot, "\nGame ended abnormally. %s\n", message);
X fprintf (bulletin, "%-30s : %30s -> %s\n",
X name[_first], name[_second], message);
X }
X }
X}
X
X/*************************************************************************/
X/***** IMPLEMENTATION of visible Functions *******************************/
X/*************************************************************************/
X
X
Xint main (argc, argv)
X int argc;
X char *argv[];
X{
X { /* get_and_check_arguments (Level 1) */
X if (argc < 3 || argc > 10) {
X fprintf (stderr, (
X "usage: knobeln first second [L a b k maxcpu maxmem show_interval]\n")
X );
X fprintf (stderr, " e.g. knobeln maria thorsten 500 1 6000 10 30 \n");
X fprintf (stderr, " optional args can be left out one by one from end\n");
X exit (1);
X }
X name[_first] = argv[1];
X name[_second] = argv[2];
X L = argc > 3 ? atoi (argv[3]) : std_L;
X a = argc > 4 ? atoi (argv[4]) : std_a;
X b = argc > 5 ? atoi (argv[5]) : std_b;
X k = argc > 6 ? atoi (argv[6]) : std_k;
X maxcpu = argc > 7 ? atoi (argv[7]) : std_maxcpu;
X maxmem = argc > 8 ? atoi (argv[8]) : std_maxmem;
X display_interval = argc > 9 ? atoi (argv[9]) : L/10;
X if (display_interval < 0) {
X display_interval = -display_interval;
X display_on_alarm = true;
X }
X else
X display_on_alarm = false;
X if (a <= 0 || b <= a || b > 100000000) {
X fprintf (stderr, "\nmust be 0 < a < b <= 1e8\n");
X exit (1);
X }
X if (k <= 1 || L/10 <= k || L > 1000000) {
X fprintf (stderr, "\nmust be 1 < k < L/10 <= 1e5\n");
X exit (1);
X }
X if (maxcpu >= 3600) { /* see get_process_info(): `get TIME */
X fprintf (stderr, "\nmust be maxcpu < 3600\n");
X exit (1);
X }
X }
X { /* open_protocol (Level 1) */
X protocol = fopen (protocolfilename, "w");
X if (protocol == NULL) {
X perror (protocolfilename);
X exit (1);
X }
X setbuffer (protocol, 0, 0); /* no buffering */
X prot = fopen (shortprotocolfilename, "w");
X if (prot == NULL) {
X perror (shortprotocolfilename);
X exit (1);
X }
X setbuffer (prot, 0, 0); /* no buffering */
X bulletin = fopen (bulletinfilename, "w");
X if (bulletin == NULL) {
X perror (bulletinfilename);
X exit (1);
X }
X }
X { /* install_signal_catchers (Level 1) */
X signal (SIGALRM, alarm_catcher);
X signal (SIGINT, terminate_by_signal);
X }
X { /* create_subprocesses_and_make_redirections (Level 1) */
X pipe (from[_first]);
X pipe (to[_first]);
X pipe (from[_second]);
X pipe (to[_second]);
X { /* do_forks (Level 2) */
X process_id[_first] = fork();
X if (process_id[_first] == -1) {
X perror ("fork first");
X terminate_abnormally (1);
X }
X else if (process_id[_first] == 0) { /* first child process */
X dup2 (from[_first][p_write], 1); /* redirect first's stdout */
X /* dup2 (from[_first][p_write], 2);*/ /* redirect first's stderr */
X dup2 (to[_first][p_read], 0); /* redirect first's stdin */
X execl(name[_first], name[_first], (char*)0); /* start first subprocess */
X /* execl returns only on failure: */
X perror ("execl first");
X write (1, "#", 1); /* send illegal character to stop game */
X exit (1);
X }
X else /* parent process */
X { /* do_second_fork (Level 3) */
X process_id[_second] = fork();
X if (process_id[_second] == -1) {
X perror ("fork second");
X terminate_abnormally (1);
X }
X else if (process_id[_second] == 0) { /* first child process */
X dup2 (from[_second][p_write], 1); /* redirect second's stdout */
X /* dup2 (from[_second][p_write], 2); */ /* redirect second's stderr */
X dup2 (to[_second][p_read], 0); /* redirect second's stdin */
X execl(name[_second], name[_second], (char*)0); /* start second subprocess */
X /* execl returns only on failure: */
X perror ("execl second");
X write (1, "#", 1); /* send illegal character to stop game */
X exit (1);
X }
X else { /* parent process */
X ; /* nothing */
X }
X }
X }
X /* only the parent process can ever come to this point */
X }
X alarm (alarm_interval);
X play (to, from, name, protocol, prot, result, a, b, L, k,
X maxcpu, maxmem, display_interval);
X terminate_normally ();
X}
X
X
END_OF_FILE
if test 24048 -ne `wc -c <'knobeln.c'`; then
echo shar: \"'knobeln.c'\" unpacked with wrong size!
fi
# end of 'knobeln.c'
fi
if test -f 'knobeln.cr' -a "${1}" != "-c" ; then
echo shar: Will not clobber existing file \"'knobeln.cr'\"
else
echo shar: Extracting \"'knobeln.cr'\" \(23854 characters\)
sed "s/^X//" >'knobeln.cr' <<'END_OF_FILE'
X/*************************************************************************
XProject : KNOBELN
XModule : Conductor and referee for one game
XAuthor : Lutz Prechelt, Karlsruhe
XDate : 94/03/05
XEnvironment: SUN-OS 4.1, ANSI-C (gcc), C-Refine 3.0
XRCS : $Id$
X**************************************************************************/
X
X#if 0
X
X[[ This program is written using C-Refine 3.0, which is available for anonymous
X ftp from ftp.ira.uka.de in /pub/gnu/crefine.3.0.tar.Z (93 kB)
X or from any comp.sources.reviewed archive (appeared as v02i013 to v02i19
X on comp.sources.reviewed on 15 Jul 92)
X]]
X
X
Xusage: knobeln first second [L a b k maxcpu maxmem show_interval]
X
XConducts a game of Knobeln with L throws in the interval a..b
Xminimum sequence length is k, opponent strategies are 'first' and 'second'.
XThe strategies are Unix programs, who on every throw write one number
Xtextually to stdout and then read one from stdin. Each number is ended
Xwith a newline character. Each module is allowed to use at most maxcpu
Xseconds of cpu time and maxmem kilobytes process size (SIZE field of ps).
XThe intermediate result is shown after every show_interval throws.
XFor the default values see the #define std_... below.
X
XThis program transduces the numbers thrown between the opponents,
Xchecks for the rules and computes the result.
X
X
XMethod:
X-------
XThe program creates two pipes for each opponent program.
XThe opponent programs are started via fork and exec.
XThe timeout, cputime, and space limitations are checked by a routine
Xthat is invoked by a timer alarm and reads from 'popen("ps -ux")'
XThe scanning of the ps output is critical to portability, i.e.
Xyou may need to adjust get_process_info() for a different kind of Unix.
X
XOutput:
X-------
XThe program writes three files:
X the protocol the compact protocol, and the bulletin.
XThe protocol looks roughly like this:
X------------------------------------------------------------------------
X# 1000-throw KNOBELN (interval 1...12288, minimum sequence length 8)
X# Player 1: "fribyte"
X# Player 2: "GrandPrix"
X 1: 1 6700 -> 0 : 0
X 2: 3349 10714 -> 11 : 0
X 3: 5356 11412 -> 23 : 0
X 4: 5705 12006 -> 35 : 0
X.... (here are the lines for the other throws)
X999: 12288 12288 -> 7870 : 1112
X1000: 12288 12288 -> 7870 : 1112
X
X# Game ended normally.
X# Result:
X# "fribyte": 7870 points
X# "GrandPrix": 1112 points
X------------------------------------------------------------------------
XThe corresponding short protocol looks roughly like this:
X------------------------------------------------------------------------
X# fribyte GrandPrix
X1 6700
X3349 10714
X5356 11412
X5705 12006
X.... (here are the lines for the other throws)
X12288 12288
X12288 12288
X# Game ended normally.
X------------------------------------------------------------------------
XThe bulletin is a one-line file and has one of the following forms:
X------------------------------------------------------------------------
Xteam_name_1 : team_name_2 -> 345 : 536
Xteam_name_1 : team_name_2 -> Failure of player 1
Xteam_name_1 : team_name_2 -> Failure of player 2
Xteam_name_1 : team_name_2 -> Failure of both players
X------------------------------------------------------------------------
X
X#endif
X
X/*************************************************************************/
X
X#include <assert.h>
X#include <stdio.h>
X#include <signal.h>
X
X
Xtypedef enum {false, true} bool;
X
X#define shortprotocolfilename "knobeln.prot"
X#define protocolfilename "knobeln.protocol"
X#define bulletinfilename "knobeln.bulletin"
X
X#define std_L 1000
X#define std_a 1
X#define std_b 12288
X#define std_k 8
X#define std_maxcpu 30
X#define std_maxmem 1024
X
X#define alarm_interval 10 /* check processes all ... seconds */
X
X
X#define p_read 0
X#define p_write 1
X#define _first 0
X#define _second 1
X#define _nobody -1
X/* example to[_first][p_write] is the file descriptor used by the parent
X process to write to the 'first' subprocess
X*/
X
Xstatic char *name[2]; /* the strategies' names */
Xstatic int a, b, L, k; /* the game parameters */
Xstatic int maxcpu, maxmem; /* the runtime restrictions */
Xstatic int display_interval;
Xstatic bool display_on_alarm;
Xstatic FILE *protocol, /* the protocol file */
X *prot, /* the short-protocol file */
X *bulletin; /* the result file */
Xstatic int result[2], /* current points */
X current[2]; /* last numbers thrown */
Xstatic int from[2][2],
X to[2][2]; /* the pipes */
Xstatic int process_id[2] =
X { -1, -1 }; /* the child processes */
Xstatic int throw_nr, /* number of current throw */
X old_throw_nr = 0, /* throw_nr at last alarm */
X next_to_throw; /* which player's turn it is */
X
X#if __STDC__
X#define A(a) a
X#else
X#define A(a) ()
X#endif
X
X/* Signal handling and process handling:*/
Xvoid alarm_catcher();
Xvoid kill_child_processes ();
Xvoid terminate_abnormally A((int status));
Xvoid terminate_by_signal ();
Xvoid terminate_normally ();
Xvoid watch A((int pids[2], char *name[2], int maxcpu, int maxmem,
X int throw_nr, int old_throw_nr));
Xvoid get_process_info A((int pids[2], bool still_living[2],
X int cpu[2], int mem[2]));
X
X/* help functions: */
Xvoid display ();
Xint log2 A((int n));
Xint read_int A((int fd, char *name));
X
X/* game conductor: */
Xvoid play A((int to[2][2], int from[2][2], char *name[2],
X FILE *protocol, FILE *prot,
X int result[2], int a, int b, int L, int k,
X int maxcpu, int maxmem, int display_interval));
X
X/* main: */
Xint main A((int argc, char *argv[]));
X
X/*************************************************************************/
X
Xvoid alarm_catcher()
X{
X /* handler for SIGALARM */
X watch (process_id, name, maxcpu, maxmem, throw_nr, old_throw_nr);
X old_throw_nr = throw_nr;
X if (display_on_alarm)
X display ();
X alarm (alarm_interval);
X}
X
Xvoid kill_child_processes ()
X{
X int i, result;
X for (i = _first; i <= _second; i++) {
X if (`this process > 0) {
X result = kill (`this process, SIGKILL);
X /* fprintf (stderr, "kill -9 %d --> %d ", `this_process, result); */
X }
X }
X
X`this process:
X process_id[i]
X
X}
X
X
Xvoid terminate_abnormally (exit_status)
X int exit_status;
X{
X /* actions to perform on termination because of error */
X alarm (0);
X kill_child_processes();
X exit (exit_status);
X}
X
X
Xvoid terminate_by_signal ()
X{
X /* actions to perform when interrupt signal is catched */
X fprintf (stderr, "\nSignal catched. \n");
X alarm (0);
X kill_child_processes();
X exit (1);
X}
X
X
Xvoid terminate_normally ()
X{
X /* actions to perform when normal end of program is reached */
X alarm (0);
X kill_child_processes();
X exit (0);
X}
X
X
Xvoid watch (process_id, name, maxcpu, maxmem, throw_nr, old_throw_nr)
X int process_id[2];
X char *name[2];
X int maxcpu, maxmem;
X int throw_nr, old_throw_nr;
X{
X /* This function is activated from the timer alarm catcher.
X It checks, whether the child processes identified by process_id are
X still alive, have consumed not more than maxcpu seconds cputime and
X don't use more than maxmem kilobytes of memory.
X It also checks whether the game has made any progress since the
X last alarm by comparing throw_nr with old_throw_nr. If no progress
X was made, the blame is put on next_player_to_throw which is
X either _first or _second.
X */
X bool still_living[2], failure[2];
X int cpu[2], mem[2];
X int i;
X failure[_first] = failure[_second] = false;
X get_process_info (process_id, still_living, cpu, mem);
X for (i = _first; i <= _second; i++) {
X if (!still_living[i])
X `process terminated prematurely;
X else {
X if (mem[i] > maxmem)
X `process too large;
X if (cpu[i] > maxcpu)
X `process used too much time;
X }
X }
X if (throw_nr == old_throw_nr)
X ; /* we catch this case via cputime check. Processes can't stop! */
X if (failure[_first] || failure[_second])
X `write bulletin and terminate;
X
X`process terminated prematurely:
X fprintf (protocol, "\n# Process \"%s\" terminated prematurely.", name[i]);
X fprintf (prot, "\n# Process \"%s\" terminated prematurely.", name[i]);
X fprintf (stderr, "\nProcess \"%s\" terminated prematurely.", name[i]);
X failure[i] = true;
X
X`process too large:
X fprintf (protocol, "\n# Process \"%s\" uses too much memory: %d kb",
X name[i], mem[i]);
X fprintf (prot, "\n# Process \"%s\" uses too much memory: %d kb",
X name[i], mem[i]);
X fprintf (stderr, "\nProcess \"%s\" uses too much memory: %d kb\n",
X name[i], mem[i]);
X failure[i] = true;
X
X`process used too much time:
X fprintf (protocol, "\n# Process \"%s\" used too much CPU time", name[i]);
X fprintf (prot, "\n# Process \"%s\" used too much CPU time", name[i]);
X fprintf (stderr, "\nProcess \"%s\" used too much CPU time\n", name[i]);
X failure[i] = true;
X
X`write bulletin and terminate:
X char *message = "";
X if (failure[_first] && failure[_second])
X message = "Failure of both players";
X else if (failure[_first])
X message = "Failure of player 1";
X else if (failure[_second])
X message = "Failure of player 2";
X fprintf (protocol, "\n# Game ended unnormally: %s\n", message);
X fprintf (prot, "\n# Game ended unnormally: %s\n", message);
X fprintf (bulletin, "%-30s : %30s -> %s\n",
X name[_first], name[_second], message);
X terminate_normally();
X
X}
X
X
Xvoid get_process_info (process_id, still_living, cpu, mem)
X int process_id[2];
X bool still_living[2];
X int cpu[2], mem[2];
X{
X /* uses 'popen ("ps -ux")' to get information about the child processes.
X returns in still_living, whether they still exist, and if yes, returns
X in maxmem how many kilobytes their SIZE is and how many seconds of
X CPU time they have consumed.
X */
X FILE *ps = popen ("ps -ux", "r");
X char lbuf[`N]; /* line buffer */
X int nr_of_processes_found = 0;
X `discard header line;
X still_living[_first] = false;
X still_living[_second] = false;
X while (!feof (ps) && nr_of_processes_found < 2)
X `examine next line;
X pclose (ps);
X
X`discard header line:
X fgets (lbuf, `N, ps);
X
X`examine next line:
X /* Outputformat of 'ps -ux' (SUN-4, Sun-OS 4.1):
X #USER____ PID__ CP.U ME.M SZ__ RSS_ TT STAT START TIME__ COMMAND________
X prechelt 12945 11.8 2.9 180 420 p4 R 08:15 0:00 ps -u
X 0 1 2 3 4 5 6
X 0123456789012345678901234567890123456789012345678901234567890123456789
X ^ $ ^ $ ^ $ ^ $^ $^ $ ^$ ^ $ ^ $^ $ ^
X */
X char ccc[20]; /* a few chars from lbuf */
X int index;
X int pid;
X char STAT; /* first char of STAT field */
X int SZ, /* value of SZ field */
X RSS, /* value of RSS field */
X TIME; /* value of TIME field in seconds for form mmm:mm*/
X fscanf (ps, "%s %d", ccc, &pid); /* read username and process id */
X fgets (lbuf, `N, ps); /* read rest of line, starting at column `offset */
X if (pid != process_id[_first] && pid != process_id[_second])
X leave `examine next line;
X nr_of_processes_found++;
X index = (pid == process_id[_first]) ? _first : _second;
X fprintf (stdout, "#%s", lbuf);
X `get SZ;
X `get RSS;
X `get STAT;
X `get TIME;
X `interpret values;
X
X`get SZ:
X strncpy (ccc, lbuf - `offset + `SZpos, `SZlen);
X ccc[`SZlen] = 0; /* put null terminator behind */
X SZ = atoi (ccc);
X
X`get RSS:
X strncpy (ccc, lbuf - `offset + `RSSpos, `RSSlen);
X ccc[`RSSlen] = 0; /* put null terminator behind */
X RSS = atoi (ccc);
X
X`get STAT:
X STAT = lbuf[-`offset + `STATpos];
X
X`get TIME:
X if (`is minutes and seconds format) {
X strncpy (ccc, lbuf - `offset + `TIMEminpos, `TIMEminlen);
X ccc[`TIMEminlen] = 0; /* put null terminator behind */
X TIME = 60 * atoi (ccc);
X strncpy (ccc, lbuf - `offset + `TIMEsecpos, `TIMEseclen);
X ccc[`TIMEseclen] = 0; /* put null terminator behind */
X TIME += atoi (ccc);
X }
X else {
X TIME = 3600 + 1; /* see test at `get options in main() */
X }
X
X`is minutes and seconds format:
X lbuf[`TIMEcolonpos - `offset] == ':'
X
X`interpret values:
X assert (STAT >= 'A' && STAT <= 'Z');
X still_living[index] = (STAT != `zombie);
X cpu[index] = TIME;
X mem[index] = SZ;
X
X`N: 200
X`offset: 14
X`SZpos: 24
X`SZlen: 5
X`RSSpos: 29
X`RSSlen: 5
X`STATpos: 38
X`TIMEminpos: 49
X`TIMEminlen: 3
X`TIMEsecpos: 53
X`TIMEseclen: 2
X`TIMEcolonpos: 52
X`zombie: 'Z'
X
X}
X
X
Xvoid display ()
X{
X fprintf (stdout, "%7d: %8d %8d --> %6d : %d\n", throw_nr,
X current[_first], current[_second],
X result[_first], result[_second]);
X}
X
X
Xint log2 (n)
X int n;
X{
X /* returns the floor part of logarithmus dualis of n.
X n has to be positive, but is not checked.
X */
X int result = 0;
X while (n > 1) {
X n >>= 1;
X result++;
X }
X return (result);
X}
X
X
Xint read_int (fd, name)
X int fd;
X char *name;
X{
X /* Reads characterwise from file descriptor fd. This reading must
X deliver a single integer.
X If no integer is found, complains about strategy 'name' breaking
X the rules and exits.
X */
X int result = 0;
X int sign = 1;
X char c;
X for (;;) {
X read (fd, &c, 1);
X if (c == ' ')
X `handle blanks;
X else if (c == '\n')
X return (sign*result);
X else if (c == '-')
X sign *= -1;
X else if (c >= '0' && c <= '9')
X result = 10*result + c - '0';
X else
X `complain loudly;
X }
X
X`handle blanks:
X if (result == 0)
X ; /* ignore leading spaces */
X else /* trailing spaces */
X return (sign*result);
X
X`complain loudly:
X fprintf (stderr, "\n>>> \"%s\" %s '%c' (code %d). Game aborted <<<\n",
X name, "transfers illegal character", c, (int)c);
X terminate_abnormally (2);
X
X}
X
X
Xvoid play (to, from, name, protocol, prot, result, a, b, L, k,
X maxcpu, maxmem, display_interval)
X int to[2][2], from[2][2]; /* file handles */
X char *name[2];
X FILE *protocol, *prot;
X int result[2];
X int a, b, L, k;
X int maxcpu, maxmem;
X int display_interval;
X{
X /* conducts a game between the two strategies accessible via the pipe pairs
X <to> and <from> having the names accessible in <name>.
X A protocol is written on FILE <protocol>, a short protocol on <prot>.
X The results are returned in <result> which is initialized with zeroes
X at the beginning.
X The game is of length L, in the interval a..b, with
X minimum sequence length k
X */
X int sequence_length[2]; /* current sequence lengths */
X int last[2]; /* previous values of current */
X bool failure[2];
X `init;
X `show start message;
X `perform throws;
X alarm (0);
X `write bulletin;
X
X`init:
X int i;
X for (i = _first; i <= _second; i++) {
X result[i] = 0;
X sequence_length[i] = 0;
X last[i] = -1;
X failure[i] = false;
X }
X
X`show start message:
X char buffer[200];
X sprintf (buffer, "\n# %d-throw KNOBELN (interval %d...%d, %s%d)",
X L, a, b, "minimum sequence length ", k);
X fprintf (stdout, "%s", buffer);
X fprintf (protocol, "%s", buffer);
X fprintf (prot, "%s", buffer);
X sprintf (buffer, "\n# Player 1: %s\n# Player 2: %s\n",
X name[_first], name[_second]);
X fprintf (stdout, "%s", buffer);
X fprintf (protocol, "%s", buffer);
X fprintf (prot, "\n# %s %s\n", name[_first], name[_second]);
X
X`perform throws:
X for (throw_nr = 1; throw_nr <= L && `no failure; throw_nr++) {
X `make throw;
X `protocol throw;
X `check rules;
X if (`no failure) {
X `count throw;
X `update remaining variables;
X `protocol result;
X `broadcast last throw;
X }
X }
X
X`no failure:
X !failure[_first] && !failure[_second]
X
X`make throw:
X int i;
X for (i = _first; i <= _second; i++) {
X next_to_throw = i;
X current[i] = read_int (from[i][p_read], name[i]);
X }
X next_to_throw = _nobody;
X
X`protocol throw:
X fprintf (protocol, "%4d: %5d %5d", throw_nr,
X current[_first], current[_second]);
X fprintf (prot, "%d %d\n", current[_first], current[_second]);
X
X`check rules:
X int i;
X for (i = _first; i <= _second; i++)
X if (`value is outside interval)
X `complain for interval;
X else if (`sequence is too short)
X `complain for sequence length;
X
X`value is outside interval:
X current[i] < a || current[i] > b
X
X`complain for interval:
X fprintf (stderr, "\n>>> \"%s\" throws illegal number %d. Game aborted <<<\n",
X name[i], current[i]);
X fprintf (protocol, "\n# \"%s\" throws illegal number %d.\n",
X name[i], current[i]);
X fprintf (prot, "\n# \"%s\" throws illegal number %d.\n",
X name[i], current[i]);
X failure[i] = true;
X
X`sequence is too short:
X sequence_length[i] < k && current[i] < last[i]
X
X`complain for sequence length:
X fprintf (stderr,
X "\n>>> \"%s\" throws %d after %d\n but has only %d %s <<<\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.\n Game aborted");
X fprintf (protocol,
X "\n# \"%s\" throws %d after %d\n but has only %d %s\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.");
X fprintf (prot,
X "\n# \"%s\" throws %d after %d\n but has only %d %s\n",
X name[i], current[i], last[i], sequence_length[i],
X "nondecreasing throws before.");
X failure[i] = true;
X
X`count throw:
X int i;
X for (i = _first; i <= _second; i++)
X if (`player i has won the throw)
X result[i] += log2 (current[i]);
X
X`update remaining variables:
X int i;
X for (i = _first; i <= _second; i++) {
X if (current[i] < last[i])
X sequence_length[i] = 0;
X sequence_length[i]++;
X last[i] = current[i];
X }
X
X`player i has won the throw:
X `won with more points || `won with less points
X
X`won with more points:
X /* the following expression is a bit of a hack !!! */
X current[i] > current[(i+1)%2] &&
X 2*current[(i+1)%2] >= current[i]
X
X`won with less points:
X /* the following expression is a bit of a hack !!! */
X 2*current[i] < current[(i+1)%2]
X
X`protocol result:
X fprintf (protocol, " -> %4d : %d\n", result[_first], result[_second]);
X if (throw_nr % display_interval == 0)
X display ();
X
X`broadcast last throw:
X /* hands the last number thrown by first to second and vice versa */
X char buffer[100];
X sprintf (buffer, "%d\n", current[_first]);
X write (to[_second][p_write], buffer, strlen (buffer));
X sprintf (buffer, "%d\n", current[_second]);
X write (to[_first][p_write], buffer, strlen (buffer));
X
X`write bulletin:
X if (`no failure) {
X fprintf (protocol, "\n# Game ended normally.");
X fprintf (protocol, "\n# Result:\n# %s: %d points\n# %s: %d points\n",
X name[_first], result[_first], name[_second], result[_second]);
X fprintf (prot, "\n# Result:\n# %s: %d points\n# %s: %d points\n",
X name[_first], result[_first], name[_second], result[_second]);
X fprintf (bulletin, "%-30s : %30s -> %5d : %d\n",
X name[_first], name[_second], result[_first], result[_second]);
X }
X else {
X char *message = "";
X if (failure[_first] && failure[_second])
X message = "Failure of both players";
X else if (failure[_first])
X message = "Failure of player 1";
X else if (failure[_second])
X message = "Failure of player 2";
X fprintf (protocol, "\n# Game ended abnormally. %s\n", message);
X fprintf (prot, "\n# Game ended abnormally. %s\n", message);
X fprintf (bulletin, "%-30s : %30s -> %s\n",
X name[_first], name[_second], message);
X }
X
X}
X
X/*************************************************************************/
X
Xint main (argc, argv)
X int argc;
X char *argv[];
X{
X `get and check arguments;
X `open protocol;
X `install signal catchers;
X `create subprocesses and make redirections;
X alarm (alarm_interval);
X play (to, from, name, protocol, prot, result, a, b, L, k,
X maxcpu, maxmem, display_interval);
X terminate_normally ();
X
X`get and check arguments:
X if (argc < 3 || argc > 10) {
X fprintf (stderr, `usage string);
X fprintf (stderr, " e.g. knobeln maria thorsten 500 1 6000 10 30 \n");
X fprintf (stderr, " optional args can be left out one by one from end\n");
X exit (1);
X }
X name[_first] = argv[1];
X name[_second] = argv[2];
X L = argc > 3 ? atoi (argv[3]) : std_L;
X a = argc > 4 ? atoi (argv[4]) : std_a;
X b = argc > 5 ? atoi (argv[5]) : std_b;
X k = argc > 6 ? atoi (argv[6]) : std_k;
X maxcpu = argc > 7 ? atoi (argv[7]) : std_maxcpu;
X maxmem = argc > 8 ? atoi (argv[8]) : std_maxmem;
X display_interval = argc > 9 ? atoi (argv[9]) : L/10;
X if (display_interval < 0) {
X display_interval = -display_interval;
X display_on_alarm = true;
X }
X else
X display_on_alarm = false;
X if (a <= 0 || b <= a || b > 100000000) {
X fprintf (stderr, "\nmust be 0 < a < b <= 1e8\n");
X exit (1);
X }
X if (k <= 1 || L/10 <= k || L > 1000000) {
X fprintf (stderr, "\nmust be 1 < k < L/10 <= 1e5\n");
X exit (1);
X }
X if (maxcpu >= 3600) { /* see get_process_info(): `get TIME */
X fprintf (stderr, "\nmust be maxcpu < 3600\n");
X exit (1);
X }
X
X`usage string:
X "usage: knobeln first second [L a b k maxcpu maxmem show_interval]\n"
X
X`open protocol:
X protocol = fopen (protocolfilename, "w");
X if (protocol == NULL) {
X perror (protocolfilename);
X exit (1);
X }
X setbuffer (protocol, 0, 0); /* no buffering */
X prot = fopen (shortprotocolfilename, "w");
X if (prot == NULL) {
X perror (shortprotocolfilename);
X exit (1);
X }
X setbuffer (prot, 0, 0); /* no buffering */
X bulletin = fopen (bulletinfilename, "w");
X if (bulletin == NULL) {
X perror (bulletinfilename);
X exit (1);
X }
X
X`install signal catchers:
X signal (SIGALRM, alarm_catcher);
X signal (SIGINT, terminate_by_signal);
X
X`create subprocesses and make redirections:
X pipe (from[_first]);
X pipe (to[_first]);
X pipe (from[_second]);
X pipe (to[_second]);
X `do forks;
X /* only the parent process can ever come to this point */
X
X`do forks:
X process_id[_first] = fork();
X if (process_id[_first] == -1) {
X perror ("fork first");
X terminate_abnormally (1);
X }
X else if (process_id[_first] == 0) { /* first child process */
X dup2 (from[_first][p_write], 1); /* redirect first's stdout */
X /* dup2 (from[_first][p_write], 2);*/ /* redirect first's stderr */
X dup2 (to[_first][p_read], 0); /* redirect first's stdin */
X execl(name[_first], name[_first], (char*)0); /* start first subprocess */
X /* execl returns only on failure: */
X perror ("execl first");
X write (1, "#", 1); /* send illegal character to stop game */
X exit (1);
X }
X else /* parent process */
X `do second fork;
X
X`do second fork:
X process_id[_second] = fork();
X if (process_id[_second] == -1) {
X perror ("fork second");
X terminate_abnormally (1);
X }
X else if (process_id[_second] == 0) { /* first child process */
X dup2 (from[_second][p_write], 1); /* redirect second's stdout */
X /* dup2 (from[_second][p_write], 2); */ /* redirect second's stderr */
X dup2 (to[_second][p_read], 0); /* redirect second's stdin */
X execl(name[_second], name[_second], (char*)0); /* start second subprocess */
X /* execl returns only on failure: */
X perror ("execl second");
X write (1, "#", 1); /* send illegal character to stop game */
X exit (1);
X }
X else { /* parent process */
X ; /* nothing */
X }
X}
X
X
END_OF_FILE
if test 23854 -ne `wc -c <'knobeln.cr'`; then
echo shar: \"'knobeln.cr'\" unpacked with wrong size!
fi
# end of 'knobeln.cr'
fi
echo shar: End of shell archive.
exit 0
0 new messages