|
Hello,
Suppose that we have a NxN square filled with letters. Which algorithm is the best to find any words starting with NiNj and continue from the starting point through adjacent squares (left-right-cross) where the word is in any length L?
Thanks and best regards..
.:: Something is Wrong ::.
|
|
|
|
|
I wrote a decent 5x5 Boggle game and felt that the problem was the dictionary. So...I kept multiple partial matches going always working the partial match with the lowest lexical value.
Finds game buried in some oddball directory... Discovers it does not work in xp. Posting an old result...
A L E R E
O O T S T
T G L U T
N Z O Y E
S C E N F
alert
alertest
alertly
ales
aloe
alter
alto
alts
colog
cols
colt
colter
coly
cone
coney
cony
coulter
couter
cozen
cozey
enfetter
enol
erst
ester
eyen
eyne
fets
fetter
fetus
feus
fytte
glue
gluey
glut
gluten
goal
goer
goes
gone
gout
gouty
lest
lets
logo
loot
looter
lots
lotus
lust
luster
lustre
lusty
lute
nets
nett
netter
neuter
nolo
nous
oleo
oles
oots
ousel
oust
ouster
outer
outgo
outgoes
outre
outs
outsert
outset
oyez
reset
rest
result
retool
rets
retuse
scene
scone
scouse
scout
scouter
sere
sloe
slog
slot
slue
slut
stela
steno
stere
stereo
stey
stoa
stole
stool
strette
stutter
stye
suet
suety
sutler
tela
terse
test
tester
testy
toes
tola
tole
tolu
toluene
tool
tooler
toot
tooter
tootle
tootler
tote
toter
tots
trestle
tret
tuts
tutty
tyne
ulster
user
utter
yett
youse
zone
|
|
|
|
|
So ? 
.:: Something is Wrong ::.
|
|
|
|
|
pashje wrote: Which algorithm is the best
It depends on the value of N and on the lenght of the dictionary (L)...
If N is too big (compared with L) the best way is to try to search every word of the dictionary on the NxN square.
Elseway (N small) try to extract every possible words, and then test if the word exist.
BTW I prefere in both cases to use the first method. It seemes easyer to be implemented.
Russell
|
|
|
|
|
Well both methods will do the job surely but what if N is a Z+ ? It may 3 but also 3000.. So the performance is an important issue..
Maybe a genetic algorithm or somemthing with trees will work well ? Any text about thiss issue will really help !;)
.:: Something is Wrong ::.
|
|
|
|
|
if N can change from 3 to 3000...well...I think that it is not possible to find an algorithm with always an High performance. You need to implement at least 2 algorithms: the program will use the first one if N<k and="" the="" other="" if="" n="">K.
The treshold K must be set during your test to find what algorythm is faster.
About genetic algorithms I think that this isn't the right way.
I think that you can perform a tree algorithm sorting the dictionary somehow to avoid to check every words.
Russell
|
|
|
|
|
I did my final year project on a scrabble game and i found that the best way to increase speed when matching words is by choosing an efficient data storage technique for your dictionary.
A tree structure is needed to solve this problem, a DAWG would probably be the best choice.
|
|
|
|
|
Hi everyone,
Could anyone kindly assist with some code (preferably Java) for the Travelling Salesman Problem that uses any of the following Heuristics
1. Tabu Search
2. Hill Climbing
3. GRASP (Greedy Randomized Adaptive Search Procedure)
4. Simulated Annealing
I need this to just text some problems.
Thanks
laremtj
Jesus Loves You, Give your Heart to Him Today
|
|
|
|
|
laremtj wrote: preferably Java
This is a Visual Studio/.NET Centric site, if in case you haven't noticed.
"Any sort of work in VB6 is bound to provide several WTF moments." - Christian Graus
|
|
|
|
|
I'm not sure this is the rigth place to post this question but it sounds like a math problem to me so...
Problem:
I need all the combinations of a set of numbers (to make it easy lets take 3 numbers, but eventualy it has to work for 15numbers and more)
the user will give in 3 number for example: 1 , 5 , 19
then the programme needs to give the following combinations:
1, 5, 19
1, 19, 5
5, 1, 19
5, 19, 1
19, 1, 5
19, 5, 1
I've been searching for some algoritme our other way to do this for several weeks now and just can't find it
any ideas on how I could achieve this??
If my help was helpfull let me know, if not let me know why.
The only way we learn is by making mistaks.
|
|
|
|
|
Hi,
if you want to list all combinations, recursion is what you need.
Build a method that takes a collection as an input, and let a for loop pick one element,
remove it, then call recursively with wath remains in the collection, until the collection
is empty; then return.
BTW: if your collection is ordered, and your method picks in that same order, the result will
be ordered too.
Warning: for n elements, the recursion depth will be n, the number of combinations n!
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Recursion is a bad thing. You can almost always remove recursion from an algorithm using a simple stack. Case in point, you can remove recursion from the suggested algorithm with a stack. Something like this:
1 on Stack
5 on Stack
19 on Stack
Start popping -> 1,5,19
19 on Stack
5 on Stack
Start popping -> 1,19,5
etc ...
HossFly
|
|
|
|
|
Hoss Fly wrote: Recursion is a bad thing
Nonsense! Recursion is simply one tool that any professional should consider. There may be performance issues in some applications, but often you can't beat it for simplicity and elegance. Recursive descent parsing is an excellent example.
Hoss Fly wrote: You can almost always remove recursion from an algorithm using a simple stack
So why not use the processor stack - i.e. recursion. If you use built-in support rather than roll your own stack the code may be cleaner and less error prone.
Unless the number of elements is large (in which case there is no point enumerating all n! permutations), recursion is a perfectly valid method of solution to consider.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
You made my point for me. You shouldn't use recursion if you do not know the recursion depth. Whereas with a stack it is never an issue. I can describe many a problem where one cannot KNOW the recursion depth in advance (Flood Fill, Point Insertion w/r to Triangulation, clipping, etc...)
I have fixed recurssion based algorithms in two commercial products. The crashes this type of logic causes is often very difficult to catch. Try finding it in millions of lines of code and you will have the same opinion.
It is probably ok for some text book or academic problems. problem is developers fail to realize the stack problem and take the easy approach. I advocate thinking stack first, and recursion second (or last resort, or never.)
HossFly
|
|
|
|
|
|
As Peter already told you, recursion has its merits; it is often abused, but in this case
it is the right approach. My last remark (the depth n and result count n!) was
intended to illustrate that: if you care to consume n! results, then a stack depth of n
would not be an obstacle.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
<br />
char[] harfler = new char[7];<br />
harfler[0] = tb1.Text.ToCharArray()[0];<br />
harfler[1] = tb2.Text.ToCharArray()[0];<br />
harfler[2] = tb3.Text.ToCharArray()[0];<br />
harfler[3] = tb4.Text.ToCharArray()[0];<br />
harfler[4] = tb5.Text.ToCharArray()[0];<br />
harfler[5] = tb6.Text.ToCharArray()[0];<br />
harfler[6] = tb7.Text.ToCharArray()[0];<br />
<br />
List<string> liste = new List<string>();<br />
<br />
for (int i = 0; i < harfler.Length; i++)<br />
{<br />
for (int j = (i + 1) % 7, x = 0; x < harfler.Length; x++)<br />
{<br />
if (i != j)<br />
{<br />
for (int k = (j + 1) % 7, y = 0; y < harfler.Length; y++)<br />
{<br />
if (k != i && k != j)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k]);<br />
for (int l = (k + 1) % 7, z = 0; z < harfler.Length; z++)<br />
{<br />
if (l != i && l != j && l != k)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l]);<br />
for (int m = (l + 1) % 7, t = 0; t < harfler.Length; t++)<br />
{<br />
if (m != i && m != j && m != k && m != l)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m]);<br />
for (int n = (m + 1) % 7, v = 0; v < harfler.Length; v++)<br />
{<br />
if (n != i && n != j && n != k && n != l && n != m)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m] + "" + harfler[n]);<br />
for (int o = (n + 1) % 7, q = 0; q < harfler.Length; q++)<br />
{<br />
if (o != i && o != j && o != k && o != l && o != m && o != n)<br />
{<br />
liste.Add(harfler[i] + "" + harfler[j] + "" + harfler[k] + "" + harfler[l] + "" + harfler[m] + "" + harfler[n] + "" + harfler[o]);<br />
<br />
}<br />
<br />
o = (++o) % 7;<br />
}<br />
}<br />
<br />
n = (++n) % 7;<br />
}<br />
}<br />
<br />
m = (++m) % 7;<br />
}<br />
}<br />
<br />
l = (++l) % 7;<br />
}<br />
}<br />
<br />
k = (++k) % 7;<br />
}<br />
}<br />
<br />
j = (++j) % 7;<br />
}<br />
}<br />
Surely it is not an efficient way but in a specisific project this has worked well for me. It combinates 7 letters and produce words at least with length 3 and at most length 7.
.:: Something is Wrong ::.
|
|
|
|
|
Hmmm... that looks like permutations to me, not combinations.
|
|
|
|
|
In C++ something like this is the way to go:
--------------------------------------------
// Console.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <iostream>
#include <algorithm>
#include <iterator>
void main()
{
using namespace std;
int Numbers[] = {1, 5, 19};
int *pOnePastEnd = Numbers + sizeof(Numbers)/sizeof(Numbers[0]);
sort(Numbers, pOnePastEnd);
copy(Numbers, pOnePastEnd, ostream_iterator<int>(cout, " "));
cout << endl;
while (next_permutation(Numbers, pOnePastEnd))
{
copy(Numbers, pOnePastEnd, ostream_iterator<int>(cout, " "));
cout << endl;
}
}
Steve
|
|
|
|
|
I see I got 2ed. Well it works perfectly and the OP didn't mention a language. If he's got a C++ compiler he can look in the source code and adapt the algorithm used to another language. Alternatively he could download STLport and do the same.
Steve
|
|
|
|
|
This is pseudocode for your solution:
ListCombinatoricalOrder(List L)
if (L is empty)
return
int n = L.Count
if (n == 1)
Write L[0]
return
Write(L)
ListCombinatoricalOrder(empty, L, n)
Done
ListCombinatoricalOrder(List Prefix, List comb, int count)
for (int i = 0; i < count; ++i)
List newPre = Prefix append comb[i]
List newComb = comb subtract comb[i]
if (i != 0)
Write(newPre, newComb)
ListCombinatoricalOrder(newPre, newComb, count - 1)
Done
WHERE:
Write(L) will write the entire list
Write(newPre, NewComb) will Write the list newPre then append the list NewComb to it
Notice the is an output generating algorithm not suited well for a library. But I left the details to you to make it more generic. This is just an idea of how to go about solving the combinatorical problem.
I hope this helps.
--Avi
-- modified at 4:42 Sunday 14th October, 2007
|
|
|
|
|
I have a set of machines, let's call them A,B,C,...etc and a bunch of tasks let's call them 1,2,3,...an so on. Now my machines aren't terribly reliable and often it may be the case that say A can do tasks 1 & 3, but can't do task 2, so obviously I shouldn't have it do task 2. Also each machine can only be assigned one task, so A can do 1 or 3, but not both. So let's say for example I have this:
A can do 1 & 3
B can do 1, 2 & 3
C can only do 3
The solution is obvious, A does 1, B does 2 and C does 3. This is fairly trivial for the case of only 3 machines and 3 tasks, but my real problem has 30 machines and potentially 30 tasks.
Is there an algorithm that handles these types of problems that somebody can point me in the direction of. It would need to suggest a solution (it's not necessary the case that any one solution would be better than another) or let me know that there is no solution and I need to fix my machines.
All I need is a nudge in the right direction.
Cheers!
|
|
|
|
|
Hungarian algorithm[^] maybe?
---- I don't care what you consider witty, but at least I do not blather on posting nonsense like Jim Crafton.-- Stringcheese, humbled by Crafton's ability to string together multiple sentences
|
|
|
|
|
Thanks, I'll check it out.
|
|
|
|
|
Hello,
I work for a steel fabrication plant and am faced with a problem I cannot solve. Hopefully the gang over here at Code Project can help me out a little...
First, let me define the terms I will use (a crash course in steel purchasing):
-Mill Order: simply an order of material placed to the steel mill
-Beams: should be self explanatory, but I want to cover their dimensioning:
-a beam has three dimensions, they are as follows; nominal flange depth (aka width), pounds per foot (weight), and length.
Sample: 10x15x9'-0" ( I should note here that the length property for each beam in the program is defined as the number
of 1/16ths of an inch that make up the length. ->
For the sample, the length would be 1728 (1728/16)/12=9).)
-Hundred Weight (or CWT): is the price of the beam per 100lbs. This is usually around $40-$50
-Standard Size: any beam length 30ft-65ft in increments of 5ft.
-Non-Standard Size: any beam of any length in increments of 6in. There is an extra charge of $0.25/cwt for non-standard beams.
-Bundle Requirements: a standard size 10x15 beam is sold in bundles of 3. If you need 5, you must buy 2 bundles and inventory
the extra.
a non-standard size 10x15 must meet at least one bundle requirement. So, if you need 4, they will sell you
4. But if you need 2, you must buy 3 and inventory the extra.
The bundle requirements change with each flange depth and weight.
Ok. Now to the logic bit...
I am given a list of all the beams for a job to order from the mill. Obviously I do not want to order every beam as is. I need to nest the beams into the mill order to optimize the amount of money being spent. If you do not know what I mean by "nest", let me explain: If I have 6 beams whose dimesions are 10x15x20', instead of ordering the beams without nesting and incuring a charge of $0.25/cwt for the non-standard length, I want to nest those 6 beams into 1 40' bundle.
This is the part that is difficult. I cannot seem to find a logic process to optimize all standard sizes vs. non-standard sizes vs. bundle requiremnts vs. pricing. If I could see a step by step process, or just have an idea of where to start, I would probably be able to begin serious development on the program.
I want to make it VERY CLEAR at this point that I am NOT asking anyone to do this for me. All I am looking for is a point in the right direction or something of that nature. I DO NOT WANT SOURCE FROM ANY LANGUAGE.
Thank you in advance for your time and input,
-David
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
