how to use a dictionary in a program?

[conan19870619]

i had a thought to write a program to play boggle.
i already know how it works and decide to use a heap-based method.
However, i just dont know how to write a basic step: look up a word in a dictionary.
So,if i have a word "program", how can i search it in the dictionary?
i suppose i need a dictionary file. what does this file look like and how can i use it in the
program?(how to write the code).

[iamthwee]

A dictionary is like any other file.

You read it in using fstreams.

[Duoas]

How is your dictionary stored? If, like iamthwee suggests, it is a file with words in it, you can just search the file for the given word.

You can even use the STL for that:

#include <algorithm>
#include <fstream>
#include <iterator>
#include <string>

// findword()
//   Determine whether or not a given word exists in a file.
//   This routine assumes that no word has spaces in it.
// returns
//   True if the word was found. False for any other reason.
//
bool findword( const std::string& filename, const std::string& word )
  {
  bool result = false;
  std::ifstream file( filename.c_str() );
  std::istream_iterator <std::string> end;

  result =
    std::find(
      std::istream_iterator <std::string> ( file ),
      end,
      word
      )
    != end;

  result &&= file.good();

  file.close();
  return result;
  }

However, this requires a large file access every time. You could open the file elsewhere and just seekg( 0 ); before each search, or you could load the file into memory (into a std::deque or some other container) and search it there.

#include <deque>

std::deque <std::string>
loadwords( const std::string& filename )
  {
  std::deque <std::string> result;
  ifstream file( filename.c_str() );
  std::copy(
    std::istream_iterator <std::string> ( file ),
    std::istream_iterator <std::string> (),
    std::back_inserter( result )
    );
  file.close();
  return result;
  }

bool findword(
  std::deque <std::string> words,
  const std::string& word
  ) {
  return
    std::find(
      words.begin(),
      words.end(),
      word
      )
    != words.end();
  }

(Use a deque over a vector for this kind of thing.)

Hope this helps.

[iamthwee]

Yes Duoas' example certainly has all the bows and whistles, but you can make it considerably simpler if you wish.

Google file I/O with c++.

You can do this by reading in the file just once.

- Think of the boggle grid as one large set of jumbled letters.
- Find all the possible words you can make from those letters. -(Use letter frequency matches to help)
- Go through each word and see if they are legit on the boggle grid.
- I believe a trie would be a good datastructure to use here.

[Duoas]

The reason I suggested the STL is because it is the simplest possible answer.

Doing all that stuff you recommended would require considerably more than ~30 lines of code, it would cost extra time to enumerate and check every possible word --even with optimizations.

The use of an associative array is good, but again the STL provides one: std::map.

Personally, I'd avoid it's overhead just for space considerations in a large dictionary, and just use a deque to read a pre-sorted dictionary file (which is normal), and write my own binary search algorithm to find a word quickly. It can be done in log(N) time, with a usual successful search taking only a few iterations even if your dictionary is 10,000 elements or more.

The algorithm itself is is very simple and can be done in under 20 lines of code.

[iamthwee]

Why would you need a std:map?
What is your definition of a pre-sorted dictionary file?

Are you saying you can write a boggle solve in under 20 lines of code?

[Duoas]

Why would I need a map? You suggested using the associative array. It can be useful during scoring, at least.

"Pre-sorted" implies that something has been sorted before it is needed or used.

And no, I did not say that. I said a binary search can be written in under 20 lines of code. But that's moot because I forgot that the STL provides the std::binary_search() <algorithm> anyway...

Remember, you don't have to know every solution --just the ones that the user(s) suggest.

But if you really want to know, a boggle solve (every solution) probably could be written in under 20 lines of code. Maybe 30.

;)

[Duoas]

Heh heh heh -- I couldn't resist iamthwee's challenge (sorry conan --look below for where to get a dictionary).

// boggle-solver.cpp
// Copyright (c) 2008 Michael Thomas Greer
// <http://www.boost.org/LICENSE_1_0.txt>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
using namespace std;

char gameboard[ 4 ][ 4 ];

bool validate_word( const string& word, int row, int col, int index, int touched )
  {
  if ((unsigned)index == word.length()) return true;
  for (int r = -1; r < 2; r++)
  for (int c = -1; c < 2; c++)
    {
    int mask = 1 << (((row +r) *4) +col +c);
    if (((touched & mask) == 0)
    &&  (gameboard[ row +r ][ col +c ] == word[ index ]))
      if (validate_word( word, (word[ index ] == 'q') ? index +2 : index +1, row +r, col +c, touched | mask ))
        return true;
    }
  return false;
  }

