src/cwc.cc

   1 /**
   2  * cwc - a crossword compiler.
   3  *
   4  * Copyright (C) 1999, 2000, 2001, 2002 Lars Christensen, 2008 Mark Longair
   5  *
   6  * This program is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU General Public License as
   8  * published by the Free Software Foundation; either version 2 of the
   9  * License, or (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful, but
  12  * WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software
  18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
  19  * 02111-1307, USA.
  20  **/
  21
  22 #include <unistd.h>
  23 #include <fcntl.h>
  24 #include <stdio.h>
  25 #include <locale.h>
  26 #include <iostream>
  27 #include <sys/time.h>
  28
  29 #include <fstream>
  30 #include <string>
  31 #include <sstream>
  32 #include <math.h>
  33 #include <stdlib.h>
  34
  35 #include <set>
  36 #include <vector>
  37 #include <list>
  38
  39 #include "timer.hh"
  40 #include "symbol.hh"
  41 #include "dict.hh"
  42 #include "letterdict.hh"
  43 #include "grid.hh"
  44
  45 #include "cwc.hh"
  46
  47 using std::ofstream;
  48 using std::ostringstream;
  49
  50 //////////////////////////////////////////////////////////////////////
  51 // class walker
  52
  53 walker::walker(grid &thegrid) : current(0), g(thegrid) {
  54     limit = thegrid.getempty();
  55     inited = false;
  56 }
  57
  58 cell &walker::currentcell() {
  59     if (!inited) throw error("walker not inited");
  60     return g.cellno(current);
  61 }
  62
  63 void walker::backto(int c) {
  64     while (current != c)
  65         backward();
  66 }
  67
  68 bool walker::current_oneof(int no[], int n) {
  69     for (int i=0;i<n;i++) {
  70         if (no[i] == current)
  71             return true;
  72     }
  73     return false;
  74 }
  75
  76 void walker::backto_oneof(int no[], int n) {
  77     while (!current_oneof(no, n))
  78         backward();
  79 }
  80
  81 void walker::backto_oneof(backtracker &bt) {
  82     backward(false); // dont save current
  83     while (!bt.stophere(current))
  84         backward(true); // save all we skip
  85 }
  86
  87 void walker::forward() {
  88     if (inited) {
  89         cellno.push_back(current);
  90         do step_forward(); while (!g.cellno(current).isempty());
  91     } else {
  92         init();
  93         inited = true;
  94     }
  95 }
  96
  97 void walker::backward(bool savepreferred) {
  98     if (!g.cellno(current).isoutside())
  99         g.cellno(current).clear(savepreferred);
 100     current = cellno.back();
 101     cellno.pop_back();
 102 }
 103
 104 bool walker::moresteps() {
 105     return (cellno.size() + 1) < unsigned(limit);
 106 }
 107
 108 void walker::findnext() {
 109     int ncells = g.numcells();
 110     for (int i = 0; i < ncells; i++)
 111         if (g.cellno(i).isempty()) {
 112             current = i;
 113             return;
 114         }
 115     throw error("No empty cells");
 116 }
 117
 118 void walker::init() {
 119     findnext();
 120 }
 121
 122 //////////////////////////////////////////////////////////////////////
 123 // class prefix_walker
 124
 125 void prefix_walker::step_forward() {
 126     current++; // not correct now
 127 }
 128
 129 //////////////////////////////////////////////////////////////////////
 130 // class flood_walker
 131
 132 flood_walker::flood_walker(grid &g) : walker(g) {
 133 }
 134
 135 void flood_walker::step_forward() {
 136     vector<int>::iterator i;
 137     for (i = cellno.begin(); i != cellno.end(); i++) {
 138         int cno = *i;
 139
 140         int nwords = g.cellno(cno).numwords();
 141         for (int w = 0; w < nwords; w++) {
 142             cell &thecell = g.cellno(cno);
 143             wordblock &wb = thecell.getwordblock(w);
 144             int pos = thecell.getpos(w);
 145             int len = wb.length();
 146
 147             if (pos > 0) {
 148                 int cellbefore = wb.getcellno(pos-1);
 149                 if (g.cellno(cellbefore).isempty()) {
 150                     current = cellbefore;
 151                     return;
 152                 }
 153             }
 154             if (pos < len-1) {
 155                 int cellafter = wb.getcellno(pos + 1);
 156                 if (g.cellno(cellafter).isempty()) {
 157                     current = cellafter;
 158                     return;
 159                 }
 160             }
 161         }
 162     }
 163     // at this point: no adjacent cells found
 164     findnext();
 165 }
 166
 167 //////////////////////////////////////////////////////////////////////
 168 // class backtracker
 169
 170 backtracker::backtracker(grid &thegrid) : g(thegrid) {
 171 }
 172
 173 //////////////////////////////////////////////////////////////////////
 174 // class naive_backtracker
 175
 176 // The naive backtracker simply backs up to the previously
 177 // filled cell.
 178
 179 void naive_backtracker::backtrack(walker &w) {
 180     w.backward(false);
 181 }
 182
 183 //////////////////////////////////////////////////////////////////////
 184 // class smart_backtracker
 185 //
 186 // the smart backtracker steps back to the previously filled cell
 187 // that is within reach from the current cell
 188
 189 void smart_backtracker::backtrack(walker &w) {
 190     // search up
 191     int cpos = w.stepno();
 192
 193     // initially, forget all bt points that are dependend on cells behind
 194     // current point.
 195     list<cpair>::iterator next;
 196     for (list<cpair>::iterator i = bt_points.begin();
 197          i != bt_points.end();
 198          i = next) {
 199         next = i; next++;
 200         if ((*i).first <= cpos) {
 201             if (setup.debuginfo) cout << "removing " << (*i).second << "(from " << (*i).first << ")" << endl;
 202             bt_points.erase(i);
 203         }
 204     }
 205
 206     int cno = w.getcurrent();
 207
 208     cell &c = g.cellno(cno);
 209     int nwords = c.numwords();
 210     for (int wno = 0; wno < nwords; wno++) {
 211         wordblock &wb = c.getwordblock(wno);
 212         int len = wb.length();
 213
 214         int pos = c.getpos(wno);
 215         for (int p = 0; p < len; p++) {
 216             if ((p!=pos)&&(wb.getcell(p).isfilled()))
 217                 bt_points.push_back(cpair(cpos, wb.getcellno(p)));
 218         }
 219
 220     }
 221
 222     if (setup.debuginfo) {
 223         cout << "BTSET:" << endl;
 224         for (list<cpair>::iterator i = bt_points.begin(); i != bt_points.end(); i++)
 225             cout << " (" << (*i).first << ',' << (*i).second << ")";
 226         cout << endl;
 227     }
 228
 229     w.backto_oneof(*this);
 230 }
 231
 232 bool smart_backtracker::stophere(int p) {
 233     for (list<cpair>::iterator i = bt_points.begin();
 234          i != bt_points.end();
 235          i++) {
 236         if ((*i).second == p) {
 237             bt_points.erase(i); // dont stop here again
 238             return true;
 239         }
 240     }
 241     return false;
 242 }
 243
 244 //////////////////////////////////////////////////////////////////////
 245 // compiler
 246 //
 247 // Cross word compiler logic
 248
 249 compiler::compiler(grid &thegrid, walker &thewalker,
 250                    backtracker &thebacktracker, dict &thedict)
 251     : g(thegrid), w(thewalker), bt(thebacktracker), d(thedict) {
 252     g.verbose = verbose = false;
 253     findall = false;
 254 }
 255
 256 #define success true
 257 #define failure false
 258
 259 // upon failure, walker is backed up to some cell
 260 // the reclevel trying to compute this cell catches it
 261 // and others will return.
 262
 263 timer dtimer;
 264
 265 bool compiler::compile_rest(double rejected) {
 266     int c = w.getcurrent();
 267     if (verbose)
 268         cout << "attempting to find solution for " << c << endl;
 269     symbolset ss = g(c).findpossible(d);
 270     int npossible = numones(ss);
 271     rejected += (numalpha-double(npossible)) * pow(numalpha, numcells - w.stepno());
 272     if (verbose)
 273         dumpset(ss);
 274
 275     symbolset bit;
 276     // use preferred if any
 277     if (g(c).haspreferred()) {
 278         symbol s = g(c).getpreferred();
 279         symbolset ss2 = s.getsymbolset();
 280         if (ss2 & ss) {
 281             bit = ss2;
 282             ss &= ~bit; // remove bit from set
 283         }
 284         else
 285             bit = pickbit(ss);
 286     } else
 287         bit = pickbit(ss);
 288     for (; bit; bit=pickbit(ss)) {
 289         symbol s = symbol::symbolbit(bit);
 290         g(c).setsymbol(s);
 291         if (setup.showallsteps) {
 292             g.dump_simple(cout);
 293         } else if ((showsteps && dtimer.getmsecs() > 500)) {
 294             g.dump_simple(cout);
 295             dtimer.reset();
 296         }
 297         if (w.moresteps()) {
 298             w.forward();
 299             if (compile_rest(rejected) == success) return success;
 300             if (w.getcurrent() != c) return failure; // catch if ==
 301             // cout << "continue at " << c << endl;
 302             rejected += pow(numalpha, numcells - w.stepno());
 303         } else {
 304             this->rejected = rejected;
 305             return success;
 306         }
 307         g(c).setsymbol(symbol::empty);
 308     }
 309     if (w.stepno() > 1) {
 310         bt.backtrack(w);
 311         int cur = w.getcurrent();
 312         if (verbose)
 313             cout << "return to " << cur << " from " << c << endl;
 314     }
 315     return failure;
 316 }
 317
 318 void compiler::compile() {
 319     dtimer.reset(); dtimer.start();
 320     w.forward();
 321     numcells = g.numopen();
 322     numalpha = symbol::numalpha();
 323     compile_rest();
 324 }
 325
 326 //////////////////////////////////////////////////////////////////////
 327 // main
 328
 329 void dumpset(symbolset ss) {
 330     int i,n;
 331     cout << '{';
 332     for (i=1, n = 0; i; i<<=1, n++) {
 333         if (ss&i)
 334             cout << symbol::alphabet[n];
 335     }
 336     cout << '}' << endl;
 337 }
 338
 339 void dumpsymbollist(symbol *s, int n) {
 340     for (int i=0;i<n;i++) {
 341         if (s[i] == symbol::empty)
 342             cout << '-';
 343         else
 344             cout << s[i];
 345     }
 346     cout << endl;
 347 }
 348
 349 void trivial_random_init() {
 350     struct timeval tv;
 351     gettimeofday(&tv, 0);
 352     srand(tv.tv_usec);
 353 }
 354
 355 void random_init(setup_s &s) {
 356     unsigned int q;
 357     if (!s.setseed) {
 358         int fd = open("/dev/random", O_RDONLY);
 359         if (fd == -1) {
 360             trivial_random_init();
 361             return;
 362         }
 363         if (read(fd, &q, 4) == -1)
 364             perror("read");
 365         close(fd);
 366     } else {
 367         q = s.seed;
 368     }
 369     cout << "random seed: " << q << endl;
 370     srand(q);
 371 }
 372
 373 setup_s setup = {
 374     setup.ascii_format,
 375     setup.floodwalker,
 376     setup.letterdict,
 377     false,
 378     false,
 379     false,
 380     DEFAULT_DICT_FILE,
 381     "",
 382     "",
 383     setup.noformat,
 384     false,
 385     false,
 386     0,
 387     false,
 388 };
 389
 390 char usage[] =
 391 "Usage: cwc [options]\n"
 392 "\n"
 393 "options:\n"
 394 "   -d <filename>     use another dictionary file (default " DEFAULT_DICT_FILE ")\n"
 395 "   -p <filename>     read grid pattern from file\n"
 396 "   -w <walkertype>   Walking heuristics: prefix or flood\n"
 397 "   -f <format>       output format, one of `simple' or `ascii'\n"
 398 "   -i <indextype>    Choose dictionary index style. `btree' or `letter'\n"
 399 "   -x <svgfilename>  Output an SVG version of the grid to <svgfilename>\n"
 400 "   -r seed           Set the random seed\n"
 401 "   -v                Be verbose - prints algorithmic info\n"
 402 "   -s                Print the grid filling regularly during compilation\n"
 403 "   -S                Print the grid filling each step\n"
 404 "   -b                Benchmark dictionaries\n"
 405 "   -? -h             Display this help screen\n"
 406 ;
 407
 408 int parseparameters(int argc, char *argv[]) {
 409     int c;
 410     while (c=getopt(argc, argv, "d:p:vf:hsSw:i:x:br:g:?"), c != -1) {
 411         switch (c) {
 412         case 'g':
 413             setup.gridfile = optarg;
 414             setup.gridformat = setup.generalgrid;
 415             break;
 416         case 'b': setup.benchdict = true; break;
 417         case 'd': setup.dictfile = optarg; break;
 418         case 'p':
 419             setup.gridfile = optarg;
 420             setup.gridformat = setup.squaregrid;
 421             break;
 422         case 'v': setup.verbose = true; break;
 423         case 'r': setup.setseed = true; setup.seed = atoi(optarg); break;
 424         case 'f': {
 425             string s(optarg);
 426             if (s=="simple")
 427                 setup.output_format = setup.simple_format;
 428             else if (s == "ascii")
 429                 setup.output_format = setup.ascii_format;
 430             else {
 431                 puts("Invalid format specifier");
 432                 return -1;
 433             }
 434         }
 435             break;
 436         case 'w': {
 437             string s(optarg);
 438             if (s=="prefix")
 439                 setup.walkertype = setup.prefixwalker;
 440             else if (s=="flood")
 441                 setup.walkertype = setup.floodwalker;
 442             else {
 443                 puts("Invalid walker specifier");
 444                 return -1;
 445             }
 446         }
 447             break;
 448         case 'i': {
 449             string s(optarg);
 450             if (s=="btree")
 451                 setup.dictstyle = setup.btreedict;
 452             else if (s=="letter")
 453                 setup.dictstyle = setup.letterdict;
 454             else {
 455                 puts("Invalid dictionary index style");
 456                 return -1;
 457             }
 458         }
 459             break;
 460         case 'x': {
 461             setup.svgfile = optarg;
 462         }
 463             break;
 464         case 's': setup.showsteps = true; break;
 465         case 'S': setup.showallsteps = true; break;
 466         case '?':
 467         case 'h': printf(usage); return -1;
 468         }
 469     }
 470     return 0;
 471 }
 472
 473 void draw_to_svg(ostream &os, grid &g, answers * an) { // FIXME: probably should be const grid &
 474
 475     // We only deal with millimeters here:
 476     int page_width = 210.0;
 477     int page_height = 297.0;
 478
 479     os << "<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\"?>" << endl;
 480     os << "<svg" << endl;
 481     os << "   xmlns:svg=\"http://www.w3.org/2000/svg\"" << endl;
 482     os << "   xmlns=\"http://www.w3.org/2000/svg\"" << endl;
 483     os << "   xmlns:xlink=\"http://www.w3.org/1999/xlink\"" << endl;
 484     os << "   version=\"1.0\"" << endl;
 485     os << "   width=\"" << page_width << "mm\"" << endl;
 486     os << "   height=\"" << page_height << "mm\"" << endl;
 487     os << "   id=\"svg2\">" << endl;
 488     os << "  <defs" << endl;
 489     os << "     id=\"defs4\" />" << endl;
 490
 491     float empty_cell_side = 6.2;
 492     float answer_cell_side = empty_cell_side / 2;
 493     float margin_to_clues = empty_cell_side / 2;
 494
 495     float top_margin = 7.5;
 496
 497     float fontSizeTitle = (g.w * empty_cell_side) / 8;
 498     float titleHeight = 1.2 * fontSizeTitle;
 499
 500     float fontSizeRubric = fontSizeTitle / 4;
 501     float rubricHeight = fontSizeTitle;
 502
 503     float clues_top_left_x = 7.5;
 504     float clues_top_left_y = top_margin + titleHeight + rubricHeight;
 505
 506     // Output the title:
 507
 508     os << "        <text" << endl;
 509     os << "       x=\"" << clues_top_left_x << "\"" << endl;
 510     os << "       y=\"" << top_margin << "\"" << endl;
 511     os << "       style=\"font-size:40px;font-style:normal;font-weight:bold;fill:#000000;fill-opacity:1;stroke:none;stroke-width:1px;stroke-linecap:butt;stroke-linejoin:miter;stroke-opacity:1;font-family:Bitstream Charter\"" << endl;
 512     os << "       id=\"title\"" << endl;
 513     os << "       xml:space=\"preserve\"><tspan" << endl;
 514     os << "         x=\"" << clues_top_left_x << "mm\"" << endl;
 515     os << "         y=\"" << (top_margin + fontSizeTitle)  << "mm\"" << endl;
 516     os << "         style=\"font-size:" << fontSizeTitle << "mm\"" << endl;
 517     os << "         id=\"title-inner\">Crossword Title</tspan></text>" << endl;
 518
 519     // Output some example rubric:
 520
 521     os << "    <flowRoot" << endl;
 522     os << "       id=\"flowRootRubric\"" << endl;
 523     os << "       xml:space=\"preserve\"><flowRegion" << endl;
 524     os << "         id=\"flowRegionRubric\"><rect" << endl;
 525     os << "           width=\"" << (empty_cell_side * g.w) << "mm\"" << endl;
 526     os << "           height=\"" << (clues_top_left_y - fontSizeTitle) << "mm\"" << endl;
 527     os << "           x=\"" << clues_top_left_x << "mm\"" << endl;
 528     os << "           y=\"" << top_margin + titleHeight << "mm\"" << endl;
 529     os << "           id=\"flowRegionRect\" /></flowRegion><flowPara" << endl;
 530     os << "         style=\"font-style:italic;font-family:Bitstream Charter;font-size:" << fontSizeRubric << "mm\"" << endl;
 531     os << "         id=\"flowParaRubric\">Example rubric here...</flowPara></flowRoot>" << endl;
 532
 533     float clue_column_width = answer_cell_side * g.w;
 534
 535     os << "  <g id=\"empty-grid\">" << endl;
 536     g.dump_svg(os, an, empty_cell_side, false, true, clues_top_left_x, clues_top_left_y);
 537     os << "  </g>" << endl;
 538
 539     float answers_top_left_x = clues_top_left_x + g.w * empty_cell_side + margin_to_clues + clue_column_width + margin_to_clues;
 540
 541     float clue_column_height = g.h * empty_cell_side * 2 + top_margin;
 542
 543     os << "  <g id=\"answers-grid\">" << endl;
 544     g.dump_svg(os, an, answer_cell_side, true, false, answers_top_left_x, top_margin + clue_column_height - (answer_cell_side * g.h));
 545     os << "  </g>" << endl;
 546
 547     os << "  <g id=\"clue-list\">" << endl;
 548
 549     // Now position two rectangles for the clues to flow into:
 550
 551     ostringstream clue_rectangle_style;
 552     clue_rectangle_style << "fill:#ffffff;fill-opacity:1;stroke:#000000;stroke-width:";
 553     clue_rectangle_style << (0.15 * (empty_cell_side / 6.5));
 554     clue_rectangle_style << ";stroke-miterlimit:4;stroke-dasharray:1.14168612, 3.42505837;stroke-dashoffset:0;stroke-opacity:1";
 555
 556     float rect_x = clues_top_left_x + g.w * empty_cell_side + margin_to_clues;
 557     float rect_y = top_margin;
 558
 559     os << "  <rect" << endl;
 560     os << "     style=\"" << clue_rectangle_style.str() << "\"" << endl;
 561     os << "     id=\"clue-column-0\"" << endl;
 562     os << "     width=\"" << clue_column_width << "mm\"" << endl;
 563     os << "     height=\"" << clue_column_height << "mm\"" << endl;
 564     os << "     x=\"" << rect_x << "mm\"" << endl;
 565     os << "     y=\"" << rect_y << "mm\"/>" << endl;
 566
 567     rect_x += clue_column_width + margin_to_clues;
 568     clue_column_height -= margin_to_clues + answer_cell_side * g.h;
 569
 570     os << "  <rect" << endl;
 571     os << "     style=\"" << clue_rectangle_style.str() << "\"" << endl;
 572     os << "     id=\"clue-column-1\"" << endl;
 573     os << "     width=\"" << clue_column_width << "mm\"" << endl;
 574     os << "     height=\"" << clue_column_height << "mm\"" << endl;
 575     os << "     x=\"" << rect_x << "mm\"" << endl;
 576     os << "     y=\"" << rect_y << "mm\"/>" << endl;
 577
 578     os << "    <flowRoot xml:space=\"preserve\" id=\"clues-flow-root\">";
 579
 580     os << "<flowRegion id=\"clues-flow-region\">";
 581
 582     os << "<use x=\"0\" y=\"0\" xlink:href=\"#clue-column-0\" id=\"use-clue-column-0\" width=\"210mm\" height=\"210mm\"/>";
 583     os << "<use x=\"0\" y=\"0\" xlink:href=\"#clue-column-1\" id=\"use-clue-column-1\" width=\"210mm\" height=\"210mm\"/>";
 584
 585     os << "</flowRegion>";
 586
 587     ostringstream clue_font_style_string;
 588     clue_font_style_string << "font-size:";
 589     clue_font_style_string << ((2 * fontSizeTitle) / 5);
 590     clue_font_style_string << "mm;font-family:Bitstream Charter";
 591
 592     an->dump_to_svg(os,clue_font_style_string.str());
 593
 594     os << "</flowRoot>";
 595
 596     os << "  </g>" << endl;
 597
 598     os << "</svg>" << endl;
 599 }
 600
 601 int main(int argc, char *argv[]) {
 602     if (parseparameters(argc, argv) == -1) exit(EXIT_FAILURE);
 603     random_init(setup);
 604     symbol::buildindex();
 605
 606     if (setlocale(LC_CTYPE, "") == 0)
 607         cout << "Failed to set locale" << endl;
 608
 609     try {
 610
 611         if (setup.benchdict) {
 612             dodictbench();
 613             exit(EXIT_SUCCESS);
 614         }
 615
 616         dict *d = 0;
 617         if (setup.dictstyle==setup.btreedict) {
 618             cout << "Using binary tree index" << endl;
 619             d = new btree_dict();
 620         } else if (setup.dictstyle==setup.letterdict) {
 621             cout << "Using letter index" << endl;
 622             d = new letterdict();
 623         }
 624         d->load(setup.dictfile);
 625
 626         grid g;
 627         if (setup.gridformat == setup.generalgrid)
 628             g.load(setup.gridfile);
 629         else if (setup.gridformat == setup.squaregrid)
 630             g.load_template(setup.gridfile);
 631         // g.dump_ggrid(cout);
 632         int nopen = g.numopen();
 633         double space = pow(symbol::numalpha(), nopen);
 634         cout << nopen << " cells to be filled. " << space << " possible fillings." << endl;
 635         walker *w;
 636         if (setup.walkertype==setup.prefixwalker) {
 637             w = new prefix_walker(g);
 638             puts("Using prefix walking heuristics");
 639         } else if (setup.walkertype==setup.floodwalker) {
 640             w = new flood_walker(g);
 641             puts("Using flood walking heuristics");
 642         } else {
 643             puts("Internal error");
 644             exit(EXIT_FAILURE);
 645         }
 646
 647         cout << "Degree of interlock: " << g.interlockdegree()*100 << "%" << endl;
 648         double depdeg1 = g.dependencydegree(1);
 649         double depdeg2 = g.dependencydegree(2);
 650         cout << "Degree of dependency: " << depdeg1 << '(' << (depdeg1*100.0/nopen) << "%)" << endl;
 651         cout << "Degree of 2nd level dependency: " << depdeg2 << '(' << (depdeg2*100.0/nopen) << "%)" << endl;
 652
 653         smart_backtracker bt(g);
 654
 655         compiler c(g, *w, bt, *d);
 656         c.verbose = setup.verbose;
 657         c.showsteps = setup.showsteps;
 658         timer t; t.start();
 659         c.compile();
 660         t.stop();
 661
 662         if (g.w == 0) {
 663             g.dump(cout,setup.output_format,0);
 664             if( setup.svgfile.length() > 0 ) {
 665                 cout << "Warning: can't currently generate SVG files ";
 666                 cout << "for non-grid crosswords, so ";
 667                 cout << "ignoring '-s " << setup.svgfile << "'" << endl;
 668             }
 669         } else {
 670             answers an = g.getanswers();
 671             g.dump(cout, setup.output_format, &an);
 672             cout << endl;
 673             an.dump(cout);
 674
 675             if( setup.svgfile.length() > 0 ) {
 676                 ofstream ofs(setup.svgfile.c_str());
 677                 draw_to_svg(ofs, g, &an);
 678                 ofs.close();
 679                 cout << "Wrote SVG to: '" << setup.svgfile << "'" << endl;
 680             }
 681         }
 682         cout << "Attempt average: " << g.attemptaverage() << endl;
 683         cout << "Compilation time: " << t.getmsecs() << " msecs" << endl;
 684
 685         double searched = c.getrejected();
 686         cout << searched << " solutions searched. " << (searched*100/space) << "% of search space." << endl;
 687     } catch (error e) {
 688         cout << e.what() << endl;
 689         exit(EXIT_FAILURE);
 690     }
 691 }
 692
 693 void dodictbench() {
 694     int t1, t2;
 695
 696     btree_dict bd;
 697     bd.load(DEFAULT_DICT_FILE);
 698     t1 = dictbench(bd);
 699
 700     letterdict d2;
 701     d2.load(DEFAULT_DICT_FILE);
 702     t2 = dictbench(d2);
 703
 704     cout << "btree=" << t1 << ", letter=" << t2 << endl;
 705 }
 706
 707 int dictbench(dict &d) {
 708     symbol s[MAXWORDLEN];
 709     int o[MAXWORDLEN];
 710
 711     timer t; t.start();
 712
 713     for (int r=0; r<100; r++) {
 714         for (int i=0;i<MAXWORDLEN;i++)
 715             o[i] = i;
 716
 717         for (int len = 1; len < MAXWORDLEN; len++) {
 718             for (int i=0;i<len;i++) {
 719                 s[i] = symbol::empty;
 720                 // shuffle
 721                 int q = rand()%len;
 722                 int t = o[q]; o[q] = o[i]; o[i] = t;
 723             }
 724             int n = 0;
 725             int pos = o[n++];
 726             while (n <= len) {
 727                 symbolset ss = d.findpossible(s, len, pos);
 728                 if (!ss) break;
 729                 s[pos] = symbol::symbolbit(pickbit(ss));
 730                 pos = o[n++];
 731             }
 732         }
 733     }
 734
 735     t.stop();
 736
 737     return t.getticks();
 738 }