604 - The Boggle Game

All about problems in Volume 6. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

User avatar
shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

604 Boggle Game(Resolved)

Post by shamim » Thu Jul 08, 2004 11:25 am

I am getting WA in this problem. I tried all sort of input, yet i could not find any mistake. I was really frustrated and submitted this to acm.zju.edu.cn.
I got AC there. The run-time indicates that they have very few data. But I still don't understand as to why my code would get WA.

I used C++. I first obtained all valid words from first board using recursion and stored them in a <map>.

For the second board, I again searched for all valid word, but i put them in a new <map> only if they existed in the first one.

Then I printed all the words in the second map, if any existed, otherwise
"There are no common words for this pair of boggle boards."

I cleared both the map before processing a new set of boards.

Here is my code:

[cpp]

AC now
[/cpp]
Last edited by shamim on Sat Jul 10, 2004 7:19 am, edited 1 time in total.

tat tvam asi
New poster
Posts: 30
Joined: Sat Nov 30, 2002 1:04 pm

Post by tat tvam asi » Fri Jul 09, 2004 9:07 pm


medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

604 - WA. Help me!

Post by medv » Fri May 20, 2005 10:05 pm

Hello! I tried a lot of tests, but get WA.
I don't know why. I even found author's test data
(in previous board messages were links there).
My program works well. But getting WA.

#pragma warning(disable:4786)
#include <cstdio>
#include <memory>
#include <set>
#include <string>
using namespace std;

set<string> SetS,Result;
set<string>::iterator iter;
char board0[4][4], board1[4][4];
char c[1];
char s[5];
int used[4][4];

int isvowel(char ch)
{
if ((ch == 'A') || (ch == 'O') || (ch == 'I') || (ch == 'U')
|| (ch == 'Y') || (ch == 'E')) return 1;
return 0;
}

int Accepted(string s)
{
int i,v=2;
if (s.size() != 4) return 0;
for (i=0;i<4;i++)
if (isvowel(s[i])) v--;
if (v) return 0;
else return 1;
}

void FindWords(int BoardNo, int posx, int posy, int depth)
{
int i,j;
if (depth == 4)
{
if ((!BoardNo) && (Accepted(s))) SetS.insert(s); else
if (SetS.find(s) != SetS.end()) Result.insert(s);
return;
}
for(i=-1;i<=1;i++)
for(j=-1;j<=1;j++)
{
if (!i && !j) continue;
if ((posx + i > 3) || (posx + i < 0) || (posy + j > 3) || (posy + j < 0)) continue;
if (!used[posx+i][posy+j]) continue;
s[depth] = (!BoardNo) ? board0[posx+i][posy+j] : board1[posx+i][posy+j];
used[posx+i][posy+j] = 0;
FindWords(BoardNo, posx+i,posy+j,depth+1);
used[posx+i][posy+j] = 1;
}
}

int main(void)
{
int i,j;
while (1)
{
Result.clear();
for(i=0;i<4;i++)
for(j=0;j<8;j++)
{
scanf("%s",c);
if (c[0] == '#') exit(0);
if (j < 4) board0[i][j] = c[0];
else board1[i][j-4] = c[0];
}

memset(used,1,sizeof(used));
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
s[0] = board0[i][j];
used[i][j] = 0;
FindWords(0,i,j,1);
used[i][j] = 1;
}

memset(used,1,sizeof(used));
for(i=0;i<4;i++)
for(j=0;j<4;j++)
{
s[0] = board1[i][j];
used[i][j] = 0;
FindWords(1,i,j,1);
used[i][j] = 1;
}

if (!Result.size()) printf("There are no common words for this pair of boggle boards.\n\n"); else
{
for(iter=Result.begin();iter!=Result.end();iter++)
printf("%s\n",(*iter).c_str());
printf("\n");
}
}
return 0;
}

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Wed Mar 15, 2006 2:56 am

you should generate the words in the first square and at the same time check to see if the square are adjacent. you can do that using dfs to do the backtracking. Then you generate words in the second square, and output only those that are found in first square. You can also use the number of vowels to prune. It should run in less than 1 sec if done properly.

ThanhNhan
New poster
Posts: 15
Joined: Sun Aug 08, 2004 12:24 am

Post by ThanhNhan » Tue Mar 28, 2006 5:36 am

You do not get all words of length 4. After a word is found, you need to get to another free square which is not needed.

example
AE..
BC..
......
......

Your code do not accept BCEA as a word.

lyh91208
New poster
Posts: 4
Joined: Mon Mar 20, 2006 1:26 pm
Location: Taipei

604 The Boggle Game WA

Post by lyh91208 » Tue May 09, 2006 5:20 am

I tried to solve this problem some days before, but WA.
Today I tried it again, but still failed.
I have used all the test data on the board to test my program, and all ouput of my program are as same as that on the board.
So, can someone help me or give me more test data?

Thanks in advance.

Code: Select all

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

char matrix[2][4][4],make[5],list[20000][5];
int listcount,has[2][20001],used[4][4],exist[3][27];
int step[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};

int getid()
{
    int i;
    for(i=1;i<=listcount;i++) if(strcmp(make,list[i])==0) return i;
    listcount++;
    strcpy(list[listcount],make);
    return listcount;
}

int isvowel(char c)
{
    if(c=='A'||c=='E'||c=='I'||c=='O'||c=='U'||c=='Y') return 1;
    else return 0;
}

void go(int box,int x,int y,int level,int vo,int nvo)
{
    if(isvowel(matrix[box][x][y])==1) vo++; else nvo++;
    if(vo>2||nvo>2) return;
    make[level] = matrix[box][x][y];
    int i;
    if(level==3)
    {
        int i;
        make[4] = '\0';
        i = getid();
        has[box][i] = 1;
        return;
    }
    used[x][y] = 1;
    for(i=0;i<8;i++)
    {
        if(x+step[i][0]>3||x+step[i][0]<0||y+step[i][1]>3||y+step[i][1]<0) continue;
        if(used[x+step[i][0]][y+step[i][1]]==1) continue;
        if(matrix[box][x+step[i][0]][y+step[i][1]]=='#') continue;
        go(box,x+step[i][0],y+step[i][1],level+1,vo,nvo);
    }
    used[x][y] = 0;
}

