Word Puzzle ACM problem

ACM Oceania - South Pacific - 2001/2002

In certain entertainment magazines there is a type of crossword puzzle where, instead of clues for words, the cells contain positive integers. There is a hidden one-to-one correspondence with numbers and letters, and the goal of the puzzle is to assign alphabet letters to these positive numbers so that sequences of two or more letters (across the rows and down the columns) form valid words. Your task is to write a program to help solve this type of puzzles.

Input

The input will consist of a series of games. Each game will have a valid dictionary of words (preceded by a size) that can be used, followed by a puzzle grid (preceded by r and c, the number of rows and columns). Each word will be at least 2 and at most 10 characters in length from the set `a'-`z'. The dictionary size will be at most 1000 words; the dictionary entries are unique but not necessarily sorted. Each puzzle grid consists of c columns, 1 c 10, and r rows, 1 r 10, of cell numbers in the range 0-26. A positive cell number denotes a letter and a cell number of `0' denotes a ` ' (blank character). The numbers form a continuous range, thus one can expect numbers such as 0, 1, 2, 3, 4, 5 but not 0, 1, 12, 13, 24, 25. The series of games is terminated by a ``game'' with dictionary size `0' and should not be processed.

Output

The output should consist of the guaranteed uniquely solved puzzle for each game, where the cell numbers are replaced with characters `a'-`z', ` '. A blank line should separate output solutions.

Sample Input

3

max

min

nix

3 4

1 2 3 0

4 0 0 0

5 4 3 0

12

boon

boonbar

boony

foobar

foorag

goon

goony

rannoo

ranoon

toon

toonbar

toony

6 6

1 2 2 3 4 5

2 0 0 2 0 0

2 0 0 2 0 6

5 4 7 7 2 2

4 0 0 8 0 2

9 0 0 0 0 7

0

Sample Output

max

i

nix

foobar

o o

o o t

rannoo

a y o

g n

Solution

Please refer the files def.h and main.cpp for solution. matrix.txt, words.txt and matrix1.txt, words1.txt are examples.

Download: puzzle.zip

02/28/2008

C++ STL set example

/*
* C++ STL set example
* Anwar Mamat anwar@cse.unl.edu
*/
#include "set"
#include "iostream"
using namespace std;

class Student{
public:
int num;
string name;
};


class Comp
{
public:
bool operator()(Student s1, Student s2)
{
if(s1.num < s2.num )
return true;
else
return false;
}
};

int main(int argc, char* argv[])
{
set ＜Student, Comp＞ myStudent;

Student a1;
Student a2;

a1.num = 10;
a1.name = "Anwar";

a2.num = 5;
a2.name = "Ziale";

myStudent.insert(a1);
myStudent.insert(a2);
myStudent.insert(a1);

cout << "The number of students " << myStudent.size() << endl;

set ＜Student, Comp＞::iterator it;
for( it = myStudent.begin(); it != myStudent.end(); it++ ) {
cout << it-＞num << "\t" << it-＞name << endl;
}
return 0;
}

Uyghur Input Text Box Linux C++ code

After so many years of MFC programming on Windows, I tried my first C++ GUI code on Linux. I installed the Qt4.3 on OpenSuse 10.3 and tested this (classic) Uyghur Input Text Box.

The Textbox works fine. It can map the keyboard input to the user defined strings. User can map the key press event to any string, so that this code can be modified to input any language. It is a free code, withoot fancy features. It is tested on OpenSuse 10.3 with Qt4.3. Please enjoy.

-------------------------
File 1: main.cpp
------------------------
/*
* This is a free software. Please feel free to modify
* and improve it.
*
* UTextEdit class inherits the QTextEdit class and changes the
* key press event.
*
*
* compile:
* qmake -project
* qmake
* make
*
* Tested on OpenSuse10.3 with Qt4.3
*
* Anwar Mamat anwar@cse.unl.edu
* Feb 4,2008
*/

#include "interface.h"

int main(int argc, char *argv[])
{
QApplication app(argc, argv);
MyWidget uEdit;

uEdit.show();

return app.exec();
}


--------------------------
file 2: utextedit.h
--------------------------
/*
* UTextEdit Class
* This class inherits the QTextEdit class, intercepts the
* keypress events, and changes the keypress events based
* on the user predefined mapping.
*
* This is a free code. Please feel free to modify it.
*
* Anwar Mamat anwar@cse.unl.edu
* Feb 4,2008
*/

#ifndef UTEXTEDIT_H
#define UTEXTEDIT_H

#include "QtCore/QVariant"
#include "QtGui/QApplication"
#include "QtGui/QTextEdit"
#include "QtGui/QWidget"
#include "QKeyEvent"

class UTextEdit : public QTextEdit
{
Q_OBJECT
public:
UTextEdit(QWidget *parent = 0);

protected:
void keyPressEvent(QKeyEvent *e);

};

#endif //UTEXTEDIT_H

File3: utextedit.cpp

#include "utextedit.h"

UTextEdit::UTextEdit(QWidget *parent)

: QTextEdit(parent)

{

}

void UTextEdit::keyPressEvent(QKeyEvent *e)

{

QString Latin = {"abcdefghijklmnopqrstuvwxyz ABCDEFGHIJKLMNOPQRSTUVWXYZ/?.,:;"};

char Uyghur[][5] = {

"ھ",//a

"ب",//b

"غ",//c

"د",//d

"ې",//e

"ا",//f

"ە",//g

"ى",//h

"ڭ",//i

"ق",//j

"ك",//k

"ل",//l

"م",//m

"ن",//n

"و",//o

"پ",//p

"چ",//q

"ر",//r

"س",//s

"ت",//t

"ۇ",//u

"ۈ",//v

"ۋ",//w

"ش",//x

"ي",//y

"ز",//z

" ",// space

"",// A

"",// B

"",// C

"ژ",// D

"",//E

"ف",//F

"گ",//G

"خ",//H

"",//I

"ج",//J

"ۆ",//K

"لا",//L

"",//M

"",//N

"",//O

"",//P

"",//Q

"",//R

"",//S

"",//T

"",//U

"",//V

"",//W

"",//X

"",//Y

"",//Z

"ئ", // /

"؟",//?

".",//.

"،",//,

":",//:

"؛",//;

};

//Do something here.

switch (e->key()) {

case Qt::Key_Enter:

case Qt::Key_Return:

case Qt::Key_Escape:

case Qt::Key_Tab:

case Qt::Key_Backtab:

e->ignore();

return;

}

unsigned int iPos = Latin.indexOf(e->text()) ;

//Intercept the predefined keyevents

if(e->key() < style="color: blue;">sizeof(Uyghur) / 5 )

{

QKeyEvent ker(QKeyEvent::KeyPress, Qt::Key_0, 0, QObject::trUtf8(Uyghur[iPos]), 0);

QTextEdit::keyPressEvent(&ker);

}

else //other keys

QTextEdit::keyPressEvent(e);

}

----------------------

file 4: interface.4

#ifndef INTERFACE_H

#define INTERFACE_H

#include "QObject"

#include "QtGui/QApplication"

#include "QtGui/QWidget"

#include "QMessageBox"

#include "QPushButton"

class MyWidget : public QWidget

{

Q_OBJECT

public:

MyWidget(QWidget *parent = 0);

public slots:

void about();

};

#endif //INTERFACE_H

--------------------------

file 5: interface.cpp

--------------------------

#include "interface.h"

#include "utextedit.h"

void MyWidget::about()

{

QMessageBox::about(this, "UTextEdit","A simple Uyghur Input Program.");

}

MyWidget::MyWidget(QWidget *parent )

: QWidget(parent)

{

setFixedSize(640, 240);

QPushButton *quit = new QPushButton(tr("Quit"), this);

QPushButton *about = new QPushButton(tr("About"), this);

UTextEdit *txtBox = new UTextEdit(this);

quit->setGeometry(480, 200, 60, 30);

quit->setFont(QFont("Times", 14, QFont::Bold));

about->setGeometry(540, 200, 80, 30);

about->setFont(QFont("Times", 14, QFont::Bold));

txtBox->setGeometry(10,10,620,180);

txtBox->setFont(QFont("UKIJ Tuz", 24, QFont::Bold));

txtBox->setAlignment(Qt::AlignRight);

connect(quit, SIGNAL(clicked()), qApp, SLOT(quit()));

connect(about, SIGNAL(clicked()), this, SLOT(about(void)));

}