project-euler

https://projecteuler.net/
Log | Files | Refs | README

Euler_98.cpp (3481B)

      1 #include "Euler.h" 
      2 #include <algorithm>
      3 #include <fstream>
      4 #include <vector>
      5 #include <unordered_map>
      6 
      7 int anagrams_match(std::vector<std::string>& anagram_pair, std::vector<std::string>& anagram_squares) {
      8     int solution = -1;
      9 
     10     for (uint64_t i = 0; i < anagram_squares.size(); ++i) {
     11         std::unordered_map<char, char> char_map;
     12         bool match = true;
     13 
     14         for (uint64_t c = 0; c < anagram_pair[0].size(); ++c) {
     15             bool char_in_map = char_map.find(anagram_pair[0][c]) != char_map.end();
     16 
     17             for (std::pair<char, char> p : char_map) {
     18                 if (p.second == anagram_squares[i][c] && ((p.first != anagram_pair[0][c]) || !char_in_map)) {
     19                     match = false;
     20                     break;
     21                 }
     22             }
     23 
     24             if (match && !char_in_map) {
     25                 char_map.insert(std::pair<char, char>(anagram_pair[0][c], anagram_squares[i][c]));
     26             }
     27         }
     28 
     29         if (match) {
     30             std::string built;
     31 
     32             for (uint64_t c = 0; c < anagram_pair[1].size(); ++c) {
     33                 built.append(&char_map.find(anagram_pair[1][c])->second);
     34             }
     35 
     36             for (std::string anagram_square : anagram_squares) {
     37                 if (built == anagram_square) {
     38                     solution = std::max(std::max(std::stoi(built), std::stoi(anagram_squares[i])), solution);
     39                 }
     40             }
     41         }
     42     }
     43 
     44     return solution;
     45 }
     46 
     47 std::vector<std::vector<std::string> > find_all_anagrams(std::vector<std::string>& words) {
     48     std::vector<std::vector<std::string> > anagram_pairs;
     49 
     50     for (std::string& word : words) {
     51         bool word_is_anagram = false;
     52 
     53         for (std::vector<std::string>& anagram_pair : anagram_pairs) {
     54             std::string temp1 = word; std::sort(temp1.begin(), temp1.end());
     55             std::string temp2 = anagram_pair[0]; std::sort(temp2.begin(), temp2.end());
     56 
     57             if (temp1 == temp2) {
     58                 word_is_anagram = true;
     59                 anagram_pair.push_back(word);
     60                 break;
     61             }
     62         }
     63 
     64         if (!word_is_anagram) {
     65             anagram_pairs.push_back(std::vector<std::string>({word}));
     66         }
     67     }
     68 
     69     return anagram_pairs;
     70 }
     71 
     72 int Euler::AnagramicSquares() {
     73     std::vector<std::string> words, squares;
     74     std::ifstream file;
     75     std::string temp;
     76 
     77     file.open("files/p098_words.txt");
     78 
     79     while(std::getline(file, temp, ',')) {
     80         temp.erase(temp.size() - 1, 1); temp.erase(0, 1);
     81         words.push_back(temp);
     82     }
     83 
     84     file.close();
     85 
     86     for (int i = 0; i < sqrt(1e9); ++i) {
     87         squares.push_back(std::to_string(i * i));
     88     }
     89 
     90     std::vector<std::vector<std::string> > anagram_pairs = find_all_anagrams(words);
     91     std::vector<std::vector<std::string> > anagram_squares = find_all_anagrams(squares);
     92 
     93     int largest_square = 0;
     94 
     95     for (std::vector<std::string>& anagram_pair : anagram_pairs) {
     96         for (std::vector<std::string>& anagram_square : anagram_squares) {
     97             if (anagram_square.size() > 1 && anagram_square[0].size() == anagram_pair[0].size() && anagram_pair.size() > 1) {
     98                 int solution = anagrams_match(anagram_pair, anagram_square);
     99                 if (solution > largest_square) {
    100                     largest_square = solution;
    101                 }
    102             }
    103         }
    104     }
    105 
    106     return largest_square;
    107 }