main()
{
    int i,j,k,m,n,end=0,line,commoncount;
    char word[31],common[10000][5],tmp[5];
    for(i=0;i<4;i++) for(j=0;j<4;j++) used[i][j] = 0;
    while(1)
    {
        line = listcount = 0;
        for(i=1;i<=26;i++) exist[0][i] = exist[1][i] = 0;
        for(i=1;i<=20000;i++) has[0][i] = has[1][i] = 0;
        while(cin.getline(word,30,'\n'))
        {
            if(strlen(word)==0) continue;
            if(strcmp(word,"#")==0)
            {
                end = 1;
                break;
            }
            matrix[0][line][0] = word[0];  matrix[0][line][1] = word[2];
            matrix[0][line][2] = word[4];  matrix[0][line][3] = word[6];
            matrix[1][line][0] = word[11];  matrix[1][line][1] = word[13];
            matrix[1][line][2] = word[15];  matrix[1][line][3] = word[17];
            line++;
            if(line==4) break;
        }
        if(end) break;
        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
            {
                exist[0][matrix[0][i][j]-'A'+1]++;
                exist[1][matrix[1][i][j]-'A'+1]++;
            }
        }
        for(i=1;i<=26;i++)
        {
            if(exist[0][i]>0&&exist[1][i]>0)
                exist[2][i] = 1;
            else
                exist[2][i] = 0;
        }
        for(i=0;i<4;i++)
        {
            for(j=0;j<4;j++)
            {
                if(exist[2][matrix[0][i][j]-'A'+1]==0) matrix[0][i][j] = '#';
                if(exist[2][matrix[1][i][j]-'A'+1]==0) matrix[1][i][j] = '#';
            }
        }
        for(k=0;k<2;k++) for(i=0;i<4;i++) for(j=0;j<4;j++) if(matrix[k][i][j]!='#') go(k,i,j,0,0,0);
        commoncount = 0;
        for(i=1;i<=listcount;i++)
        {
            if(has[0][i]==1&&has[1][i]==1)
            {
                commoncount++;
                strcpy(common[commoncount],list[i]);
            }
        }
        for(i=1;i<=commoncount-1;i++)
        {
            for(j=1;j<=commoncount-i;j++)
            {
                if(strcmp(common[j],common[j+1])==1)
                {
                    strcpy(tmp,common[j]);
                    strcpy(common[j],common[j+1]);
                    strcpy(common[j+1],tmp);
                }
            }
        }
        if(commoncount==0) cout << "There are no common words for this pair of boggle boards." << endl << endl;
        else
        {
            for(i=1;i<=commoncount;i++) cout << common[i] << endl;
            cout << endl;
        }
    }
}


serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Fri May 12, 2006 7:21 pm

Hi lyh!

If You want to know how I did it (just in case you will find it useful :) )- I used binary search trees, but while inserting compared words with a special function.
Last edited by serur on Sat Apr 14, 2012 3:29 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

rub.l
New poster
Posts: 1
Joined: Mon Nov 06, 2006 2:11 am
Contact:

604 need help

Post by rub.l » Mon Nov 06, 2006 2:23 am

I don

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

Re: 604 - Boggle Game

Post by DD » Fri Nov 07, 2008 4:58 pm

lyh91208 wrote:I tried to solve this problem some days before, but WA.
Today I tried it again, but still failed.
I have used all the test data on the board to test my program, and all ouput of my program are as same as that on the board.
So, can someone help me or give me more test data?

Thanks in advance.

Code: Select all

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

char matrix[2][4][4],make[5],list[20000][5];
int listcount,has[2][20001],used[4][4],exist[3][27];
int step[8][2]={{0,1},{1,1},{1,0},{1,-1},{0,-1},{-1,-1},{-1,0},{-1,1}};

int getid()
{
int i;
for(i=1;i<=listcount;i++) if(strcmp(make,list[i])==0) return i;
listcount++;
strcpy(list[listcount],make);
return listcount;
}

int isvowel(char c)
{
if(c=='A'||c=='E'||c=='I'||c=='O'||c=='U'||c=='Y') return 1;
else return 0;
}

void go(int box,int x,int y,int level,int vo,int nvo)
{
if(isvowel(matrix[box][x][y])==1) vo++; else nvo++;
if(vo>2||nvo>2) return;
make[level] = matrix[box][x][y];
int i;
if(level==3)
{
int i;
make[4] = '\0';
i = getid();
has[box][i] = 1;
return;
}
used[x][y] = 1;
for(i=0;i<8;i++)
{
if(x+step[i][0]>3||x+step[i][0]<0||y+step[i][1]>3||y+step[i][1]<0) continue;
if(used[x+step[i][0]][y+step[i][1]]==1) continue;
if(matrix[box][x+step[i][0]][y+step[i][1]]=='#') continue;
go(box,x+step[i][0],y+step[i][1],level+1,vo,nvo);
}
used[x][y] = 0;
}

main()
{
int i,j,k,m,n,end=0,line,commoncount;
char word[31],common[10000][5],tmp[5];
for(i=0;i<4;i++) for(j=0;j<4;j++) used[i][j] = 0;
while(1)
{
line = listcount = 0;
for(i=1;i<=26;i++) exist[0][i] = exist[1][i] = 0;
for(i=1;i<=20000;i++) has[0][i] = has[1][i] = 0;
while(cin.getline(word,30,'\n'))
{
if(strlen(word)==0) continue;
if(strcmp(word,"#")==0)
{
end = 1;
break;
}
matrix[0][line][0] = word[0]; matrix[0][line][1] = word[2];
matrix[0][line][2] = word[4]; matrix[0][line][3] = word[6];
matrix[1][line][0] = word[11]; matrix[1][line][1] = word[13];
matrix[1][line][2] = word[15]; matrix[1][line][3] = word[17];
line++;
if(line==4) break;
}
if(end) break;
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
exist[0][matrix[0][i][j]-'A'+1]++;
exist[1][matrix[1][i][j]-'A'+1]++;
}
}
for(i=1;i<=26;i++)
{
if(exist[0][i]>0&&exist[1][i]>0)
exist[2][i] = 1;
else
exist[2][i] = 0;
}
for(i=0;i<4;i++)
{
for(j=0;j<4;j++)
{
if(exist[2][matrix[0][i][j]-'A'+1]==0) matrix[0][i][j] = '#';
if(exist[2][matrix[1][i][j]-'A'+1]==0) matrix[1][i][j] = '#';
}
}
for(k=0;k<2;k++) for(i=0;i<4;i++) for(j=0;j<4;j++) if(matrix[k][i][j]!='#') go(k,i,j,0,0,0);
commoncount = 0;
for(i=1;i<=listcount;i++)
{
if(has[0][i]==1&&has[1][i]==1)
{
commoncount++;
strcpy(common[commoncount],list[i]);
}
}
for(i=1;i<=commoncount-1;i++)
{
for(j=1;j<=commoncount-i;j++)
{
if(strcmp(common[j],common[j+1])==1)
{
strcpy(tmp,common[j]);
strcpy(common[j],common[j+1]);
strcpy(common[j+1],tmp);
}
}
}
if(commoncount==0) cout << "There are no common words for this pair of boggle boards." << endl << endl;
else
{
for(i=1;i<=commoncount;i++) cout << common[i] << endl;
cout << endl;
}
}
}

Your program fail to pass the following input.

Input:

