4x5_nostar.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
  ./4x5_nostar 5 => uldll:11
  ./4x5_nostar 6 => uldruu:10
  ./4x5_nostar 7 => llulurr:8
  ./4x5_nostar 8 => llulurur:6
  ./4x5_nostar 9 => llulururu:6
  ./4x5_nostar 10 => llullurrur:3
  ./4x5_nostar 11 => llullurruru:3
  ./4x5_nostar 12 => llullurrurul:3
  ./4x5_nostar 13 => llullurrurull:3
  ./4x5_nostar 14 => lurdllullurrur:0
 */

void print_field(char field[4][6])
{
  int i;

  for (i = 0; i < 4; i++) {
    printf("%s\n", field[i]);
  }
}

void move_pos(char field[4][6], int x, int y, char *s)
{
  int new_x = x, new_y = y;
  char tmp;

  while (*s != '\0') {
    switch (*s) {
    case 'u': new_y--; break;
    case 'd': new_y++; break;
    case 'l': new_x--; break;
    case 'r': new_x++; break;
    }
    s++;
    if (new_x < 0 || new_x >= 5 || new_y < 0 || new_y >= 4) {
      continue;
    }
    tmp = field[y][x];
    field[y][x] = field[new_y][new_x];
    field[new_y][new_x] = tmp;
    x = new_x;
    y = new_y;
  }
}

int check_pos(int checker[4][5], int x, int y)
{
  if (checker[y][x] == 0) {
    checker[y][x] = 1;
    return 1;
  }
  return 0;
}

void mark_field(char field[4][6], int checker[4][5])
{
  int x, y;

  for (y = 0; y < 4; y++) {
    for (x = 0; x < 5; x++) {
      if (checker[y][x] != 0) {
        field[y][x] = '*';
      }
    }
  }
}

int test_field(char field[4][6])
{
  int checker[4][5];
  int count = 0;
  int x, y;

  memset(checker, 0, sizeof(checker));
  for (x = 0; x < 3; x++) {
    for (y = 0; y < 4; y++) {
      if (field[y][x] == field[y][x + 1] && field[y][x] == field[y][x + 2]) {
        count += check_pos(checker, x, y)
          + check_pos(checker, x + 1, y)
          + check_pos(checker, x + 2, y);
      }
    }
  }

  for (x = 0; x < 5; x++) {
    for (y = 0; y < 2; y++) {
      if (field[y][x] == field[y + 1][x] && field[y][x] == field[y + 2][x]) {
        count += check_pos(checker, x, y)
          + check_pos(checker, x, y + 1)
          + check_pos(checker, x, y + 2);
      }
    }
  }

#ifdef DISPLAY
  printf("[Result]\n");
#endif
  mark_field(field, checker);
#ifdef DISPLAY
  print_field(field);
#endif

  return count;
}

char *set_path(char *s, int len, int num)
{
  char *t = s;

  *t = "lu"[num & 1];
  len--;
  t++;
  num >>= 1;
  for (; len > 0; len--, t++, num >>= 2) {
    *t = "lurd"[num & 3];
  }
  *t = '\0';

  return s;
}

int main(int argc, char* argv[])
{
  char field_base[4][6] = {
    "aaacc",
    "abccc",
    "abccc",
    "bbbba"
  };
  char field[4][6];
  int i;
  int count_min = -1;
  char path_min[17];
  int path_len = 5;

  if (argc > 1) {
    int len = atoi(argv[1]);
    if (len >= 1 && len <= 16) {
      path_len = len;
      printf("path_len=%d\n", path_len);
    }
  }

#ifdef LISTALL
  for (i = 0; i < (1 << (2 * 4 + 1)); i++) {
    set_path(path_min, 5, i);
    printf("%s:%d\n", path_min, i);
  }
#endif

  for (i = 0; i < (1 << (2 * path_len - 1)); i++) {
    char path[17] = {0};
    int count;

    set_path(path, path_len, i);
    memcpy(field, field_base, sizeof(field_base));

#ifdef DISPLAY
    printf("[[%s]]\n", path);
    printf("[1]\n");
    print_field(field);
#endif

    move_pos(field, 4, 3, path);
#ifdef DISPLAY
    printf("[2]\n");
    print_field(field);
#endif

    count = test_field(field);
    if (count_min < 0 || count < count_min) {
      count_min = count;
      strcpy(path_min, path);
      printf("updated:%s:%d\n", path, count);
      if (count == 0) {
        return 0;
      }
    }
  }

#ifdef DISPLAY
  printf("[[Result]]\n");
  printf("path=%s, count=%d\n", path_min, count_min);
#endif

  return 0;
}