1

My question is similar to THIS question that hasn't been answered yet.

How can I make my code (or any javascript code that might be suggested?) find all possible solutions of a known string length with multiple missing characters in variation with repetition?

I'm trying to take a string of known character lengths and find missing characters from that string. For example:

var missing_string = "ov!rf!ow"; //where "!" are the missing characters

I'm hoping to run a script with a specific array such as:

var r = new Array("A","B","C","D","E","F","G","H","I","J","K",
                  "L","M","N","O","P","Q","R","S","T","U","V",
                  "W","X","Y","Z",0,1,2,3,4,5,6,7,8,9);

To find all the possible variations with repetition of those missing characters to get a result of:

ovArfAow
ovBrfAow
ovCrfAow
...
ovBrfBow
ovBrfCow
...
etc //ignore the case insensitive, just to emphasize the example

and of course, eventually find ovErfLow within all the variations with repetition.

I've been able to make it work with 1 (single) missing character. However, when I put 2 missing characters with my code it obviously repeats the same array character for both missing characters which is GREAT for repition but I also need to find without repetition as well and might need to have 3-4 missing characters as well which may or may not be repeated. Here's what I have so far:

var r = new Array("A","B","C","D","E","F","G","H","I","J","K",
                  "L","M","N","O","P","Q","R","S","T","U","V",
                  "W","X","Y","Z",0,1,2,3,4,5,6,7,8,9);
var missing_string = "he!!ow!r!d";
var bt_lng = missing_string.length;
var bruted="";

for (z=0; z<r.length; z++) {
for(var x=0;x<bt_lng;x++){
    for(var y=0;y<r.length;y++){
        if(missing_string.charAt(x) == "!"){
            bruted += r[z];
            break;
        }
        else if(missing_string.charAt(x) == r[y]){
            bruted += r[y];
        }
    }
}
console.log("br: " + bruted);
bruted="";
}

This works GREAT with just ONE "!":

helloworAd
helloworBd
helloworCd
...
helloworLd

However with 2 or more "!", I get:

heAAowArAd
heBBowBrBd
heCCowCrCd
...
heLLowLrLd

which is good for the repetition part but I also need to test all possible array M characters in each missing character spot.

Community
  • 1
  • 1
Jon Cole
  • 15
  • 8
  • You seem to have forgotten to ask a question. What **specific** part of this are you having problems with? ("All of it" or "Getting it to work" are not suitable answers to my question. ) A suggestion: Ask yourself how you would do this with a pencil and paper manually. Start with two missing letters. – Ken White Mar 23 '13 at 03:13
  • My question is how can I make my code (or similar code that might be suggested?) work with multiple missing characters in variation with repetition. – Jon Cole Mar 23 '13 at 03:17
  • You **still** have not asked a question. Please [edit] your question and ask one. Start with the thought that questions end with *question marks* in mind. (I shouldn't have to work so hard to get you to tell us what you want us to help you with, since you're the one asking for our help.) :-) I'm having problems getting the whole thing to work is not specific at all. – Ken White Mar 23 '13 at 03:19
  • You might also want to look into already written functions for combinatorics: http://www.mennovanslooten.nl/blog/post/70 then add this piece http://stackoverflow.com/questions/881085/count-the-number-of-occurences-of-a-character-in-a-string-in-javascript after that you would have to iterate over the string and the array of combinations and it's sub array to get your solutions – scones Mar 23 '13 at 03:21
  • Thanks for the link, however I've done a lot of research on a LOT of different functions for combinatorics, however I need it in javascript (no php, ruby, etc) and without extensions such as prototype. – Jon Cole Mar 23 '13 at 03:26
  • what do you compare the words too - I mean after you put your chars in the placeholder ! in the loop - against what are you checking that the word is correct ? – Adidi Mar 23 '13 at 03:28
  • @Adidi That part I already have figured out. Basically I have an ajax post that submits each possible solution checking for a response. And before anything thinks this is some form of a password brute force or something...it's not. It's part of an ARG / experiment. – Jon Cole Mar 23 '13 at 04:15

1 Answers1

1

Maybe the following function in pure javascript is a possible solution for you. It uses Array.prototype.reduce to create the cartesian product c of the given alphabet x, whereby its power n depends on the count of the exclamation marks in your word w.

function combinations(w) {
    var x = new Array(
            "A","B","C","D","E","F","G","H","I","J","K",
            "L","M","N","O","P","Q","R","S","T","U","V",
            "W","X","Y","Z",0,1,2,3,4,5,6,7,8,9
        ),
        n = w.match(/\!/g).length,
        x_n = new Array(),
        r = new Array(),
        c = null;

    for (var i = n; i > 0; i--) {
        x_n.push(x);
    }

    c = x_n.reduce(function(a, b) {
        var c = [];
        a.forEach(function(a) {
            b.forEach(function(b) {
                c.push(a.concat([b]));
            });
        });
        return c;
    }, [[]]);

    for (var i = 0, j = 0; i < c.length; i++, j = 0) {
        r.push(w.replace(/\!/g, function(s, k) {
            return c[i][j++];
        }));
    }

    return r;
}

Call it like this console.log(combinations("ov!rf!ow")) in your browser console.

witrin
  • 3,701
  • 1
  • 24
  • 49
  • I appreciate the effort and idea! Unfortunately, I don't think this will work since I need it in pure JS as mentioned before in my comments without extensions such as prototype (it's just not possible to use this extension in the current setup). – Jon Cole Mar 23 '13 at 04:40
  • This is pure javascript, just put the stuff in your console and it will work! – witrin Mar 23 '13 at 04:43
  • I wasn't saying it wasn't pure JS, I was just re-iterating what I said in my prior comment. I don't think I'll have access to the prototype extension in our implementation, but I will try this tomorrow in our setup and see if it I can make it work and let you know for sure. – Jon Cole Mar 23 '13 at 04:49
  • I don't get your point here, there is no need for an extension like Prototype. What makes you think about that? You know that `Array.protoype.reduce` is part of [ECMA-262](http://www.ecma-international.org/publications/files/ECMA-ST/Ecma-262.pdf) (15.4.4.21)? – witrin Mar 23 '13 at 05:03
  • I also change the code, thus there is no word like `prototype` in it, even if it would make no difference. – witrin Mar 23 '13 at 05:05
  • Sorry about the confusion, I had tested it in my console and it worked but I wasn't sure if it would work in our implementation. I've seen suggestions before using the Jquery library or Prototype framework. While we have access to Jquery we don't have access to Prototype. I didn't realize this was completely different. I tested it today and seems to work flawlessly. THANKS! :accepted answer: – Jon Cole Mar 23 '13 at 14:49