naoya_t@topcoder

しりとり

15:03 |

• 一応プログラムで
• けどlevel 3のグラフ構造は読み切れないのでlevel3のグラフは手書き
• level 1, 2 は適当にやっても勝てるけど、level 3は向こうも勝ちに来るので
• これまでの履歴と、相手が出してきた手から最善手を教えてくれるっぽいプログラムを書いた
• level 3 はなんというかステージ１、ステージ２があって、ステージ１から先に抜けた方が負け、な感じ
  • ステージ1: d,e,f,g,i,j,q,s,w の中での移動
• なのでステージ１の語だけ拾いだして上のプログラムを適用
• （ステージ２に行ったら同じ文字に追い込めば勝てる！）

//...
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<string> vs;
typedef vector<long long> vll;
#define sz(a)  int((a).size())
#define pb  push_back
#define FOR(var,from,to) for(int var=(from);var<=(to);var++)
#define rep(var,n)  for(int var=0;var<(n);var++)
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e)  ((s).find(e)!=(s).end())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define remove_(c,val) (c).erase(remove((c).begin(),(c).end(),(val)),(c).end())
#define lastc(str) (*((str).end()-1))
#define RFOR(var,from,to) for(int var=(to);var>=(from);var--)

//#include "cout.h"

typedef pair<char,char> cc;

int arc[26][26];
long long trial=0LL;

typedef pair<int,int> ii;

#define LIM 5000000LL

int sub(int now, vector<int>& route)
{
  trial++; //if (trial%5000000LL == 0) printf("[%lld]\n", trial);
  if (trial >= LIM) {
    if (trial == LIM) printf("too deep. break.\n");
    return 0;
  }

  int way=0, res=0;
  rep(next,26){
    if (arc[now][next]){
      way++;
      arc[now][next]--;
      res = sub(next, route);
      arc[now][next]++;

      if (res < 0) {
        route.pb(-1);
        route.pb(now); return next;
      }
    }
  }
  if (way==0) {
    route.clear(); route.pb(now);
    return -1;
  }

  route.pb(now);
  return res ? -1 : 0;
}

void dump(int last)
{
  printf("\n%c.. ", 'a'+last);
  rep(c,26) printf(" %c", 'a'+c);
  printf("\n");
  
  rep(r,26){
    printf("%c ->", 'a'+r);
    rep(c,26){
      if (arc[r][c])
        printf(" %d", arc[r][c]);
      else
        printf(" -");
    }
    printf("\n");
  }
  printf("\n");
}

main(int argc, char **argv)
{
  rep(i,26) rep(j,26) arc[i][j]=0;
  int wn=0;

  if (argc != 2) {
    printf("usage: %s <word-list>\n", argv[0]);
    return 0;
  }
  FILE *fp = fopen(argv[1], "r"); if (!fp) return 0;
  char buf[256], first_str[256];
  while (fgets(buf,256,fp) != NULL) {
    //string s; cin >> s;
    int len = strlen(buf);
    while (len>0 && buf[len-1]<' ') buf[--len]=0;
    int b=buf[0]-'a', e=buf[len-1]-'a';
    if (wn == 0) strcpy(first_str, buf);
    arc[b][e]++; wn++;
  }
  fclose(fp);
  
  set<int> candidates;
  int last = 0, b, e;
  
  for (int wi=wn; wi>0; wi-=2) {
    if (wi < wn) {
      candidates.clear();
      rep(i,26) if (arc[last][i]) candidates.insert(i);
      if (candidates.empty()) {
        printf("YOU WIN!!\n"); break;
      }
    }
    printf("[%d] Which word did Google consume? ", wi);
    if (wi == wn) {
      printf("(%s) ", first_str);
    } else {
      printf("%c..[", 'a'+last);
      tr(candidates,it) printf("%c,", 'a'+*it);
      printf("] : "); fflush(NULL);
    }
    fflush(NULL);
    string s; cin >> s;
    switch (sz(s)) {
      case 0:
        b=last;
        rep(i,26) if (arc[last][i]) { e=i; break; }
        break;
      case 1:
        b=last; e=s[0]-'a'; break;
      case 2: default:
        b=s[0]-'a', e=lastc(s)-'a'; break;
    }
    arc[b][e]--;
    
    dump(last=e);

    vector<int> route; trial = 0LL;
    int res = sub(last, route);
    if (res) {
      if (sz(route)>0) route.pop_back();
      reverse(all(route));
      tr(route,it) printf(" -> %c", 'a' + *it);
    }
    
    candidates.clear();
    rep(i,26) if (arc[last][i]) candidates.insert(i);
    if (candidates.empty()) {
      printf("GOOGLE WINS!!\n"); break;
    }
    printf("\n[%d] Your choice (input last char): %c..[", wi-1, 'a'+last);
    tr(candidates,it) printf("%c,", 'a'+*it);
    printf("] : "); fflush(NULL);
    cin >> s;
    b = last, e = s[0]-'a'; arc[b][e]--;

    dump(last=e);
  }
}