anyone done regex before?

[leewillz]

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?

[Kulverstukas]

I don't think you can do this with regex. You will have to search for words one by one, comparing char by char.

[Deque]

It is not possible with regex alone.
But you can try something like this:

Code: [Select]

private static boolean isScrambledWord(char[] word1, char[] word2) {
        Arrays.sort(word1);
        Arrays.sort(word2);
        return Arrays.equals(word1, word2);
}

[Kulverstukas]

I just whipped a complete solution for you. It was fun remembering how to code in Java
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.

Code: [Select]

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));
    }

}


[Deque]

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".

[Kulverstukas]

Oh darn 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.

[ca0s]

Is this for a SO challenge?

[s3my0n]

It is not possible with regex alone.
But you can try something like this:

Code: [Select]

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.

[techb]

Le regex reff. 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.

[Deque]

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.

[leewillz]

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!

[s3my0n]

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.

Code: [Select]

#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;                                         
}


[leewillz]

excellent thanks for this, ive rewritten in java and adapted slightly this is what i have now and it works wonderfully!

[Deque]

@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.

Code: [Select]

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?

Code: [Select]

else
                {//do nothing basically}
?

Code: [Select]

if (compare(scrambled_word.length(), dictionary[i].length()) == 0)
Writing

Code: [Select]

if(scrambled_word.length() == dictionary[i].length()) is more straightforward, more concise and better understandable.

Code: [Select]

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. 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]

@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