Skip to content

Instantly share code, notes, and snippets.

@jrjhealey
Last active February 1, 2018 10:54
Show Gist options
  • Save jrjhealey/b783cfba2a72dd5fd3bc41f7b794c8b8 to your computer and use it in GitHub Desktop.
Save jrjhealey/b783cfba2a72dd5fd3bc41f7b794c8b8 to your computer and use it in GitHub Desktop.
Work out if 2 words are anagrams based on their unique prime products.
#!/usr/bin/env python
"""
Using products of primes to work out whether 2 strings are anagrams of one another.
Inspired by: https://twitter.com/fermatslibrary/status/958700402647674880
Map each of the 26 english characters (A, B, C, ...) to a (unique) prime number.
Multiply the values mapped to each character together (A x B x C x ...).
Since every integer is a prime, or a unique product of primes, according to the
fundamental theorem of arithmetic), two words are anagrams of one another if their
products are the same!
E.g.: f(A) = 2, f(E) = 11, f(R) = 61
F(ARE) = 2 x 61 x 11 = 1342
F(EAR) = 11 x 2 x 61 = 1342
ARE = EAR
"""
import sys
def get_args():
import argparse
try:
parser = argparse.ArgumentParser(description="Detecting anagrams with prime number products!")
parser.add_argument('word1', action='store', metavar='abc', help='First word to compare.')
parser.add_argument('word2', action='store', metavar='cab', help='Second word to compare.')
except:
print('An exception occurred with argument parsing. Check the options used.')
sys.exit(1)
return parser.parse_args()
def map_strings(word):
prime_mapping = {'A': 2, 'B': 3, 'C': 5, 'D': 7, 'E': 11, 'F': 13,
'G': 17, 'H': 19, 'I': 23, 'J': 29, 'K': 31, 'L': 37,
'M': 41, 'N': 43, 'O': 47, 'P': 53, 'Q': 59, 'R': 61,
'S': 67, 'T': 71, 'U': 73, 'V': 79, 'W': 83, 'X': 89,
'Y': 97, 'Z': 101}
return [prime_mapping.get(char) for char in word.upper()]
def product(mapped_vals):
from functools import reduce
return reduce( (lambda x, y: x * y), mapped_vals)
def main():
args = get_args()
w1_vals = map_strings(args.word1)
w2_vals = map_strings(args.word2)
w1_prod = product(w1_vals)
w2_prod = product(w2_vals)
if w1_prod == w2_prod:
anagram = "Anagrams"
else:
anagram = "Not Anagrams"
print("Result: " + anagram)
print("Word:" + '\t' + "Word Map" + '\t' + "Product")
print(str(args.word1) + '\t' + str(w1_vals) + '\t' + str(w1_prod))
print(str(args.word2) + '\t' + str(w2_vals) + '\t' + str(w2_prod))
if __name__ == "__main__":
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment