javascript to brute combinations of a string
New here? Learn about Bountify and follow @bountify to get notified of new bounties! x

We need to brute check a string with common user typed errors. We have an app similar to authy in that it generates 10 digit codes but they are often written down and faxed (yes faxed) and we end up with some transcribing issues. To overcome some of this in a crude way we have decided to brute force it and then suggest to the user if one of our matches is the actual written value

Suppose we have the following code

q160sDszkU

We would like some javascript that will lookup the letters against a definition table and output all of the iterations of the code. (we will use this output to brute what we think the user meant) for example

0 is commonly mistyped and miswritten as o or O so in the js we would define 0,o,O as aliases for each other and need to output all of the variants with those changes. we would define multiple of these sort of letters (i,I,L,1) for example is another

Next we need to iterate through all of the upper and lower case variants of the codes

q160sDszkU
would output
Q160sDszkU

q160SDszkU

q160sDszkU

Q160SDszkU

etc..

a couple of assumptions can be made here,

our codes are always 10 characters
are a mix of numbers and letters

this code will be run server side so ideally no big heavy js libs are needed here. ideally output is a .json file or .txt file

So the concept is this: the users input the code they had written down in some kind of form (probably with some typos) and then you want to check their input against a list of correct codes (server-side)?
kostasx 1 month ago
you got it. technically we have some aws lambdas that will spawn to check each of the codes against a decryption method if the initial typed version doesnt work. our thought is we can try a few hundred versions of the code as a fallback and then have something more informative for the user other than "notta"
Qdev 1 month ago
OK. It would be really helpful, if you can provide some samples, e.g. 4~5 correct codes and a list of their respective mistyped codes.
kostasx 1 month ago
yep so i started down this route https://codepen.io/social_quotient/pen/XWJJmZM from a SO article and it seems to work but it doesnt handle my weird aliases need. so basically would be something like this codepen but would need to also handle replacing some of the characters with their alias and then dedupping. There could be better js code than this as well, i literally grabbed it to start messing with. from the looks of it I dont think it works well with numbers either.
Qdev 1 month ago
awarded to Vlad
Tags
javascript

Crowdsource coding tasks.

4 Solutions


Here's a take using Fuse.js and Levenshtein distance: https://codepen.io/kostasx/pen/WNbbQxq?editors=0012

hey Kostasx we are looking to just generate all of the permutations. we will handle the checking on our side. I need a method for creating and generating all of the combinations of outcomes for the upper / lower/ and alias items
Qdev 1 month ago
Yes, I know. I am just suggesting a solution where there's no need to create the permutations, just check the input code against a list of correct code values and find the closest matches.
kostasx 1 month ago
ah got it, in our case we have to decrypt this 10 digit code, we dont have a corpus to compare as a lookup. if we did this would be awesome way of handling it. the issue with our decryption is that 1 character off and we are dead decrypting with the public keys. so our idea is to generate all outcomes if we fail and then attempt to decrypt all with the public keys we have. its weird i know, but could you expect anything different from us :)
Qdev 1 month ago
OK. Got it. It wasn't quite clear in the description that there's some sort of hashing algorithm in the middle, that's why I asked. No worries then.
kostasx 1 month ago

Define a function to calculate permutations

const getPermutationsOfCode = (input, combinations) => {

  const find = char => {
    let found = [char];

    combinations.forEach(arr => {
      if (arr.indexOf(char) !== -1) {
        found = arr;
      }
    });

    return found;
  };

  const permute = (array, prefix = "") => {
    if (!array.length) {
      return prefix;
    }

    const recurse = (result, value) =>
      result.concat(permute(array.slice(1), prefix + value));

    return array[0].reduce(recurse, []);
  };

  const found = input.split("").map(find);

  return permute(found);
}

Define combinations array and get permutations of code

const combinations = [["q", "Q", "9"], ["s", "S"]];
getPermutationsOfCode('q160sDszkU', combinations) //?

Result should look like this

[
  "q160sDszkU",
  "q160sDSzkU",
  "q160SDszkU",
  "q160SDSzkU",
  "Q160sDszkU",
  "Q160sDSzkU",
  "Q160SDszkU",
  "Q160SDSzkU",
  "9160sDszkU",
  "9160sDSzkU",
  "9160SDszkU",
  "9160SDSzkU"
]
for uppercase/lowercase variants, you can just add them to the combinations arrays [['a', 'A'], ['b', 'B'], /*...etc */]
billymoon 1 month ago
hey thats a neat way to handle the upper lower and alias - can you put together a codepen or jsfiddle to run it?
Qdev 1 month ago
Winning solution
hey this is cool. i notice that its replacing q with the alias list. I think it should just replace alias character with the permutations of that alias?
Qdev 1 month ago
Hi Qdev, sorry about that, can you check again ? Is this the desired output ?
Vlad 1 month ago
I've also added a flatDeep function to return only a single list if that's what you need.
Vlad 1 month ago
Nice solution, but there is an issue with concatenating capitals, it causes duplication when you already have capital and non capital in other variations. Type input string 'hi' and you will get twice as many outputs as you need, because it's replacing i first for variations of ['1', 'l', 'L', 'I', 'i'] and then for ['I', 'i'] and of course, they compound. My solution sidesteps this issue by defining capitals as just another combination. Perhaps you could use some kind of filter to check if capitals are already defined in combinations before adding to array. https://repl.it/repls/IdealJumpyDatum
billymoon 1 month ago

Hey Qdev, here's my go at the solution: https://jsfiddle.net/Wuddrum/ypjhcm3e/7/

You only need to specify aliases, the upper and lower case variants are added automatically. The output is a an array of objects that contain permutation field for the resulting permutation and distance field for the letter difference count of the permutation vs input string. The result is sorted by the distance field, so that the top results are more likely to yield the correct code for the typo.

the getPermutations function also accepts maxDistance and limit parameters, which are self explanatory.

View Timeline