Omnimaga

Calculator Community => Other Calc-Related Projects and Ideas => TI-Nspire => Topic started by: cyanophycean314 on June 30, 2012, 02:53:49 pm

Title: Scramble/Boggle Lua
Post by: cyanophycean314 on June 30, 2012, 02:53:49 pm
Because I recently got Scramble with Friends for my Android tablet, I took it upon myself to make this game. Right now, the screenshot shows most of what it can do. I may enter this for the contest if I can code an AI to be your "friend." You'll have the option to watch him play.

Right now the biggest problem is the dictionary. I've googled online for a dictionary and it was 170,000+ words. I tried to put that into my Lua file, but it said there was not enough memory  :P. So the dictionary right now is all the words I can think of.

I still need to add a solver to find all possible words, change the scoring scheme to be more like Scramble (without double/triple), add some results page, randomly generated puzzles, and get the dictionary working.

Hope you guys enjoy.
Title: Re: Scramble/Boggle Lua
Post by: Adriweb on July 01, 2012, 09:46:24 am
Very nice ! :D
Title: Re: Scramble/Boggle Lua
Post by: shmibs on July 01, 2012, 11:08:14 am
would using some form of text compression slow things down too much, or would that plus a binary search be doable?/me has no clues about the speed of nspire lua
Title: Re: Scramble/Boggle Lua
Post by: Jim Bauwens on July 01, 2012, 12:48:49 pm
Adding compression should not slow it down much.
Anyway, how do you store the data ? Just a large table ?
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on July 01, 2012, 03:52:14 pm
Currently all the dictionary is stored in a table, and I don't really know a better way to do that. I have binary search implemented so speed shouldn't be a problem, hopefully. I have no idea about compression...
Title: Re: Scramble/Boggle Lua
Post by: Loulou 54 on July 21, 2012, 09:34:01 am
Hello cyanophycean !

In TI-Translate (http://ourl.ca/13193/297363), I stored the data in huge strings IN the TI Nspire document. (indeed I couldn't paste all into ONE string because the length of a string on the TI Nspire is limited ! So I had to split my list into small pieces ! (516 words per string if I remember, or 516*84 characters)) That was rather complicated and I had to make a kind of a script to automate "copy/paste"s from notepad to the student software.. %)
Why such a weird and difficult solution ?
Because my strings contained a lot of accentuated characters and the TI Nspire scripting tool made shit.. (just closed the Student Software every time I pasted the code !)
(I also tried with Luna, and the generated file produces an error too..)

About memory problems : my biggest version (english/french) contains 58 959 words from english to french AND 56 252 words from french to english. Moreover, the storage isn't really optimized... Actually each word takes exactly 84 characters and the remaining place is filled with blanks.
An extract :
Quote
a b c {m} [abécédaire]         primer {n} [ABC]                                     a latere [REL‚ loc adj]        a latere [adj phr]                                   a latere [REL‚ loc adv]        a latere [adv phr]                                   a priori [loc adj]             a priori [adj]                                       a priori [loc adv]             a priori [adv], guess; at a ~ [adv phr]              a priori {m inv}               apriorism {n}, preconception {n}                     A {m} [alphabet latin]         A {n} [Roman alphabet]                               A {n} [ÉLEC‚ ampère]           amp {n} [ELEC‚ an ampere]                            abaissement {m}                abatement {n}, decay {n}, lowering {n}               abaisser [v tr]                lower [v tr‚ make lower]                             abaisser [v tr‚ raccourcir]    cut up [v tr]                                        abaisser [v tr‚ réduire]       bring down [vt‚ lower a price]                       abaisser; s'~ [v pr]           off; to get ~, demean; to ~ oneself                  abaisser; s'~ vivement [v pr]  duck down [v intr]                                   abaisser; s'~ à faire          stoop; to ~ to doing                                

This was the original format of the data from Freelang dictionnaries. On the other side, this format was convenient to navigate through the list because you just have to make 84 characters steps to get the next word ! :)

