chiark - git - mdw - wordchain/blob - chain.cc

   1 #include <cassert>
   2 #include <cstdarg>
   3 #include <cstdio>
   4 #include <cstdlib>
   5 #include <cstring>
   6
   7 #include <string>
   8 #include <utility>
   9
  10 #define CXX_MAP 1
  11 #define CXX_UOMAP 2
  12
  13 struct Node;
  14 typedef std::pair<const std::string, Node> WordNode;
  15 struct Node {
  16   WordNode *down, *right, *up;
  17   int len;
  18 };
  19
  20 #if !TREE
  21 #  error "`TREE' not defined or bungled constant setting"
  22 #elif TREE == CXX_MAP
  23 #  include <map>
  24    typedef std::map<std::string, Node> Map;
  25 #elif TREE == CXX_UOMAP
  26 #  include <unordered_map>
  27    typedef std::unordered_map<std::string, Node> Map;
  28 #else
  29 #  error "unknown `TREE' value"
  30 #endif
  31
  32 #define WORDMAX 64
  33
  34 static void bail(const char *msg, ...)
  35 {
  36   va_list ap;
  37   long pos;
  38
  39   va_start(ap, msg); std::vfprintf(stderr, msg, ap); va_end(ap);
  40   pos = std::ftell(stdin);
  41   if (pos >= 0) std::fprintf(stderr, " (input pos = %ld)", pos);
  42   std::fputc('\n', stderr);
  43   std::exit(2);
  44 }
  45
  46 static void print_chain(WordNode *wnode)
  47 {
  48   const std::string *word = &wnode->first;
  49   Node *node = &wnode->second;
  50
  51   if (!node->right) {
  52     std::fputs(word->c_str(), stdout);
  53     if (node->down)
  54       { std::putchar(' '); print_chain(node->down); }
  55   } else {
  56     std::fputs("{ ", stdout);
  57     for (;;) {
  58       std::fputs(word->c_str(), stdout);
  59       if (node->down)
  60         { std::putchar(' '); print_chain(node->down); }
  61       wnode = node->right; if (!wnode) break;
  62       std::fputs(" | ", stdout);
  63       word = &wnode->first; node = &wnode->second;
  64     }
  65     std::fputs(" }", stdout);
  66   }
  67 }
  68
  69 int main(void)
  70 {
  71   Map map{};
  72   char buf[WORDMAX]; size_t n;
  73
  74   for (;;) {
  75     if (!std::fgets(buf, WORDMAX, stdin)) break;
  76     n = std::strlen(buf); assert(n);
  77     if (buf[n - 1] == '\n') buf[--n] = 0;
  78     else if (n == WORDMAX - 1) bail("word too long");
  79     else {
  80       int ch;
  81       if (ch = std::getchar(), ch != EOF)
  82         bail("short read, found `%c'", ch);
  83     }
  84
  85     auto r = map.insert(WordNode(std::string(buf, n), Node{}));
  86     if (!r.second) printf(";; duplicate `%s'\n", buf);
  87     else {
  88       Node *node = &r.first->second;
  89       node->len = 1; node->up = node->down = node->right = 0;
  90     }
  91   }
  92
  93   WordNode *winners, **winners_tail = &winners;
  94   int max = 0;
  95
  96   for (auto p = map.begin(); p != map.end(); ++p) {
  97     /* std::fprintf(stderr, ";; ponder `%.*s'\n",
  98                     p->first.length(), p->first.c_str()); */
  99     WordNode *wnode = &*p, *pwnode;
 100     const std::string *word = &wnode->first;
 101     Node *node = &wnode->second;
 102     if (word->length() <= 1)
 103       continue;
 104     else {
 105       /* std::fprintf(stderr, ";; search `%.*s'\n",
 106                       w->first.length(), w->first.c_str()); */
 107       std::string prefix{*word, 0, word->length() - 1};
 108       auto p = map.find(prefix); if (p == map.end()) continue;
 109       pwnode = &*p;
 110     }
 111     int nlen = node->len;
 112     node->up = pwnode;
 113     for (;;) {
 114       if (!pwnode) {
 115         if (nlen >= max) {
 116           if (nlen > max)
 117             { max = nlen; *winners_tail = 0; winners_tail = &winners; }
 118           *winners_tail = wnode; winners_tail = &node->right;
 119         }
 120         break;
 121       }
 122       Node *parent = &pwnode->second;
 123       nlen++; int plen = parent->len;
 124       if (plen > nlen)
 125         break;
 126       else if (plen == nlen) {
 127         node->right = parent->down; parent->down = wnode;
 128         break;
 129       } else {
 130         parent->down = wnode; node->right = 0;
 131         parent->len = nlen;
 132         wnode = pwnode; node = &wnode->second; pwnode = node->up;
 133       }
 134     }
 135   }
 136
 137   *winners_tail = 0;
 138   for (WordNode *next, *wnode = winners; wnode; wnode = next) {
 139     next = wnode->second.right; wnode->second.right = 0;
 140     print_chain(wnode); std::putchar('\n');
 141   }
 142   return (0);
 143 }