Code: Select all

H G A V					G S F U
U N G O					A H F T
Y T G I					G N A L
B G O P					B O P L

#
Your program output:

Code: Select all

There are no common words for this pair of boggle boards.
Correct output:

Code: Select all

ANGO
AOGN
GAGO
GNAO
GOAN
HNAO
NAGO
NAOG
NGOA
OANG
OANH
OGAG
OGAN
OGNA
Good luck! 8)
Have you ever...
  • Wanted to work at best companies?
  • Struggled with interview problems that could be solved in 15 minutes?
  • Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 604 - Boggle Game

Post by Jehad Uddin » Sun Jul 26, 2009 12:19 pm

Hello every body, i m getting WA in this pro,i cant understand about blank lines.. Here is my code.

Code: Select all

#include<iostream>
#include<string>
using namespace std;
char word1[2000][10],word2[2000][10];
char grid1[5][5],grid2[5][5],kisu[10],kis[10],common[2000][10];
bool tr1[5][5],tr2[5][5],gr1[2000],gr2[2000];
long int cnt1,cnt2; 
bool isbig(char *from,char *to)
{
 long int i,j=1;
 for(i=0;i<4;i++)
 
  if(from[i]<to[i])
  {
   j=0;
   break;
  }
  else if(from[i]>to[i])
  {
   j=1;
   break;
  }
 if(j) return true;
 else return false;

}

bool check(char *wr)
{
 long int i,j,k=0,m,l=1;
 j=strlen(wr);
 for(i=0;i<j;i++)
	 if(wr[i]=='A'||wr[i]=='E'||wr[i]=='I'||wr[i]=='O'||wr[i]=='U')
		 k++;
 
 if(k==2&&l==1) return true;
 else return false;
}
void wordmaker1(long int i,long int j,long int count)
{
 if(count==4)
 {
  kisu[count]='\0';
  if(check(kisu))
  {
   strcpy(word1[cnt1],kisu);
   cnt1++;
  }
 
 }
 else
 {
  if(i+1<4&&j+1<4&&tr1[i+1][j+1])
  {
   tr1[i+1][j+1]=false;
   kisu[count]=grid1[i+1][j+1];
   wordmaker1(i+1,j+1,count+1);
   tr1[i+1][j+1]=true;
  }
  if(i+1<4&&tr1[i+1][j])
  {
   tr1[i+1][j]=false;
   kisu[count]=grid1[i+1][j];
   wordmaker1(i+1,j,count+1);
   tr1[i+1][j]=true;
  }
  if(i+1<4&&j-1>=0&&tr1[i+1][j-1])
  {
   tr1[i+1][j-1]=false;
   kisu[count]=grid1[i+1][j-1];
   wordmaker1(i+1,j-1,count+1);
   tr1[i+1][j-1]=true;
  }
  if(j+1<4&&tr1[i][j+1])
  {
   tr1[i][j+1]=false;
   kisu[count]=grid1[i][j+1];
   wordmaker1(i,j+1,count+1);
   tr1[i][j+1]=true;
  }
  if(j-1>=0&&tr1[i][j-1])
  {
   tr1[i][j-1]=false;
   kisu[count]=grid1[i][j-1];
   wordmaker1(i,j-1,count+1);
   tr1[i][j-1]=true;
  }
  if(i-1>=0&&tr1[i-1][j])
  {
   tr1[i-1][j]=false;
   kisu[count]=grid1[i-1][j];
   wordmaker1(i-1,j,count+1);
   tr1[i-1][j]=true;
  }
  if(i-1>=0&&j+1<4&&tr1[i-1][j+1])
  {
   tr1[i-1][j+1]=false;
   kisu[count]=grid1[i-1][j+1];
   wordmaker1(i-1,j+1,count+1);
   tr1[i-1][j+1]=true;
  }
  if(i-1>=0&&j-1>=0&&tr1[i-1][j-1])
  {
   tr1[i-1][j-1]=false;
   kisu[count]=grid1[i-1][j-1];
   wordmaker1(i-1,j-1,count+1);
   tr1[i-1][j-1]=true;
  }
 
 
 }


}
void wordmaker2(long int i,long int j,long int count)
{
 if(count==4)
 {
  kis[count]='\0';
  if(check(kis))
  {
   strcpy(word2[cnt2],kis);
   cnt2++;
  }
 
 }
 else
 {
  if(i+1<4&&j+1<4&&tr2[i+1][j+1])
  {
   tr2[i+1][j+1]=false;
   kis[count]=grid2[i+1][j+1];
   wordmaker2(i+1,j+1,count+1);
   tr2[i+1][j+1]=true;
  }
  if(i+1<4&&tr2[i+1][j])
  {
   tr2[i+1][j]=false;
   kis[count]=grid2[i+1][j];
   wordmaker2(i+1,j,count+1);
   tr2[i+1][j]=true;
  }
  if(i+1<4&&j-1>=0&&tr2[i+1][j-1])
  {
   tr2[i+1][j-1]=false;
   kis[count]=grid2[i+1][j-1];
   wordmaker2(i+1,j-1,count+1);
   tr2[i+1][j-1]=true;
  }
  if(j+1<4&&tr2[i][j+1])
  {
   tr2[i][j+1]=false;
   kis[count]=grid2[i][j+1];
   wordmaker2(i,j+1,count+1);
   tr2[i][j+1]=true;
  }
  if(j-1>=0&&tr2[i][j-1])
  {
   tr2[i][j-1]=false;
   kis[count]=grid2[i][j-1];
   wordmaker2(i,j-1,count+1);
   tr2[i][j-1]=true;
  }
  if(i-1>=0&&tr2[i-1][j])
  {
   tr2[i-1][j]=false;
   kis[count]=grid2[i-1][j];
   wordmaker2(i-1,j,count+1);
   tr2[i-1][j]=true;
  }
  if(i-1>=0&&j+1<4&&tr2[i-1][j+1])
  {
   tr2[i-1][j+1]=false;
   kis[count]=grid2[i-1][j+1];
   wordmaker2(i-1,j+1,count+1);
   tr2[i-1][j+1]=true;
  }
  if(i-1>=0&&j-1>=0&&tr2[i-1][j-1])
  {
   tr2[i-1][j-1]=false;
   kis[count]=grid2[i-1][j-1];
   wordmaker2(i-1,j-1,count+1);
   tr2[i-1][j-1]=true;
  }
 
 
 }

}