void process_word( const string& word )
  {
  if ((3 > word.length()) or (word.length() > 17)) return;
  for (int row = 0; row < 4; row++)
  for (int col = 0; col < 4; col++)
    if (gameboard[ row ][ col ] == word[ 0 ])
      if (validate_word( word, row, col, 1, (row *4) +col ))
        cout << word << '\n';
  }

int main()
  {
  cerr << "Enter the gameboard. Use just 'Q' for 'Qu'.\n";
  for (int n = 0; n < 16; n++)
    *((char*)gameboard +n) = tolower( (cin >> ws).get() );

  ifstream words( "word.lst" );
  if (!words) return 1;
  for_each( istream_iterator <string> ( words ), istream_iterator <string> (), process_word );
  words.close();

  return 0;
  }

If you leave out the boilerplate and the stuff to actually read and store the gameboard, the boggle solver is 25 lines long (lines 14 to 37 and line 47). I could have compressed it smaller, but I figure that would be cheating, what with it already lacking any commentary and having a few really long lines.

The "word.lst" dictionary is the Updated Millennial Edition of ENABLE.

*smirk*

[iamthwee]

Tested on Dev-cpp with the board

dwji
eafm
kfop
awft

output?

fem
fib
fid
fie
fig
fil
fin
fir
fit
fix
fiz
fop
fop
fop
ikat
ikon
imp
jib
jig
jimp
jin
kaas
kabs
kadi
kaes
kafs
kagu
kaif
kail
kain
kaka
kaki
kale
kame
kami
kana
kane
kaon
kapa
kaph
karn
kart
kata
kats
kava
kayo
kays
maar
mabe
mace
mach
mack
macs
mad
made
mads
maes
mage
magi
mags
maid
mail
maim
main
mair
make
mako
male
mall
malm
malt
mama
mana
mane
mano
mans
many
maps
marc
mare
mark
marl
mars
mart
mash
mask
mass
mast
mate
math
mats
matt
maud
maul
maun
maut
mawn
maws
maxi
maya
mayo
mays
maze
mazy
mead
meal
mealier
mealies
mean
meanies
meaning
meat
meatier
meatily
meed
meek
meet
meeting
megrims
megs
meinies
meld
melding
mell
melling
meloids
mels
melt
melting
meme
memo
memoirs
mems
mend
mendigo
mending
menhirs
meno
mensing
mention
menu
meou
meouing
meow
meowing
mercies
mere
merging
merk
merl
merlins
merrier
merrily
mesa
mesh
meshier
meshing
mess
messiah
messier
messily
messing
mestino
mestiza
mestizo
meta
mete
meth
metope
metrics
metrify
metring
metrist
mew
mewl
mewling
mews
meze
mib
mid
mig
mil
milpa
mim
mir
mis
mix
mom
mop
mot
ofay
oft
oms
oot
ope
ops
opt
paca
pace
pack
pacs
pact
padi
pads
page
paid
paik
pail
pain
pair
pale
pall
palm
palp
pals
paly
pams
pane
pang
pans
pant
papa
paps
para
pard
pare
park
parr
pars
part
pase
pash
pass
past
pate
path
pats
paty
pave
pawl
pawn
paws
pays
pom
pop
pot
tabs
tabu
tace
tach
tack
taco
tact
tads
tael
tags
tahr
tail
tain
taka
take
tala
talc
tale
tali
talk
tall
tame
tamp
tams
tang
tank
tans
taos
tapa
tape
taps
tar
tare
tarn
taro
tarp
tars
tart
task
tass
tate
tats
taus
taut
tavs
taws
taxa
taxi
tom
top
tot
wop
wot

Am I inputting it in wrong? What does the dictionary file supose'd to look like, is it just a file of words on every line?

[Duoas]

Yep. Those are all the possible solutions for the given gameboard. (Your post is missing the first 39 answers though.) There are 338 solutions for that board using the default "word.lst" file.

Believe it or not those are all valid English words. :-O

(The fourth one you posted is even an olde potty word. :scared: )

My old Parker Brothers Boggle game box has the following puzzle pictured:

SGHB
TAIM
EURO
DCLA

...which produces 350 solutions out of "word.lst".

It seems I goofed when handling Qu... let me fix that...

[iamthwee]

Huh?

http://www.circlemud.org/~jelson/software/netboggle.pl

Says different for my original 4 x 4 grid.

