GameCipher
SRM 113 · 2002-09-10 · by leelin
Problem Statement
You are part of the development team for a fantasy role-playing game with many different creatures who speak many different languages. To simplify the language mechanism, your team decides to make every language a simple cipher of the English language. That means, there is a simple mapping between letters in the fake language and letters in English. If B maps to D and E maps to A, then "BEB" in the cipher language means "DAD" in English.
The team quickly finds out that not every random set of mappings will actually work.
1) First of all, self-mappings are not preferable, so you may not have a mapping of say G to G.
2) Next, although not every letter in English needs to be used, the set of letters in the cipher language and the set of letters used in the English language must be equinumerous. That means, there is a one to one mapping from the cipher language to English as well as a one to one mapping from English to the cipher language.
3) Lastly, because the role-playing game will use actual human speech, the team wants to ensure that vowels in the cipher language map to vowels in English (otherwise it would be too hard for the voice actors to speak cipher). Non-vowels must also map to non-vowels.
Write a method violation that takes as input a
Notes
- Vowels are always A,E,I,O,U,Y. Note that Y is always a vowel for this problem.
- If there are multiple violations, return the index of the first one that causes a mapping violation.
- Indices are zero-based. The first element has index 0.
- If mappings contains a repeat mapping, then that is a violation, e.g. { "L-P", "A-E", "L-P" }.
Constraints
- Each element of mappings will be formatted exactly as an uppercase letter ('A'-'Z'), a '-', and another uppercase letter.
- There will be between 0 and 26 elements in mappings, inclusive.
{"A-E", "B-C", "C-D", "D-B"}
Returns: -1
Nothing is wrong with this cipher.
{"C-D", "Z-Z", "Y-Y"}
Returns: 1
There are two violations because of self-mappings. Return the earliest one.
{"B-D", "C-F", "L-M", "P-Y", "I-O", "A-Q"}
Returns: 3
There are again two violations because of a vowel mismatch. Return the earlier one (P-Y).
{"B-C", "X-Z", "B-D"}
Returns: 2
The violation is from the mapping of B-D, since an earlier mapping maps B-C. Return the mapping that actually causes the violation, which is B-D.
{"B-C", "D-C"}
Returns: 1
Again, the violation is that C is already used, so return the mapping that causes the violation.
{"A-E", "E-A"}
Returns: -1
This is perfectly ok, even though the cipher is a reverse of itself.
{"A-E","B-D","A-E"}
Returns: 2
You may not have the same mapping twice.
Submissions are judged against all 68 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class GameCipher with a public method int violation(vector<string> mappings) · 68 test cases · 2 s / 256 MB per case