Computer Science 15-100 (Sections T & U), Spring 2008
Homework 9a
Due:  Tue 1-Apr-2008 at 3pm (online submission) and at class (physical copy)
(no late submissions accepted <-- really!)

• Be sure to include your name, your Andrew ID, and your section (T or U) clearly on the top of each file in your assignment.
• Name your program and your methods exactly as indicated.
  • You will have exactly one program:
    1. Hw9a.java -- this will contain all the questions
• Use well-named variables, proper indenting, reasonable commenting, etc.  Do not use magic numbers!
• Provide complete (but concise) test cases!
• Provide the UI exactly as indicated.  File-based UI should not include prompts.
• Submit printed solutions in class.  Your printed solutions must be identical copies of your emailed solutions!
• Even though you are not always provided with a test method, you must write an appropriate test method for every method you write!

1. This assignment is based on the Combinatorial Iterators lecture (notes are here), and uses Permutations, Combinations, Power Sets, and/or BaseNCounting from that lecture.
   
   For this problem, we will solve one kind of Cryptarithm problem.  There are variants on this game, so we will set out the rules here, especially as we are restricting our solution to just one kind of Cryptarithm.  Here, you are given an addition problem where letters are substituted for the digits.  Your goal is to reform the problem using digits rather than letters.  For example, if you are given "SEND + MORE = MONEY", you would find that this can be solved by substituting 9 for S, 5 for E, 6 for N, and so on, until you get:  "9567 + 1085 = 10652".  Here are some more specific rules:
   • The problem will be given as a single String, as will the solution.
   • The incoming string will always have this exact format: a word, a space, a plus, a space, another word, a space, an equals, a space, and a third word.  You do not have to verify this, and you can do anything (including crashing!) if this is not the case.
   • The incoming words will all be restricted to uppercase letters.  Again, you do not have to verify this.
   • The returned string will have the same format, only with digits replacing their respective letters.
   • Each occurrence of a letter must be replaced by the same digit throughout the problem, and no two distinct letters may be replaced by the same digit.
   • No number in the returned string shall begin with a leading zero.
   • Hence, there are always exactly two numbers being added, and both these numbers plus the solution are all positive integers.
   • If there is no solution, you should return null.
   • A true cryptarithm has exactly one solution.  However, if there is more than one solution, you can return the first solution you find, whatever it is.
     
     Your task:  write a method with this signature:
       public static String solveCryptarithm(String cryptarithm) {
       }
     This method takes a non-null String as described above and returns the solved cryptarithm, again as described above, or null if no solution exists.
     
     Here is the start of a test method for solveCryptarithm
     
      public static void testSolveCryptarithm() {
        verify(solveCryptarithm("SEND + MORE = MONEY").equals(
                                "9567 + 1085 = 10652"));
        verify(solveCryptarithm("HAS + NO = SOLUTION") == null);
      }
     
     Aside: before writing your code, you might see if you can solve these true Cryptarithms by hand (and you may also wish to include these in your test method):
     
          IDAHO + NEVADA = STATES
     
          SIENNA + SILVER = COLORS
     
          RENOIR + SEURAT = GAUGUIN
     
     Hints:
     • The idea is to try every possible mapping of digits to letters.
     • So, first, find a way to extract the letters that are used in the problem.  The incoming format is not the best for this, so find a better format to store these letters in.
     • Next, because digits cannot be reused (they can map to only one of the unique letters), and because order matters when mapping the digits to letters, you should use a permutation (think about this!).
     • You could permute all 10 digits, but unless there are 10 unique letters, this is unnecessary.
     • Instead, if there are K unique letters in the problem, you really just need to permute K digits from among the 10 total digits.
     • For example, in the problem "SEND + MORE = MONEY", the unique letters are "DEMNORSY".  There are 8 unique letters, so we just need to permute 8 digits from among the 10 total digits.  One such permutation, [7,5,1,6,0,8,9,2], is in fact the solution to the problem (though we still need to format it back into the desired format).
     • Use well-chosen helper methods of your own choosing.  Do not place all your code in one method!
     • As with the Krypto assignment, don't get discouraged by this long description and the fact that the problem itself is hard for humans to solve.  As far as a Java solution goes, the "heavy lifting" is again mostly done for you in the Permutation class.  The solution we wrote for this problem required about 50 lines of code.  You can do this!

Carpe diem!