[WIP] dragon.c: Try to find the fastest strategy to guess the ordering of four items.

dragon.c

/* Game: given four different items, try to put them in order.
With each try, a number is returned indicating how many items are in their correct position.  (As in a recent Crystal Maze game)
Challenge: find a strategy that minimises the (worst-case) number of moves needed to guess the order.
*/

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

typedef unsigned char move_count;
typedef unsigned char perm;
typedef unsigned int state;

#define SHL4(a, n) ( (a) << ((n)*4) )
#define SHR4(a, n) ( (a) >> ((n)*4) )

#define POW2(n) (1u << (n))
#define ONES(n) (POW2(n) - 1)
#define BLANK_STATE ((state)ONES(24))

move_count moves_lut[POW2(24)];

int max(int a, int b) { return (a >= b)? a : b; }
int min(int a, int b) { return (a <= b)? a : b; }
int bit_count(unsigned int n) { return n? bit_count(n & (n-1)) + 1 : 0; }
int ilog2(unsigned int n) { return (n > 2)? (1 + ilog2(n / 2)) : (n - 1); }

int swap_digs(int p, int a, int b) {
  int x = 0xf & (SHR4(p, a) ^ SHR4(p, b));
  return p ^ SHL4(x, a) ^ SHL4(x, b);
}

int expand(perm p) {
  int ret = 0x1234;
  int i, n ;

  for (i = 0; i < 3; i++) {
    n = 4 - i;
    ret = swap_digs(ret, i, i + (p % n));
    p /= n;
  }

  return ret;
}

perm unexpand(int h) {
  perm ret;
  for (ret = 0; ret < 24; ret++) {
    if (expand(ret) == h) {
      return ret;
    }
  }

  return -1;
}

int how_many(perm guess, perm actual) {
  int ret = 0;
  int e_guess = expand(guess), e_actual = expand(actual);
  for (int i = 0; i < 4; i++) {
    int d_guess  = (e_guess  >> (i * 4)) & 0xf;
    int d_actual = (e_actual >> (i * 4)) & 0xf;
    if (d_guess == d_actual) ret++;
  }

  return ret;
}

int matches(perm guess, perm actual, int num_correct) {
  return (how_many(guess, actual) == num_correct);
}

move_count moves(state s);

state state_if_num(state s, perm guess, int num_correct) {
  perm actual;
  for (actual = 0; actual < 24; actual++) {
    if (s & POW2(actual)) {
      if (!matches(guess, actual, num_correct)) {
        s &= ~POW2(actual);
      }
    }
  }

  return s;
}

move_count worst_case_moves(state s) {
  return bit_count(s);
}

move_count moves_if_num(state s, perm guess, int num_correct) {
  state s_new = state_if_num(s, guess, num_correct);
  //printf("%x < %x\n", s_new, s);

  /* prevent infinite loops */
  if (s_new > s) return 99;
  if (s_new == s) return worst_case_moves(s_new);

  return moves(s_new) + 1;
}

move_count moves_if_guess(state s, perm guess) {
  int worst = moves_if_num(s, guess, 0);
  int num_correct = 0;
  for (num_correct = 1; num_correct <= 4-2; num_correct++) {
    worst = max(worst, moves_if_num(s, guess, num_correct));
  }
  return worst;
}

move_count moves(state s) {

  if ((s & (s-1)) == 0) {
    return 0;
  }
  if (moves_lut[s] > 0) {
    return moves_lut[s];
  }

  perm guess = 0;
  move_count best_moves = 99;
  for (guess = 0; guess < 24; guess++) {
    best_moves = min(best_moves, moves_if_guess(s, guess));
  }

  moves_lut[s] = best_moves;
  return best_moves;
}

perm best_guess(state s) {
  perm guess = 0, b_guess = 0;
  move_count b_moves = 99;
  for (guess = 0; guess < 24; guess++) {
    move_count c_moves = moves_if_guess(s, guess);
    if (c_moves < b_moves) {
      b_moves = c_moves;
      b_guess = guess;
    }
  }
  return b_guess;
}

void print_state_code(state s, int indent) {
  perm guess;
  state s2;
  if (indent/2 > 5) {
    printf("%*s/* ... */\n", indent,"");
    return;
  }

  printf("%*s/* 0x%06x, %d possible orders */\n",     indent,"", s, bit_count(s));
  //printf("%*s/* %d worst-case moves left */\n",     indent,"", moves(s));

  if (s == 0) {
    printf("%*s/* What!? */\n",          indent,"");
  } else if ((s & (s-1)) == 0) {
    // printf("%*s/* Done! */\n",          indent,"");
    printf("%*s/* 0x%4x! */\n",          indent,"", expand(ilog2(s)));
  } else {

    guess = best_guess(s);
    printf("%*sswitch guess(0x%4x) {\n", indent,"", expand(guess));

    /* 0 matches */
    s2 = state_if_num(s, guess, 0);
    if (s2) {
      printf("%*s case 0:\n",        indent,"");
      print_state_code(s2, indent+2);
      printf("%*s break:\n",         indent,"");
    }

    /* 1 match */
    s2 = state_if_num(s, guess, 1);
    if (s2) {
      printf("%*s case 1:\n",        indent,"");
      print_state_code(s2, indent+2);
      printf("%*s break:\n",         indent,"");
    }

    /* 2 matches */
    s2 = state_if_num(s, guess, 2);
    if (s2) {
      printf("%*s case 2:\n",        indent,"");
      print_state_code(s2, indent+2);
      printf("%*s break:\n",         indent,"");
    }

    /* all 4 matches (3 can't happen) */
    s2 = state_if_num(s, guess, 4);
    if (s2) {
      printf("%*s default:\n",       indent,"");
      print_state_code(s2, indent+2);
      printf("%*s break:\n",         indent,"");

      printf("%*s}\n",                indent,"");
    }
  }
}

void print_code() {
  state s = BLANK_STATE;
  print_state_code(s, 0);
}

int main() {
  //for (int i = 0; i < 24; i++) {
  //  printf("%2i %4x %2i\n", i, expand(i), unexpand(expand(i)));
  //}
  printf("%0x\n", state_if_num(BLANK_STATE, 1, 0));
  printf("%d\n", moves_if_guess(BLANK_STATE, (perm)0));
  print_code();
}