年齢並べ

プログラマのための論理パズルに掲載されているパズル「年齢並べ」をC言語に解かせてみました。順列の生成のところで、つまってしまって少し凹みました。

コード

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
struct Person {
  const char* name;
  int age;
  struct Person* next;
  struct Person* prev;
};
struct Person* person(const char* name,int age) {
  struct Person* p = malloc(sizeof(struct Person));
  p->name = name;
  p->age = age;
  p->next = NULL;
  p->prev = NULL;
  return p;
}
struct People {
  struct Person** p;
  int n;
};
static struct People people;
void init_people(const char* name) {
people.p = malloc(5*sizeof(people.p[0]));
people.p[people.n++] = person(name, 0);
}
void free_people(void) {
int i;
for(i = 0;i < people.n; i++) 
  free(people.p[i]);
free(people.p);
people.n = 0;
}
void add_person(const char* name) {
struct Person* p = person(name, 0);
  people.p[people.n -1]->next = p;
  p->prev = people.p[people.n -1];
  people.p[people.n++] = p;
}
struct Person* lookup(const char* name) {
  int i;
  for(i = 0; i < people.n; i++)
    if(!strcmp(name, people.p[i]->name))
      return people.p[i];
  return NULL;
}

void set_age(void) {
struct Person* p;
  p = lookup("Luke");
  // Lukeは16歳
  p->age = 16; 
  // Lukeは左隣より5歳下
  p->prev->age = 21;//16 + 5 
  p = lookup("Carol");
  // Carolは40歳
  p->age = 40;
  // Carolは左隣より12歳上
  p->prev->age = 28;//40 -12
  //合計は135歳(残り一人の年齢は30=(135-16-21-40-28)歳)
  int i;
  for(i = 0; i < people.n; i++)
    if(0 ==  people.p[i]->age)
      people.p[i]->age = 30;// 135 - 16 - 21 - 40 - 28
}
int check_ordering(void) {
struct Person *Tommy, *Jessica;
  Tommy = lookup("Tommy");
//Tommyは右隣より5歳上
if(Tommy->age != (Tommy->next->age +5))
  return 0;
  Jessica = lookup("Jessica");
//Jessicaは左隣より14歳上
if(Jessica->age != (Jessica->prev->age +14))
  return 0;  
if(!(lookup("Luke")->age < Tommy->age &&
     Tommy->age < lookup("Andrew")->age &&
     lookup("Andrew")->age < Jessica->age &&
     Jessica->age < lookup("Carol")->age))
       return 0;
int i;
int tot = 0;
  for(i = 0; i < people.n; i++)
    tot += people.p[i]->age;
  people.n = 0;
  return tot == 135;
}
void construct_people(int argc, char* argv[]) {
  init_people(argv[0]);
  int i;
  for(i = 1; i < argc; i++)
    add_person(argv[i]);
  people.p[0]->prev = people.p[4];
  assert(people.n == 5 && "check #people");
  people.p[4]->next = people.p[0];
  set_age();
}
static char* names[] = { 
           "Andrew",
	   "Carol",
	   "Jessica", 
	   "Luke", 
	   "Tommy"};
void swap(char** names,int i, int j) {
char* t;
  t = names[i]; names[i] = names[j]; names[j] = t;
}
void permutation(char**names,int depth, int max_depth) {
static count = 1;  
  if(depth == max_depth) {
    int i;
    names--;
    construct_people(max_depth+1, names);
    printf("%d)", count++);
    for(i = 0; i < max_depth+1; i++) {
      printf("%s ", names[i]);
    }
    if(check_ordering()) {
      printf(":success!\n");
      int i;
      for(i = 0; i< 5; i++) {
        printf("  %s, age=%d\n", people.p[i]->name, people.p[i]->age);
      }
    }
    else
      printf(":failed\n");
    free_people();
    return;
  }
  int i;
  for(i = depth; i < max_depth; i++) {
    swap(names, depth , i);
    permutation(names, depth + 1, max_depth);
    swap(names, i , depth);
  }
}

void test(void);
int main(int argc, char* argv[]) { 
  if(argc == 2 && !strcmp(argv[1], "test")) {
    test();
    exit(0);
  }
  permutation(names+1,0, 4);
  exit(0);
}
CheckPerson(struct Person* p, const char* name,
            int age, struct Person* next, struct Person* prev, FILE* fp) {
  if(fp) {
    fprintf(fp,"name:%s, age:%d, next:%s, prev:%s\n", 
    p->name, p->age,
    (p->next)? "NN": "NULL",
    (p->prev)? "NN": "NULL"  
    );
  }
 assert(!strcmp(name, p->name) && "check name");
 assert(age == p->age && "check age");
 assert(next == p->next && "check next");
 assert(prev == p->prev && "check prev");
}
void test_person(void) {
struct Person* p = person("Luke", 16);
CheckPerson(p, "Luke", 16, NULL, NULL, NULL);
free(p);
}

