Statistics

Problem Statement for "Ambigram"

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,

  1. H I N O S X Z look unchanged after rotation
  2. 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.

Definition

Class:
Ambigram
Method:
ambiword
Parameters:
String
Returns:
String
Method signature:
String ambiword(String word)
(be sure your method is public)

Constraints

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

Examples

  1. "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.

  2. "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).

  3. "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'.

  4. "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.

  5. "ABCDEFGHIJKLMNOP"

    Returns: "HHHHIIIIHHHH"

  6. "MIW"

    Returns: "MIW"

  7. "MWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMW"

    Returns: "MWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMW"

  8. "MWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWM"

    Returns: "NMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWMWN"

  9. "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA"

    Returns: "H"

  10. "DDDDDDDDDD"

    Returns: "HHHHHHHHHH"

  11. "FDKLKJSDKJSAKJDASDLKDLKHALKASKL"

    Returns: "HHINHIWHIISIISIIHMIHNIHH"

  12. "GLSMSMWMSIDHSFLLSMDMMWMWLSFKDFH"

    Returns: "HISNWNWNSIHHSHHISNMNMNSIH"

  13. "HEREISASTRINGOFMODESTLENGTH"

    Returns: "HHNHISSONHNHNHNOSSIHNHH"

  14. "WHOKNOWSWHATTHISMIGHTBE"

    Returns: "HMHHIWSWHSSHMSMIHHWH"

  15. "LLLLLSTUVW"

    Returns: "MMMMMWWWWW"

  16. "ZZZZZZZZZZZZ"

    Returns: "ZZZZZZZZZZZZ"

  17. "ZZYZZZZZZZZZZ"

    Returns: "ZZZZZZZZZZZZZ"

  18. "Y"

    Returns: "X"

  19. "ZZZZZZYZZZZZZ"

    Returns: "ZZZZZZXZZZZZZ"

  20. "DDDDDDDDDDD"

    Returns: "HHHHHHHHHHH"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: