13_four

bot_karl.c

#include "bot_karl.h"

bool bot_karl_ready_to_work = false;

void intialize_bot_karl(pt_four_wins_ctx ctx) {
  //printf("Bot Karl intialized\n");
 
  srand(time(NULL));
  bot_karl_ready_to_work = true;
}

void impl_send_bot_karl_play_request(pt_four_wins_ctx ctx) {
 
  if (bot_karl_ready_to_work == false)
    intialize_bot_karl(ctx);

  four_turn_result turn_result = INVALID;
  
  while(turn_result == INVALID || turn_result == NOT_EMPTY) {
     unsigned short x_request = (unsigned short)round((double)rand() / RAND_MAX * ctx->width);
     printf("%d\n", x_request);

     turn_result = ctx->func_receive_request((unsigned short)x_request);
  }

}

pt_four_player get_player() {
  pt_four_player bot_player = (pt_four_player)calloc(1, sizeof(four_player));
  
  bot_player->name = PLAYER_NAME_KARL; 
  bot_player->func_send_request = &impl_send_bot_karl_play_request;

  return bot_player;
}

bot_karl.h

#ifndef _BOT_KARL_H_
#define _BOT_KARL_H_

#include "four.h"

#define PLAYER_NAME_KARL "karl"


#endif // _BOT_KARL_H_

four.c

#include "four.h"
#include "utils.h"

four_wins_ctx ctx = { 7, 6, { { 0 } } };

short transform_x_for_quadrant(unsigned short q, short x)
{
  switch(q) {
    case 0:
    case 3:
      return x;
    case 1:
    case 2:
      return -1 * x;
    default:
      return 0; // never reached
  }
}

short transform_y_for_quadrant(unsigned short q, short y)
{
   switch(q) {
    case 0:
    case 1:
      return y;
    case 2:
    case 3:
      return -1 * y;
    default:
      return 0; // never reached
  }
}

short calculate_max_four_count(pt_four_in_row_counts counts) {
  // Summe in Quadraten bilden, Horz.- & Vertikal-Werte
  // kommen aus Symmetriegründen doppelt vor.
  short horizontal = counts->n[0] + counts->n[3]; // == counts->n[6] + counts->n[9]
  short vertical   = counts->n[2] + counts->n[8]; // == counts->n[5] + counts->n[11]
  short d_tlbr     = counts->n[4] + counts->n[10];
  short d_bltr     = counts->n[7] + counts->n[1];

#ifdef DEBUG
  printf("h: %d, v: %d, d_tlbr: %d, d_bltr: %d\n", horizontal, vertical, d_tlbr, d_bltr);
#endif

  return MAX(horizontal, MAX(vertical, MAX(d_tlbr, d_bltr)));
}

void count_single_entry(pt_four_wins_ctx ctx,
                        unsigned short q, unsigned short r,
                        pt_four_in_row_counts counts,
                        four_turn t,
                        short x, short y) 
{
  short idx = 3 * q + r;

  if (counts->blocked[idx] == true)
    return;

  if (x < 0 || x >= ctx->width) {
    counts->blocked[idx] = true;
    return;
  }

  four_turn u = get_turn_at(ctx, x, y);
  if (u != t) {
    counts->blocked[idx] = true;
    return;
  }

  counts->n[idx]++;
}

void count_four_in_quadrant(pt_four_wins_ctx ctx,
                            unsigned short q, 
                            pt_four_in_row_counts counts, 
                            four_turn t,
                            unsigned short o_x, unsigned short o_y)
{
  for (short lookaside = 1; lookaside < 4; lookaside++) {
    // horizontal
    short x = ((short)o_x) + transform_x_for_quadrant(q, lookaside);
    short y = ((short)o_y);
    count_single_entry(ctx, q, 0, counts, t, x, y);

    // diagonal
    x = ((short)o_x) + transform_x_for_quadrant(q, lookaside);
    y = ((short)o_y) + transform_y_for_quadrant(q, lookaside);
    count_single_entry(ctx, q, 1, counts, t, x, y);

    // vertical
    x = ((short)o_x);
    y = ((short)o_y) + transform_y_for_quadrant(q, lookaside);
    count_single_entry(ctx, q, 2, counts, t, x, y);
  }
}

void debug_count(pt_four_in_row_counts counts) {
#ifdef DEBUG
  for (int i = 0; i < 12; i++) {
    if (i % 3 == 0)
      printf("|");

    printf(" %i ", counts->n[i]);
  }
  printf("\n");

  for (int i = 0; i < 12; i++) {
    if (i % 3 == 0)
      printf("|");

    printf(" %c ", counts->blocked[i] == true ? 't' : 'f');
  }
  printf("\n---------------------------------------\n");
#endif
}

bool is_four_found(pt_four_wins_ctx ctx, unsigned short o_x, unsigned short o_y) {
  four_in_row_counts counts = {{ 0 }, { 0 }};
  four_turn t = get_turn_at(ctx, o_x, o_y);

  for (unsigned short q = 0; q < 4; q++) {
    count_four_in_quadrant(ctx, q, &counts, t, o_x, o_y);
  }
  debug_count(&counts);
  if (calculate_max_four_count(&counts) == 3)
    return true;

  return false;
}

void print_grid() {
  printf("\n");
  
  for (int y = (ctx.height - 1); y >= 0; y--) {
    for (int x = 0; x < ctx.width; x++) {
      char turn_mnemonic = get_mnemonic_for_turn_at(&ctx, x, y); 
      char *last_delimiter = (x + 1) == ctx.width ? "|" : "";

      printf("| %c %s", turn_mnemonic, last_delimiter);
    }
    printf("\n");
  }
}

void print_axis() {
  for (int i = 0; i < ctx.width; i++) {
    char *last_delimiter = (i + 1) == ctx.width ? "+" : "";
    printf("+---%s", last_delimiter);
  }
  printf("\n");

  for (int i = 0; i < ctx.width; i++) {
    printf("  %d ", i);
  }
  printf("\n");
}

void print_field() {
  printf("\n");

  print_grid();
  print_axis();

  printf("\n");
}

void print_player_prompt(four_turn turn) {
    printf("Player '%s': ", 
        turn == PLAYER_X ? ctx.player_x->name : ctx.player_o->name);
}

void send_play_request(four_turn turn) {
  if (turn == PLAYER_X)
    ctx.player_x->func_send_request(&ctx);
  else
    ctx.player_o->func_send_request(&ctx);
}

void game_read_eval_print_loop() {

  ctx.turn = PLAYER_X;

  while(true) {

    print_field();
    print_player_prompt(ctx.turn);
    
    send_play_request(ctx.turn);

    if (ctx.latest_turn_result == FIELD_FULL) {
      printf("Unentschieden \n");
      return;
    }
    else if (ctx.latest_turn_result == FOUR_FOUND) {
      print_field();
      printf("Spieler '%s' hat gewonnen?\n", 
            ctx.turn == PLAYER_X
              ? ctx.player_x->name
              : ctx.player_o->name);
      return;
    }

    ctx.turn = ctx.turn == PLAYER_X 
                        ? PLAYER_O 
                        : PLAYER_X;
  }
}

four_turn_result impl_receive_play_request(unsigned short x) {
  if (x >= ctx.width)
    return INVALID;

  int y = -1;
  if ((y = set_next_free_in_column(&ctx, x)) < 0)
    return NOT_EMPTY;

  if (is_four_found(&ctx, x, (unsigned short)y) == true) {
    ctx.latest_turn_result = FOUR_FOUND;
    return FOUR_FOUND;
  }

  if (is_field_full(&ctx)) {
    ctx.latest_turn_result = FIELD_FULL;
    return FIELD_FULL;
  }

  ctx.latest_turn_result = FOUR_NOT_FOUND;
  return FOUR_NOT_FOUND;
}

void print_usage() {
  fprintf(stderr, "\nUSAGE: four [PLAYER_X] [PLAYER_O]\n\n");
}

void initialize_player(four_player **player, char *player_name) {
  if (strlen(player_name) == 0) {
    print_usage();
    exit(2);
  }
  
  *player = find_player_in_cwd(player_name);
  if (*player == NULL) {
    fprintf(stderr, 
            "**Error** Kann keinen Spieler mit dem Namen '%s' finden\n", 
            player_name);
    exit(2);
  }
}