void test_add_person(void) {
init_people("Andrew");
add_person("Carol");
add_person("Jessica");
add_person("Luke");
add_person("Tommy");
people.p[0]->prev = people.p[4];
CheckPerson(people.p[0], "Andrew", 0, people.p[1], people.p[4], NULL);
CheckPerson(people.p[1], "Carol", 0, people.p[2], people.p[0], NULL);
CheckPerson(people.p[2], "Jessica", 0, people.p[3], people.p[1], NULL);
CheckPerson(people.p[3], "Luke", 0, people.p[4], people.p[2], NULL);
CheckPerson(people.p[4], "Tommy", 0, NULL, people.p[3], NULL);
assert(people.n == 5 && "#people");
free_people();
}

void test_lookup(void) {
init_people("Andrew");
add_person("Carol");
add_person("Jessica");
add_person("Luke");
add_person("Tommy");
CheckPerson(lookup("Andrew"), "Andrew", 0, people.p[1], NULL, NULL);
CheckPerson(lookup("Carol"), "Carol", 0, people.p[2], people.p[0], NULL);
CheckPerson(lookup("Jessica"), "Jessica", 0, people.p[3], people.p[1], NULL);
CheckPerson(lookup("Luke"), "Luke", 0, people.p[4], people.p[2], NULL);
CheckPerson(lookup("Tommy"), "Tommy", 0, NULL, people.p[3], NULL);
assert(NULL == lookup("nabeyang"));
free_people();
}

void test_set_age(void) {
init_people("Luke");
add_person("Jessica");
add_person("Andrew");
add_person("Carol");
add_person("Tommy");
people.p[4]->next = people.p[0];
people.p[0]->prev = people.p[4];
set_age();
CheckPerson(people.p[0], "Luke", 16, people.p[1], people.p[4], NULL);
CheckPerson(people.p[1], "Jessica", 30, people.p[2], people.p[0], NULL);
CheckPerson(people.p[2], "Andrew", 28, people.p[3], people.p[1], NULL);
CheckPerson(people.p[3], "Carol", 40, people.p[4], people.p[2], NULL);
CheckPerson(people.p[4], "Tommy", 21, people.p[0], people.p[3], NULL);
assert(check_ordering() && "check ordering");
free_people();
}

void test_check_ordering(void) {
{
  char* input[] = {"Tommy", "Luke", "Jessica", "Andrew", "Carol"};
  construct_people(5, input);
  assert(check_ordering() && "expect  success");
  free_people();
}
{
  char* input[] = {"Luke", "Tommy", "Jessica", "Andrew", "Carol"};
  construct_people(5, input);
  assert(!check_ordering() && "should be failed");
  free_people();
}
}
void test_swap(void) {
  char* greetings[] = {"good morning", "hello", "hi", "bye"};
  swap(greetings, 1, 2);
  assert(!strcmp("good morning", greetings[0]));
  assert(!strcmp("hi", greetings[1]));
  assert(!strcmp("hello", greetings[2]));
  assert(!strcmp("bye", greetings[3]));
}

void test(void) {
  test_person();
  test_add_person();
  test_lookup();
  test_set_age();
  test_check_ordering();
  test_swap();
}

出力結果

1)Andrew Carol Jessica Luke Tommy :failed

2)Andrew Carol Jessica Tommy Luke :failed

3)Andrew Carol Luke Jessica Tommy :failed

4)Andrew Carol Luke Tommy Jessica :failed

5)Andrew Carol Tommy Luke Jessica :success!

  Andrew, age=28

  Carol, age=40

  Tommy, age=21

  Luke, age=16

  Jessica, age=30

6)Andrew Carol Tommy Jessica Luke :failed

7)Andrew Jessica Carol Luke Tommy :failed

8)Andrew Jessica Carol Tommy Luke :failed

9)Andrew Jessica Luke Carol Tommy :failed

10)Andrew Jessica Luke Tommy Carol :failed

11)Andrew Jessica Tommy Luke Carol :failed

12)Andrew Jessica Tommy Carol Luke :failed

13)Andrew Luke Jessica Carol Tommy :failed

14)Andrew Luke Jessica Tommy Carol :failed

15)Andrew Luke Carol Jessica Tommy :failed

16)Andrew Luke Carol Tommy Jessica :failed

17)Andrew Luke Tommy Carol Jessica :failed

18)Andrew Luke Tommy Jessica Carol :failed

19)Andrew Tommy Jessica Luke Carol :failed

20)Andrew Tommy Jessica Carol Luke :failed

21)Andrew Tommy Luke Jessica Carol :failed

22)Andrew Tommy Luke Carol Jessica :failed

23)Andrew Tommy Carol Luke Jessica :failed

24)Andrew Tommy Carol Jessica Luke :failed