EvilZone
Programming and Scripting => Java => : leewillz May 12, 2012, 09:24:54 PM
-
im looking for an expression that takes a scrambled word and finds it in a list i have currently
"^["+word+"]{"+word.length()+"}$"
but its not perfect i gets confused quite easily anyone know a better one?
-
I don't think you can do this with regex. You will have to search for words one by one, comparing char by char.
-
It is not possible with regex alone.
But you can try something like this:
private static boolean isScrambledWord(char[] word1, char[] word2) {
Arrays.sort(word1);
Arrays.sort(word2);
return Arrays.equals(word1, word2);
}
-
I just whipped a complete solution for you. It was fun remembering how to code in Java :D
I am certain it works like you described. Loops through every word in array (your list) until the match is found, or not. Just run and see! hope this helps you to understand what is going on, tried to comment the code as much as I can.
package bandymas;
public class test {
// our array of words
private final static String[] scrambledWordArray = {"apple", "carrot", "tomatoe", "cannabis", "manure", "garden", "tree"};
// scrambled "manure"
private final static String wordToMatch = "rueanm";
// method to match 2 words
private static boolean matchWord(String scrambledWord, String word) {
char[] charArray = scrambledWord.toCharArray(); // split the word into chars
boolean matches = false;
// loop through each char of the scrambled word, checking if given words contains them
for (int i = 0; i < charArray.length; i++) {
if (word.contains(charArray[i]+"")) {
matches = true;
} else {
matches = false;
break; // if single char can't be found then get out, it's not the word
}
}
return matches;
}
// method that loops through word array checking each word for a match
private static String findWord(String scrambledWord) {
int arraySize = scrambledWordArray.length;
// default string to be returned. If match is found it will be overwritten
String returnString = "No match can be done, sorry!";
boolean matchFound = false;
for (int i = 0; i < arraySize; i++) {
matchFound = matchWord(scrambledWord, scrambledWordArray[i]);
if (matchFound) {
returnString = "Found a match of word \""+scrambledWord+"\" as \""+scrambledWordArray[i]+"\"";
break; // not very good code-wise but it'll do this time
}
}
return returnString;
}
public static void main(String[] args) {
System.out.println(findWord(wordToMatch));
}
}
-
Kulver, I am sorry to disappoint you, but your code is not better than the regex of leewillz. Example: Change "manure" to "mannurre". Your program will still say that is matches "rueanm".
-
Oh darn :D well I tried... I'm sure this can be corrected with a simple hack, but I won't bother - let the OP do his homework.
-
Is this for a SO challenge? :P
-
It is not possible with regex alone.
But you can try something like this:
private static boolean isScrambledWord(char[] word1, char[] word2) {
Arrays.sort(word1);
Arrays.sort(word2);
return Arrays.equals(word1, word2);
}
This ^ .
Runs in O(k(n log n)), as far as I can tell, where k is the number of words in checking dictionary, and n is the length of the scrambled word. You only need to sort the scrambled word once.
Before sorting though you gotta check if the lengths of the two words are the same.
-
Le regex reff (http://www.regular-expressions.info/reference.html). But really regex was a problematic thing for me to get a grasp of. It will take more than one example or use of regular expressions is required.
Just remember regex is used for special occasions when regular splitting and error checking is viable. The only place in real life I've ever seen regex, except for learning, is with PBX and voice manipulations when human language is required. Linguistics is the only area I've personally seen it in. Correct me if I'm wrong, I enjoy regex.
-
This ^ .
Runs in O(k(n log n)), as far as I can tell, where k is the number of words in checking dictionary, and n is the length of the scrambled word. You only need to sort the scrambled word once.
Before sorting though you gotta check if the lengths of the two words are the same.
It's only a sketch. ;)
The code has a trap too. It changes its arguments, because the arrays are not copied before sorting. But I think the TO is responsible for taking care of the details.
Edit: If I write "something like this" it usually means you shouldn't copy&paste the code without thinking.
-
thanks guys,
glad this sparked some interest and discussion, it was just something that interested me, being able to find a jumbled word from a list of words, the solutions are very good and different being the key, sadly i still have no complete solution to this but i will update you if i find one. thanks all for the replies!
-
I coded the solution in C (if you don't mind me posting C code in Java forum ^^):
Basically it sorts the scrambled word and then loops through every word in the dictionary, and if the word's length is the same as the scrambled word it copies the scrambled word and then sorts that copy. After that it tries to match the two sorted words and if they are the same then the scrambled is found.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SIZE 7
char scrambled_word[] = "esmdcrlab"; // scrambled
char *dictionary[SIZE] = {"world", "array", "testing", "largeword", "abitlargerword", "scrambled", "download"};
int compare(const void *a, const void *b)
{
return ( *(char*)a - *(char*)b );
}
int matchWord(const char *scrambled, char *word)
{
// assuming scrambled is aready sorted
size_t wlen = strlen(word);
char test_word[wlen+1];
if (strlen(scrambled) == wlen){
strncpy(test_word, word, wlen);
qsort(test_word, wlen, sizeof(char), compare);
if (!strncmp(test_word, scrambled, wlen))
return 1;
}
return 0;
}
int main(void)
{
size_t scrlen = strlen(scrambled_word);
char orig_scrambled[scrlen+1];
strncpy(orig_scrambled, scrambled_word, scrlen);
qsort(scrambled_word, scrlen, sizeof(char), compare);
int i;
for (i = 0; i < SIZE; i++){
printf("Testing: %s\n", dictionary[i]);
if (matchWord(scrambled_word, dictionary[i])){
printf("[+] %s is %s !\n", orig_scrambled, dictionary[i]);
return 0;
}
}
printf("[-] %s is not in the dictionary\n", scrambled_word);
return 0;
}
-
excellent thanks for this, ive rewritten in java and adapted slightly this is what i have now and it works wonderfully!
-
@leewillz
public static boolean matchWord(String scrambled, String aWord)
Java has a method called equals() for every Object that is overriden by String for string comparison. Use it instead of implementing a worse O(n^2) version.
public static void toChar(int i)
{
for (int j = 0; j < dictionary[i].length(); j++)
{
array_elem = dictionary[i].toCharArray();
}
}
Why do you assign the array n times? Do you realize that you are overriding the previous assignment several times?
else
{//do nothing basically}
?
if (compare(scrambled_word.length(), dictionary[i].length()) == 0)
Writing if(scrambled_word.length() == dictionary[i].length()) is more straightforward, more concise and better understandable.
array_elem = null;//reset the array for the next word.
Useless line of code.
You didn't apply any sorting. You say it works, but if it does I don't believe it works right.
The version you gave doesn't even compile.
You adapted the C style for naming your variables. There are Java code conventions (http://www.oracle.com/technetwork/java/codeconv-138413.html). Variable names should be camel case.
________________________________________________
@s3my0n:
After your last post I thought you would create a version with a better asymptotic runtime (it seemed to be your point of argument).
-
@s3my0n:
After your last post I thought you would create a version with a better asymptotic runtime (it seemed to be your point of argument).
No, I was happy with the sorting approach to this problem, I just wanted to implement it :)
-
No, I was happy with the sorting approach to this problem, I just wanted to implement it :)
I am not a C expert, but well done.
-
the code does work fine, bearing in mind it was 2:30 on me doing it, the toChar method is pointless i see it now ive changed it, the output i get is attatched. ive not corrected everything is it works fine even if its not to "java convention"
thanks Lee
-
the code does work fine, bearing in mind it was 2:30 on me doing it, the toChar method is pointless i see it now ive changed it, the output i get is attatched. ive not corrected everything is it works fine even if its not to "java convention"
thanks Lee
Then let me tell you this again: The code you provided here does not compile. There is at least one curly bracket and a return statement missing in the end.
I didn't say that it doesn't run on your machine. Maybe something went wrong with copy&paste or whatever, but it doesn't work, no matter what you tell me.
And now to the working right part: That it works right for one input, doesn't mean it works right for every input. Testing can never tell you the absence of bugs. It only might tell you the presence.
However I can't prove anything, because your code doesn't compile.
Of course it works although you didn't care for java code conventions. You didn't even look what they are for, did you? Otherwise you would know that this has nothing to do with each other.
-
ive just downloaded the file and tried to compile, the problem is the comment in the else statement,
else
{//do nothing basically}
if u want it to run then get rid of the comment or the else in total, up to you but basically the comment is commenting out the bracket, work after that.
-
ive just downloaded the file and tried to compile, the problem is the comment in the else statement,
else
{//do nothing basically}
if u want it to run then get rid of the comment or the else in total, up to you but basically the comment is commenting out the bracket, work after that.
You are right, that was the reason it didn't work.
Now try "array" and "aaray". They will match, because your algorithm doesn't care how often the characters occur. As long as the length is the same and every distinct character is at least one time in the scrambled word, it will match.
Testing: world
Testing: araay
array is araay !
-
indeed, i have thought of a way to overcome this, i shall test this now and post the results.
-
i think this has sored it out, basically ive changed it to an array list of the characters and when if finds the element it removes it from the arraylist therefore matching the correct ammount of letters in the word. let me know if it works for you :)
import java.util.ArrayList;
import java.util.Scanner;
public class Scrambled {
public static String scrambled_word;
public static String[] dictionary = {"world", "array", "scrambled", "testing", "scrambley", "largeword", "abitlargerword", "download"};
public static ArrayList<Character> orig_word = new ArrayList<Character>();
public static ArrayList<Character> array_elem = new ArrayList<Character>();
public static char[] array_elem1 = new char[100];
public static char[] orig_word1 = new char[100];
public static boolean quit = false;
public static void main(String[] args) {
while (!quit) {
Scanner s = new Scanner(System.in);
System.out.println("Enter a string to look for:>");
scrambled_word = s.nextLine();
if (scrambled_word.equalsIgnoreCase("q")) {
quit = true;
} else {
orig_word1 = scrambled_word.toCharArray();
for (int i = 0; i < orig_word1.length; i++) {
orig_word.add(orig_word1[i]);
}
for (int i = 0; i < dictionary.length; i++) {
if (compare(scrambled_word.length(), dictionary[i].length()) == 0) {
System.out.println("Testing: " + dictionary[i]);
array_elem1 = dictionary[i].toCharArray();
swap(array_elem1);
if (matchWord()) {
System.out.println(dictionary[i] + " is the word you are loooking for");
} else {
System.out.println("this is not the scrambled word");
}
}
removeElem();
}
}
}
}
public static int compare(int a, int b) {
return a - b;
}
public static void swap(char[] words) {
for (int i = 0; i < words.length; i++) {
array_elem.add(words[i]);
}
}
public static void removeElem() {
for (int i = array_elem.size() - 1; i >= 0; i--) {
array_elem.remove(i);
}
}
public static boolean matchWord() {
// assuming scrambled is aready sorted
int m = 0;
for (int i = 0; i < orig_word.size(); i++) {
for (int j = 0; j < array_elem.size(); j++) {
if (orig_word.get(i) == array_elem.get(j)) {
m = 1;
array_elem.remove(j);
array_elem.trimToSize();
break;
} else {
}
}
if (m == 0) {
return false;
} else {
m = 0;
}
}
return true;
}
}
-
yrraa should match array, but it doesn't.
Enter a string to look for:>
yrraa
Testing: world
this is not the scrambled word
Testing: array
this is not the scrambled word
Edit: It is a good thing that you try to solve this yourself. You could have just used the sorting approach that s3myon and I suggested, but what you do is a complete different way. Go on, you will get it your way.
-
hi idont know whats going on there but ive just had a go on yrraa and it seems to pick it up :S ive done a few tweeks again ill post it now, this time ive used a text file with the words and it reads from the file to an array but main code is still the same.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class Scrambled {
public static String scrambled_word;
public static ArrayList<String> dictionary = new ArrayList<String>();
public static ArrayList<Character> orig_word = new ArrayList<Character>();
public static ArrayList<Character> array_elem = new ArrayList<Character>();
public static char[] array_elem1 = new char[100];
public static char[] orig_word1 = new char[100];
public static boolean quit = false;
public static void main(String[] args) throws FileNotFoundException, IOException {
while (!quit) {
try{
removeElem(dictionary);
BufferedReader in = new BufferedReader(new FileReader("C:\\Users\\Lee\\Documents\\NetBeansProjects\\Lab12\\src\\lab15\\read.txt"));
int add = 0;
while(in.ready()){
dictionary.add(add, in.readLine());
add++;
}
}catch(FileNotFoundException e)
{
System.out.println("File not found");
}
Scanner s = new Scanner(System.in);
System.out.println("Enter a string to look for:>");
scrambled_word = s.nextLine();
if (scrambled_word.equalsIgnoreCase("q")) {
quit = true;
} else {
orig_word1 = scrambled_word.toCharArray();
for (int i = 0; i < orig_word1.length; i++) {
orig_word.add(orig_word1[i]);
}
for (int i = 0; i < dictionary.size(); i++) {
if (compare(scrambled_word.length(), dictionary.get(i).length()) == 0) {
array_elem1 = dictionary.get(i).toCharArray();
swap(array_elem1);
if (matchWord()) {
System.out.println(dictionary.get(i) + " is the word you are loooking for");
} else {
}
}
removeElem(array_elem);
}
}
}
}
public static int compare(int a, int b) {
return a - b;
}
public static void swap(char[] words) {
for (int i = 0; i < words.length; i++) {
array_elem.add(words[i]);
}
}
public static void removeElem(ArrayList array) {
for (int i = array.size() - 1; i >= 0; i--) {
array.remove(i);
}
}
public static boolean matchWord() {
// assuming scrambled is aready sorted
int m = 0;
for (int i = 0; i < orig_word.size(); i++) {
for (int j = 0; j < array_elem.size(); j++) {
if (orig_word.get(i) == array_elem.get(j)) {
m = 1;
array_elem.remove(j);
array_elem.trimToSize();
break;
} else {
}
}
if (m == 0) {
return false;
} else {
m = 0;
}
}
return true;
}
}
-
I solved this problem with a hash table. Something like (wants to be perl syntax):
Initialization:
foreach (@word) {
$w = $_;
$table{sort_letters_alphabetically($w)} = $w;
}
Lookup:
echo $table{sort_letters_alphabetically($scrambled_word)};
Where sort_letters_alphabetically("testingword") = "deginorsttw"
Just giving another way. IDK if would work fine in every testing case.
-
Alright. I used the updated code and yrraa works, but raary doesn't.
Enter a string to look for:>
yrraa
array is the word you are loooking for
Enter a string to look for:>
raary
Enter a string to look for:>
It may help you to create a test suite, that covers a lot of cases at once while you are working on your algorithm.
-
i know why that is aswell, when it finds array once it gets deleted from the arraylist so some more tweeking i think.
-
correction, the reason was very simple i wasnt clearing the orig_word arraylist so basically when you were enterring yrraa it was looking for yrraa but then when you enter raary it was actually looking for yrraaraary because it wasnt clearing the array this should solve it.
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Scanner;
public class Scrambled {
public static String scrambled_word;
public static ArrayList<String> dictionary = new ArrayList<String>();
public static ArrayList<Character> orig_word = new ArrayList<Character>();
public static ArrayList<Character> array_elem = new ArrayList<Character>();
public static char[] array_elem1 = new char[100];
public static char[] orig_word1 = new char[100];
public static boolean quit = false;
public static void main(String[] args) throws FileNotFoundException, IOException {
try{
BufferedReader in = new BufferedReader(new FileReader("C:\\Users\\Lee\\Documents\\NetBeansProjects\\Lab12\\src\\lab15\\read.txt"));
int add = 0;
while(in.ready()){
dictionary.add(add, in.readLine());
add++;
}
in=null;
}catch(FileNotFoundException e)
{
System.out.println("File not found");
}
while (!quit) {
Scanner s = new Scanner(System.in);
removeElem(orig_word);
removeElem(array_elem);
System.out.println("Enter a string to look for:>");
scrambled_word = s.nextLine();
if (scrambled_word.equalsIgnoreCase("q")) {
quit = true;
} else {
orig_word1 = scrambled_word.toCharArray();
for (int i = 0; i < orig_word1.length; i++) {
orig_word.add(orig_word1[i]);
}
for (int i = 0; i < dictionary.size(); i++) {
if (compare(scrambled_word.length(), dictionary.get(i).length()) == 0) {
array_elem1 = dictionary.get(i).toCharArray();
swap(array_elem1);
if (matchWord()) {
System.out.println(dictionary.get(i) + " is the word you are loooking for");
} else {
}
}
removeElem(array_elem);
}
}
}
}
public static int compare(int a, int b) {
return a - b;
}
public static void swap(char[] words) {
for (int i = 0; i < words.length; i++) {
array_elem.add(words[i]);
}
}
public static void removeElem(ArrayList array) {
for (int i = array.size() - 1; i >= 0; i--) {
array.remove(i);
}
}
public static boolean matchWord() {
// assuming scrambled is aready sorted
int m = 0;
for (int i = 0; i < orig_word.size(); i++) {
for (int j = 0; j < array_elem.size(); j++) {
if (orig_word.get(i) == array_elem.get(j)) {
m = 1;
array_elem.remove(j);
array_elem.trimToSize();
break;
} else {
}
}
if (m == 0) {
return false;
} else {
m = 0;
}
}
return true;
}
}
-
Congrats, it works now.
(but the code got pretty messy)
-
haha excellent (just how i like it) ;)