bog dew
bog deaf
bog daw
bog daff
bog dak
bog wed
bog weak
bog weka
bog wad
bog wade
bog wae
bog waff
bog waffed
bog wake
bog waked
bog jiff
bog jimp
bog jade
bog jaw
bog jawed
bog jake
bog imp
bog eff
bog awe
bog awed
bog aff
bog fad
bog fade
bog fake
bog faked
bog fop
bog miff
bog miffed
bog moa
bog mop
bog mow
bog mot
bog kea
bog kef
bog kae
bog kaf
bog fed
bog few
bog oaf
bog oak
bog off
bog offed
bog opt
bog oft
bog pom
bog pow
bog pot
bog woad
bog wop
bog wot
bog toad
bog toff
bog tom
bog top
bog tow

Care to explain how you interpret the rules for boggle?

[Duoas]

I'm really embarrassed about these little goofs!

Line 23 should read

if (validate_word( word, row +r, col +c, (word[ index ] == 'q') ? index +2 : index +1, touched | mask ))

and line 35 should read

if (validate_word( word, row, col, (word[ 0 ] == 'q') ? 2 : 1, (row *4) +col ))

Now it works right. You can test 'Qu's it with the gameboards:

QICK
ABCD
EFGH
IJKL
(produces "quick" as the last word)

ACEQ
NAIB
CDEF
GHIJ
(produces "aquacade" as the fourteenth word)

Too bad I can't edit my above post so people checking this out won't have to cut and paste the corrections...

Fooey.

[edit]
That list has two words each line. "bog dew" is two words.
I use the most basic rule. Each die can only be used once, and successive letters must be on one of the eight adjacent dice.

[iamthwee]

I still fail to see how those words adhere to the strict boggle 2d definition. As far as I'm aware for every word found in the grid , all letters in the word must be connected on the Boggle board horizontally, vertically, or diagonally. Yours doesn't, and even has letters that ain't in the grid.

>That list has two words each line. "bog dew" is two words.

And bog is just an arbitary word the guy uses to prefix each discovered valid word. It could be anything else.

Meh I'll leave you with it.

[Duoas]

Argh! I'm a total idiot!

I forgot to check wrap-around bounds...

I always regret it when I hack something out in 30 mins. I'll post back with a proper fix.

[conan19870619]

thanks folks. now i'm just gonna find this thing called Tournament Word List Scrabble dictionary.

[Duoas]

Here's the proper fix. 'Twas another stupidism that messed things up. The complete (working) code:

// boggle-solver.cpp
// Copyright (c) 2008 Michael Thomas Greer
// <http://www.boost.org/LICENSE_1_0.txt>

#include <algorithm>
#include <fstream>
#include <iostream>
#include <iterator>
#include <string>
using namespace std;

char gameboard[ 4 ][ 4 ];

bool validate_word( const string& word, int row, int col, int index, int touched )
  {
  if ((unsigned)index == word.length()) return true;
  for (int r = -1; r < 2; r++)
  for (int c = -1; c < 2; c++)
    {
    if (((row +r) < 0) or ((row +r) > 3) or ((col +c) < 0) or ((col +c) > 3)) continue;
    int mask = 1 << (((row +r) *4) +col +c);
    if (((touched & mask) == 0)
    &&  (gameboard[ row +r ][ col +c ] == word[ index ]))
      if (validate_word( word, row +r, col +c, (word[ index ] == 'q') ? index +2 : index +1, touched | mask ))
        return true;
    }
  return false;
  }

void process_word( const string& word )
  {
  if ((3 > word.length()) or (word.length() > 17)) return;
  for (int row = 0; row < 4; row++)
  for (int col = 0; col < 4; col++)
    if (gameboard[ row ][ col ] == word[ 0 ])
      if (validate_word( word, row, col, (word[ 0 ] == 'q') ? 2 : 1, (1 << ((row *4) +col)) ))
        cout << word << '\n';
  }

int main()
  {
  cerr << "Enter the gameboard. Use just 'Q' for 'Qu'.\n";
  for (int n = 0; n < 16; n++)
    *((char*)gameboard +n) = tolower( (cin >> ws).get() );

  ifstream words( "word.lst" );
  if (!words) return 1;
  for_each( istream_iterator <string> ( words ), istream_iterator <string> (), process_word );
  words.close();

  return 0;
  }

So I'm up to 26 lines....

iamthwee
Ah, they precede each answer with the word "cog". How... normal. Anyway, that's right, and mine matches (now).

conan
A great dictionary, though propriatary...
The dictionary I've been using sometimes repeats itself and includes acronyms at times...

Sorry for the stupid mistakes. :$