int main()
{
 long int i,j,k,l=0,m,p,q,r,s;
	string str;
	char ch2[10];
 while(getline(cin,str,'\n'))
 {
  if(str[0]=='#') break;
 cout<<endl;
  for(i=0,k=0,j=0;i<str.length();i++)
  {
   if(k<4&&str[i]>=65&&str[i]<=90)
	   grid1[0][k++]=str[i];
   else if(k>=4&&str[i]>=65&&str[i]<=90)
	   grid2[0][j++]=str[i];
  }
  for(p=1;p<4;p++)
  {
   getline(cin,str,'\n');
   for(i=0,k=0,j=0;i<str.length();i++)
   {
    if(k<4&&str[i]>=65&&str[i]<=90)
	   grid1[p][k++]=str[i];
    else if(k>=4&&str[i]>=65&&str[i]<=90)
	   grid2[p][j++]=str[i];
   }
  
  
  }
  cnt1=0,cnt2=0;
  for(i=0;i<4;i++)
	  for(j=0;j<4;j++)
	  {
		 
		  tr1[i][j]=true;
	      tr2[i][j]=true;
	  }
 for(i=0;i<4;i++)
	 for(j=0;j<4;j++)
	 {
	   
		 
		 kisu[0]=grid1[i][j];
	  kis[0]=grid2[i][j];
	  tr1[i][j]=false;
	  tr2[i][j]=false;
	  wordmaker1(i,j,1);
	  wordmaker2(i,j,1);
	  tr1[i][j]=true;
	  tr2[i][j]=true;
	 
	 }
 
 for(i=0;i<cnt1;i++)
	 gr1[i]=true;
 for(i=0;i<cnt2;i++)
	 gr2[i]=true;
 for(i=0,q=0;i<cnt1;i++)
	 for(j=0;j<cnt2;j++)
		 if(gr1[i]&&gr2[j]&&strcmp(word1[i],word2[j])==0)
		 {
		  gr1[i]=false;
		  gr2[j]=false;
          for(r=0,s=1;r<q;r++)
			  if(strcmp(common[r],word1[i])==0)
				  s=0;
			  if(s) {strcpy(common[q],word1[i]);
			  q++;}
		 }
 
 for(i=1;i<q;i++)
	 for(j=q-1;j>=i;j--)
	 {
	  if(isbig(common[j-1],common[j]))
	  {
	   strcpy(ch2,common[j-1]);
	   strcpy(common[j-1],common[j]);
	   strcpy(common[j],ch2);
	  
	  }
	 
	 }
		 
 for(i=0;i<q;i++)
	 cout<<common[i]<<endl;
	 if(!q) cout<<"There are no common words for this pair of boggle boards."<<endl;
  cout<<endl;
	 l++;
  
 }


 return 0;
}
Advanced thanks to helpers.

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 604 - Boggle Game

Post by Jehad Uddin » Thu Aug 06, 2009 12:15 pm

no body is replying yet?? pls help!!!!!!

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 604 - Boggle Game

Post by Shafaet_du » Mon May 09, 2011 10:50 pm

input:

Code: Select all

A E F G    M L A E
P G T G    A P G T
Z C D E    Z C D E
F G R E    G R E K

#
out:

Code: Select all

AEGC
AEGD
AEGP
AEGT
AETD
AETG
AGDE
AGET
AGTE
APGE
CDEE
CGAE
CGEA
CPAE
CREE
DEEG
DEER
DEET
DETE
DGAE
DGEA
DGEE
DREE
DTEA
DTEE
EAGC
EAGD
EAGP
EAGT
EAPC
EAPG
EAPZ
EDEG
EDER
EDET
EDGA
EDGE
EDRE
EDTE
EEDC
EEDG
EEDR
EEDT
EEGD
EEGT
EERC
EERD
EERG
EETD
EETG
EGAP
EGDE
EGPA
EGTE
ERDE
ETDE
ETED
ETEG
ETGA
ETGE
GAET
GDEE
GEAP
GEDE
GEED
GEER
GETE
GPAE
GREE
GTEA
GTEE
PAEG
PAET
PAGE
PGAE
PGEA
RDEE
REDE
REED
REEG
REET
TDEE
TEAG
TEAP
TEDE
TEED
TEER
TEGA
TGAE
TGEA
TGEE
ZPAE
use backtrack,generate all the words and check in hash table to find the commons.

valeriAsus
New poster
Posts: 5
Joined: Wed Mar 07, 2012 10:53 pm

wrong answer The boggle game

Post by valeriAsus » Thu Mar 15, 2012 1:20 pm

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.regex.Pattern;
import java.util.Collections;

class Main{
	
	public static void main(String args[]) throws IOException{
	    MaterialePerK matPerK[]= new MaterialePerK[16];
	        
	        int Adiac0 []={1,4,5};
		     matPerK[0]= new MaterialePerK(new CellaBoggle(0, 0),Adiac0 );
		    int Adiac1[]={0,4,5,6,2};
			 matPerK[1]= new MaterialePerK(new CellaBoggle(0, 1),Adiac1 );
			 int Adiac2[]={1,5,6,3,7};	
			 matPerK[2]= new MaterialePerK(new CellaBoggle(0, 2),Adiac2 );
			 int Adiac3[]={2,6,7};
			  matPerK[3]= new MaterialePerK(new CellaBoggle(0, 3),Adiac3 );
		
			  
			 int Adiac4[]= {0,1,5,9,8};
			   matPerK[4]= new MaterialePerK(new CellaBoggle(1, 0),Adiac4);
			 int Adiac5[]= {4,0,1,2,6,10,9,8};
			 matPerK[5]= new MaterialePerK(new CellaBoggle(1, 1),Adiac5 );	
			 int Adiac6[]={5,1,2,3,7,11,10,9};
			 matPerK[6]= new MaterialePerK(new CellaBoggle(1, 2),Adiac6 );	
	 		 int Adiac7[]={3,2,6,10,11};
			 matPerK[7]= new MaterialePerK(new CellaBoggle(1, 3),Adiac7 );	
			 
			 int Adiac8[]={4,5,9,13,12};		 
			 matPerK[8]= new MaterialePerK(new CellaBoggle(2, 0),Adiac8 );	
			 int Adiac9[]={8,4,5,6,10,14,13,12};		
			 matPerK[9]= new MaterialePerK(new CellaBoggle(2, 1),Adiac9);	
			 int Adiac10[]={9,5,6,7,11,15,14,13};
			 matPerK[10]= new MaterialePerK(new CellaBoggle(2, 2),Adiac10);
			 int Adiac11[]={7,6,10,14,15};
			 matPerK[11]= new MaterialePerK(new CellaBoggle(2, 3),Adiac11);
			 
	         int Adiac12[]={8,9,13};		 
	         matPerK[12]= new MaterialePerK(new CellaBoggle(3, 0),Adiac12);
	         int Adiac13[]={12,8,9,10,14};	
	         matPerK[13]= new MaterialePerK(new CellaBoggle(3, 1),Adiac13);
	         int Adiac14[]={13,9,10,11,15};	
	         matPerK[14]= new MaterialePerK(new CellaBoggle(3, 2),Adiac14);
	         int Adiac15[]={11,10,14};
	         matPerK[15]= new MaterialePerK(new CellaBoggle(3,3),Adiac15);
            
	         ContenitorePigEwu C= new ContenitorePigEwu();
	         GrafoBoggle Gr= new GrafoBoggle(matPerK,C);
	         LeggiPreparaM L= new LeggiPreparaM(Gr);
	          L.LeggiRigheM();
}	

