Next

Morph 2 U.S. states into 2 other states
  • the problem
  • all combinations of X things taken Y at a time
  • comparing strings
  • design 1
  • implementation 1
  • design 2
  • implementation 2
  • design 3
  • implementation 3
  •  

    Next   Previous   Top

    The Problem

     

    Take the names of two U.S. States,
    mix them all together,
    then rearrange the letters
    to form the names of two other U.S. States.
     

    What are the states?

     

     

    Next   Previous   Top

    Next   Previous   Top

    Next   Previous   Top

    "all combinations"

    Next   Previous   Top

    Next   Previous   Top

    How about adapting the inner loops to not "visit territory" already visited by outer loops
    ("j = i + 1" and "k = j + 1"),

    and instrumenting the outer loops to not duplicate work reserved for inner loops
    ("i < 4" and "j < 5")?

    Next   Previous   Top

    Combinations

    Next   Previous   Top

    Combinations

    Next   Previous   Top

    Strategy Review

    Next   Previous   Top

    Comparing

    What is the easiest way to "compare" a 2-state combination with another 2-state combination?

    Do we want to step through the characters of one combination, and find and check off each character in the other combination until a mismatch is identified?

    What about converting each combination to some canonical form that could reduce the comparison to a simple string compare?

    How about sorting each combination before comparing?

    Next   Previous   Top

    The strategy of sorting each string makes it easy to identify the 3 words composed of identical characters.

    Next   Previous   Top

    Next   Previous   Top

    What algorithm?

    Next   Previous   Top

    An algorithm

    1. Declare an array to hold the combination strings, and a second array to hold the sorted strings.

    2. Iterate through all possible combinations of two states.

    2-1. Sort the letters of each combination.

    2-2. Store the unsorted string in the first array, and the sorted string in the second.

    3. Iterate through all elements in the second array.

    3-1. Compare each sorted string to every other sorted string.

    3-2. If the sorted strings match, then report the unsorted strings.

    Next   Previous   Top

    Solution 1

    Next   Previous   Top

    Instead of using a brute force sequential search to find a match
    (the second loop within a loop),

    is a more inspired approach possible?

    Next   Previous   Top

    Less brute force?

    What about sorting the sorted combinations, and then looking for 2 adjacent combinations that are equal?

    We will need to keep the sorted string and the unsorted string "together" so that when the sorted strings match, then the unsorted strings can be reported.

    Is there a C++ data structure with sufficient mojo for this context?

    Next   Previous   Top

    Less brute force?

    Next   Previous   Top

    multimap example

    Next   Previous   Top

    An algorithm

    1. Iterate through all possible combinations of two states.

    1-1. Sort the letters of each combination.

    1-2. "Pair-up" each sorted representation with its unsorted original.

    1-3. Insert each pairing into a multimap object.

    2. After the multimap is loaded, declare 2 iterator objects on the multimap, and advance one of the iterators one step.

    3. Increment both iterator objects until 2 of the sorted strings are found to be equal.

    Next   Previous   Top

    Solution 2

    Next   Previous   Top

    Next   Previous   Top

    An algorithm

    1. Iterate through all possible combinations of two states.

    1-1. Sort the letters of each combination.

    1-2. Before each sorted string is loaded into a map data structure, check to see if that string already exists.

    1-2-1. If the string exists, then report the answer.

    1-2-2. If the string does not exist, then add it to the map.

    Next   Previous   Top

    Solution 3

    impl