Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
?
Solved

algorithm to unlock this problem...

Posted on 2003-11-16
9
Medium Priority
?
306 Views
Last Modified: 2012-05-04
imagine a 4x4 matrix filled with letters, how can i make an algorithm that will give me every possible word ,with four letters, made with the letters of the matrix, knowing that each letter may only associate with ones next to it (imagine mine sweeper) the return values should be in the form of a string per word... preferably a linked list of objects with a string inside or a string array...
if someone could make me the class that would do the job i would be very grateful
(ps: i think its with a Heap, but i cant imagine how)
0
Comment
Question by:omega-t-k
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 6
  • 3
9 Comments
 
LVL 15

Expert Comment

by:JakobA
ID: 9759823
not a class or algorithm, but a bit of logic:

with a 4*4 matrix you ghave 4*4 = 16 letters that may be the first letter
for each of those you can then make 'all possible 4-step paths from there'. there is a limited number of those (permute multiple nsew), though some need to be pruned depending of which of the 16 starting location you begin at (and wheater you permit the path to double back ('ewew').

regards JakobA
0
 

Author Comment

by:omega-t-k
ID: 9759954
i know that in teory its quite simple... im not that dum :P the problem is the implementation of the teory... i need an algorithm that does the permutations and belive me it isnt that obvious.. :) imagine trail starting at one of those letters, and each of the letters next to it are possible paths. and for each steap you give you have another number of possible paths... now what i need is an algorithm that wil give me all the 4 letter words that you ca make starting at one letter. i give a starting letter to the imput and the algorithm gives me all the possibilities! in the form of four letter strings... get it? ;)
0
 
LVL 15

Expert Comment

by:JakobA
ID: 9760007
I think we can agree that the basis is a recursive function going 4 steps (levels)

a useful support-method would be a  canIGoInThatDirection metod to be called before taking each step. in that method you would collect all the rules (not outside board, not same letter revisited, and maybe more). Dont find same path twice are implicit in the recursion:

take step;
for i = north, south, east, west
     if ( iCanGoInThatDirection ) {
         recurseInThatDirection;
    }
0
Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

 
LVL 15

Expert Comment

by:JakobA
ID: 9760016
PS:  the reason I am not more specific is that this is a typical homework problem, intended to teach you logical thinking.
0
 

Author Comment

by:omega-t-k
ID: 9760212
lol you´re quite right... but belive me... i´ve studied! and the reason i´ve asked for help is because i cant do the complete work because im missing that part,that algorithm... the rest of problem is done... well thnks anyway :) ill leave this open for now and if im not given a better answer, i will accept that one :) it as been some help, althought the coding is strange... im using low-level java and i dont understand the
"for" implementation :/ we use java as if using C "for(bla;bla;bla)"
if you could explain that, i would be gratfull. thanks for the help!
0
 
LVL 15

Expert Comment

by:JakobA
ID: 9760410
It is called 'pseudo code', meaning that it is not really code, just thinking that look a bit like code.
an alternative for
  for i = north, south, east, west
would be
  for ( each possible direction )

later it can then be turned into a syntactically correct for statement
0
 
LVL 15

Accepted Solution

by:
JakobA earned 500 total points
ID: 9760420
If you make a start and show the code (even if it di not work) we can point out errors and maybe even suggest improvements as long as it is not "handing you the algorithm on a silver platter".

regards JakobA
0
 

Author Comment

by:omega-t-k
ID: 9765631
im already on the tracks! and first in the class to do it ;) ive already made the algorithm the rest is simple tnks for the help
0
 
LVL 15

Expert Comment

by:JakobA
ID: 9765656
sounds good :)
thanks
0

Featured Post

Free Tool: Port Scanner

Check which ports are open to the outside world. Helps make sure that your firewall rules are working as intended.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
Introduction This article is the second of three articles that explain why and how the Experts Exchange QA Team does test automation for our web site. This article covers the basic installation and configuration of the test automation tools used by…
Viewers will learn about basic arrays, how to declare them, and how to use them. Introduction and definition: Declare an array and cover the syntax of declaring them: Initialize every index in the created array: Example/Features of a basic arr…
This tutorial will introduce the viewer to VisualVM for the Java platform application. This video explains an example program and covers the Overview, Monitor, and Heap Dump tabs.
Suggested Courses

636 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question