Experiments with Knuth's 5,757 five letter words. https://charlesreid1.com/wiki/Five_Letter_Words
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

85 lines
2.3 KiB

  1. """
  2. diff_by_one.py
  3. Donald Knuth, Art of Computer Programming, Volume 4 Facsimile 0
  4. Exercise #28
  5. Find pairs of SGB word vectors that differ by +/-1 in each component.
  6. """
  7. from get_words import get_words
  8. def gen_variations(word,fragment,depth,variations):
  9. """
  10. Recursive backtracking method to assemble strings
  11. differing by +/-1 at each position
  12. """
  13. if depth==5:
  14. variations.add(fragment)
  15. else:
  16. # make a choice
  17. fragment_p1 = fragment + chr(ord(word[depth])+1)
  18. fragment_m1 = fragment + chr(ord(word[depth])-1)
  19. for new_fragment in [fragment_p1,fragment_m1]:
  20. gen_variations(word,new_fragment,depth+1,variations)
  21. def get_all_variations(word):
  22. """
  23. Return all possible words that differ
  24. from `word` by +/-1 in each index.
  25. This does not include `word` in the
  26. variations.
  27. """
  28. word_variations = set()
  29. gen_variations(word,'',0,word_variations)
  30. word_variations = list(word_variations)
  31. return word_variations
  32. def main():
  33. """
  34. Find pairs of SGB word vectors that differ by +/-1 in each component.
  35. To do this, iterate through each word,
  36. generate the 32 possible candidate matchings,
  37. and if they exist, add the pair to a set.
  38. """
  39. # words is a hash table (unsorted)
  40. words = get_words()
  41. #words = words[:1000]
  42. words = set(get_words())
  43. # List of string tuples
  44. off_by_one = set()
  45. # Iterate over every word
  46. for iw,word in enumerate(words):
  47. # Generate all 2^5 = 32 possible candidate
  48. # matches for this word (total 185k strings)
  49. all_vars = get_all_variations(word)
  50. for word_var in all_vars:
  51. # O(1) check if this variation exists
  52. # in the five letter words set
  53. if word_var in words:
  54. # Found a new (unordered) pair
  55. if word<word_var:
  56. left=word
  57. right=word_var
  58. else:
  59. left=word_var
  60. right=word
  61. off_by_one.add((left,right))
  62. off_by_one = list(off_by_one)
  63. off_by_one.sort()
  64. for o in off_by_one:
  65. print("{:s} {:s}".format(o[0],o[1]))
  66. print("Found {0:d} pairs of words that differ by +/-1 in each component.".format(len(off_by_one)))
  67. if __name__=="__main__":
  68. main()