/* * Quackle -- Crossword game artificial intelligence and analysis tool * Copyright (C) 2005-2019 Jason Katz-Brown, John O'Laughlin, and John Fultz. * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 3 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program. If not, see . */ #include #include #include #include "datamanager.h" #include "evaluator.h" #include "generator.h" #include "gaddag.h" #include "board.h" #include "boardparameters.h" #include "gameparameters.h" #include "lexiconparameters.h" // #define DEBUG_GENERATOR using namespace std; using namespace Quackle; Generator::Generator() { } Generator::Generator(const GamePosition &position) : m_position(position) { } Generator::~Generator() { } void Generator::kibitz(int kibitzLength, int flags) { // don't just record best move, unless kibitz length is one setrecordall(kibitzLength > 1); // perform actual kibitz findstaticbest(!(flags & CannotExchange)); m_kibitzList.clear(); if (kibitzLength <= 1) { m_kibitzList.push_back(best); return; } filterOutDuplicatePlays(); MoveList::sort(m_moveList, MoveList::Equity); int i = 0; MoveList::iterator end(m_moveList.end()); for (MoveList::iterator it = m_moveList.begin(); it != end; ++it, ++i) { if (i >= kibitzLength) break; m_kibitzList.push_back(*it); } } void Generator::filterOutDuplicatePlays() { map oneTilePlayMap; for (MoveList::iterator it = m_moveList.begin(); it != m_moveList.end();) { LetterString usedTiles = (*it).usedTiles(); if (usedTiles.size() == 1) { const LetterString &tiles = (*it).tiles(); int actualTileIndex = 0; for (LetterString::const_iterator letterIt = tiles.begin(); letterIt != tiles.end(); ++letterIt, ++actualTileIndex) if ((*letterIt) != QUACKLE_PLAYED_THRU_MARK) break; const int row = (*it).startrow + ((*it).horizontal? 0 : actualTileIndex); const int column = (*it).startcol + ((*it).horizontal? actualTileIndex : 0); int key = row + QUACKLE_MAXIMUM_BOARD_SIZE * column + (QUACKLE_MAXIMUM_BOARD_SIZE * QUACKLE_MAXIMUM_BOARD_SIZE) * tiles[actualTileIndex]; if (oneTilePlayMap.find(key) == oneTilePlayMap.end()) { oneTilePlayMap[key] = true; ++it; } else { it = m_moveList.erase(it); } } else { ++it; } } } void Generator::allCrosses() { vector vrows, vcols, hrows, hcols; for (int i = 0; i < board().height(); i++) { for (int j = 0; j < board().width(); j++) { vrows.push_back(i); vcols.push_back(j); hrows.push_back(i); hcols.push_back(j); } } // check the appropriate crosses for (unsigned int i = 0; i < vrows.size(); i++) { int row = vrows[i]; int col = vcols[i]; if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { board().setVCross(row, col, LetterBitset()); } else { LetterString pre; if (row > 0) { for (int i = row - 1; i >= 0; i--) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { i = -1; } else { LetterString newpre; newpre += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(i, col)); newpre += pre; pre = newpre; } } } LetterString suf; if (row < board().height() - 1) { for (int i = row + 1; i < board().height(); i++) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { i = board().height(); } else { suf += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(i, col)); } } } #ifdef DEBUG_GENERATOR UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << " / " << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; #endif if (pre.empty() && suf.empty()) { board().setVCross(row, col, LetterBitset().set()); } else { board().setVCross(row, col, fitbetween(pre, suf)); } #ifdef DEBUG_GENERATOR UVcout << "board().vcross[" << row << "][" << col << "] = " << cross2string(board().vcross(row, col)) << endl; #endif } } for (unsigned int i = 0; i < hrows.size(); i++) { int row = hrows[i]; int col = hcols[i]; if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { board().setHCross(row, col, LetterBitset()); } else { LetterString pre; if (col > 0) { for (int i = col - 1; i >= 0; i--) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { i = -1; } else { LetterString newpre; newpre += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(row, i)); newpre += pre; pre = newpre; } } } LetterString suf; if (col < board().width() - 1) { for (int i = col + 1; i < board().width(); i++) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { i = board().width(); } else { suf += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(row, i)); } } } if (pre.empty() && suf.empty()) { board().setHCross(row, col, LetterBitset().set()); } else { board().setHCross(row, col, fitbetween(pre, suf)); } #ifdef DEBUG_GENERATOR UVcout << "board().hcross[" << row << "][" << col << "] = " << cross2string(board().hcross(row, col)) << endl; #endif } } } void Generator::makeMove(const Move &move, bool regenerateCrosses) { if (move.action != Move::Place) return; if (!regenerateCrosses) { board().makeMove(move); return; } // mark which squares need their crosses checked vector hrows; vector hcols; vector vrows; vector vcols; hrows.reserve(2 * QUACKLE_MAXIMUM_BOARD_SIZE); hcols.reserve(2 * QUACKLE_MAXIMUM_BOARD_SIZE); vrows.reserve(2 * QUACKLE_MAXIMUM_BOARD_SIZE); vcols.reserve(2 * QUACKLE_MAXIMUM_BOARD_SIZE); if (move.horizontal) { int row = move.startrow; int endcol = move.startcol + move.tiles().length() - 1; if (move.startcol > 0) { hrows.push_back(row); hcols.push_back(move.startcol - 1); } if (endcol < board().width() - 1) { hrows.push_back(row); hcols.push_back(endcol + 1); } for (int col = move.startcol; col <= endcol; col++) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { int upempty = -1; for (int hookrow = row - 1; hookrow >= 0; hookrow--) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(hookrow, col))) { upempty = hookrow; hookrow = -1; } } if (upempty >= 0) { vrows.push_back(upempty); vcols.push_back(col); } int downempty = board().height(); for (int hookrow = row + 1; hookrow < board().height(); hookrow++) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(hookrow, col))) { downempty = hookrow; hookrow = board().height(); } } if (downempty < board().height()) { vrows.push_back(downempty); vcols.push_back(col); } } } } else { int col = move.startcol; int endrow = move.startrow + move.tiles().length() - 1; if (move.startrow > 0) { vrows.push_back(move.startrow - 1); vcols.push_back(col); } if (endrow < board().height() - 1) { vrows.push_back(endrow + 1); vcols.push_back(col); } for (int row = move.startrow; row <= endrow; row++) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { int upempty = -1; for (int hookcol = col - 1; hookcol >= 0; hookcol--) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, hookcol))) { upempty = hookcol; hookcol = -1; } } if (upempty >= 0) { hrows.push_back(row); hcols.push_back(upempty); } int downempty = board().width(); for (int hookcol = col + 1; hookcol < board().width(); hookcol++) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, hookcol))) { downempty = hookcol; hookcol = board().width(); } } if (downempty < board().width()) { hrows.push_back(row); hcols.push_back(downempty); } } } } board().makeMove(move); // check the appropriate crosses for (unsigned int i = 0; i < vrows.size(); i++) { int row = vrows[i]; int col = vcols[i]; if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { board().setVCross(row, col, LetterBitset()); } else { LetterString pre; if (row > 0) { for (int i = row - 1; i >= 0; i--) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { i = -1; } else { LetterString newpre; newpre += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(i, col)); newpre += pre; pre = newpre; } } } LetterString suf; if (row < board().height() - 1) { for (int i = row + 1; i < board().height(); i++) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { i = board().height(); } else { suf += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(i, col)); } } } #ifdef DEBUG_GENERATOR UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << " / " << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; #endif if ((pre.empty()) && (suf.empty())) { board().setVCross(row, col, LetterBitset().set()); } else { board().setVCross(row, col, fitbetween(pre, suf)); } #ifdef DEBUG_GENERATOR UVcout << "board().vcross[" << row << "][" << col << "] = " << cross2string(board().vcross(row, col)) << endl; #endif } } for (unsigned int i = 0; i < hrows.size(); i++) { int row = hrows[i]; int col = hcols[i]; if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { board().setHCross(row, col, LetterBitset()); } else { LetterString pre; if (col > 0) { for (int i = col - 1; i >= 0; i--) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { i = -1; } else { LetterString newpre; newpre += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(row, i)); newpre += pre; pre = newpre; } } } LetterString suf; if (col < board().width() - 1) { for (int i = col + 1; i < board().width(); i++) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { i = board().width(); } else { suf += QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(row, i)); } } } #ifdef DEBUG_GENERATOR UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << " / " << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; #endif if ((pre.empty()) && (suf.empty())) { board().setHCross(row, col, LetterBitset().set()); } else { board().setHCross(row, col, fitbetween(pre, suf)); } #ifdef DEBUG_GENERATOR UVcout << "board().hcross[" << row << "][" << col << "] = " << cross2string(board().hcross(row, col)) << endl; #endif } } } void Generator::readFromDawg(int index, unsigned int &p, Letter &letter, bool &t, bool &lastchild, bool &british, int &playability) const { QUACKLE_LEXICON_PARAMETERS->dawgAt(index, p, letter, t, lastchild, british, playability); } bool Generator::checksuffix(int i, const LetterString &suffix) { unsigned int p; Letter c; bool t; bool lastchild; bool british; int playability; readFromDawg(i, p, c, t, lastchild, british, playability); Letter sc = suffix[0]; //#ifdef DEBUG_BOARD //UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(suffix) << " i: " << i << ", p: " << p << ", c: " << QUACKLE_ALPHABET_PARAMETERS->userVisible(c) << ", sc: " << QUACKLE_ALPHABET_PARAMETERS->userVisible(sc) << endl; //#endif if (c == sc) { if (suffix.length() == 1) { return t; } else { if (p != 0) { return checksuffix(p, String::allButFront(suffix)); } else { return false; } } } else if (true) { //else if (c < sc) { if (lastchild) { return false; } else { return checksuffix(i + 1, suffix); } } else { return false; } } LetterBitset Generator::gaddagFitbetween(const LetterString &pre, const LetterString &suf) { // UVcout << "fit " // << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) // << "_" // << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; LetterBitset crosses; /* process the suffix once */ const GaddagNode *sufNode = QUACKLE_LEXICON_PARAMETERS->gaddagRoot(); int sufLen = suf.length(); for (int i = sufLen - 1; i >= 0; --i) { sufNode = sufNode->child(suf[i]); if (!sufNode) { // this can only happen if an illegal word is on the board return crosses; } } int preLen = pre.length(); for (const GaddagNode* node = sufNode->firstChild(); node; node = node->nextSibling()) { Letter childLetter = node->letter(); if (childLetter == QUACKLE_GADDAG_SEPARATOR) { break; } const GaddagNode *n = node; for (int i = preLen - 1; i >= 0; --i) { n = n->child(pre[i]); if (!n) { break; } } if (n && n->isTerminal()) { crosses.set(childLetter - QUACKLE_FIRST_LETTER); } } return crosses; } LetterBitset Generator::fitbetween(const LetterString &pre, const LetterString &suf) { if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) { return gaddagFitbetween(pre, suf); } //UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << "_" << // QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; LetterBitset crosses; for (Letter c = QUACKLE_FIRST_LETTER; c <= QUACKLE_ALPHABET_PARAMETERS->lastLetter(); c++) { /* UVcout << "Let's check " << QUACKLE_ALPHABET_PARAMETERS->userVisible(pre) << QUACKLE_ALPHABET_PARAMETERS->userVisible(c) << QUACKLE_ALPHABET_PARAMETERS->userVisible(suf) << endl; */ if (checksuffix(1, pre + c + suf)) { // subtract first letter because crosses hold values starting from zero crosses.set(c - QUACKLE_FIRST_LETTER); //UVcout << " that's a word" << endl; // UVcout << c; } } //UVcout << " crosses: " << crosses << " " << cross2string(crosses) << endl; return crosses; } UVString Generator::counts2string() { UVString ret; for (Letter i = 0; i < QUACKLE_ALPHABET_PARAMETERS->lastLetter(); i++) for (int j = 0; j < m_counts[i]; j++) ret += QUACKLE_ALPHABET_PARAMETERS->userVisible(i); return ret; } UVString Generator::cross2string(const LetterBitset &cross) { UVString ret; for (int i = 0; i < QUACKLE_ALPHABET_PARAMETERS->length(); i++) if (cross.test(i)) ret += QUACKLE_ALPHABET_PARAMETERS->userVisible(QUACKLE_FIRST_LETTER + i); return ret; } /* Gen(pos, word, rack, arc): pos = offset from anchor IF a letter, L, is already on this square THEN GoOn(pos, L, word, rack, NextArc(arc, L), arc) ELSE IF letters remain on the rack THEN FOR each letter on the rack, L, allowed on this square GoOn(pos, L, word, rack - L, NextArc(arc, L), arc) IF the rack contains a BLANK THEN FOR each letter the BLANK could be, L, allowed... GoOn(pos, L, word, rack - BLANK, NextArc(arc, L), arc) GoOn(pos, L, word, rack, NewArc, OldArc): IF pos <= 0 THEN // moving left word <- L + word IF L on OldArc & no letter directly left THEN Record IF NewArc != 0 THEN IF room to the left THEN Gen(pos - 1, word, rack, NewArc) NewArc <- NextArc(NewArc, ^) IF NewArc != 0, no letter directly left & room to the right THEN Gen(1, word, rack, NewArc) ELSE IF pos > 0 THEN // moving right word <- word + L IF L on OldArc & no letter directly right THEN Record IF NewArc != & room to the right THEN Gen(pos + 1, word, rack, NewArc) */ void Generator::gordongoon(int pos, char L, LetterString word, const GaddagNode *node) { //UVcout << "gordongoon(" << pos << ", " << L << ", " << word << ", " << newarc << ", " << oldarc << ")" << // " horiz: " << m_gordonhoriz << endl; if (pos <= 0) { int currow = m_anchorrow; int curcol = m_anchorcol; int leftrow = m_anchorrow; int leftcol = m_anchorcol; if (m_gordonhoriz) { curcol += pos; leftcol += pos - 1; } else { currow += pos; leftrow += pos - 1; } if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(currow, curcol))) { L = QUACKLE_PLAYED_THRU_MARK; } LetterString newWord; newWord += L; newWord += word; bool emptyleft = true; bool roomtoleft = true; bool atboardedge = false; if ((leftcol >= 0) && (leftrow >= 0)) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(currow, curcol)) && QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(leftrow, leftcol))) { roomtoleft = false; } if (pos < -m_leftlimit) { roomtoleft = false; } if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(leftrow, leftcol))) { emptyleft = false; } } else { atboardedge = true; } if (node->isTerminal() && (roomtoleft) && (m_laid > 0)) { // UVcout << "found a word or something " << word << " at " << pos << endl; Move move; move.action = Move::Place; move.setTiles(newWord); if (m_gordonhoriz) { move.startrow = m_anchorrow; move.startcol = m_anchorcol + pos; } else { move.startrow = m_anchorrow + pos; move.startcol = m_anchorcol; } move.horizontal = m_gordonhoriz; move.score = board().score(move, &move.isBingo); move.equity = equity(move); if (m_recordall) { m_moveList.push_back(move); } if (MoveList::equityComparator(best, move)) { best = move; } // UVcout << "found a move: " << move << " score: " << move.score << ", equity: " << move.equity << // " outputted by leftmoving loop" << endl; } if (roomtoleft && pos != -m_leftlimit && !atboardedge) { gordongen(pos - 1, newWord, node); } // UVcout << "looking for the delimiter" << endl; node = node->child(QUACKLE_GADDAG_SEPARATOR); // UVcout << "after all that, delimiter's newarc is " << newarc << endl; int rightrow = m_anchorrow; int rightcol = m_anchorcol; if (m_gordonhoriz) { rightcol++; } else { rightrow++; } bool atrightedge = false; if ((rightrow > board().height() - 1) || (rightcol > board().width() - 1)) { atrightedge = true; } if ((node != 0) && emptyleft && !atrightedge) { gordongen(1, newWord, node); } } else { // UVcout << "looking to the right" << endl; int currow = m_anchorrow; int curcol = m_anchorcol; int rightrow = m_anchorrow; int rightcol = m_anchorcol; if (m_gordonhoriz) { curcol += pos; rightcol += pos + 1; } else { currow += pos; rightrow += pos + 1; } if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(currow, curcol))) { word += QUACKLE_PLAYED_THRU_MARK; } else { word += L; } bool roomtoright = true; bool atboardedge = false; // UVcout << "rightsquare: " << (char)(rightcol + 'A') << rightrow + 1 << endl; if ((rightcol <= board().width() - 1) && (rightrow <= board().height() - 1)) { if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rightrow, rightcol))) { roomtoright = false; // UVcout << "can't record " << word << " here because of the " << board().letter(rightrow, rightcol) << endl; } else { // UVcout << "yay! " << (char)(rightcol + 'A') << rightrow + 1 << " is empty!" << endl; // UVcout << board() << endl; } } else { // UVcout << "at board edge so i can maybe record " << word << endl; atboardedge = true; } if (node->isTerminal() && (roomtoright) && (m_laid > 0)) { // UVcout << "found a word or something " << word << " at " << pos << endl; Move move; move.action = Move::Place; move.setTiles(word); if (m_gordonhoriz) { move.startrow = m_anchorrow; move.startcol = m_anchorcol - word.length() + pos + 1; } else { move.startrow = m_anchorrow - word.length() + pos + 1; move.startcol = m_anchorcol; } move.horizontal = m_gordonhoriz; move.score = board().score(move, &move.isBingo); move.equity = equity(move); if (m_recordall) { m_moveList.push_back(move); } if (MoveList::equityComparator(best, move)) { best = move; } // UVcout << "found a move: " << move << " score: " << move.score << ", equity: " << move.equity << // " outputted by rightmoving loop" << endl; } // UVcout << "newarc is " << newarc << endl; if (!atboardedge) { gordongen(pos + 1, word, node); } else { // UVcout << "didn't go ahead because we were at board edge" << endl; } } } void Generator::gordongen(int pos, const LetterString &word, const GaddagNode *node) { // UVcout << "gordongen(" << pos << ", " << word << ", " << i << ")" << " horiz: " << m_gordonhoriz << endl; int currow = m_anchorrow; int curcol = m_anchorcol; if (m_gordonhoriz) { curcol += pos; } else { currow += pos; } LetterBitset cross; if (m_gordonhoriz) { cross = board().vcross(currow, curcol); } else { cross = board().hcross(currow, curcol); } if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(currow, curcol))) { // UVcout << "gordongen sez a letter (" << board().letter(currow, curcol) << ") already on this square" << endl; Letter boardc = QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(currow, curcol)); const GaddagNode *child = node->child(boardc); if (child) { gordongoon(pos, board().letter(currow, curcol), word, child); } } else { for (const GaddagNode* child = node->firstChild(); child; child = child->nextSibling()) { Letter childLetter = child->letter(); if ((m_counts[childLetter] <= 0) || !cross.test(childLetter - QUACKLE_FIRST_LETTER)) { continue; } if (childLetter == QUACKLE_GADDAG_SEPARATOR) { // UVcout << "ran into a delimiter" << endl; break; } m_counts[childLetter]--; m_laid++; // UVcout << " yeah that'll work" << endl; gordongoon(pos, childLetter, word, child); m_counts[childLetter]++; m_laid--; } if (m_counts[QUACKLE_BLANK_MARK] >= 1) { for (const GaddagNode* child = node->firstChild(); child; child = child->nextSibling()) { Letter childLetter = child->letter(); // UVcout << "childLetter is " << (char)(arcc + 'A') << endl; if (childLetter == QUACKLE_GADDAG_SEPARATOR) { // UVcout << "ran into a delimiter" << endl; break; } if (cross.test(childLetter - QUACKLE_FIRST_LETTER)) { m_counts[QUACKLE_BLANK_MARK]--; m_laid++; // UVcout << " yeah that'll work" << endl; gordongoon(pos, QUACKLE_ALPHABET_PARAMETERS->setBlankness(childLetter), word, child); m_counts[QUACKLE_BLANK_MARK]++; m_laid--; } } } } } void Generator::extendright(const LetterString &partial, int i, int row, int col, int edge, int righttiles, bool horizontal) { if (i == 0) { // is this really correct? return; } unsigned int p; Letter c; bool t; bool lastchild; bool british; int playability; readFromDawg(i, p, c, t, lastchild, british, playability); int rowpos = row; int rownext = row; int colpos = col; int colnext = col; int dirpos; int edgeDirpos; if (horizontal) { colpos = col + righttiles; colnext = col + righttiles + 1; dirpos = colpos; edgeDirpos = board().width() - 1; } else { rowpos = row + righttiles; rownext = row + righttiles + 1; dirpos = rowpos; edgeDirpos = board().height() - 1; } #ifdef DEBUG_GENERATOR UVcout << "extendright(" << QUACKLE_ALPHABET_PARAMETERS->userVisible(partial) << ", " << i << ", " << counts2string() << ", " << rowpos << ", " << colpos << ", " << horizontal << ")" << endl; #endif if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rowpos, colpos))) { if (m_counts[c] >= 1) { LetterBitset cross; if (horizontal) { cross = board().vcross(rowpos, colpos); } else { cross = board().hcross(rowpos, colpos); } if (cross.test(c - QUACKLE_FIRST_LETTER)) { if (t) { bool couldend = true; if (dirpos < edgeDirpos) { if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rownext, colnext))) { couldend = false; } } if (couldend) { Move move; move.action = Move::Place; move.setTiles(partial + c); if (horizontal) { move.startrow = row; move.startcol = col - (partial.length() - righttiles); } else { move.startrow = row - (partial.length() - righttiles); move.startcol = col; } move.horizontal = horizontal; move.score = board().score(move, &move.isBingo); move.equity = equity(move); // i added this because m_laid is wrong and i don't want to break anything by fixing it :) // will need to remember to add this bit to the DAGGAD code when we start using it again int laid = move.wordTilesWithNoPlayThru().length(); bool onetilevert = (!move.horizontal) && (laid == 1); bool ignore = onetilevert && !board().hcross(row, col).all(); if (1 || !ignore) { if (m_recordall) { m_moveList.push_back(move); } if (MoveList::equityComparator(best, move)) { best = move; } #ifdef DEBUG_GENERATOR UVcout << "found a move: " << move << " laid: " << m_laid << ", score: " << move.score << ", equity: " << move.equity << endl; #endif } } } if (dirpos < edgeDirpos) { m_counts[c]--; m_laid++; extendright(partial + c, p, row, col, 0, righttiles + 1, horizontal); m_counts[c]++; m_laid--; } } } if ((m_counts[QUACKLE_BLANK_MARK] >= 1)) { LetterBitset cross; if (horizontal) { cross = board().vcross(rowpos, colpos); } else { cross = board().hcross(rowpos, colpos); } if (cross.test(c - QUACKLE_FIRST_LETTER)) { if (t) { bool couldend = true; if (dirpos < edgeDirpos) { if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rownext, colnext))) { couldend = false; } } if (couldend) { Move move; move.action = Move::Place; move.setTiles(partial + QUACKLE_ALPHABET_PARAMETERS->setBlankness(c)); if (horizontal) { move.startrow = row; move.startcol = col - (partial.length() - righttiles); } else { move.startrow = row - (partial.length() - righttiles); move.startcol = col; } move.horizontal = horizontal; move.score = board().score(move, &move.isBingo); move.equity = equity(move); int laid = move.wordTilesWithNoPlayThru().length(); bool onetilevert = (!move.horizontal) && (laid == 1); bool ignore = onetilevert && !board().hcross(row, col).all(); if (1 || !ignore) { if (m_recordall) { m_moveList.push_back(move); } if (MoveList::equityComparator(best, move)) { best = move; } #ifdef DEBUG_GENERATOR UVcout << "found a move: " << move << " laid: " << m_laid << ", score: " << move.score << ", equity: " << move.equity << endl; #endif } } } if (dirpos < edgeDirpos) { m_counts[QUACKLE_BLANK_MARK]--; m_laid++; extendright(partial + QUACKLE_ALPHABET_PARAMETERS->setBlankness(c), p, row, col, 0, righttiles + 1, horizontal); m_counts[QUACKLE_BLANK_MARK]++; m_laid--; } } } if (!lastchild) { extendright(partial, i + 1, row, col, edge + 1, righttiles, horizontal); } } else { Letter boardc = QUACKLE_ALPHABET_PARAMETERS->clearBlankness(board().letter(rowpos, colpos)); if (c == boardc) { #ifdef DEBUG_GENERATOR UVcout << "We're playing with " << QUACKLE_ALPHABET_PARAMETERS->userVisible(partial) << " through a letter (" << boardc << ") or trying to" << endl; #endif bool endofthrough = false; if (dirpos < edgeDirpos) { extendright(partial + (Letter)QUACKLE_PLAYED_THRU_MARK, p, row, col, 0, righttiles + 1, horizontal); #ifdef DEBUG_GENERATOR UVcout << " next square is " << board().letter(rownext, colnext) << endl; #endif if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(rownext, colnext))) { endofthrough = true; #ifdef DEBUG_GENERATOR UVcout << " woohoo! next square is empty" << endl; #endif } } else { endofthrough = true; #ifdef DEBUG_GENERATOR UVcout << " woohoo! at the edge of the board" << endl; #endif } if (!t) { #ifdef DEBUG_GENERATOR UVcout << " but " << partial + boardc << " isn't a word" << endl; #endif } if (endofthrough & t) { if (m_laid > 0) { Move move; move.action = Move::Place; move.setTiles(partial + (Letter)QUACKLE_PLAYED_THRU_MARK); if (horizontal) { move.startrow = row; move.startcol = col - (partial.length() - righttiles); } else { move.startrow = row - (partial.length() - righttiles); move.startcol = col; } move.horizontal = horizontal; move.score = board().score(move, &move.isBingo); move.equity = equity(move); int laid = move.wordTilesWithNoPlayThru().length(); bool onetilevert = (!move.horizontal) && (laid == 1); bool ignore = onetilevert && !board().hcross(row, col).all(); if (1 || !ignore) { if (m_recordall) { m_moveList.push_back(move); } if (MoveList::equityComparator(best, move)) { best = move; } #ifdef DEBUG_GENERATOR UVcout << "found a move: " << move << " which has equity " << move.equity << endl; #endif } } } } else if (!lastchild) // else if ((c < boardc) && (!lastchild)) { extendright(partial, i + 1, row, col, edge + 1, righttiles, horizontal); } } } void Generator::leftpart(const LetterString &partial, int i, int limit, int row, int col, int edge, bool horizontal) { #ifdef DEBUG_GENERATOR UVcout << "leftpart(" << QUACKLE_ALPHABET_PARAMETERS->userVisible(partial) << ", " << i << ", " << counts2string() << ", " << row << ", " << col << ", " << edge << ")" << endl; #endif if (edge == 0) { extendright(partial, i, row, col, 0, 0, horizontal); } if (limit > 0) { if (i == 0) { // is this right at all? return; } unsigned int p; Letter c; bool t; bool lastchild; bool british; int playability; readFromDawg(i, p, c, t, lastchild, british, playability); if (m_counts[c] >= 1) { m_counts[c]--; m_laid++; leftpart(partial + c, p, limit - 1, row, col, 0, horizontal); m_counts[c]++; m_laid--; } if (m_counts[QUACKLE_BLANK_MARK] >= 1) { m_counts[QUACKLE_BLANK_MARK]--; m_laid++; leftpart(partial + QUACKLE_ALPHABET_PARAMETERS->setBlankness(c), p, limit - 1, row, col, 0, horizontal); m_counts[QUACKLE_BLANK_MARK]++; m_laid--; } if (!lastchild) { leftpart(partial, i + 1, limit, row, col, edge + 1, horizontal); } } } void Generator::setupCounts(const LetterString &letters) { String::counts(letters, m_counts); } double Generator::equity(const Move &move) const { return QUACKLE_EVALUATOR->equity(m_position, move); } Move Generator::generate() { #ifdef DEBUG_GENERATOR UVcout << "generate called" << endl; #endif for (int row = 0; row < board().height(); row++) { for (int col = 0; col < board().width(); col++) { // generate horizontal plays // what defines an anchor square? bool anchor = false; if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && !board().vcross(row, col).all()) { if (col == 0) { anchor = true; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col - 1))) { anchor = true; } } else if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { if (col == 0) { anchor = true; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col - 1))) { anchor = true; } } if (anchor) { int k = 0; for (int i = col - 1; i >= 0; i--) { // UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl; if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i)) && board().vcross(row, i).all()) { if (i == 0) { k++; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i - 1))) { k++; } } else { i = -1; } } #ifdef DEBUG_GENERATOR UVcout << "looking horizontally with the " << QUACKLE_ALPHABET_PARAMETERS->userVisible(board().letter(row, col)) << " at " << row + 1 << (char)(col + 'A') << endl; UVcout << "Apparently there are " << k << " empty spots to our left" << endl; #endif m_laid = 0; leftpart(LetterString(), 1, k, row, col, 0, true); } // generate vertical plays // what defines an anchor square? anchor = false; if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && !board().hcross(row, col).all()) { if (row == 0) { anchor = true; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row - 1, col))) { anchor = true; } } else if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { if (row == 0) { anchor = true; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row - 1, col))) { anchor = true; } } if (anchor) { int k = 0; for (int i = row - 1; i >= 0; i--) { // UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl; if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col)) && board().hcross(i, col).all()) { if (i == 0) { k++; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i - 1, col))) { k++; } } else { i = -1; } } #ifdef DEBUG_GENERATOR UVcout << "looking vertically with the " << board().letter(row, col) << " at " << row + 1 << (char)(col + 'A') << endl; UVcout << "Apparently there are " << k << " empty spots to our left" << endl; #endif m_laid = 0; leftpart(LetterString(), 1, k, row, col, 0, false); } } } return best; } // TODO GET RID OF CODE DUPLICATION Move Generator::gordongenerate() { for (int row = 0; row < board().height(); row++) { for (int col = 0; col < board().width(); col++) { // generate horizontal plays // what defines an anchor square? bool anchor = false; if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && !board().vcross(row, col).all()) { if (col == 0) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col + 1))) { anchor = true; } } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col - 1))) { if (col == board().width() - 1) { anchor = true; } else { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col + 1))) { anchor = true; } } } } else if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { if (col == board().width() - 1) { anchor = true; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col + 1))) { anchor = true; } } if (anchor) { int k = 0; for (int i = col; i >= 0; i--) { // skip over filled sqs if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i))) { k++; } else { i = -1; } } for (int i = col - k - 1; i >= 0; i--) { // UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl; if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i)) && board().vcross(row, i).all()) { if (i == 0) { k++; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, i - 1))) { k++; } } else { i = -1; } } // UVcout << "Apparently there are " << k << " empty spots to our left" << endl; // leftpart("", 1, k, row, col, 0, true); // UVcout << "looking horizontally with the " << board().letter(row, col) << // " at " << row + 1 << (char)(col + 'A') << endl; m_anchorrow = row; m_anchorcol = col; m_gordonhoriz = true; m_laid = 0; m_leftlimit = k; gordongen(0, LetterString(), QUACKLE_LEXICON_PARAMETERS->gaddagRoot()); } // generate vertical plays // what defines an anchor square? anchor = false; if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col)) && !board().hcross(row, col).all()) { if (row == 0) { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row + 1, col))) { anchor = true; } } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row - 1, col))) { if (row == board().height() - 1) { anchor = true; } else { if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row + 1, col))) { anchor = true; } } } } else if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row, col))) { if (row == board().height() - 1) { anchor = true; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(row + 1, col))) { anchor = true; } } if (anchor) { int k = 0; for (int i = row; i >= 0; i--) { if (QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col))) { k++; } else { i = -1; } } for (int i = row - k - 1; i >= 0; i--) { // UVcout << "board().vcross[" << row << "][" << i << "] = " << board().vcross(row, i) << endl; if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i, col)) && board().hcross(i, col).all()) { if (i == 0) { k++; } else if (!QUACKLE_ALPHABET_PARAMETERS->isSomeLetter(board().letter(i - 1, col))) { k++; } } else { i = -1; } } // UVcout << "Apparently there are " << k << " empty spots to our left" << endl; // leftpart("", 1, k, row, col, 0, false); // UVcout << "looking vertically with the " << board().letter(row, col) << // " at " << row + 1 << (char)(col + 'A') << endl; m_anchorrow = row; m_anchorcol = col; m_gordonhoriz = false; m_laid = 0; m_leftlimit = k; gordongen(0, LetterString(), QUACKLE_LEXICON_PARAMETERS->gaddagRoot()); } } } return best; } void Generator::spit(int i, const LetterString &prefix, int flags) { // UVcout << "spit called... i: " << i << ", prefix: " << prefix << endl; unsigned int p; Letter c; bool t; bool lastchild; bool british; int playability; readFromDawg(i, p, c, t, lastchild, british, playability); if (m_counts[c] >= 1) { m_counts[c]--; if (t) { // UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(prefix) << c << endl; bool usedAll = true; if (!(flags & NoRequireAllLetters)) { for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) { if (m_counts[j] > 0) { usedAll = false; break; } } } if (usedAll) { m_spat.push_back(prefix + c); if (flags & SingleMatch) { return; } } } if (p != 0) { spit(p, prefix + c, flags); } m_counts[c]++; } if (!(flags & ClearBlanknesses && m_counts[c] >= 1)) { if (m_counts[QUACKLE_BLANK_MARK] >= 1 || flags & AddAnyLetters) { m_counts[QUACKLE_BLANK_MARK]--; if (t) { // UVcout << prefix << QUACKLE_ALPHABET_PARAMETERS->setBlankness(c) << endl; bool usedAll = true; if (!(flags & NoRequireAllLetters)) for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) if (m_counts[j] > 0) usedAll = false; if (usedAll) { m_spat.push_back(prefix + (flags & ClearBlanknesses? c : QUACKLE_ALPHABET_PARAMETERS->setBlankness(c))); if (flags & SingleMatch) { return; } } } if (p != 0) { spit(p, prefix + (flags & ClearBlanknesses? c : QUACKLE_ALPHABET_PARAMETERS->setBlankness(c)), flags); } m_counts[QUACKLE_BLANK_MARK]++; } } if (!lastchild) { spit(i + 1, prefix, flags); } } void Generator::wordspit(int i, const LetterString &prefix, int flags) { // UVcout << "spit called... i: " << i << ", prefix: " << prefix << endl; unsigned int p; Letter c; bool t; bool lastchild; bool british; int playability; //UVcout << "wordspit(" << i << ", " << QUACKLE_ALPHABET_PARAMETERS->userVisible(prefix) << ", " << flags << ")" << endl; readFromDawg(i, p, c, t, lastchild, british, playability); if (m_counts[c] >= 1) { m_counts[c]--; if (t) { // UVcout << QUACKLE_ALPHABET_PARAMETERS->userVisible(prefix) << c << endl; bool usedAll = true; if (!(flags & NoRequireAllLetters)) { for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) { if (m_counts[j] > 0) { usedAll = false; break; } } } if (usedAll) { WordWithInfo word; word.wordLetterString = prefix + c; word.british = british; word.playability = playability; m_wordspat.push_back(word); } } if (p != 0) { wordspit(p, prefix + c, flags); } m_counts[c]++; } if (!lastchild) { wordspit(i + 1, prefix, flags); } } Move Generator::exchange() { map throwmap; const int rackSize = rack().tiles().length(); const int permutations = 1 << rackSize; for (int i = 1; i < permutations; i++) { LetterString thrown; for (int j = 0; j < rackSize; j++) if (i & (1 << j)) thrown += rack().tiles()[j]; Move move; move.action = Move::Exchange; move.setTiles(String::alphabetize(thrown)); move.score = 0; move.equity = equity(move); if (throwmap.find(move.tiles()) == throwmap.end()) { if (m_recordall) m_moveList.push_back(move); if (MoveList::equityComparator(best, move)) best = move; throwmap[move.tiles()] = true; } } return best; } Move Generator::findstaticbest(bool canExchange) { best = Move::createPassMove(); m_moveList.clear(); setupCounts(rack().tiles()); if (QUACKLE_LEXICON_PARAMETERS->hasSomething()) { if (board().isEmpty()) { anagram(); } else { // UVcout << rack() << endl; // UVcout << board() << endl; if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) gordongenerate(); else generate(); // UVcout << "gaddag says: " << best << " " << best.score << " " << best.equity; // UVcout << endl; // UVcout << " dawg says: " << best << " " << best.score << " " << best.equity << endl; } } if (canExchange) exchange(); if (m_moveList.empty()) m_moveList.push_back(best); return best; } void Generator::gaddagAnagram(const GaddagNode *node, const LetterString &prefix, int flags) { for (const GaddagNode* child = node->firstChild(); child; child = child->nextSibling()) { Letter childLetter = child->letter(); if (childLetter == QUACKLE_GADDAG_SEPARATOR) { break; } if (m_counts[childLetter] <= 0) continue; m_counts[childLetter]--; LetterString newPrefix; newPrefix += childLetter; newPrefix += prefix; if (child->isTerminal()) { bool usedAll = true; if (!(flags & NoRequireAllLetters)) { for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) { if (m_counts[j] > 0) { usedAll = false; break; } } } if (usedAll) { m_spat.push_back(newPrefix); if (flags & SingleMatch) { return; } } } if (child->firstChild()) { gaddagAnagram(child, newPrefix, flags); if (flags & SingleMatch && m_spat.size() > 0) { m_counts[childLetter]++; return; } } m_counts[childLetter]++; } if (m_counts[QUACKLE_BLANK_MARK] >= 1 || flags & AddAnyLetters) { for (const GaddagNode* child = node->firstChild(); child; child = child->nextSibling()) { Letter childLetter = child->letter(); if (childLetter == QUACKLE_GADDAG_SEPARATOR) { break; } if (flags & ClearBlanknesses && m_counts[childLetter] >= 1) { continue; } m_counts[QUACKLE_BLANK_MARK]--; LetterString newPrefix; newPrefix += flags & ClearBlanknesses ? childLetter : QUACKLE_ALPHABET_PARAMETERS->setBlankness(childLetter); newPrefix += prefix; if (child->isTerminal()) { bool usedAll = true; if (!(flags & NoRequireAllLetters)) for (int j = 0; j < QUACKLE_FIRST_LETTER + QUACKLE_MAXIMUM_ALPHABET_SIZE; ++j) if (m_counts[j] > 0) usedAll = false; if (usedAll) { m_spat.push_back(newPrefix); if (flags & SingleMatch) { return; } } } if (child->firstChild()) { gaddagAnagram(child, newPrefix, flags); if (flags & SingleMatch && m_spat.size() > 0) { m_counts[QUACKLE_BLANK_MARK]++; return; } } m_counts[QUACKLE_BLANK_MARK]++; } } } Move Generator::anagram() { // UVcout << "anagram called" << endl; // UVcout << "about to call spit" << endl; m_spat.clear(); if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) { gaddagAnagram(QUACKLE_LEXICON_PARAMETERS->gaddagRoot(), LetterString(), NoRequireAllLetters); } else { spit(1, LetterString(), NoRequireAllLetters); } // UVcout << "m_spat has " << m_spat.size() << " words in it" << endl; WordList::const_iterator end = m_spat.end(); for (WordList::const_iterator it = m_spat.begin(); it != end; ++it) { for (unsigned int k = 0; k < (*it).length(); k++) { Move move; move.action = Move::Place; move.setTiles(*it); move.horizontal = true; move.startrow = QUACKLE_BOARD_PARAMETERS->startRow(); move.startcol = (QUACKLE_BOARD_PARAMETERS->startColumn() - (*it).length() + 1) + k; if (move.startcol < 0) continue; move.score = board().score(move, &move.isBingo); move.equity = equity(move); // UVcout << move << " has equity " << move.equity << endl; if (m_recordall) m_moveList.push_back(move); if (MoveList::equityComparator(best, move)) best = move; } } return best; } bool Generator::isAcceptableWord(const LetterString &word) { WordList results = anagramLetters(word); WordList::const_iterator end = results.end(); for (WordList::const_iterator it = results.begin(); it != end; ++it) if ((*it) == word) return true; return false; } WordList Generator::anagramLetters(const LetterString &letters, int flags) { setupCounts(String::clearBlankness(letters)); m_spat.clear(); if (QUACKLE_LEXICON_PARAMETERS->hasGaddag()) { gaddagAnagram(QUACKLE_LEXICON_PARAMETERS->gaddagRoot(), LetterString(), flags); } else if (QUACKLE_LEXICON_PARAMETERS->hasSomething()) { spit(1, LetterString(), flags); } return m_spat; } void Generator::storeWordInfo(WordWithInfo *wordWithInfo) { if (!QUACKLE_LEXICON_PARAMETERS->hasSomething()) return; setupCounts(String::clearBlankness(wordWithInfo->wordLetterString)); wordWithInfo->probability = Bag::probabilityOfDrawingFromFullBag(wordWithInfo->wordLetterString); m_wordspat.clear(); wordspit(1, LetterString(), 0); vector::const_iterator end = m_wordspat.end(); for (vector::const_iterator it = m_wordspat.begin(); it != end; ++it) { if ((*it).wordLetterString == wordWithInfo->wordLetterString) { wordWithInfo->british = (*it).british; wordWithInfo->playability = (*it).playability; return; } } } void Generator::storeExtensions(WordWithInfo *wordWithInfo) { // TODO(olaugh) }