Computer Science Canada

Kool problem
Author:  MihaiG [ Tue Aug 30, 2005 12:28 pm ]
Post subject:  Kool problem
well i saw this problem cant fin liunk again but it went soemthign like this...

Find the largest possible box of letters than in every horizontal/vertical direction makes a legal english word....

seems preaty hard...you woudl need to make somethign that could access a database for words etc. any suggestions
Author:  [Gandalf] [ Tue Aug 30, 2005 2:29 pm ]
Post subject: 
Try it out using paper first, with three letter words, then four, etc...

The problem I see with this kind of problem is that you would need a large database of pretty much all english words. If you have that, then it would take a long time to sort, or do anything with that huge list.
Author:  Tony [ Tue Aug 30, 2005 7:00 pm ]
Post subject: 
I'm sure that there are a lot of tricks to this problem. Writing a crossword generator might be a good first step to understanding the complex problems that could appear in this larger, more restrictive case.

You know how most crosswords have those 4x4 boxes in their corners (usually).. Getting that is a start.

Another problem is simply having enough words of the right length. 10x10 box = 20 ten letter words. Now think larger Wink
Author:  Delos [ Tue Aug 30, 2005 7:19 pm ]
Post subject: 
Whoosh. Nobody knows what just happened.

[mod:3be0dfdb40="Delos"]
Hmm...editting my posts eh? I'll remember this one Tony.
[/mod:3be0dfdb40]
Author:  zylum [ Fri Sep 02, 2005 4:45 am ]
Post subject: 
i managed to get a solution (in turing) to give 7x7 solutions in a reasonable amount of time. the first one is generated in 12 seconds on a 733MHz celeron. from what ive read, the largest box was 9x9 so im not too far off... the word list i used is attached.

i will post my solution later on, i just want to see if anyone else can achieve a better result than me Wink
Author:  Mazer [ Fri Sep 02, 2005 8:30 am ]
Post subject: 
...

zylum, what rules did you use for a "legal" English word?
Author:  Hikaru79 [ Fri Sep 02, 2005 10:19 am ]
Post subject: 
Dictionary.com wrote:
zyz·zy·va P Pronunciation Key (zz-v)
n.
Any of various tropical American weevils of the genus Zyzzyva, often destructive to plants.

Oh my god, you weren't making it up, it actually is a real word Shocked
Author:  Mazer [ Fri Sep 02, 2005 10:30 am ]
Post subject: 
I can't say I'm not surprised by that, but my main concern was "aarrghh" Smile
Author:  zylum [ Fri Sep 02, 2005 3:59 pm ]
Post subject: 
aarrghh is a legal word.. google it. the wordlist i use is the enable2k wordlist and it has all the legal scrabble words and all that garbage. you can also find it with a google search.

has anyone got any solutions yet???

im converting mine into java at the moment and adding a few more features that should speed it up a bit... maybe ill be able to get to 8x8 or even 9x9...
Author:  Tony [ Fri Sep 02, 2005 4:30 pm ]
Post subject: 
are all the words used supposed to be unique?
Author:  zylum [ Fri Sep 02, 2005 5:43 pm ]
Post subject: 
no... if they are not unique its considered a regular word square where as if all column words do not match the corrisponding row words, then it's considered a double word square.
Author:  [Gandalf] [ Fri Sep 02, 2005 7:09 pm ]
Post subject: 
Tony covering his tracks. I don't think it was quite like this:
Quote:
Another problem is simply having enough words of the right length. 10x10 box = 20 ten letter words. Now think larger Wink

Laughing


The thing about these words is that a lot of them are random names and places....
Author:  zylum [ Fri Sep 02, 2005 7:46 pm ]
Post subject: 
the people who are trying to find the first 10x10 word square are using even larger and more obscure wordlists than i am Wink.
Author:  Tony [ Fri Sep 02, 2005 8:04 pm ]
Post subject: 
zylum wrote:
are using even larger and more obscure wordlists than i am Wink.

Where would I get a hold of such a wordlist?
Author:  zylum [ Fri Sep 02, 2005 8:36 pm ]
Post subject: 
http://ibiblio.org/pub/Linux/libs/yawl-0.3.2.tar.gz

if you can convert it into a txt for windows, i would appreciate it... this list contains 264000+ words. the current word list i am using is 173000+ Mad
Author:  [Gandalf] [ Fri Sep 02, 2005 8:48 pm ]
Post subject: 
I don't see the problem...
Author:  Tony [ Fri Sep 02, 2005 9:12 pm ]
Post subject: 
could someone do me a favour and break that list up into groups by length? thx
Author:  rizzix [ Fri Sep 02, 2005 9:49 pm ]
Post subject: 
easy with perl...
code:
perl -e 'print for (sort {length($a) <=> length($b)} <>);' < word.txt > sorted_length_words.txt
Author:  [Gandalf] [ Fri Sep 02, 2005 10:02 pm ]
Post subject: 
I am having trouble believing that aa is a word. "ka" "nu" "st" "aga"!?

*edit* All these are abbreviations... Except 'nu' which is a letter in the greek alphabet and 'aga' which is "used as a title for a civil or military leader, especially in Turkey."

*edit2* Perl seems like a pretty useful language...
Author:  wtd [ Fri Sep 02, 2005 10:09 pm ]
Post subject: 
[Gandalf] wrote:
*edit2* Perl seems like a pretty useful language...


It is.