So, here is how it works for my TI translate ! ^^

In term of number of characters, it represents for both lists 9 677 724 characters !

So if you want to solve your problem, maybe you could do as I did, but I don't think that's the best solution. Moreover you don't need here the assets of this solution, as I did. (storing in a string to ease the string research, supporting accentuation,...)

So I think that the easier solution is to reduce the amount of word ! :P

PS : have you tried to split your table into smallest ones ? (maybe it's the length of a table wich is limited..)

Anyway, good luck ! :D

EDIT :
Your program must search words in your list actually ? How do you do that with your table ? You scan the whole table to see if it contains the word ?
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on July 21, 2012, 09:59:42 am
Thanks Loulou for the explanation and suggestions.  :)

I'll try splitting up my table into smaller ones, probably divided by letters. Or I could also use strings like you did.

I planned on using binary search to go through my list and find the word, but now I just realized that there were string search functions provided by Lua.
Title: Re: Scramble/Boggle Lua
Post by: Nick on July 22, 2012, 05:26:00 am
wow, this is a great game :o maybe you could just use semicolons (;) to split words, and the look for the matching ; so split them up, that would be the most easy way i think..

is it correct if i saw that you don't get extra points if you make a word you already formed, or did i just look bad?

how do you make the grid? because you say 'randomly generate ouzzles', does that mean you now just make them by hand and type them in?
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on July 23, 2012, 09:07:34 am
Thanks.  :)

What exactly do you mean when you said to use semicolons to split words? To select words, you press the tab button, and then use the numpad to move along the board, selecting letters as you go. Then you release tab, and that's your word.

The program checks if you've already used that word.  :)

Currently this is just a hard-coded grid, but I'm working on random generation (balancing it is kinda tricky...).

Edit: Woah, it's my 300th post.
Title: Re: Scramble/Boggle Lua
Post by: Nick on July 23, 2012, 05:50:07 pm
i meant that semicolon thing for your encoding of the library.

if you do for example lib = "can;pie;cake;board;door" etc you can easely split them up to find the words, and you don't need that endlessly long table to store your entries..
Title: Re: Scramble/Boggle Lua
Post by: Loulou 54 on July 23, 2012, 06:31:53 pm
binary search == dichotomy ?

i meant that semicolon thing for your encoding of the library.

if you do for example lib = "can;pie;cake;board;door" etc you can easely split them up to find the words, and you don't need that endlessly long table to store your entries..

Yes it could be a good solution, using the string.find function. :)
(Actually that's almost what I did for TI translate, but in Basic.)

Moreover this function provides very powerful features with what's called "patterns". You can look in the Lua manual to get more informations. :)

(little trick : if you want to convert your table into Nick's format, don't forget the "Replace" function of your notepad ! ;) I mean, for example : {"hello","world","I'm happy"} => Replace `","` by `;` => {"hello;world;I'm happy"} => then just delete the "{" and you have your string :) )
Title: Re: Scramble/Boggle Lua
Post by: 3rik on July 23, 2012, 08:02:43 pm
If the plan is to have large dictionaries, this might be useful.  :)

