Crossword puzzle
Helge Haensel
Hallo NG!
Still somebody watching this newsgroup?
I have a wordlist with some 180.000 entries, of course of different length
and not necessarily sorted. I create a pattern of characters like
'.EA...R'.
Now I am looking for a search algorithm that throws up 'WEATHER' but not
'THEATER' and so on.
This is a classical crossword puzzle issue and I assume it is already
solved.
Do you know a suitable/fast solution?
Thanks!
Vy 73! Helge
--
Helge, DJ1WM
Ralph
"Helge Haensel" <dj...@nurfuerspam.de> wrote in message
news:op.u2nuk...@dj1wm.fqdn.th-h.de...
You might take a look at regular expressions.
Which library will depend on your OS, development platform, ...
-ralph
Gordon Rahman
a$(1) = "coconut"
a$(2) = "american"
a$(3) = "weather"
a$(4) = "heater"
a$(5) = "theater"
a$(6) = "amphi-theater"
for t = 1 to 6
if instr(a$(t),"ea",2) = 2 and instr(a$(t),"e",6) = 6 then print a$(t)
next t
Gordon
"Helge Haensel" <dj...@nurfuerspam.de> wrote in message
news:op.u2nuk...@dj1wm.fqdn.th-h.de...
>
DMCC
grep does that:
user@unixbox:~$ grep '^.ea...r$' /usr/share/dict/words
Heather
Leander
Realtor
beadier
feather
headier
heather
heavier
leafier
leakier
learner
leather
mealier
meander
meatier
reactor
readier
realtor
seamier
teacher
tearier
wearier
weather
ne...@rtrussell.co.uk
> You might take a look at regular expressions.
> Which library will depend on your OS, development platform, ...
A BBC BASIC solution using regular expressions is listed below.
Richard.
http://www.rtrussell.co.uk/
To reply by email change 'news' to my forename.
SYS "LoadLibrary", @lib$+"gnu_regex.dll" TO gnu_regex%
IF gnu_regex% = 0 ERROR 100, "Cannot load gnu_regex.dll"
SYS "GetProcAddress", gnu_regex%, "regcomp" TO `regcomp`
SYS "GetProcAddress", gnu_regex%, "regexec" TO `regexec`
DIM buffer% 255
pattern$ = "^.ea..e. "
SYS `regcomp`, buffer%, pattern$, 2 TO result%
IF result% ERROR 101, "Failed to compile regular expression"
sowpods% = OPENIN("C:\mydown~1\sowpods.txt")
REPEAT
INPUT #sowpods%, A$
IF ASC(A$) = 10 A$ = MID$(A$,2)
SYS `regexec`, buffer%, A$, 0, 0, 0 TO result%
IF result% = 0 PRINT A$
UNTIL EOF#sowpods%
CLOSE #sowpods%
Gordon Rahman
I watch this Newsgroup too.
Thougth it was about BASIC.
So here is my BASIC solution.
This may not be a fast solution, but it's BASIC.
while b$ <> "zzz"
b = b + 1
read b$
wend
restore
dim a$(b)
for t = 1 to b
read b$
a$(t) = b$
next t
data Heather,Leander,Realtor,beadier,feather,headier,heather
data heavier,leafier,leakier,learner,realtor,seamier,teacher
data tearier,wearier,weather,coconut,american,theater,"ampi-theater"
data zzz
input "first instring to look for ";f$
input "position of first instring ";pf
input "second instring to look for ";s$
input "position of second instring ";ps
for t = 1 to b
if instr(a$(t),f$,pf) = pf and instr(a$(t),s$,ps) = ps then
print a$(t)
end if
next t
print :print "done"
wait
'global items
'function found$(f$,pf,s$,ps)
'for t = 1 to items
'if instr(a$(t),f$,pf) = pf and instr(a$(t),s$,ps) = ps then
'found$ = a$(t)
'end if
'next t
'end function
Gordon
"Helge Haensel" <dj...@nurfuerspam.de> wrote in message
news:op.u2nuk...@dj1wm.fqdn.th-h.de...
>
Helge Haensel
Hi, surprise!
Well, I was a little bit short with my search/find problem.
My system is: WindowsXP/HE/SP3, OfficeXP/Pro/SP3, VB5EE/SP3
Starting with the pattern as given above I need the possible fitting words
from the word list. 'WEATHER' or 'REALTOR' fits, 'BROTHER', 'WEATHERMAN'
don't fit.
Regular Expressions are a good idea, but I think I can't use them in VB5/6.
The solution of Gordon is a first step but not very flexible for an
extensive use.
Something like 'grep' would be optimal when using a linux/unix system and
being a keyboard hacker. The example code by Gordon isn't very flexible
because the pattern of course changes in length, in chars positions and so
in '.'-positions as a 'grep' would easily allow. But it is possibly the
only starting point to begin with.
Thanks so far.
Helge
ne...@rtrussell.co.uk
> Regular Expressions are a good idea, but I think I can't use them
> in VB5/6.
I'm pretty sure you can. If you can use 'gnu_regex.dll' in BBC BASIC
(see the example I posted) I'd be extremely surprised if you can't use
it in VB too. For details of where to download 'gnu_regex.dll' see
here:
http://bb4w.wikispaces.com/Using+regular+expressions
Helge Haensel
<ne...@rtrussell.co.uk>:
Hi, Richard.
Downloaded 'gnu_regex.exe' via the given link to my desktop.
After executing the exe I can't find it anywhere.
Searched for 'gnu_regex.dll'. OK?
Helge
Gordon Rahman
I will give it a try.
I'll make it flexible.
Someone (Derek) did that in QB already and published
the code in the ALT.LANG.BASIC Newsgroup. (15 september 2009)
I'm thinking of a different approach than Derek.
I'm back to the drawingboard.
Gordon.
"Helge Haensel" <dj...@nurfuerspam.de> wrote in message
news:op.u2nuk...@dj1wm.fqdn.th-h.de...
>
Helge Haensel
> Hallo Helge,
>
> I will give it a try.
> I'll make it flexible.
>
> Someone (Derek) did that in QB already and published
> the code in the ALT.LANG.BASIC Newsgroup. (15 september 2009)
>
> I'm thinking of a different approach than Derek.
> I'm back to the drawingboard.
>
> Gordon.
>
Sorry about all that trouble. But now it becomes an interesting project.
BTW, all packers I have do not unpack that EXE! (downl'd from 'here' on
the linked page)
I'll check the ALB-Group via Google.
So long!
Helge
Helge Haensel
> Hallo Helge,
>
> I will give it a try.
> I'll make it flexible.
>
> Someone (Derek) did that in QB already and published
> the code in the ALT.LANG.BASIC Newsgroup. (15 september 2009)
Hi, actually 15.09.2008. Got it.
Helge
Gordon Rahman
'Pattern recognition meaning find ea and e and their relative pos
c$ = "...hello...ea...e." :print c$
for t = 1 to len(c$)
if mid$(c$,t,1)="." and mid$(c$,t+1,1)<>"." then gosub [dotEndFound]
if mid$(c$,t,1)<>"." and mid$(c$,t+1,1)="." then gosub [charEndFound]
next t
pf = s(1)+1
f$ = mid$(c$,pf,u(1)-s(1))
print "from ";pf,f$;" to ";u(1)
ps = s(2)+1
s$ = mid$(c$,ps,u(2)-s(2))
print "from ";ps,s$;" to ";u(2)
wait
[dotEndFound]
s1 = s1 + 1 :s(s1) = t
'print "start";s1;" at position ";s(s1) 't
return
[charEndFound]
s2 = s2 + 1 :u(s2) = t
'print "stop";s2;" at position ";u(s2) 't
return
'input "first instring to look for ";f$
'input "position of first instring ";pf
'input "second instring to look for ";s$
'input "position of second instring ";ps
Good luck,
Gordon
"Helge Haensel" <dj...@nurfuerspam.de> wrote in message
news:op.u2nuk...@dj1wm.fqdn.th-h.de...
>
ne...@rtrussell.co.uk
> Downloaded 'gnu_regex.exe' via the given link to my desktop.
> After executing the exe I can't find it anywhere.
Looks like the file has become corrupted since I last downloaded it.
I've put the correct version here for you:
http://www.rtr.myzen.co.uk/gnu_regex.exe
Helge Haensel
Well, I got Dereks code to run for me. I simplified it to my needs and it
finds the pattern (see above) within 2 seconds out of my wordlist with
178510 entries.
For Dereks code look here:
http://groups.google.com/group/alt.lang.basic/browse_thread/thread/f68297c561faef89/c33db2c75758f0e3?lnk=gst&q=regex#c33db2c75758f0e3
Thanks to Derek, thanks to all of you!
Helge
The code of my main is as follows:
Sub main()
Let J = 1
hdl0 = FreeFile
Open "C:\Utilities\Kreuzwort\dist\files\wordlist.txt" For Input As #hdl0
Do While Not EOF(hdl0)
M$ = "-1"
RE$ = "^.EA...R$"
Line Input #hdl0, Text$
If M$ = LTrim$(Str$(RegExp%(RE$, Text$))) Then Debug.Print "Okay"
Let J = J + 1
DoEvents
Loop
Debug.Print J
Close
End sub
Ralph
<snipped>
> Regular Expressions are a good idea, but I think I can't use them in
VB5/6.
I prefer the other suggestions as a foundation for a dedicated application,
but for completeness - you can certainly use Regular Expression with VB...
"How to Use Regular Expressions in Visual Basic"
http://www.regular-expressions.info/vb.html
Regular Expressions are handy and easy to code, however, no RegExp library
will be as quick as a dedicated parser/pattern-matcher. And not slower in
terms of a few percentage, but in terms of 3 to 5 times slower. This goes
for any of the RegExp tools like 'Grep' or 'Awk' tools.
But works well enough for proof-of-concept, and discovering initial rules
(patterns).
-ralph
Phred
>On Nov 1, 11:02=A0am, "Helge Haensel" <dj...@nurfuerspam.de> wrote:
>> Downloaded 'gnu_regex.exe' via the given link to my desktop.
>> After executing the exe I can't find it anywhere.
>
>Looks like the file has become corrupted since I last downloaded it.
>I've put the correct version here for you:
>
> http://www.rtr.myzen.co.uk/gnu_regex.exe
G'day Richard,
Curiosity got the better of me and I had a squiz at that site -- is it
all yours? Seems like quite an eclectic mix of stuff there!
I couldn't resist downloading the small JPEG (bp.jpg) and note that at
least it seems to be yours. (Judging by the annotation in it! :-)
So now I'm even more curious -- what do you mean by that "Full
gamut colour recovery"? What did you start with? And what did you
use to do it? (Apart from obvious skill!)
Cheers, Phred.
--
ppnerk...@THISyahoo.com.INVALID
ne...@rtrussell.co.uk
> So now I'm even more curious -- what do you mean by that "Full
> gamut colour recovery"?
http://colourrecovery.wikispaces.com/
Derek
> Am 31.10.2009, 11:40 Uhr, schrieb Helge Haensel <dj...@nurfuerspam.de>:
>
>
>
> > Hallo NG!
> > Still somebody watching this newsgroup?
>
> > I have a wordlist with some 180.000 entries, of course of different
> > length and not necessarily sorted. I create a pattern of characters
> > like '.EA...R'.
> > Now I am looking for a search algorithm that throws up 'WEATHER' but not
> > 'THEATER' and so on.
> > This is a classical crossword puzzle issue and I assume it is already
> > solved.
> > Do you know a suitable/fast solution?
> > Thanks!
>
> > Vy 73! Helge
>
> Well, I got Dereks code to run for me. I simplified it to my needs and it
> finds the pattern (see above) within 2 seconds out of my wordlist with
> 178510 entries.
> Thanks to Derek, thanks to all of you!
> Helge
Helge, you are entirely welcome. I am glad that you actually got some
use out of it. I have actually been thinking about how to handle this
crossword puzzle issue of yours for the last couple of days using a
non-regexp solution. I've reached the point where I may churn out a
bit of code but soince the regexp solution does what you need, it will
just be for my own amusement now.
Cheers
Derek
Derek
>
> - Show quoted text -
So in the interests of amusement, here is the non-regexp code...
-- Begin code ----
CONST WordList$ = "C:\BASIC\WORDLIST\2OF12.TXT"
CLS
PRINT "This looks up partial words for a crossword"
LET Wcount = 0
OPEN WordList$ FOR INPUT AS #1
DO WHILE NOT EOF(1)
LET Wcount = Wcount + 1
LINE INPUT #1, T$
LOOP
CLOSE #1
PRINT "The wordList contains"; Wcount; "words"
PRINT
PRINT "Enter a word using dots where you don't know the letters"
PRINT "For instance: h..th.."
PRINT "The program will give you a list of possible words"
PRINT "When you are finished or fed up, just enter a blank word."
DO
PRINT
LINE INPUT "Partial word: ", W$
LET W$ = UCASE$(LTRIM$(RTRIM$(W$)))
IF W$ = "" THEN EXIT DO
LET W = LEN(W$)
PRINT W$; " matches: ";
OPEN WordList$ FOR INPUT AS #1
DO WHILE NOT EOF(1)
LET Wcount = Wcount + 1
LINE INPUT #1, T$
IF LEN(T$) = W THEN
LET P$ = UCASE$(T$)
FOR J = 1 TO W
IF MID$(W$, J, 1) = "." THEN
MID$(P$, J, 1) = "."
END IF
NEXT
IF P$ = W$ THEN
PRINT T$; " ";
END IF
END IF
LOOP
CLOSE #1
PRINT
LOOP
SYSTEM
-- End code ----
This is proof of concept. It wouldn't be difficult to repackage it as
a function though. And it is much faster than a regexp.
Cheers
Derek
Helge Haensel
> Helge, you are entirely welcome. I am glad that you actually got some
> use out of it. I have actually been thinking about how to handle this
> crossword puzzle issue of yours for the last couple of days using a
> non-regexp solution. I've reached the point where I may churn out a
> bit of code but soince the regexp solution does what you need, it will
> just be for my own amusement now.
>
> Cheers
>
> Derek
Hi, Derek.
Again thanks for your code. I also came to the solution, that solving it
by use of regex functions would be the best way. At first I thought that a
much simpler way should be possible but when imaging that thousands and
much more different (in length and configuration) patterns by the time
need to be evaluated I think that the regex way is ok. I now simply create
a pattern like "^" & "..xyz...abc" & "$" and scan the list, done. Before
- I change all words in the list to lower case and german 'umlaute' to
their two letter combinations. Words including some kind of punctuation
generally are skipped. Sorting is also helpful so I can generate an
alphabetic array and when a first character is available the search speeds
up tremendously. 180.000 words are scanned in less than 2 seconds but the
preparation of the list once at start of the program takes some seconds.
You can use it also for lists of English words, of course. Do you are
interested? (It is not yet ready!). Give me a note.
Cheers Helge
winston...@yahoo.com
My question is who comes up with the wordlists? I ran this on OS X and
got some extra words compared to this list above and these extras did
not seem to be real english words. Guess I need to look them up.
Helge Haensel
Well, I will check that, sorry later!
Helge
winston...@yahoo.com
Thanks, I always enjoy Basic code. That is why I'm subscribed to this
newsgroup after all.
My bookshelf is filled with Basic books...
Able
"Derek" <dere...@yahoo.ca> wrote in message
news:a6828112-67cb-4713...@d10g2000yqh.googlegroups.com...
-- Begin code ----
-- End code ----
Cheers
Derek
There are a few points that have occurred to me.
1) 180,000 words may not be enough. Each root word can
have it's prefixes and suffixes. A more complete database
would have an unmanageable number of words, or would
have to have root words and a qualifying number, each bit
set or not depending upon a supplementary list of the said
suffixes and prefixes.
2) a data store which is not being altered by the users(s)
can be index sorted, as I remember the O/P said sorting
was a difficulty.
3)sticking with the existing word list, it could be indexed for
both length and alpha sorted on each character.
the code (perhaps yours) might make use of pruning first to
length, then on reference to the required index. e.g in the
example, you would look at the length first, then the second
character sort, then the third, etc.
I would like to read how this might or might not work
in practice.(I wouldn't dream of trying it myself)
Helge Haensel
Hi Able,
the points you mentioned are absolutely correct. I have other lists
containing >500.000 words. But that alters nothing to what you said.
My starting issue was to have a tool that helps me to solve
crossword puzzles and so I need list with the most common words for that
reason.
BTW, I am using VB5(/6).
> 2) a data store which is not being altered by the users(s)
> can be index sorted, as I remember the O/P said sorting
> was a difficulty.
Yes a quick sort over the 180.000 words took minutes and so
didn't speed up the search process.
Correct, my alpha array as mentioned earlier is a first start
in that direction.
> 3)sticking with the existing word list, it could be indexed for
> both length and alpha sorted on each character.
> the code (perhaps yours) might make use of pruning first to
> length, then on reference to the required index. e.g in the
> example, you would look at the length first, then the second
> character sort, then the third, etc.
Ok, there are many chances to achieve a goal.
Thanks for your ideas. I see much work needs to be done.
Helge
Phred
>On Nov 2, 10:43=A0am, ppnerkDELETET...@yahoo.com (Phred) wrote:
>> So now I'm even more curious -- what do you mean by that "Full
>> gamut colour recovery"?
>
> http://colourrecovery.wikispaces.com/
Thanks for that info Richard. I must admit I was mainly interested
because I have some old colour pics and slides that have seriously
degraded (especially 30-year-old Ectachrome slides taken when I was
foolish and ignorant enough to use it instead of Kodachrome).
From what I gather, your technique depends on "clues" in the recorded
image(s), so wouldn't be of much use to me? :-(
[But I admit I haven't yet followed *all* the links on that site.]
Cheers, Phred.
--
ppnerk...@THISyahoo.com.INVALID
ne...@rtrussell.co.uk
> From what I gather, your technique depends on "clues" in the recorded
> image(s), so wouldn't be of much use to me? :-(
That's right.
Richard.
Helge Haensel
Well, Derek.
I shrinked my function by help of your code to:
Function AliasRegex(ByVal aRegExp as string, ByVal aText As String) As
String
Dim t As Integer
If Len(aRegExp) <> Len(aText) Then AliasRegex = "0": Exit Function
For t = 1 To Len(aRegExp)
If Mid(aRegExp, t, 1) <> "." Then
If Mid(aRegExp, t, 1) <> Mid(aText, t, 1) Then
AliasRegex = "0"
Exit Function
End If
End If
Next t
AliasRegex = "-1"
End Function
I think that is it now!
Cheers, Helge
Derek
>
> Well, Derek.
> I shrinked my function by help of your code to:
>
> Function AliasRegex(ByVal aRegExp as string, ByVal aText As String) As
> String
> Dim t As Integer
>
> If Len(aRegExp) <> Len(aText) Then AliasRegex = "0": Exit Function
> For t = 1 To Len(aRegExp)
> If Mid(aRegExp, t, 1) <> "." Then
> If Mid(aRegExp, t, 1) <> Mid(aText, t, 1) Then
> AliasRegex = "0"
> Exit Function
> End If
> End If
> Next t
> AliasRegex = "-1"
> End Function
>
> I think that is it now!
Excellent! That looks good.
Cheers
Derek
Bob Larter
The process relies on residual chroma information retained on
cine-recorded colour TV programs, so it's of no use for film.
Personally, I recover faded photos by scanning them (with as many bits
per colour channel as possible), then re-levelling R,G & B in Photoshop
(16 bit mode). It gives you a pretty good result, & with some tweaking,
an excellent result - even on badly faded colour prints dating back to
the 70's.
--
W
. | ,. w , "Some people are alive only because
\|/ \|/ it is illegal to kill them." Perna condita delenda est
---^----^---------------------------------------------------------------
Phred
In article <4afa711a$1...@dnews.tpgi.com.au>, Bob Larter
<bobby...@gmail.com> wrote:
>Phred wrote:
>> In article
> <1a96ebe5-6464-4842...@j24g2000yqa.googlegroups.com>,
> "ne...@rtrussell.co.uk" <ne...@rtrussell.co.uk> wrote:
>>> On Nov 2, 10:43=A0am, ppnerkDELETET...@yahoo.com (Phred) wrote:
>>>> So now I'm even more curious -- what do you mean by that "Full
>>>> gamut colour recovery"?
>>> http://colourrecovery.wikispaces.com/
>>
>> Thanks for that info Richard. I must admit I was mainly interested
>> because I have some old colour pics and slides that have seriously
>> degraded (especially 30-year-old Ectachrome slides taken when I was
>> foolish and ignorant enough to use it instead of Kodachrome).
>>
>> From what I gather, your technique depends on "clues" in the recorded
>> image(s), so wouldn't be of much use to me? :-(
>>
>> [But I admit I haven't yet followed *all* the links on that site.]
>
>The process relies on residual chroma information retained on
>cine-recorded colour TV programs, so it's of no use for film.
>
>Personally, I recover faded photos by scanning them (with as many bits
>per colour channel as possible), then re-levelling R,G & B in Photoshop
>(16 bit mode). It gives you a pretty good result, & with some tweaking,
>an excellent result - even on badly faded colour prints dating back to
>the 70's.
Thanks for that advice Bob. Have you tried that approach with slides?
I guess it should work the same, but a problem could be scanning
slides with sufficient resolution without going to an expensive
dedicated slide scanner. (Do those still exist? I haven't seen
mention of them for a few years now, not even ads. Perhaps like so
much else, they have succumbed to the mediocrity of the masses?)
Cheers, Phred.
--
ppnerk...@THISyahoo.com.INVALID