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
142
S
38
G
26
Posts: 4,080
Reputation: 47,235

Post » Thu Mar 03, 2011 7:17 pm

Might be useful for some sort of captcha, or perhaps a hash check.
Image Image
B
164
S
49
G
113
Posts: 7,650
Reputation: 78,999

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
94
S
21
G
12
Posts: 3,250
Reputation: 16,710

Post » Thu Mar 03, 2011 11:50 pm

Might also be used as some sort of random seed.
Image Image
B
164
S
49
G
113
Posts: 7,650
Reputation: 78,999

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
29
S
8
G
8
Posts: 531
Reputation: 7,181

Post » Sat Mar 05, 2011 6:07 pm

What about 13?
Spriter Dev
B
94
S
21
G
12
Posts: 3,250
Reputation: 16,710

Post » Sat Mar 05, 2011 7:32 pm

Has to be an even number.
Image Image
Scirra Founder
B
142
S
38
G
26
Posts: 4,080
Reputation: 47,235

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
142
S
38
G
26
Posts: 4,080
Reputation: 47,235

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
142
S
38
G
26
Posts: 4,080
Reputation: 47,235

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
142
S
38
G
26
Posts: 4,080
Reputation: 47,235

Next

Return to Open Topic

Who is online

Users browsing this forum: No registered users and 0 guests