 static class CellaBoggle {
    private int Righe,Col;
	
	public CellaBoggle(int r,int c){
       Righe=r;  Col=c;		
	}
	int getRiga(){ return Righe;  }
	int getCol(){  return Col;    }
	
	void setRiga(int r){Righe=r;  }
	void setCol(int c){ Col=c;    }
 }

 static class MaterialePerK {
	    private int NodiAdiacenti[];
		private CellaBoggle C;
		
		public MaterialePerK(CellaBoggle cb,int adiac[]) {
	      C=cb; 
		   NodiAdiacenti= adiac;
		}
		
		CellaBoggle getCellaBoggle(){ 
			return C; }
		

		void setArrayAdiac(int ind,int val){
			NodiAdiacenti[ind]=val;
		}

	    int [] getArrayAdiac(){
	    	return NodiAdiacenti;
	    }

	}


 static class LeggiPreparaM {
 	private GrafoBoggle Gr;
 	private String Riga;	
 	 private char B1[][];
     private char B2[][];
     private StringTokenizer st;
     private BufferedReader In_Str;
     private String pattern = "([A-Z] ){3}[A-Z]{1}(\t)+([A-Z] ){3}[A-Z]";
     private Pattern p = Pattern.compile(pattern);
     
    LeggiPreparaM(GrafoBoggle G) {
     Riga="";    B1=new char[4][4];    B2=new char[4][4];   st=null;   
     In_Str = new BufferedReader(new InputStreamReader(System.in));  Gr=G;
 	}

 	 char[][] getB1() {
 		return B1;
 	}
 	
 	 char[][] getB2() {
 		return B2;
 	}
 	
     void LeggiRigheM()throws IOException{
       int R;   boolean cicla=true;
       try{
       while(true){	
 		    	R=0;
 			    while(R<4){
                      
 			    	   Riga=In_Str.readLine();
 			    	   if(Riga.equals("#") )
                               return ;   
 			    	   
                   	        System.out.println();
 			             
          						    st= new StringTokenizer(Riga," 	");
 						      AssegnaRiga(B1,R,0);
 						      AssegnaRiga(B2,R,0);
 			    R++;
 			    }
 		               Gr.TrovaParolePigEwu(getB1(),false);
     		         
     		    
      		       if(!Gr.TrovaParolePigEwu(getB2(),true)){
 		               System.out.println("There are no common words for this pair of boggle boards.");
 		              System.out.println();
 	        	       }  

      		       
      		       
 		        Gr.getContenitoreParole().rimuoviVettore();   
                Gr.getContenitoreParole().allocaVettore();
                Gr.getContenitoreParole().setCiSonoComuni(false);  
 	 
 	  }	

     }catch (IOException e) {
    	 return;
     }
 }

         void AssegnaRiga(char B[][],int R,int C1){
 		   while(st.hasMoreTokens() && C1<4){
         	  B[R][C1] = st.nextToken().charAt(0);
         	C1++;
            }
             return ;
 	}
 	
 }

  static class ContenitorePigEwu {
	  
	private boolean ciSonoComuni;  	
  	private Vector<ArrayList<String>>  parole = new Vector<ArrayList<String>>(26); 
  	private ArrayList<String>  paroleComuni ;
 
  	
  	 ContenitorePigEwu(){
  		for(int i=0 ; i<26 ;i++){
  	       parole.insertElementAt(new ArrayList<String>(),i);
  		}  
  	   ciSonoComuni=false;
      paroleComuni= new ArrayList<String>();
  	 }
  	
  	 public Vector<ArrayList<String>> getParole() {
		return parole;
	}
  	 
  	 public ArrayList<String> getParoleComuni() {
		return paroleComuni;
	}
  	 
  	 boolean ciSonoComuni(){
  		 return ciSonoComuni;
  	 }
  	 
  	 void setCiSonoComuni(boolean p){
  	     	 ciSonoComuni=p;
  	 }

  	 void rimuoviVettore(){
  		     parole.removeAllElements();
          paroleComuni.clear();
  	 }

  	void allocaVettore(){
      for(int i=0 ; i<26 ;i++)
   	     parole.insertElementAt(new ArrayList<String>(),i);
         paroleComuni= new ArrayList<String>();
  	}
	
  	void inserInOrdineParolaDatoUnaCella(String parola){
     	 int indVett= parola.charAt(0)-65;
  	    parole.get(indVett).add(parola);
  	}

  	void ordinaVettore(ArrayList<String>  arr){
	    	Collections.sort(arr);
  	}
  	
  void cercaComuni(String parola2matr){
	  int indVett= parola2matr.charAt(0)-65;
	    if(parole.get(indVett).size()!=0){
		  int left, right; 
	         left = 0; 
			    right =parole.get(indVett).size();
	         
			    while (left!=right-1) {
			    	int m = (right+left)/2  ; 
			 
			    	String sm = parole.get(indVett).get(m);
			     
			    	if(sm.compareTo(parola2matr)<0) 
			            left = m; 
			        
			        else if (sm.compareTo(parola2matr)>0) 
			         right = m; 
			        else {
			         left = m;  
			         right = m+1; 
			           }
			   }
			    
			    if(parola2matr.equals(parole.get(indVett).get(left) )){
		        	   paroleComuni.add(parola2matr);
		                     ciSonoComuni=true;
		 	    } 
		}
	  	  
  }

    void stampaParoleInComune(){
    	int k=0 ;
    	for(; k<paroleComuni.size()-1; k++){
    		     
        	     if(! paroleComuni.get(k).equals(paroleComuni.get(k+1)   )   )
    	              System.out.println(paroleComuni.get(k));
                 
    	}

                 if(paroleComuni.get(k).equals(  paroleComuni.get(k-1)  )     )
                	 System.out.println(paroleComuni.get(k));
                 else {
                	 System.out.println(paroleComuni.get(k));
                 }
            	System.out.println();
            	    
    }   
    
}
    static class GrafoBoggle {

     private   HashMap<Integer,MaterialePerK> GrafoTavola =new HashMap<Integer, MaterialePerK>(16, 16) ;
     private MaterialePerK matPerK[];
     private  ContenitorePigEwu contenitoreParole;
     private boolean Decr[];
     
    GrafoBoggle(MaterialePerK mater[],ContenitorePigEwu cp){
    	contenitoreParole=cp;
          matPerK=mater;
           for(int k=0 ;k<16 ; k++) 
    	    GrafoTavola.put(k, matPerK[k]);      
              Decr= new boolean[4];
    }
    
