Fastest algorithm

  • Sort of worked this out today, it's pretty cool but I can't think of any use for it!

    Fastest algorithm to find out if one word is a scrambled version of the other. (Same # chars).

    If u map each character in the alphabet to a unique prime number:

    a=2, b=3, c=5 etc etc

    then you get a word like:

    "Scirra"

    Multiply all the primes together that form that word.

    Doesnt matter what order they are in, you get the same result every time, no loops needed! No other word will generate that final number. (That's a cool feature of prime numbers, hence why they are used in cryptography so often).

    This is probably theoretical because length of word + alphabet size make the maximum integer size too large to handle.

  • Might be useful for some sort of captcha, or perhaps a hash check.

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • yeah, i only recently learned about Goldbach's conjecture, which states that:

    Every even integer greater than 2 can be expressed as the sum of two primes

    and

    Every integer greater than 5 can be written as the sum of three primes.

    it really doesn't seem like it should be possible.

  • Might also be used as some sort of random seed.

  • I thought that every integer (even greater than 5) can be written as the sum of two primes.

    ex:

    10 = 7 + 3 or 5 + 5

    12 = 5 + 7

    14 = 3 + 11 or 7 + 7

    52 = 5 + 47

  • What about 13?

  • Has to be an even number.

  • Just for fun here's a Javascript implementation

    a=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101];function b(c){r=1;for(i=0;i<c.length;i++)r*=a[c.charCodeAt(0)-97];return r}

    alert(b("hello") == b("hlleo"));

  • Lol some people online have managed to ridiculously shorten the code:

    a=[r=j=p=2];for(;j<28;)if(a[j]){if(p%a[j++]==0){p++;i=j=0}}else{a[j]=p;j=0}func­tion b(c){for(;i<c.length;i++)r*=a[c.charCodeAt(0)-95];return r}

  • lol someone did this which is crazy smart, 125 chars

    for(a=[j=p=2];j<123;)a[j]?p%a[++j]<1&&p++&&(j=0):(a[j]=p,j=0);function b(c,i){return c[i=i||0]?a[c.charCodeAt(i)]*b(c,++i):1}

    alert(b("toba")==b("boat"));

  • but why the horrible formatting? It just makes it look more complicated

    VERBOSITY!

  • Hey, that's what I'm looking for!

    Sorry for the delay but how would you do the javascript trick within construct2?

    capx is welcomed :)

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)