Ambigram

SRM 183 · 2004-02-11 · by dgoodman

SRM 183 · 2004-02-11 · by dgoodman · Dynamic Programming

Show categories

Class Name: Ambigram

Return Type: String

Method Name: ambiword

Arg Types: (string)

Problem Statement

An ambigram is a (non-blank) symbol that looks unchanged when the paper on which it is written is rotated 180 degrees about the axis perpendicular to the surface of the paper. We are given a word and want to change it into an ambigram, by modifying or removing its letters.

We will restrict our word to uppercase letters. In the font we are using,

H I N O S X Z look unchanged after rotation
M W look like each other after rotation

Some examples of ambigrams are "MOW", "XXXXXXXXXXX", "XMIWX", "HXHXHXHXHXH".

We want to make minimal changes to the given word to produce an ambigram. We will measure the cost of changing by distance within the alphabet, so changing an 'F' to an 'H' would incur a cost of 2, and changing an 'I' to an 'F' would cost 3. If we keep changing a letter until we run off either end of the alphabet, the letter disappears. (When a letter disappears, letters around it slide together.) So we can make a C disappear at a cost of 3, and can make a 'T' disappear at a cost of 7.

Create a class Ambigram that contains a method ambiword that is given a String word and that returns the ambigram that is the cheapest to construct from word. Among equally cheap ambigrams, return the longest. If a tie still exists, return the contender that comes earliest alphabetically. A String with no characters is NOT an ambigram.

Constraints

word will contain between 1 and 50 characters inclusive.
Each character in word will be an uppercase letter 'A'-'Z'.

Examples

"BXC"
Returns: "X"

We can remove the 'B' at a cost of 2 and the 'C' at a cost of 3. Total cost = 5. Note that "BXB" is NOT an ambigram.

"XIXHZMOAOSHXIX"
Returns: "XIXHMOOWHXIX"

This can be done at a cost of 6 (make the 'A' disappear, make the 'Z' disappear, change 'S' to 'W' at a cost of 4).

"C"
Returns: "H"

We could make the 'C' disappear at a cost of 3, but the result would be the empty String, which is not an ambigram. At a cost of 5 we can change the 'C' into an 'H'.

"AMWZ"
Returns: "MW"

Note that we cannot change the 'A' to 'Z' cheaply by treating the alphabet as a circle. "ZMWZ" would be a longer ambigram than "MW" but it would cost 25.

"ABCDEFGHIJKLMNOP"
Returns: "HHHHIIIIHHHH"

Submissions are judged against all 20 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Ambigram with a public method string ambiword(string word) · 20 test cases · 2 s / 256 MB per case