UVa 517 - Word

Accepted date: 2016-01-24
Run Time: 0.009
Ranking (as of 2016-01-24): 13 out of 544
Language: C++

/*
  UVa 517 - Word

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_517_Word.cpp
*/

#include <algorithm>
#include <cstdio>
using namespace std;

const int nr_chars_max = 15, nr_rules = 8, nr_words_max = 1 << nr_chars_max;

int visited[nr_words_max];
int nr_words, words[nr_words_max];

int word_to_value(int word, int wi, int length)
{
  int value = 0;
  for (int i = 0, b = 1 << (length - 1);
    i < length; i++, b >>= 1, wi = (wi - 1 + length) % length)
    if (word & (1 << wi))
      value += b;
  return value;
}

int get_min_word(int word, int length)
{
  int min_word = 1 << length;
  for (int i = 0; i < length; i++)
    min_word = min(min_word, word_to_value(word, i, length));
  return min_word;
}

void print_word(int word, int length)
{
  for (int i = 0, b = 1 << (length - 1); i < length; i++, b >>= 1)
    putchar((word & b) ? 'b' : 'a');
  putchar('\n');
}

struct rule {
  int c1_, c2_, c3_, c4_;
};

int main()
{
  int length, steps;
  char s[nr_chars_max + 1];
  rule rules[nr_rules];
  while (scanf("%d", &length) != EOF) {
    for (int i = 0, j = 1 << length; i < j; i++)
      visited[i] = -1;
    nr_words = 0;
    scanf("%s", s);
    int word = 0, next_word;
    for (int i = 0, b = 1 << (length - 1); i < length; i++, b >>= 1)
      if (s[i] == 'b')
        word += b;
    word = get_min_word(word, length);
    for (int i = 0; i < nr_rules; i++) {
      scanf("%s", s);
      rules[i].c1_ = (s[0] == 'b') ? 1 : 0;
      rules[i].c2_ = (s[1] == 'b') ? 1 : 0;
      rules[i].c3_ = (s[2] == 'b') ? 1 : 0;
      rules[i].c4_ = (s[3] == 'b') ? 1 : 0;
    }
    scanf("%d", &steps);
    int cycle_start = -1, cycle_length = 0;
    for (int i = 0; i < steps; i++) {
      int next_word = word;
      for (int j = 0; j < nr_rules; j++) {
        const rule& r = rules[j];
        for (int k = 0; k < length; k++) {
          int k1 = (k + 2) % length, k3 = (k - 1 + length) % length;
          if ((word & (1 << k1)) >> k1 == r.c1_ &&
            (word & (1 << k)) >> k == r.c2_ &&
            (word & (1 << k3)) >> k3 == r.c3_) {
            if (r.c4_)
              next_word |= 1 << k;
            else
              next_word &= ~(1 << k);
          }
        }
      }
      word = get_min_word(next_word, length);
      if (visited[word] != -1) {
        cycle_start = visited[word];
        cycle_length = nr_words - cycle_start;
        break;
      }
      else {
        visited[word] = nr_words;
        words[nr_words++] = word;
      }
    }
#ifdef DEBUG
    printf("%d\n", nr_words);
    for (int i = 0; i < nr_words; i++)
      print_word(words[i], length);
#endif
    if (nr_words < steps) {
#ifdef DEBUG
      printf("%d %d\n", cycle_start, cycle_length);
#endif
      word = words[cycle_start + (steps - cycle_start - 1) % cycle_length];
    }
    print_word(word, length);
  }
  return 0;
}