    public ContenitorePigEwu getContenitoreParole() {
		return contenitoreParole;
	}

    boolean TrovaParolePigEwu(char B[][],boolean ConfrontoP){
     	int contaVoc=0;
     	int Nodo_K=0; 
     	for(int i=0 ; i<Decr.length ;i++)
            Decr[i]=false;    
         	
 while(Nodo_K<16){
         		
       if(CeVocaleAlNodo(Nodo_K,B) ){
    	   contaVoc++;
    	   Decr[0]=true;
       }
         	
    	   for(int i=0; i<GrafoTavola.get(Nodo_K).getArrayAdiac().length;i++) {  
         			int Nodo_K2=GrafoTavola.get(Nodo_K).getArrayAdiac()[i];
           
       if(Nodo_K!=Nodo_K2){		
        
        	           if(CeVocaleAlNodo(Nodo_K2,B)){
             				contaVoc++;
             				Decr[1]=true;
             			}
         				 
 				    for(int u=0; u< GrafoTavola.get(Nodo_K2).getArrayAdiac().length;u++) {
 				       int Nodo_K3 = GrafoTavola.get(Nodo_K2).getArrayAdiac()[u];  				    	
 				          
 				          if(CeVocaleAlNodo(Nodo_K3,B)){
 				        	  contaVoc++;
 				        	  Decr[2]=true;
 				          }
 				          
 				        if(contaVoc<3  && Nodo_K3!=Nodo_K && Nodo_K3!= Nodo_K2 ){             
 				        	                for(int y=0 ; y< GrafoTavola.get(Nodo_K3).getArrayAdiac().length;  y++){
    				    	                	  int Nodo_K4= GrafoTavola.get(Nodo_K3).getArrayAdiac()[y];  				    	
    				    	                	  
    				    	                	     if(CeVocaleAlNodo(Nodo_K4,B)) {
    				    	                	    	 contaVoc++;
    				    	                	    	 Decr[3]=true;
    				    	                	     }
    				    	                	       
    				    	         if(contaVoc==2  &&  Nodo_K4!=Nodo_K2 && Nodo_K4!=Nodo_K && Nodo_K4!=Nodo_K3){ 
 					String s = new StringBuilder().append(ConvertiNodoLettera(Nodo_K, B)).append(ConvertiNodoLettera(Nodo_K2, B)).
 					 append(ConvertiNodoLettera(Nodo_K3, B)).append(ConvertiNodoLettera(Nodo_K4, B)).toString();	 
 						        	   	                   if(!ConfrontoP)  
 						        	   	contenitoreParole.inserInOrdineParolaDatoUnaCella(s);
 						        	   	                	   else
 						        	   	contenitoreParole.cercaComuni(s);   
 				    	            }
    				    	                  
    				    	                	    if(Decr[3]){
    				    	                	    	contaVoc--;
    				    	                	    	Decr[3]=false;
    				    	                	    }   
    				    	                	       
    				    	                  }
 				           }
 				        	       
 				        if(Decr[2]){
 				          contaVoc--; 						  
 				 		   Decr[2]=false;
 				 	     }
 				        	       
 				        	       
 				      }
 				             
 					  if(Decr[1]){
                        contaVoc--; 						  
 						  Decr[1]=false;
 					  }
 				  
    	             }   
 					  
         		}
    	   
    	   if(Decr[0]){
    		contaVoc--;   
    		   Decr[0]=false;
    	   }
             
    	   if(!ConfrontoP){
    		  int ind = ConvertiNodoLettera(Nodo_K, B)-65;
              contenitoreParole.ordinaVettore(contenitoreParole.getParole().get(ind));    		   
    	   }    	   
  Nodo_K++;          
  } 		    

     if(ConfrontoP){
        if(contenitoreParole.ciSonoComuni()) {
     	contenitoreParole.ordinaVettore(contenitoreParole.getParoleComuni() );
       	contenitoreParole.stampaParoleInComune();
        return true;
        }
         
     }  	
        	
        return false;
         	
    }	

         char ConvertiNodoLettera(int kN,char B[][]){
 	       CellaBoggle Cb= GrafoTavola.get(kN).getCellaBoggle();
 	         int R=Cb.getRiga();  int C=Cb.getCol();
 			    return B[R][C];
      	 }

    boolean CeVocaleAlNodo(int Nodo_K,char B[][]){
 	   CellaBoggle Cb=	GrafoTavola.get(Nodo_K).getCellaBoggle();
 	     int R=Cb.getRiga();  int C=Cb.getCol();
 	     
 	     switch( B[R][C] ){
 				   	  case 'A': return true ;
 				   	  case 'Y': return true;
 				   	  case 'E': return true;
 				   	  case 'O': return true;
 				   	  case 'I': return true;
 				   	  case 'U': return true;
 	     };
            return false;
    }
 

 }
		
}
I don't understund becouse Ive as Verdict "WRONG ANSWER",can you show me what is input test that my code don't pass??please :roll:

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: wrong answer The boggle game

Post by brianfry713 » Thu Mar 15, 2012 10:46 pm

Doesn't match the sample I/O.
http://ideone.com/dd708
Problem number 604
Check input and AC output for thousands of problems on uDebug!

valeriAsus
New poster
Posts: 5
Joined: Wed Mar 07, 2012 10:53 pm

wrong answer

Post by valeriAsus » Sun Apr 29, 2012 3:45 pm

// 604 the boggle game
Hallo can I've the test that my program doesn''t pass ?please :cry:

Code: Select all


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.Vector;
import java.util.regex.Pattern;
import java.util.Collections;

