TranspositionKey
Rookie SRM 13 · 2022-05-16 · by erinn
Problem Statement
Some coding systems involve using a set of known text to create a transposition key that determines how a message will be scrambled. Unfortunately, humans are error prone and frequently make mistakes, so it will be your job to write a function to do it properly.
To create a transposition key from text, take the first letter in the alphabet that appears in the text. Number each occurrence of this letter in the text from left to right, starting with 1, 2, 3, etc. Ignore case. Then take the next letter in the alphabet that appears in the text and again number each occurrence of this letter from left to right, continuing the numbering from where you previously left off. Continue until done. The following example illustrates:
Quoth the raven, Nevermore.
The first letter in the alphabet which appears in this text is a. Thus:
1
Q U O T H T H E R A V E N N E V E R M O R E
The next letter that appears is e. Numbering the e's, we get:
2 1 3 4 5 6
Q U O T H T H E R A V E N N E V E R M O R E
Next comes h:
7 8 2 1 3 4 5 6
Q U O T H T H E R A V E N N E V E R M O R E
Continuing through the last letter, v, gives the finished key:
14 20 12 18 7 19 8 2 15 1 21 3 10 11 4 22 5 16 9 13 17 6
Q U O T H T H E R A V E N N E V E R M O R E
Your function should return the numbers across the top.
Constraints
- - text will have a length from 0 to 50 characters, inclusive.
- - text will contain only letters, spaces, commas, and periods.
"aaa"
Returns: {1, 2, 3 }
Note we go from left to right when seeing duplicates of the same letter.
"ywedkcjs"
Returns: {8, 7, 3, 2, 5, 1, 4, 6 }
No duplicates here.
"Quoth the raven, Nevermore."
Returns: {14, 20, 12, 18, 7, 19, 8, 2, 15, 1, 21, 3, 10, 11, 4, 22, 5, 16, 9, 13, 17, 6 }
This is the example from the problem statement.
"Fuzzy wuzzy was a bear."
Returns: {6, 9, 15, 16, 13, 11, 10, 17, 18, 14, 12, 1, 8, 2, 4, 5, 3, 7 }
"UCC Event"
Returns: {7, 1, 2, 3, 8, 4, 5, 6 }
Submissions are judged against all 44 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TranspositionKey with a public method vector<int> makeKey(string text) · 44 test cases · 2 s / 256 MB per case