Code: [Select]
function editDictionary(dictionary, old_dict)
local data = old_dict or {}
for _, word in ipairs(dictionary) do
local curchar = data
for i = 1, #word do
local char = word:sub(i, i)
if not curchar[char] then
curchar[char] = {endof = i == #word and true or nil}
elseif not curchar[char].endof then
curchar[char].endof = i == #word and true or nil
end
curchar = curchar[char]
end
end
data.lookup = function(tbl, str)
local function lookup(str)
local curchar = data
for i = 1, #str do
curchar = curchar[str:sub(i, i)]
end
return curchar.endof
end
err, ret = pcall(lookup, str)
return err and ret or nil
end
return data
end

It takes a table like
Code: [Select]
list={"carbon","cars","car","cat","cats"}

and creates a table like
Code: [Select]
dictionary = {
c={
a={
r={
b={
o={
n={endof = true}
}
}
s={endof = true}
endof = true
}
t = {
s={endof = true}
endof = true
}
}
}
lookup = function(tbl, str)
--blah blah blah
end
}



lookup takes a string and rapidly returns a true or nil value based on if the word is in the list of acceptable words.

Here's an example:
Code: [Select]
dict = {"cat", "cats", "dog", "mouse"}

dictionary = editDictionary(dict)

print("d:", dictionary:lookup("d"))
print("do:", dictionary:lookup("do"))
print("dog:", dictionary:lookup("dog"))
print("dogs:", dictionary:lookup("dogs"))
print("dogz:", dictionary:lookup("dogz"))

amendment = {"dogs"}
dictionary = editDictionary(amendment, dictionary)
print("\nAmendment: dogs added!\n")

print("d:", dictionary:lookup("d"))
print("do:", dictionary:lookup("do"))
print("dog:", dictionary:lookup("dog"))
print("dogs:", dictionary:lookup("dogs"))
print("dogz:", dictionary:lookup("dogz"))

prints

Code: [Select]
d: nil
do: nil
dog: true
dogs: nil
dogz: nil

Amendment: dogs added!

d: nil
do: nil
dog: true
dogs: true
dogz: nil

What I like about this way is that it narrows the search down for each letter in the string instead of searching for the whole string in a giant table or string. It could be potentially bulky, though.

Worst case scenario, it could end up indexing something like dictionary.p.n.e.u.m.o.n.o.u.l.t.r.a.m.i.c.r.o.s.c.o.p.i.c.s.i.l.i.c.o.v.o.l.c.a.n.o.c.o.n.i.o.s.i.s.endof but most of that searching would be handled by Lua itself.

This is case sensitive, but if it makes a difference it would only take a simple metatable to fix.


EDIT: Reread the first post and testing a few things first
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on July 23, 2012, 09:14:47 pm
@3rik: Your solution is interesting, but I think memory constraints will occur... I'll give it a try if my current attempt fails.

Right now, I have around 1158 strings with format: words1 = 'aa;aah;aahed;' words2 = 'aahing;aardvark;'
The problem is that I want to go through the different strings. My current code is this:
Code: [Select]
function checkWord(word)
local letterkeys = {1,72,129,241,310,360,402,437,479,533,541,551,582,647,679,720,822,827,895,1019,1076,1112,1130,1152,1153,1155}
jstart = letterkeys[string.byte(word) - string.byte('a') + 1]
for i = jstart,1158 do
loadstring("abc = words"..i)
if string.find(abc,word) then
return true
end
end
return false
end

The letterkeys indexes a place for each letter, so the searching will go faster. Then it starts at that index and goes through each string and searches it using the string.find().

The loadstring thing doesn't work. It's purpose is to try and execute
Code: [Select]
abc = words12or
Code: [Select]
abc = words13depending on the value of i. This way I can avoid a big table that'll probably give me memory errors. It's basically like indexing without a big master table without a huge variable.

I'm not too familiar with loadstring, but it seems very powerful if it can be used like this.
Title: Re: Scramble/Boggle Lua
Post by: 3rik on July 23, 2012, 10:57:29 pm
I tested this way on the student software and it took about 3 seconds to load my list of ~100,000 words and convert it to the table. From there it was able to index any word very quickly (including long words like symptomatologically). The overall memory is a tad bulky (but there's only so much you can shrink 100,000 words). Each key, however, only points to a table containing, at most, 27 new keys.

A warning: don't paste tables like this into programs bulky IDEs with syntax highlighting. I pasted a table into the student software, walked away for an hour, came back and it was still trying to highlight everything. I eventually gave up and used the old scripting tools to test out the method.

I'll attach the code I tried with.

EDIT: I just realized that there are two lists in this program. There is still a table with all 100,000 words in it. I haven't sent this code to my calculator, so I'm not 100% sure that there won't be any memory issues.

EDIT2: I just realized, if one wanted definitions included with this structure, the values of the endofs (or _s) would just need to be changed from true to the definition. This wouldn't really apply to Boggle, but it could be used elsewhere.

EDIT3: loadstring is intended to be more for accepting code from the user. oclua is a good example of this. Tables and strings should be able to handle this problem without loadstring.
Title: Re: Scramble/Boggle Lua
Post by: Nick on July 24, 2012, 12:22:03 pm
A warning: don't paste tables like this into programs with syntax highlighting. I pasted a table into the student software, walked away for an hour, came back and it was still trying to highlight everything. I eventually gave up and used the old scripting tools to test out the method.

you probably never heard of notepad++ ?? it takes 0.00001 seconds to load, and it only loads the parts you see, so as you scroll it colors the part you see, so no unnecessary coloring happens :)
Title: Re: Scramble/Boggle Lua
Post by: 3rik on July 24, 2012, 12:56:52 pm
Notepad++ took more like a whole second to paste everything (over 1,000,000 characters after all).  :P

Notepad++ is kind of the exception. It's a very lightweight program  :D. Bulky IDEs like the script editor in the student software tend to crash (or come very close) when I paste in the code, though. I don't even think the syntax highlighting can be turned off in the student software to avoid this issue.  :(
That's why I had to use the old scripting tools and Notepad++.

I clarified this in my previous post.
Title: Re: Scramble/Boggle Lua
Post by: Nick on July 24, 2012, 01:45:23 pm
Notepad++ took more like a whole second to paste everything (over 1,000,000 characters after all).  :P

Notepad++ is kind of the exception. It's a very lightweight program  :D. Bulky IDEs like the script editor in the student software tend to crash (or come very close) when I paste in the code, though. I don't even think the syntax highlighting can be turned off in the student software to avoid this issue.  :(
That's why I had to use the old scripting tools and Notepad++.

I clarified this in my previous post.

oh well, never mind then, my pc is probably faster than yours  >:D
Title: Re: Scramble/Boggle Lua
Post by: 3rik on July 24, 2012, 01:51:49 pm
Wouldn't be surprised. Mine is actually just a laptop hooked up to a monitor. I think I was also running a bunch of other things when I first tried pasting into the student software.
Title: Re: Scramble/Boggle Lua
Post by: apcalc on July 24, 2012, 07:15:26 pm
Once again, another great Nspire project!  Good work! :D
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on July 24, 2012, 08:39:11 pm
I use Notepad++ and nspire_emu!  :D I write my own C++ program to format the file.

3rik, I'll give your method a try. As long as you didn't get a memory error, that method will work.

I still wish that loadstring thing worked though, it would've been nice.  :(

EDIT: I get a memory error in nspire_emu :(, even using 3rik's shrunken dictionary. Oh, and 3rik's program also causes a memory error in nspire_emu D:
Title: Re: Scramble/Boggle Lua
Post by: 3rik on July 24, 2012, 10:35:36 pm
Figures. The student software must allow for more memory to be used. One thing that could be done is generate the table before hand. It would be faster and there wouldn't be two lists of words. 100,000 words is a bit excessive, so a dictionary with less words would also work. I tried actually sending this to my nspire cx, so as long as the rest of the program isn't massive, this should work. There are 81536 words. I'll attach the file of the pre-generated table.

Edits:

It takes a little more than 20 seconds for my calculator to open the document with the script. Indexing the table, however, takes less than a millisecond.

Also, don't forget to assign this table to a variable.

I wouldn't say "shrunken." This dictionary is probably larger than an array with the words. It just indexes a lot faster than an array since most of the guess and check is avoided.
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on July 25, 2012, 09:31:01 am
Figures. The student software must allow for more memory to be used. One thing that could be done is generate the table before hand. It would be faster and there wouldn't be two lists of words. 100,000 words is a bit excessive, so a dictionary with less words would also work. I tried actually sending this to my nspire cx, so as long as the rest of the program isn't massive, this should work. There are 81536 words. I'll attach the file of the pre-generated table.
Yeah. Having a pregenerated table is nice. Probably saves memory too. 80,000 words is around half my library of 170,000+ words. I'll test some stuff, and maybe 80,000 will be good enough.

I wouldn't say "shrunken." This dictionary is probably larger than an array with the words. It just indexes a lot faster than an array since most of the guess and check is avoided.

The dictionary you used is actually a lot shorter than mine. The filesize was noticeably smaller (by maybe 100+ kilos).

Edit: The pregenerated table still generated a memory error D: Why will this program not cooperate?
Title: Re: Scramble/Boggle Lua
Post by: 3rik on July 27, 2012, 11:22:28 pm
When I load the script with the pre-generated table, Lua is using ~20 MB of the 64 MB of operating memory. TI probably set the max level lower than full capacity. So, maybe the table by itself is just small enough to fit in under their max but when the rest of the program is running, Lua uses even more memory and that signals to Lua to throw an error.

I can attach the program I used to generate the table and you can experiment with shorter tables.

I was looking at the 12dicts wordlists. Here's a download link: http://downloads.sourceforge.net/wordlist/alt12dicts-4.zip (http://downloads.sourceforge.net/wordlist/alt12dicts-4.zip).
They come with some symbols to catagorize some of them, but I just deleted them all. I just used the replace feature in Notepad++ and turned on regular expressions. I had it find
Quote
[^a-z]
and replace it with nothing.

I also had it replace
Quote
\r\n
with
Quote
","
and added the brackets to make it a table.

Then, I assigned the result to the variable "list" in the attached program and ran it using Lua (on the computer). It will write to (or overwrite) a file called pregendict.txt (in the current directory) with the code for the pre-generated table.
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on July 29, 2012, 11:33:49 am
IT'S BEEN DONE!  ;D

Well, the solution to the problem was really underwhelming. I simply used a bunch of strings to store all of the words, separated by semicolons. And then, I put them into an array.  <_< I didn't test this earlier because I was sure I would have had a memory error. Whatever the case may be with this memory stuff, I now have the Scramble program working with a dictionary of 170,000+ words!

Thank you all for your help and support and ideas!

Right now, the random board generation ain't working too well.  :P
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on August 02, 2012, 04:36:38 pm
Progress Report!  :D

(somewhat effective) Random Board Generation, Large 170,000+ words dictionary, A scrolling results page have all been added. Idk why I capitalized those random letters.

Screenshot included.

Edit: Anybody want a release yet?

Edit2: If anybody's wondering why that game ended at 1:30, I just changed the timer value so it wouldn't take as long to get to the results page.

Edit3: I got this little flashing icon  in the top right corner. It's the low memory icon! The same one from that one screenshot from OS 3.2 demonstrating the physics engine! :D
Title: Re: Scramble/Boggle Lua
Post by: nyanfly on August 02, 2012, 11:32:58 pm
This is based off of Scramble with Friends, right? So you should find a way to add internet connectivity. Maybe even 3G :P.
Title: Re: Scramble/Boggle Lua
Post by: Scipi on August 02, 2012, 11:57:47 pm
Currently, the Nspire seires doesn't support any kind of wireless or internet connectivity, not even with Ndless. :P
Title: Re: Scramble/Boggle Lua
Post by: ruler501 on August 03, 2012, 12:22:51 am
Maybe we could fix that though...

We can write usb drivers so maybe it would be possible to hook it up to the internet one day
Title: Re: Scramble/Boggle Lua
Post by: 3rik on August 04, 2012, 10:04:03 pm
I'm glad you found a solution. It looks like there's less lag than I expected. A table probably takes up more memory than a string.
Title: Re: Scramble/Boggle Lua
Post by: Nick on August 05, 2012, 08:48:45 am
isn't there a download already? or am i just looking ove rit? because i want to test it, and see how fun it is :)
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on August 06, 2012, 11:29:07 am
Ok. Here's a release! Please feel free to post any suggestions about this game!
Title: Re: Scramble/Boggle Lua
Post by: Nick on August 06, 2012, 03:39:12 pm
ok, a quick review:

pressing '.' throws an error
making the word 'it' and 'me' throws an error (probably all words with two letters, line 211: attempt to perform arithmetic on a nil value)
i think you have to be too fast to make the words, maybe slow it down a little
after a couple of seconds you list of made words dissapears, but it does not return to the start or something, it just clears, which is kinda weird..

the timer is still at 1:30 :)

otherwise it's very nice :) i love it
Title: Re: Scramble/Boggle Lua
Post by: DJ Omnimaga on August 06, 2012, 04:33:59 pm
Looks nice and fun. I remember playing this game 20 years ago in its original form and enjoyed it. I should hopefully enjoy the calc version as much.
Title: Re: Scramble/Boggle Lua
Post by: someone on August 06, 2012, 06:59:01 pm
ok, a quick review:

pressing '.' throws an error
making the word 'it' and 'me' throws an error (probably all words with two letters, line 211: attempt to perform arithmetic on a nil value)
i think you have to be too fast to make the words, maybe slow it down a little
after a couple of seconds you list of made words disappears, but it does not return to the start or something, it just clears, which is kinda weird..

the timer is still at 1:30 :)

otherwise it's very nice :) i love it

You can change the time inside the function on.timer, just change the if timepassed > 30000 to 120000 & you'll have the 2 minutes you're supposed to have.

I also got an error, but it was on line 212, when it should be painting the path of the text selected, if I'm not mistaken.
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on August 06, 2012, 07:02:02 pm
ok, a quick review:

pressing '.' throws an error
Fixed

Quote
making the word 'it' and 'me' throws an error (probably all words with two letters, line 211: attempt to perform arithmetic on a nil value)
Really? Two letter words work for me? Are you testing on-calc, nspire_emu, or Student Software?

Quote
i think you have to be too fast to make the words, maybe slow it down a little
How do you suggest doing that, slowing down the timer? I could try that.

Quote
after a couple of seconds you list of made words dissapears, but it does not return to the start or something, it just clears, which is kinda weird..
That doesn't happen with me either...

Quote
the timer is still at 1:30 :)
Fixed.

Quote
otherwise it's very nice :) i love it
Looks nice and fun. I remember playing this game 20 years ago in its original form and enjoyed it. I should hopefully enjoy the calc version as much.
Thanks!
Title: Re: Scramble/Boggle Lua
Post by: 3rik on August 06, 2012, 09:15:52 pm
I tried it out, but it kept giving errors around line 212. This is what the console says
Quote
212: attempt to index global 'letterkeys' (a nil value)
and
Quote
212: attempt to perform arithmetic on a nil value
It seems that letterkeys isn't defined anymore.
Title: Re: Scramble/Boggle Lua
Post by: cyanophycean314 on August 12, 2012, 07:17:12 pm
Hmm, I've never ran into that error on my calculator, but I hope this new version fixes it?
Title: Re: Scramble/Boggle Lua
Post by: 3rik on August 13, 2012, 12:20:03 am
Errors happen much less frequently now that letterkeys is defined.

There are still a couple errors.
If I press, release, and then hold tab while I push a letter key, I get an error on line 228. dx is a nil value.
If I rapidly jam the tab button (or get unlucky every once in a while), there's an error on line 212. word is an empty string. This causes an arithmetic error because string.byte is returning nothing.
Holding tab doesn't work as well on the student software as on the handheld. This isn't a big concern.

This game is really coming along. Good work so far!  :)