class MainUltimo{
	public static void main(String args[]) throws IOException{
	    MaterialePerK matPerK[]= new MaterialePerK[16];
	        
	        int Adiac0 []={1,4,5};
		     matPerK[0]= new MaterialePerK(new CellaBoggle(0, 0),Adiac0 );
		    int Adiac1[]={0,4,5,6,2};
			 matPerK[1]= new MaterialePerK(new CellaBoggle(0, 1),Adiac1 );
			 int Adiac2[]={1,5,6,3,7};	
			 matPerK[2]= new MaterialePerK(new CellaBoggle(0, 2),Adiac2 );
			 int Adiac3[]={2,6,7};
			  matPerK[3]= new MaterialePerK(new CellaBoggle(0, 3),Adiac3 );
		
			  
			 int Adiac4[]= {0,1,5,9,8};
			   matPerK[4]= new MaterialePerK(new CellaBoggle(1, 0),Adiac4);
			 int Adiac5[]= {4,0,1,2,6,10,9,8};
			 matPerK[5]= new MaterialePerK(new CellaBoggle(1, 1),Adiac5 );	
			 int Adiac6[]={5,1,2,3,7,11,10,9};
			 matPerK[6]= new MaterialePerK(new CellaBoggle(1, 2),Adiac6 );	
			 int Adiac7[]={3,2,6,10,11};
			 matPerK[7]= new MaterialePerK(new CellaBoggle(1, 3),Adiac7 );	
			 
			 int Adiac8[]={4,5,9,13,12};		 
			 matPerK[8]= new MaterialePerK(new CellaBoggle(2, 0),Adiac8 );	
			 int Adiac9[]={8,4,5,6,10,14,13,12};		
			 matPerK[9]= new MaterialePerK(new CellaBoggle(2, 1),Adiac9);	
			 int Adiac10[]={9,5,6,7,11,15,14,13};
			 matPerK[10]= new MaterialePerK(new CellaBoggle(2, 2),Adiac10);
			 int Adiac11[]={7,6,10,14,15};
			 matPerK[11]= new MaterialePerK(new CellaBoggle(2, 3),Adiac11);
			 
	         int Adiac12[]={8,9,13};		 
	         matPerK[12]= new MaterialePerK(new CellaBoggle(3, 0),Adiac12);

	         int Adiac13[]={12,8,9,10,14};	
	         matPerK[13]= new MaterialePerK(new CellaBoggle(3, 1),Adiac13);
	         
	         int Adiac14[]={13,9,10,11,15};	
	         matPerK[14]= new MaterialePerK(new CellaBoggle(3, 2),Adiac14);
	         int Adiac15[]={11,10,14};
	         matPerK[15]= new MaterialePerK(new CellaBoggle(3,3),Adiac15);
            
	         ContenitorePigEwu C= new ContenitorePigEwu();
	         GrafoBoggle Gr= new GrafoBoggle(matPerK,C);
	         LeggiPreparaM L= new LeggiPreparaM(Gr);
	          L.LeggiRigheM();
}	

 static class CellaBoggle {
    private int Righe,Col;
	
	public CellaBoggle(int r,int c){
       Righe=r;  Col=c;		
	}
	int getRiga(){ return Righe;  }
	int getCol(){  return Col;    }
	
	void setRiga(int r){Righe=r;  }
	void setCol(int c){ Col=c;    }
 }

 static class MaterialePerK {
	    private int NodiAdiacenti[];
		private CellaBoggle C;
		
		public MaterialePerK(CellaBoggle cb,int adiac[]) {
	      C=cb; 
		   NodiAdiacenti= adiac;
		}
		
		CellaBoggle getCellaBoggle(){ 
			return C; }
		
		void setArrayAdiac(int ind,int val){
			NodiAdiacenti[ind]=val;
		}

	    int [] getArrayAdiac(){
	    	return NodiAdiacenti;
	    }
	}

 static class LeggiPreparaM {
     private GrafoBoggle Gr;
 	 private String Riga;	
 	 private char B1[][];
     private char B2[][];
     private StringTokenizer st;
     private BufferedReader In_Str;
     
    LeggiPreparaM(GrafoBoggle G) {
     Riga="";    B1=new char[4][4];    B2=new char[4][4];   st=null;   
     In_Str = new BufferedReader(new InputStreamReader(System.in));  Gr=G;
 	}

 	 char[][] getB1() {
 		return B1;
 	}
 	
 	 char[][] getB2() {
 		return B2;
 	}
 	
     void LeggiRigheM()throws IOException{
       int R;   boolean cicla=true;
       try{
       while(true){	
 		    	R=0;
 			    while(R<4){
                      
 			    	   Riga=In_Str.readLine();
 			    	   if(Riga.equals("#") ){
                        Gr.getContenitoreParole().stampaParoleComuni(); 
 			    		   return ;   
 			    	   }       
          						 st= new StringTokenizer(Riga,"    ");
 						      AssegnaRiga(B1,R,0);
 						      AssegnaRiga(B2,R,0);
 			    R++;
 			    }
 			   System.out.println();
 			    
 		    	    Gr.TrovaParolePigEwu(getB1(),false);
 	      
      		  Gr.TrovaParolePigEwu(getB2(),true);
      		  
 		        Gr.getContenitoreParole().rimuoviVettore();   
                Gr.getContenitoreParole().allocaVettore();
                Gr.getContenitoreParole().setCiSonoComuni(false);  
 	  }	

     }catch (IOException e) {
    	 return;
     }
 }

         void AssegnaRiga(char B[][],int R,int C1){
 		   while(st.hasMoreTokens() && C1<4){
         	  B[R][C1] = st.nextToken().charAt(0);
         	C1++;
            }
             return ;
 	}
 	
 }

  static class ContenitorePigEwu {
	private boolean ciSonoComuni;  	
  	private Vector<ArrayList<String>>  parole = new Vector<ArrayList<String>>(26); 
  	private ArrayList<String>  paroleComuni ;
  	private ArrayList<String> paroleComuniPerCoppiaDiM= new ArrayList<String>();
  	 ContenitorePigEwu(){
  		for(int i=0 ; i<26 ;i++){
  	       parole.insertElementAt(new ArrayList<String>(),i);
   		}  
    	   ciSonoComuni=false;
           paroleComuni= new ArrayList<String>();
  	 }
  	
  	 public Vector<ArrayList<String>> getParole() {
		return parole;
	}
  	 
  	 public ArrayList<String> getParoleComuni() {
		return paroleComuni;
	}
  	 
  	 boolean ciSonoComuni(){
  		 return ciSonoComuni;
  	 }
  	 
  	 void setCiSonoComuni(boolean p){
  	     	 ciSonoComuni=p;
  	 }

  	 void rimuoviVettore(){
  		  parole.removeAllElements();
          paroleComuni.clear();
  	 }

  	void allocaVettore(){
      for(int i=0 ; i<26 ;i++)
   	     parole.insertElementAt(new ArrayList<String>(),i);
         paroleComuni= new ArrayList<String>();
  	}
	
  	void inserInOrdineParolaDatoUnaCella(String parola){
     	 int indVett= parola.charAt(0)-65;
  	    parole.get(indVett).add(parola);
  	}

  	void ordinaVettore(ArrayList<String>  arr){
	    	Collections.sort(arr);
  	}
  	
  void cercaComuni(String parola2matr){
	int indVett= (parola2matr.charAt(0)-65);
	   
	  if(parole.get(indVett).size()!=0){
		  int left, right; 
	         left = 0; 
			    right =parole.get(indVett).size();
	         
			    while (left!=right-1) {
			    	int m = (right+left)/2  ; 
			 
			    	String sm = parole.get(indVett).get(m);
			     
			    	if(sm.compareTo(parola2matr)<0) 
			            left = m; 
			        
			        else if (sm.compareTo(parola2matr)>0) 
			         right = m; 
			        else {
			         left = m;  
			         right = m+1; 
			           }
			   }
			    
			    if(parola2matr.equals(parole.get(indVett).get(left) )){
		        	   paroleComuni.add(parola2matr);
		                     ciSonoComuni=true;
		 	    } 

	  }
  }

