algorithmlistcpu-word

Alphabet mapped to values: How to find actual words that add up to given value?


I came across a G+ post where someone shared:

If
  A B C D E F G H I J  K  L  M  N  O  P  Q  R  S  T  U  V  W  X  Y  Z

Equals
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

Then
  K + N + O + W + L + E + D + G + E = 96% 
  H + A + R + D + W + O + R + K     = 98%

But
  A + T + T + I + T + U + D + E     = 100%

So much for that and for the fun of it, ignoring the percent trick and leaving the rest of the talk to the G+ comments.

But I ask myself: What would be the best approach (algorithm) to find all the words out of a given word list (a fixed set of n words) that add up to 100?


Solution

  • A similar problem is discussed here. Your specific problem, however, suggests an easier approach. Since the number of words in a wordlist is limited and always smaller than the number of character permutation up to the length of the longest word, you are best off by proceeding like this:

    Let's assume we have a charToNum function, which maps a character to the corresponding number:

    for each word in wordlist
      sum := 0
      for each character in word
        sum := sum + charToNum(character)
        if (sum > 100)
          break // Correct result no longer possible
      if (sum == 100)
        Add the word to the result set