----------------------------------- MihaiG Tue Aug 30, 2005 12:28 pm 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 ----------------------------------- [Gandalf] Tue Aug 30, 2005 2:29 pm ----------------------------------- 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. ----------------------------------- Tony Tue Aug 30, 2005 7:00 pm ----------------------------------- 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: ----------------------------------- Delos Tue Aug 30, 2005 7:19 pm ----------------------------------- Whoosh. Nobody knows what just happened. Hmm...editting my posts eh? I'll remember this one Tony. ----------------------------------- zylum Fri Sep 02, 2005 4:45 am ----------------------------------- 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: ----------------------------------- Mazer Fri Sep 02, 2005 8:30 am ----------------------------------- ... zylum, what rules did you use for a "legal" English word? ----------------------------------- Hikaru79 Fri Sep 02, 2005 10:19 am ----------------------------------- 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 :shock: ----------------------------------- Mazer Fri Sep 02, 2005 10:30 am ----------------------------------- I can't say I'm not surprised by that, but my main concern was "aarrghh" :) ----------------------------------- zylum Fri Sep 02, 2005 3:59 pm ----------------------------------- 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... ----------------------------------- Tony Fri Sep 02, 2005 4:30 pm ----------------------------------- are all the words used supposed to be unique? ----------------------------------- zylum Fri Sep 02, 2005 5:43 pm ----------------------------------- 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. ----------------------------------- [Gandalf] Fri Sep 02, 2005 7:09 pm ----------------------------------- Tony covering his tracks. I don't think it was quite like this: Another problem is simply having enough words of the right length. 10x10 box = 20 ten letter words. Now think larger ;) :lol: The thing about these words is that a lot of them are random names and places.... ----------------------------------- zylum Fri Sep 02, 2005 7:46 pm ----------------------------------- the people who are trying to find the first 10x10 word square are using even larger and more obscure wordlists than i am :wink:. ----------------------------------- Tony Fri Sep 02, 2005 8:04 pm ----------------------------------- are using even larger and more obscure wordlists than i am :wink:. Where would I get a hold of such a wordlist? ----------------------------------- zylum Fri Sep 02, 2005 8:36 pm ----------------------------------- 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+ :x ----------------------------------- [Gandalf] Fri Sep 02, 2005 8:48 pm ----------------------------------- I don't see the problem... ----------------------------------- Tony Fri Sep 02, 2005 9:12 pm ----------------------------------- could someone do me a favour and break that list up into groups by length? thx ----------------------------------- rizzix Fri Sep 02, 2005 9:49 pm ----------------------------------- easy with perl... perl -e 'print for (sort {length($a) length($b)} );' < word.txt > sorted_length_words.txt ----------------------------------- [Gandalf] Fri Sep 02, 2005 10:02 pm ----------------------------------- 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... ----------------------------------- wtd Fri Sep 02, 2005 10:09 pm ----------------------------------- "]*edit2* Perl seems like a pretty useful language... It is. For what it's worth, Ruby can mostly take its place. :) ----------------------------------- rizzix Fri Sep 02, 2005 10:17 pm ----------------------------------- i want to see that ruby one-liner.. ;) (not that i'm doubting it capabilities or anything.. just curious) ----------------------------------- [Gandalf] Fri Sep 02, 2005 10:26 pm ----------------------------------- 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 ;). ----------------------------------- rizzix Fri Sep 02, 2005 10:29 pm ----------------------------------- "]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 ;). yes yes.. but as concise as print for (sort {length($a) length($b)} );this?? it would be cool though.. if it is soo.. ----------------------------------- wtd Fri Sep 02, 2005 11:19 pm ----------------------------------- A rough first take. $ cat foo.txt hello world foo bar wooble ninja $ ruby -ne 'BEGIN { $lines = [] }; $lines > 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 ;) ----------------------------------- Mazer Sun Sep 04, 2005 8:14 am ----------------------------------- "]*edit* All these are abbreviations... Except 'nu' which is a letter in the greek alphabet No shit? Which one?! :roll: ----------------------------------- Tony Sun Sep 04, 2005 3:07 pm ----------------------------------- 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 :lol: ----------------------------------- [Gandalf] Sun Sep 04, 2005 6:20 pm ----------------------------------- Anyone care to package the word list as a .tar.gz? RAR is a pain in the ... to deal with in Linux. No shit? Which one?! :roll: Well... I wouldn't know that easily... 13th. ----------------------------------- wtd Sun Sep 04, 2005 9:07 pm ----------------------------------- Thanks everyone for pointing out that even the very wise can be frickin' morons. :) Problem solved. Well, aquiring the word list, anyway. ----------------------------------- bugzpodder Thu Sep 08, 2005 7:23 pm ----------------------------------- 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 :shock: lmao pronounce it!!! zz-v LOL ----------------------------------- bugzpodder Thu Sep 08, 2005 7:28 pm ----------------------------------- and i would build a trie to solve this problem. it is very very efficient for this type of problem. ----------------------------------- bugzpodder Thu Sep 08, 2005 7:38 pm ----------------------------------- 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;iarr[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