   void stampaParoleComuni(){
    	int k=0 ;
    	paroleComuniPerCoppiaDiM.remove(paroleComuniPerCoppiaDiM.size()-1);
    
    	for(; k<paroleComuniPerCoppiaDiM.size() ; k++){
    		
    		if(paroleComuniPerCoppiaDiM.get(k)=="-" )
    			System.out.println();
    		if(paroleComuniPerCoppiaDiM.get(k)=="0")
    			 System.out.println("There are no common words for this pair of boggle boards.");    		
    		else
    			 if(paroleComuniPerCoppiaDiM.get(k)!="-")
    			  System.out.println(paroleComuniPerCoppiaDiM.get(k));
    	
    	}
    	
   }  
  
    void memorizzaParoleInComune(){
    	ArrayList<String>  monoS = new ArrayList<String>();
         for(int i=0 ;i<paroleComuni.size() ;i++){
      	    if(!monoS.contains(paroleComuni.get(i)))
      	    	monoS.add(paroleComuni.get(i));
         }
         
    	if(monoS.size()==0){
    		paroleComuniPerCoppiaDiM.add("0");
    	}
    	else   	
    	    paroleComuniPerCoppiaDiM.addAll(monoS);
    	paroleComuniPerCoppiaDiM.add("-");
    
    	monoS.clear();
    }
}
  
   static class GrafoBoggle{
     
	 private   HashMap<Integer,MaterialePerK> GrafoTavola =new HashMap<Integer, MaterialePerK>(16, 16) ;
     private MaterialePerK matPerK[];
     private  ContenitorePigEwu contenitoreParole;
     private boolean Decr[];

     GrafoBoggle(MaterialePerK mater[],ContenitorePigEwu cp){
    	contenitoreParole=cp;
          matPerK=mater;
           for(int k=0 ;k<16 ; k++) 
    	    GrafoTavola.put(k, matPerK[k]);      
              Decr= new boolean[4];
    }
    
    public ContenitorePigEwu getContenitoreParole() {
		return contenitoreParole;
	}

   void TrovaParolePigEwu(char B[][],boolean ConfrontoP){
     	int contaVoc=0;
     	int Nodo_K=0; 
     	for(int i=0 ; i<Decr.length ;i++)
            Decr[i]=false;    
         	
 while(Nodo_K<16){
       if(CeVocaleAlNodo(Nodo_K,B) ){
    	   contaVoc++;
    	   Decr[0]=true;
       }
         	
    	   for(int i=0; i<GrafoTavola.get(Nodo_K).getArrayAdiac().length;i++) {  
         			int Nodo_K2=GrafoTavola.get(Nodo_K).getArrayAdiac()[i];
           
       if(Nodo_K!=Nodo_K2){		
        
        	           if(CeVocaleAlNodo(Nodo_K2,B)){
             				contaVoc++;
             				Decr[1]=true;
             			}
         				 
 				    for(int u=0;   u< GrafoTavola.get(Nodo_K2).getArrayAdiac().length;  u++) {
 				       int Nodo_K3 = GrafoTavola.get(Nodo_K2).getArrayAdiac()[u];  				    	
 				          
 				          if(CeVocaleAlNodo(Nodo_K3,B)){
 				        	  contaVoc++;
 				        	  Decr[2]=true;
 				          }
 				          
 				        if(contaVoc<3  && Nodo_K3!=Nodo_K && Nodo_K3!= Nodo_K2 ){             
 				        	                for(int y=0 ; y< GrafoTavola.get(Nodo_K3).getArrayAdiac().length;  y++){
    				    	                	  int Nodo_K4= GrafoTavola.get(Nodo_K3).getArrayAdiac()[y];  				    	
    				    	                	  
    				    	                	     if(CeVocaleAlNodo(Nodo_K4,B)) {
    				    	                	    	 contaVoc++;
    				    	                	    	 Decr[3]=true;
    				    	                	     }
    				    	                	       
    				    	        if(contaVoc==2  &&  Nodo_K4!=Nodo_K2 && Nodo_K4!=Nodo_K && Nodo_K4!=Nodo_K3){ 
	String s = new StringBuilder().append(ConvertiNodoLettera(Nodo_K, B)).append(ConvertiNodoLettera(Nodo_K2, B)).
		 append(ConvertiNodoLettera(Nodo_K3, B)).append(ConvertiNodoLettera(Nodo_K4, B)).toString();	 
 						        	   	                
 					                       if(!ConfrontoP)  {
 						        	   	contenitoreParole.inserInOrdineParolaDatoUnaCella(s);
 					                       }                	 
 						        	   	else
 						        	   	contenitoreParole.cercaComuni(s);   
 				    	            }
    				    	                  
    				    	                	    if(Decr[3]){
    				    	                	    	contaVoc--;
    				    	                	    	Decr[3]=false;
    				    	                	    }   
    				    	                	       
    				    	                  }
 				           }
 				        	       
 				        if(Decr[2]){
 				          contaVoc--; 						  
 				 		   Decr[2]=false;
 				 	     }
 				        	       
 				        	       
 				      }
 				             
 					  if(Decr[1]){
                        contaVoc--; 						  
 						  Decr[1]=false;
 					  }
 				  
    	             }   
 					  
         		}
    	   
    	   if(Decr[0]){
    		contaVoc--;   
    		   Decr[0]=false;
    	   }
    	   
       
    	   if(!ConfrontoP){
    		  int ind = ConvertiNodoLettera(Nodo_K, B)-65;
              contenitoreParole.ordinaVettore(contenitoreParole.getParole().get(ind));    		   
    	 }
      	   
    	   Nodo_K++;          
  } 		    

     if(ConfrontoP){
     	contenitoreParole.ordinaVettore(contenitoreParole.getParoleComuni() );
     	contenitoreParole.memorizzaParoleInComune();
     }  	

 }	

         char ConvertiNodoLettera(int kN,char B[][]){
 	       CellaBoggle Cb= GrafoTavola.get(kN).getCellaBoggle();
 	         int R=Cb.getRiga();  int C=Cb.getCol();
 			    return B[R][C];
      	 }

    boolean CeVocaleAlNodo(int Nodo_K,char B[][]){
 	   CellaBoggle Cb=GrafoTavola.get(Nodo_K).getCellaBoggle();
 	     int R=Cb.getRiga();  int C=Cb.getCol();
 	     
 	     switch( B[R][C] ){
 				   	  case 'A': return true ;
 				   	  case 'Y': return true;
 				   	  case 'E': return true;
 				   	  case 'O': return true;
 				   	  case 'I': return true;
 				   	  case 'U': return true;
 	     };
            return false;
    }
 

 }
		
}





Post Reply

Return to “Volume 6 (600-699)”