void initialize_four_wins_ctx(int argc, char **argv) {
  if (argc < 3) {
    print_usage();
    exit(1);
  }

  ctx.func_receive_request = &impl_receive_play_request;
  
  initialize_player(&(ctx.player_x), argv[1]);
  initialize_player(&(ctx.player_o), argv[2]);
}

int main (int argc, char **argv) {

  initialize_four_wins_ctx(argc, argv);
  game_read_eval_print_loop();

  return 0;
}

four.h

#ifndef _FOUR_H_
#define _FOUR_H_

#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define DEBUG

// forward declaration for function-ptr typedefs
// redifend later
struct _four_wins_ctx; 

typedef enum _four_turn {
   EMPTY = 0,
   PLAYER_X,
   PLAYER_O
} four_turn;

typedef enum _four_turn_result {
   INVALID,
   NOT_EMPTY,
   FOUR_FOUND,
   FOUR_NOT_FOUND,
   FIELD_FULL
} four_turn_result;

typedef struct _four_in_row_counts {
  int  n[12];
  bool blocked[12];
} four_in_row_counts, *pt_four_in_row_counts;

typedef four_turn_result (*pt_func_receive_play_request)(unsigned short x);
typedef void (*pt_func_send_play_request)(struct _four_wins_ctx *ctx);

typedef struct _four_player {
  char *name;
  pt_func_send_play_request func_send_request;
  unsigned int turns;
} four_player, *pt_four_player;

typedef struct _four_wins_ctx {
  unsigned short width;
  unsigned short height;
  unsigned short field[7][6];

  four_turn turn;
  four_turn_result latest_turn_result;
  pt_func_receive_play_request func_receive_request;

  pt_four_player player_x;
  pt_four_player player_o;

} four_wins_ctx, *pt_four_wins_ctx;


bool is_field_full(pt_four_wins_ctx ctx);
bool is_four_found(pt_four_wins_ctx ctx, unsigned short x, unsigned short y);

#endif // _FOUR_H_

human.c

#include "human.h"

void clear_input_buffer() {
  char ch;
  while ((ch = getchar()) != '\n' && ch != EOF);
}

void impl_send_human_play_request(pt_four_wins_ctx ctx) 
{
  four_turn_result turn_result = INVALID;
  
  while(turn_result == INVALID || turn_result == NOT_EMPTY) {
    unsigned int x_request = 0;
    if (scanf("%u", &x_request) != 1)
      continue;

    clear_input_buffer();

    turn_result = ctx->func_receive_request((unsigned short)x_request);
    if (turn_result == INVALID) {
      printf("Ausserhalb der Spielfelds, nochmal: ");
    }

    if (turn_result == NOT_EMPTY) {
      printf("Spalte voll, nochmal: ");
    }
  }
}

pt_four_player get_player() {
  pt_four_player human_player = (pt_four_player)calloc(1, sizeof(four_player));
  
  human_player->name = PLAYER_NAME_HUMAN; 
  human_player->func_send_request = &impl_send_human_play_request;

  return human_player;
}

human.h

#ifndef _HUMAN_H_
#define _HUMAN_H_

#include "four.h"

#define PLAYER_NAME_HUMAN "human"


#endif // _HUMAN_H_

makefile

CFLAGS	= -Wall -g -std=gnu99
LFLAGS	= -R/usr/local/lib -lm
SHARED  = -fPIC -shared
CC	= gcc

DEPENDFILE = .dependencies
SRC	= four.c utils.c 
SHSRC	= human.c bot_karl.c
OBJ 	= $(SRC:%.c=%.o) 
SHOBJ 	= $(SHSRC:%.c=%.so)
BIN	= four

.PHONY: dep clean

all:	$(OBJ) $(SHOBJ)
	$(CC) $(CFLAGS) -o $(BIN) $(OBJ) $(LFLAGS)

dep:
	$(CC) -MM $(SRC) $(SHSRC) > $(DEPENDFILE)

-include $(DEPENDFILE)

$(SHOBJ):	%.so: %.c
	$(CC) -o $@ $(SHARED) $(CFLAGS) $< $(LFLAGS)

%.o: %.c
	$(CC) $(CFLAGS) -c $<

clean:
	rm -f $(OBJ) $(SHOBJ) $(BIN) $(DEPENDFILE)
	rm -rf *.dSYMS

utils.c

#include "utils.h"

four_turn get_turn_at(pt_four_wins_ctx ctx, unsigned short x, unsigned short y) {
  return (four_turn)(ctx->field[x][y]);
}

char get_mnemonic_for_turn_at(pt_four_wins_ctx ctx, unsigned short x, unsigned short y) {
  four_turn turn = get_turn_at(ctx, x, y);

  return (turn == EMPTY)
            ? (' ') 
            : (turn == PLAYER_X)
              ? ('X')
              : ('O');
}

void set_turn_at(pt_four_wins_ctx ctx, unsigned short x, unsigned short y, four_turn turn) {
  ctx->field[x][y] = turn;
}

int set_next_free_in_column(pt_four_wins_ctx ctx, unsigned short x) {
  for (int y = 0; y < ctx->height; y++) {
    if (get_turn_at(ctx, x, y) != EMPTY)
      continue;

    set_turn_at(ctx, x, y, ctx->turn);
    return y;
  }

  return -1;
}

bool is_field_full(pt_four_wins_ctx ctx) {
  for (int x = 0; x < ctx->width; x++) {
    for (int y = 0; y < ctx->height; y++) {
      if (get_turn_at(ctx, x, y) == EMPTY)
        return false;
    }
  }

  return true;
}



pt_four_player find_player_in_file(char *file_name, char *player_name) {
  void *handle = dlopen(file_name, RTLD_LAZY | RTLD_LOCAL);
  if (handle == NULL) {
    fprintf(stderr, "**Error** Kann SHLIB '%s' nicht öffnen\n", file_name);
    return NULL;
  }

  pt_four_player (*func_get_player)() = dlsym(handle, GET_PLAYER_FUNC_NAME); 
  if (func_get_player == NULL) {
    dlclose(handle);
    return NULL;
  }

  pt_four_player p = func_get_player();
  if (p == NULL) {
    fprintf(stderr, "**Error** Kann von '%s' keine Player-Struktur erhalten\n", file_name);
    return NULL;
  }

  if (p->name == NULL) {
    free(p);
    dlclose(handle);

    fprintf(stderr, "**Error** Player-Struktur von '%s' enthält keinen Namen\n", file_name);
    return NULL;
  }

  if (strcasecmp(player_name, p->name) != 0) {
    free(p);
    dlclose(handle);

    return NULL;
  }

  return p;
}

pt_four_player find_player_in_cwd(char *player_name) {
  DIR *d_handle = opendir(".");

  for(struct dirent *d_entry; d_entry != NULL; d_entry = readdir(d_handle))
  {
    struct stat stat;

    if (strstr(d_entry->d_name, ".so") == NULL)
      continue;

    if (lstat(d_entry->d_name, &stat) != 0)
      continue;

    if (! (stat.st_mode & S_IFREG))
      continue;

   
    pt_four_player p = find_player_in_file(d_entry->d_name, player_name);
    if (p != NULL) {
      closedir(d_handle);
      return p;
    }
  }

  closedir(d_handle);
  return NULL;
}

utils.h

#ifndef _UTILS_H_
#define _UTILS_H_

#include <dirent.h>
#include <dlfcn.h>
#include <sys/stat.h>
#include <sys/types.h>

#include "four.h"

#define GET_PLAYER_FUNC_NAME "get_player"

#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
#define ABS(X)   ((X) > (0) ? (X) : (X * -1))



four_turn get_turn_at(pt_four_wins_ctx ctx, unsigned short x, unsigned short y);
char get_mnemonic_for_turn_at(pt_four_wins_ctx ctx, unsigned short x, unsigned short y);
void set_turn_at(pt_four_wins_ctx ctx, unsigned short x, unsigned short y, four_turn turn);
int set_next_free_in_column(pt_four_wins_ctx ctx, unsigned short x);



pt_four_player find_player_in_cwd(char *find_player_in_cwd);

#endif // _UTILS_H_