Fastest algorithm

Chat about anything not covered in these forums, but keep it civil!

Post » Thu Mar 03, 2011 6:59 pm

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.
Image Image
Scirra Founder
B
124
S
37
G
25
Posts: 3,945
Reputation: 44,897

Post » Thu Mar 03, 2011 7:17 pm

Might be useful for some sort of captcha, or perhaps a hash check.
Image Image
B
161
S
48
G
90
Posts: 7,347
Reputation: 66,749

Post » Thu Mar 03, 2011 7:32 pm

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.
Spriter Dev
B
87
S
21
G
12
Posts: 3,240
Reputation: 16,461

Post » Thu Mar 03, 2011 11:50 pm

Might also be used as some sort of random seed.
Image Image
B
161
S
48
G
90
Posts: 7,347
Reputation: 66,749

Post » Sat Mar 05, 2011 2:37 pm

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
B
28
S
8
G
8
Posts: 530
Reputation: 7,154

Post » Sat Mar 05, 2011 6:07 pm

What about 13?
Spriter Dev
B
87
S
21
G
12
Posts: 3,240
Reputation: 16,461

Post » Sat Mar 05, 2011 7:32 pm

Has to be an even number.
Image Image
Scirra Founder
B
124
S
37
G
25
Posts: 3,945
Reputation: 44,897

Post » Tue Mar 08, 2011 5:04 pm

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[i].charCodeAt(0)-97];return r}

alert(b("hello") == b("hlleo"));
Image Image
Scirra Founder
B
124
S
37
G
25
Posts: 3,945
Reputation: 44,897

Post » Wed Mar 09, 2011 12:47 pm

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}function b(c){for(;i<c.length;i++)r*=a[c[i].charCodeAt(0)-95];return r}
Image Image
Scirra Founder
B
124
S
37
G
25
Posts: 3,945
Reputation: 44,897

Post » Wed Mar 09, 2011 2:17 pm

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"));
Image Image
Scirra Founder
B
124
S
37
G
25
Posts: 3,945
Reputation: 44,897

Next

Return to Open Topic

Who is online

Users browsing this forum: No registered users and 2 guests