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

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

604 - The Boggle Game

Post by Dominik Michniewski » Fri Apr 25, 2003 3:29 pm

Could anyone tell me: Does it exist some special cases for this problem?
I try to solve it in this way:
1. Generate all possible words (which have exactly 2 vowels - AEIOUY)
2. Sort this words and remove duplicates
3. Generate all possible words for second board (in the same way) and using bsearch try to find it in first words - in success add such word to table with common words.
4. Sort common part and remove duplicates, and print it.

Is this way incorrect ? I always got WA :(

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
the LA-Z-BOy
Learning poster
Posts: 94
Joined: Wed Jul 31, 2002 12:44 pm
Location: Dacca, Bangladesh
Contact:

Re: 604 - Boggle Game WA

Post by the LA-Z-BOy » Sat Jul 19, 2003 11:56 am

Dominik Michniewski wrote:Is this way incorrect ? I always got WA :(
I got accepted with quite similar method as you. May be you are missing something else somewhere.
This test case may or may not help you
Input

Code: Select all

A A B B    A A B B    
A B A B    A B A B
A B C A    A B C A
B C A D    B C A D

#
Output

Code: Select all

AABB
AABC
AACB
AACC
AACD
AADC
ABAB
ABAC
ABAD
ABBA
ABCA
ACAB
ACAC
ACAD
ACBA
ACCA
ACDA
ADAB
ADAC
ADCA
BAAB
BAAC
BAAD
BABA
BACA
BADA
BBAA
BCAA
CAAB
CAAC
CAAD
CABA
CACA
CADA
CBAA
CCAA
CDAA
DAAB
DAAC
DABA
DACA
DCAA
thanks...
Istiaque Ahmed
Istiaque Ahmed [the LA-Z-BOy]

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Sep 03, 2003 11:44 pm

Hi Dominik,

It's been a while since you wrote your message, but according to the list you still are WA on this problem (if I looked correctly). I had a long standing WA on this one too, but fixed it finaly today. I use a similar method as you (I use a binary tree to store the generated words, but that's just a minor difference).

My mistake was: I didn't re-initialise the word list inbetween two cases :oops: :oops: :oops: . Maybe you should check your code for this kind of errors too, because your method is OK.

My ultimate input was:

Code: Select all

A B B A    A B B A
E D D E    E D D E
E F F A    E F F A
A E F G    A E F G

X X X X    A B B A
X X X X    E D D E
X X X X    E F F A
X X X X    A E F G

#
Which produced the same list of words twice!

It's just a thought, but maybe it helps.

-little joey
Last edited by little joey on Thu Sep 04, 2003 10:10 am, edited 1 time in total.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Sep 04, 2003 9:31 am

Description says:

Code: Select all

Two consecutive entries on same board will be separated by one blank.
so I think that your input is incorrect .... but I don't make such mistake as you write. Everything looks OK. On both outputs - yours and LA-Z-BOy's ...
I try to make this problem again using my algorithm, but storing words in other way ...

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Sep 04, 2003 10:14 am

Oops, you're right about the spaces :oops: . I editted my previous message. My program removes everything that's not an uppercase letter from the input, so it workes fine on this and I didn't notice.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Sep 04, 2003 2:57 pm

After all, I've got Acc on this - I change code to use binary trees and got Acc with 1.5 sec time ....

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

valderrama
New poster
Posts: 4
Joined: Wed Mar 03, 2004 9:22 pm

604 (boggle game) Time limit exceeded

Post by valderrama » Wed Mar 03, 2004 10:06 pm

Hello!!!!

I'm trying to solve to 604 proble. It runs correctly, but it is using to much time. Does anybody know any method to be faster?? Here goes my method:

1. Generate all possible words of 4 letters from the first square.

2. Look if each letter of each word have a corner or edge in common in the squares (both).

3. Push the words in a vector, sort it, and print the words.


Please, I need help!!!!

Lots of thanks.

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

How?

Post by sohel » Thu Mar 04, 2004 8:59 am

How did you generate all the four letter words?

I used dfs to generate all the legal words and used mapping to store it.

Then I did the same thing with the second grid and if it maps with that of previous then I inserted it in a vector.
Sort the vector.... and thats it.

valderrama
New poster
Posts: 4
Joined: Wed Mar 03, 2004 9:22 pm

Possible solution

Post by valderrama » Thu Mar 04, 2004 5:48 pm

I generate all word just iterating (I think I used four ar five iterators one "inside" the other).

Please, could anybody tell me some method (that I were able to understand... it's so difficult) to generate the words faster???


Thanks!!!!

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Fri Mar 05, 2004 9:09 am

try to avoid letters, which not exist in second table. with this backtracking is fast enough.

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

valderrama
New poster
Posts: 4
Joined: Wed Mar 03, 2004 9:22 pm

604 Boggle game, HELP!!!!

Post by valderrama » Wed Mar 10, 2004 1:42 pm

Hello!!!

I'm not able to solve this problem, because I get "Time Limit Exceeded" all time. Is there any method to solve the problem more quickly?

My algo is:

- Generate all possible words of the first board with two vowels and with its letters one on side the other in the board, and store it in a BST.

- The same with the other board

-Store in anther BST the common words.

-Print the common words.

Do you know any fastest method????

Thanks!!!

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

some hints

Post by sohel » Wed Mar 10, 2004 2:28 pm

Hi Velderama,

Generating all the words using DFS should work.

First for the 1st grid:
-generate all the words and store the ones that contain two vowels ( remember y is a vowel in this problem).
- I used map to flag the valid ones. (M)

Then for the 2nd grid:
-generate all the words and if it contains two vowels look whether it is in M;
if yes( push it in a vector and mark this visited using another map M2 )
-repeat the steps and if (a valid word is formed in 2nd which is also contained in 1st but it is already mapped in M2 then do not push it in ).

In this way the final vector size is greatly reduced and helps avoid TLE.

Hope it helps.
:wink:

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Mar 10, 2004 2:45 pm

Keep in mind that TLE doesn't always mean there's a problem with your algorithm. Maybe you're taking input wrong..

valderrama
New poster
Posts: 4
Joined: Wed Mar 03, 2004 9:22 pm

Post by valderrama » Wed Mar 10, 2004 5:07 pm

DFS???? Map???

What is it????

I just know basic structures such as BST, TST...

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Thu Mar 11, 2004 9:20 am

DFS - Depth First Search

Best regards
DM
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

Post Reply

Return to “Volume 6 (600-699)”