3 ms·

Not sure if you're asking about the technique, or the math, or the comparison with sorting, so here's a long answer of all of them - start like the secret codes

Not sure if you're asking about the technique, or the math, or the comparison with sorting, so here's a long answer of all of them - start like the secret codes from childhood by giving numbers to letters so A=1, B=2, C=3, D=4, etc. Then go through a word and find the values for each letter and multiply them together, e.g. "tab" is 20 x 1 x 2 = 40 and hopefully an anagram that just rearranges the letters gets the same answer because multiplication doesn't change if you shuffle the numbers around, e.g. "bat" is 2 x 1 x 20 = 40 which is the same, "bat" and "tab" are anagrams... but with the integers it doesn't always work and different words can clash e.g. "fab" 6 x 1 x 2 = 12 and "cad" 3 x 1 x 4 = 12 have the same answer but are not anagrams. Prime numbers help because the Fundamental Theorem of Arithmetic[1][2] says that there can't be any clashes when you multiply Primes, every number breaks down into a unique product of Primes (I can't prove that myself, but it is apparently true). So give the letters Prime numbers A=2, B=3, C=5, D=7, E=11, F=13, etc. and now "fab" 13 x 2 x 3 = 78 and "cad" 5 x 2 x 7 = 70 no longer clash. The only way to get the same answer is to have the same primes (in any order), so anagrams will have the same answer and non-anagrams will not. Why it drops the overhead of sorting is that the time for sorting any collection requires looking at each item and comparing at least some of them, and swapping positions of at least some of them, generally O(N items x log(N)). Lookup the letter in a Prime value array and multiplication once per letter doesn't need any comparisons or any swapping positions, so it is O(N items) time, that gives this approach less work to do for each word, so it can finish faster. It looks like (Python, assuming lowercase ASCII letters where 'a' starts at code 97): primes = [2,3,5,7,...] ascii_a = 97 product = 1 for c in word: product *= primes[ord(c) - ascii_a] Do that for the incoming word, and for every word in the wordlist, and see which have matching products, those are the anagrams. Or pre-compute for all the words in the wordlist and only do it for the incoming word and then lookup the matching ones. [1] https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme... [2] https://www.varsitytutors.com/hotmath/hotmath_help/topics/prime-factorization https://www.varsitytutors.com/hotmath/hotmath_help/topics/pr...

justinlloyd 4y ago
Prime combinatorics - I think every programmer independently discovers the technique. You can also determine if a shorter word can be made from a longer word, e.g. "cat" from "catch", by looking for modulo results. And the technique of Prime Combinatorics for an "alphabet" can be used to solve Poker hands, Blackjack hands, Match 3 puzzle games, slot machine reel positions, and a slew of other similar problems where you would ordinarily have to build a very complex logic table/switch-case/if-then-else decision tree.
kadoban 4y ago
Is it actually faster? You could just do counting sort if the big-O is important, but I'm a bit suspicious about that big-O anyway. A model where multiplying arbitrarily big numbers is constant time is a bit unrealistic, kind of feels like it's getting off the hook for a log factor for free. It's also all such small values that I'm not sure the big-O matters either, I'm not confident which would win without just trying it. I'd _guess_ that usual sort probably just wins though, or counting sort if you really went out of the way to optimize it.
- jodrellblank 4y ago
  Too late to edit my earlier reply, but I remembered what happened - for my newspaper puzzle, only 9 letter words are possible answers, and all 9 letter word products fit in an int64. Then in C# it is faster, casual runs seem to knock 20-25% off the runtime (~0.035 seconds vs ~0.045 seconds), but in PowerShell it is slower. (I'm curious,if it would be possible to shuffle the primes around to bring all words in my full wordlist down to UInt64; the highest is 2810298024552111657086849344270208275 - microspectrophotometries which is some quadrillion times too big. Rearranging the by letter frequency in the wordlist brings it down to 24474928756352445162715195352080 - electroencephalographically which is still a trillion times too big, so I doubt it).
  - kadoban 4y ago
    very interesting, both this comment and the sibling one. I didn't really consider how much could fit in an uint64. If all the words can be made to fit then that should indeed be quite fast (I was assuming bigints).
