We disguised the two partners of some famous duos by subtracting their names. If the difference of David and Goliath is -C -N J * C -T -H, then who are these duos?

1. A -T I B F

2. -P -N R D -M N

3. D * C N -T L

4. -J Q -O G E -C -H -Y

5. -A C -K J D E

Assignment

We assign each letter (str; uppercase and lowercase) a value (int) that corresponds to its position in the alphabet (A=1, B=2, C=3, …, Z=26). We consider the asterisk (*) as an extra letter with a value of zero (0).

The difference of two letters is a string (str) determined by first subtracting the values of those two letters. This yields a value between -26 and 26, which we represent as:

• positive values (1…26): the letter at the corresponding position in the alphabet (1=A, 2=B, 3=C, ... 26=Z)

• value zero (0): an asterisk (*)

• negative values (-26…-1): a dash (-) followed by the letter representing to the absolute value

A word is a string (str) consisting of one or more letters (uppercase or lowercase; no asterisks). To determine the difference of two words, we first append asterisks (*) to the end of the shortest word until both words have equal length. The difference is then a tuple (tuple) containing the differences of the two letters at corresponding positions in the two words. The length of this tuple is therefore equal to the length of the longest word.

Your task:

• Write a function diff2value that takes the difference of two letters (str; an asterisk or a letter possibly preceded by a dash). The function must return the corresponding value (int). The function should make no distinction between uppercase and uppercase letters.

• Write a function value2diff that takes a value (int) between -26 and 26. The function must return the representation of that value as the difference of two letters (str; in uppercase).

• Write a function disguise that takes two words $$w_1$$ and $$w_2$$ (str). The function must return the difference of $$w_1$$ and $$w_2$$ (in uppercase).

• Write a function partner that takes two arguments: i) a word $$w_1$$ (str) and ii) the difference $$v$$ of two words. The function must return the word $$w_2$$ (str; in uppercase) for which $$v$$ is the difference of $$w_1$$ and $$w_2$$ (see function disguise). If such a word does not exist, the value None must be returned. Keep the following things in mind:

  • in determining the difference of two words, one of the words might need to be extended with asterisks at the end; those asterisks are not part of that word

  • words only consist of uppercase and lowercase letters; strings containing characters that are no letters (also asterisks are not allowed) are not valid words

  • at least one of the words $$w_1$$ and $$w_2$$ must be as long as the difference; the other word may be shorter

• Write a function trace that takes two arguments: i) the difference of two words and ii) the location (str) of a text file containing a collection of words (one word per line; in uppercase). The function must return a set (set) containing all pairs of words from the given collection whose difference equals the given difference, with a pair of words represented as a tuple (tuple) containing the two words.

  Tip

  It will take too long if you determine the difference of each pair of words from the given collection to see if that difference equals the given difference. You get a faster algorithm if you determine the partner that corresponds to the given difference for each word from the given collection, and then check whether that partner also appears in the collection (use a set (set) for the collection to enable fast lookups). You can also use the fact that the length of the difference is equal to the length of the longer of the two words being subtracted.

Example

In the following interactive session we assume the text file words.txt¹ to be located in the current directory.

>>> diff2value('*')
0
>>> diff2value('A')
1
>>> diff2value('-t')
-20

>>> value2diff(0)
'*'
>>> value2diff(1)
'A'
>>> value2diff(-20)
'-T'

>>> disguise('Mario', 'Luigi')
('A', '-T', 'I', 'B', 'F')
>>> disguise('Batman', 'Robin')
('-P', '-N', 'R', 'D', '-M', 'N')
>>> disguise('David', 'Goliath')
('-C', '-N', 'J', '*', 'C', '-T', '-H')

>>> partner('Mario', ('A', '-T', 'I', 'B', 'F'))
'LUIGI'
>>> partner('Batman', ('-P', '-N', 'R', 'D', '-M', 'N'))
'ROBIN'
>>> partner('David', ('-C', '-N', 'J', '*', 'C', '-T', '-H'))
'GOLIATH'

>>> trace(('A', '-T', 'I', 'B', 'F'), 'words.txt2')
{('MARIO', 'LUIGI')}
>>> trace(('-P', '-N', 'R', 'D', '-M', 'N'), 'words.txt3')
{('BATMAN', 'ROBIN')}
>>> trace(('-C', '-N', 'J', '*', 'C', '-T', '-H'), 'words.txt4')
{('DAVID', 'GOLIATH')}
>>> trace(('A', '-Q', 'I', '-A', '*', '*'), 'words.txt5')
{('BARREN', 'ARISEN'), ('CARSON', 'BRITON'), ('HANSEL', 'GRETEL')}

Epilogue

The title of this assignment refers to the movie Hidden Figures⁶ (2016), telling the true story of scientists Katherine Johnson⁷ and her two colleagues Dorothy Vaughan⁸ and Mary Jackson⁹. Three women who worked in the West Area Computing unit at NASA Langley Research Center¹⁰ — an all-female African-American team that played an important role in the space race. Thanks to their calculations, American spaceman John Glenn succeeded to orbit Earth in 1962 as the first American.