1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
/*
* Quackle -- Crossword game artificial intelligence and analysis tool
* Copyright (C) 2005-2006 Jason Katz-Brown and John O'Laughlin.
*
* 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 2 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, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301 USA
*/
#include <algorithm>
#include <iostream>
#include "enumerator.h"
#include "bag.h"
#include "datamanager.h"
#include "gameparameters.h"
using namespace std;
using namespace Quackle;
Enumerator::Enumerator(Bag &B)
{
m_bag = B;
}
void Enumerator::normalizeProbabilities(ProbableRackList *racks)
{
double sum = 0;
for (ProbableRackList::const_iterator it = racks->begin(); it != racks->end(); ++it)
sum += (*it).probability;
for (ProbableRackList::iterator it = racks->begin(); it != racks->end(); ++it)
(*it).probability = (*it).probability / sum;
sum = 0;
for (ProbableRackList::const_iterator it = racks->begin(); it != racks->end(); ++it)
sum += (*it).possibility;
for (ProbableRackList::iterator it = racks->begin(); it != racks->end(); ++it)
(*it).possibility = (*it).possibility / sum;
}
void Enumerator::enumerate(ProbableRackList *racks, unsigned int rackSize)
{
racks->clear();
m_bag.letterCounts(m_bagcounts);
m_possibleBag = m_bag;
recurse(LetterString(), 0, 0, racks, rackSize);
normalizeProbabilities(racks);
}
void Enumerator::enumerate(ProbableRackList *racks)
{
enumerate(racks, QUACKLE_PARAMETERS->rackSize());
}
void Enumerator::enumeratePossible(ProbableRackList *racks, const Bag &bag)
{
racks->clear();
m_bag.letterCounts(m_bagcounts);
//UVcout << "enumeratePossible called with bag: " << bag << endl;
m_possibleBag = m_bag;
m_possibleBag.removeLetters(bag.tiles());
//UVcout << "m_bag: " << m_bag << endl;
//UVcout << "m_possibleBag: " << m_possibleBag << endl;
recurse(LetterString(), 0, 0, racks, QUACKLE_PARAMETERS->rackSize());
normalizeProbabilities(racks);
}
void Enumerator::recurse(LetterString prefix, int i, Letter start, ProbableRackList *racks, unsigned int rackSize)
{
if (prefix.length() == rackSize)
{
ProbableRack probableRack;
probableRack.rack = Rack(prefix);
probableRack.probability = m_bag.probabilityOfDrawing(probableRack.rack.tiles());
probableRack.possibility = m_possibleBag.probabilityOfDrawing(probableRack.rack.tiles());
racks->push_back(probableRack);
return;
}
for (Letter c = start; c <= QUACKLE_ALPHABET_PARAMETERS->lastLetter(); ++i, ++c)
{
if (m_bagcounts[i] > 0)
{
m_bagcounts[i]--;
recurse(prefix + c, i, c, racks, rackSize);
m_bagcounts[i]++;
}
}
}
|