- jodrellblank 4y ago
  Huh, good call; it was 2 years ago that I did it, and I've retried to test it; the values overflow an Int64 or a Uint64 for words like "abortiveness" (== 38199980262261136506). Trying in PowerShell that overflowed to a double and then errored assigning it to an Int64. Looking what was happening, I find C# doesn't throw overflow exceptions by default and instead wraps around. That takes 0.05 seconds for all 172k words compared to 0.1 seconds for sorting all words so it ran a lot faster, yes, but it was wrong and may have clashed words. Same with Rust and overflows, it seems. Turning it to System.Numerics.BigInteger in C# makes it take about the same time 0.1s for both. In Python which handles any size integers it takes a lot more time, 0.14 seconds for sorting, 0.4 seconds for products. That means my embedded arrays of products are all overflowed as well. What a good example for arguing that programs should be correct first, and fast second. (I remember being suspicious of overflows, but I don't remember what I tried to conclude that all the word results would fit into int64, but it must have been bad).

justinlloyd 4y ago

Prime combinatorics - I think every programmer independently discovers the technique. You can also determine if a shorter word can be made from a longer word, e.g. "cat" from "catch", by looking for modulo results. And the technique of Prime Combinatorics for an "alphabet" can be used to solve Poker hands, Blackjack hands, Match 3 puzzle games, slot machine reel positions, and a slew of other similar problems where you would ordinarily have to build a very complex logic table/switch-case/if-then-else decision tree.

kadoban 4y ago

Is it actually faster? You could just do counting sort if the big-O is important, but I'm a bit suspicious about that big-O anyway. A model where multiplying arbitrarily big numbers is constant time is a bit unrealistic, kind of feels like it's getting off the hook for a log factor for free. It's also all such small values that I'm not sure the big-O matters either, I'm not confident which would win without just trying it. I'd _guess_ that usual sort probably just wins though, or counting sort if you really went out of the way to optimize it.

jodrellblank 4y ago
Too late to edit my earlier reply, but I remembered what happened - for my newspaper puzzle, only 9 letter words are possible answers, and all 9 letter word products fit in an int64. Then in C# it is faster, casual runs seem to knock 20-25% off the runtime (~0.035 seconds vs ~0.045 seconds), but in PowerShell it is slower. (I'm curious,if it would be possible to shuffle the primes around to bring all words in my full wordlist down to UInt64; the highest is 2810298024552111657086849344270208275 - microspectrophotometries which is some quadrillion times too big. Rearranging the by letter frequency in the wordlist brings it down to 24474928756352445162715195352080 - electroencephalographically which is still a trillion times too big, so I doubt it).
- kadoban 4y ago
  very interesting, both this comment and the sibling one. I didn't really consider how much could fit in an uint64. If all the words can be made to fit then that should indeed be quite fast (I was assuming bigints).
jodrellblank 4y ago
Huh, good call; it was 2 years ago that I did it, and I've retried to test it; the values overflow an Int64 or a Uint64 for words like "abortiveness" (== 38199980262261136506). Trying in PowerShell that overflowed to a double and then errored assigning it to an Int64. Looking what was happening, I find C# doesn't throw overflow exceptions by default and instead wraps around. That takes 0.05 seconds for all 172k words compared to 0.1 seconds for sorting all words so it ran a lot faster, yes, but it was wrong and may have clashed words. Same with Rust and overflows, it seems. Turning it to System.Numerics.BigInteger in C# makes it take about the same time 0.1s for both. In Python which handles any size integers it takes a lot more time, 0.14 seconds for sorting, 0.4 seconds for products. That means my embedded arrays of products are all overflowed as well. What a good example for arguing that programs should be correct first, and fast second. (I remember being suspicious of overflows, but I don't remember what I tried to conclude that all the word results would fit into int64, but it must have been bad).