For what it's worth, Ruby can mostly take its place. Smile
Author:  rizzix [ Fri Sep 02, 2005 10:17 pm ]
Post subject: 
i want to see that ruby one-liner.. Wink (not that i'm doubting it capabilities or anything.. just curious)
Author:  [Gandalf] [ Fri Sep 02, 2005 10:26 pm ]
Post subject: 
I wouldn't doubt it (not that you are...) from Ruby. It's anti-whitespace capabilities and flexible syntax would allow something like this in one line Wink.
Author:  rizzix [ Fri Sep 02, 2005 10:29 pm ]
Post subject: 
[Gandalf] wrote:
I wouldn't doubt it (not that you are...) from Ruby. It's anti-whitespace capabilities and flexible syntax would allow something like this in one line Wink.
yes yes.. but as concise as
Perl:
print for (sort {length($a) <=> length($b)} <>);
this??

it would be cool though.. if it is soo..
Author:  wtd [ Fri Sep 02, 2005 11:19 pm ]
Post subject: 
A rough first take.

code:
$ cat foo.txt
hello
world
foo
bar
wooble
ninja
$ ruby -ne 'BEGIN { $lines = [] }; $lines << $_; END { puts $lines.sort { |a, b| a.length <=> b.length } }' foo.txt > bar.txt
$ cat bar.txt
bar
foo
hello
world
ninja
wooble
$
Author:  zylum [ Sat Sep 03, 2005 3:36 am ]
Post subject: 
come on people lets get some solutoins coming!

100 bits to the first person who can post a 6x6 double word square which will appear earliest alphabetically. double meaning that corresponding columns and rows are not equal. the word list to be used is attached below.

heres an example of a 5x5 double word square which appears earliest alphabetically:

code:
AAHED
AGAPE
LEMON
IRADE
ISLES


also, 100 bits to the first 8x8 regular solution which will appear earliest alphabetically. regular meaning corresponding columns and rows are equal.

example of a 7x7 regulare square:

code:
ABASERS
BEDEMEN
ADENOMA
SENATOR
EMOTIVE
REMOVER
SNARERS
Author:  Tony [ Sat Sep 03, 2005 11:41 pm ]
Post subject: 
well I've got my C code running. I must have messed something up bad, because this is way too slow pass 5 letter words.

Edit: I think I know how to improve on this

The way I load data, all the results are in reverse alphabetical (meaning it gives me alphabetically last solution).

Tony found 5x5 double word square and wrote:

ZYMES
YOUTH
MUSHY
ETHYL
SHYLY
Author:  wtd [ Sun Sep 04, 2005 12:44 am ]
Post subject: 
Anyone care to package the word list as a .tar.gz? RAR is a pain in the ... to deal with in Linux.
Author:  zylum [ Sun Sep 04, 2005 1:22 am ]
Post subject: 
wtd wrote:
Anyone care to package the word list as a .tar.gz? RAR is a pain in the ... to deal with in Linux.


just use the txts i posted...

tony >> how are you going about finding solutions?

plain brute force is not an option in this case... the number of combinations for a word list of size L which contains words of length N is L^N!!!

try to think of some ways to prune your search.


btw, your 5x5 square is indeed alphabetically last Wink
Author:  Mazer [ Sun Sep 04, 2005 8:14 am ]
Post subject: 
[Gandalf] wrote:
*edit* All these are abbreviations... Except 'nu' which is a letter in the greek alphabet

No shit? Which one?! Rolling Eyes
Author:  Tony [ Sun Sep 04, 2005 3:07 pm ]
Post subject: 
zylum wrote:
try to think of some ways to prune your search.

Yeah, I was just going though the wordlist, checking if what I have so far could make sense with the dictionary.

Anyways, I see the error of my ways. L^10000 is not a good number Laughing
Author:  [Gandalf] [ Sun Sep 04, 2005 6:20 pm ]
Post subject: 
wtd wrote:
Anyone care to package the word list as a .tar.gz? RAR is a pain in the ... to deal with in Linux.

http://ibiblio.org/pub/Linux/libs/yawl-0.3.2.tar.gz
That's what I converted to get the .rar.

Quote:
No shit? Which one?! Rolling Eyes

Well... I wouldn't know that easily...
13th.
Author:  wtd [ Sun Sep 04, 2005 9:07 pm ]
Post subject: 
Thanks everyone for pointing out that even the very wise can be frickin' morons. Smile

Problem solved. Well, aquiring the word list, anyway.
Author:  bugzpodder [ Thu Sep 08, 2005 7:23 pm ]
Post subject: 
Hikaru79 wrote:
Dictionary.com wrote:
zyz·zy·va P Pronunciation Key (zz-v)
n.
Any of various tropical American weevils of the genus Zyzzyva, often destructive to plants.

Oh my god, you weren't making it up, it actually is a real word Shocked


lmao pronounce it!!! zz-v LOL
Author:  bugzpodder [ Thu Sep 08, 2005 7:28 pm ]
Post subject: 
and i would build a trie to solve this problem. it is very very efficient for this type of problem.
Author:  bugzpodder [ Thu Sep 08, 2005 7:38 pm ]
Post subject: 
code:

struct trie{
        trie *arr[26];
        bool flag;
        trie(){flag=false;memset(arr,0,sizeof(arr));}
}*root;
int main(){
        ifstream cin("prefix.in");
        ofstream cout("prefix.out");
       
        char c;
        string s;
        int i;
        trie *t;
        root=new trie();
        while(cin>>s){
                if (s==".") break;
                for (i=0,t=root;i<s.length();i++) {
                        if (t->arr[s[i]-'A']==0) t->arr[s[i]-'A']=new trie();
                        t=t->arr[s[i]-'A'];
                }
                t->flag=true;
        }
   .....

this code is first half of my solution for prefix (usaco 4.3.3) incidently this is the last usaco problem i finished

:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy