Solution

The first part is to parse the input

// parse input
freopen("0098_words.txt", "r", stdin);
std::vector<std::string> words;
std::string word;
while (std::cin >> std::quoted(word)) {
    words.push_back(word);
    if (std::cin.peek() == ',') {
        std::cin.get();
    }
}

Next, group words by their sorted letters. For example, ["CARE", "RACE", "ACRE"] all get mapped to ACER and similarly, ["QUIET", "QUITE"] get mapped to EIQTU. The goal here is just find all the anagrams.

    std::unordered_map<std::string, std::vector<std::string>> groups;
    for (const std::string& current : words) {
        std::string sortedWord = current;
        std::sort(sortedWord.begin(), sortedWord.end());
        groups[sortedWord].push_back(current);
    }

Next, we want to generate perfect squares that have distinct digits. By examining the list of anagrams above, we can see that we at most have words of size 5. So it’s enough to really generate around 110 squares 169, 196, 256, 289, 324, ...87025,89401.

bool is_distinct(long number) {
    bool seen[10] = {};
    do {
        int digit = number % 10;
        if (seen[digit]) {
            return false;
        }
        seen[digit] = true;
        number /= 10;
    } while (number != 0);
    return true;
}
std::vector<long> generate_distinct_squares() {
    std::vector<long> squares;
    for (int i = 10; i < 500; i++) {
        long p = i*i;
        if (is_distinct(p)) {
            squares.push_back(p);
        }
    }
    return squares;
}

Next, we want to consider every possible pair of anagrams that we have. It turns out we have exactly 44 pairs

 for (const auto& entry : groups) { // 44 pairs total
        const std::vector<std::string>& group = entry.second;
        for (std::size_t i = 0; i < group.size(); ++i) {
            for (std::size_t j = i + 1; j < group.size(); ++j) {
                if (group[i].size() < 4) { continue; }
                anagram_square(group[i], group[j], squares);
            }
        }
    }

Now we come to the main step: determining whether a pair of anagrams can both represent perfect squares. We begin with a known pair of anagrams, such as CARE and RACE. We assign a perfect square to the first word, use its letter-to-digit mapping to generate the number represented by the second word, and then check whether that number is also a perfect square.

  • Assign the first candidate square to CARE. Suppose CARE = 1024. This gives us the mapping C → 1, A → 0, R → 2, and E → 4. Using the same mapping, RACE = 2014. Since 2014 is not a perfect square, this candidate is rejected.
  • Try the next candidate square. Suppose CARE = 1089. Using the resulting mapping, RACE = 8019. Since 8019 is not a perfect square, this candidate is also rejected.
  • Continue checking candidate squares until a valid pair is found. For example, CARE = 1296 produces RACE = 9216. Both numbers are perfect squares because 1296 = 36² and 9216 = 96². Therefore, this is a valid anagram-square pair.

We continue this process for every pair of anagrams and every perfect square. So roughly 44k iterations!

long max = 0;
void anagram_square(const std::string& first, const std::string& second, const std::vector<long>& squares) {
    std::vector<std::pair<long, long>> results;
    for (int i = 0; i < squares.size(); i++) {
        long first_square = squares[i];
        std::string digits = std::to_string(first_square);
        if (digits.length() != first.size()) {
            continue;
        }
        // build a map that maps the first square to the first string
        // so CARE = 1296
        std::unordered_map<char, char> m;
        for (std::size_t i = 0; i < first.size(); ++i) {
            char letter = first[i];
            char digit = digits[i];
            m[letter] = digit;
        }
        // don't allow leading zeros! abort immediately
        if (m.at(second.front()) == '0') {
            continue;
        }
        // build the second potential square using the map m
        long second_square = 0;
        for (char letter : second) {
            second_square = second_square * 10 + (m[letter] - '0');
        }
        // if it's a square, then we have squares! save it if it's a max
        if (is_perfect(second_square)) {
            if (max < first_square) {
                max = first_square;
            }
            if (max < second_square) {
                max = second_square;
            }
        }
    }
}

References

Project Euler - 98