project-euler

commit dc123f222f9781f36ecb3e87c34938f83559a8fb
parent 28d0684e17668b0d086acf581199e547b78160c9
Author: mpizzzle <m@michaelpercival.xyz>
Date:   Sun,  4 Oct 2020 20:20:06 +0100

problem 98 complete

Diffstat:
M
Euler.h
 | 
1
+
A
Euler_98.cpp
 | 
107
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M
Makefile
 | 
2
+-
M
main.cpp
 | 
3
++-

4 files changed, 111 insertions(+), 2 deletions(-)
diff --git a/Euler.h b/Euler.h
@@ -89,4 +89,5 @@ public:
     uint64_t ArrangedProbability();
     uint64_t CubeDigitPairs();
     int Sudoku();
+    int AnagramicSquares();
 };
diff --git a/Euler_98.cpp b/Euler_98.cpp
@@ -0,0 +1,107 @@
+#include "Euler.h" 
+#include <algorithm>
+#include <fstream>
+#include <vector>
+#include <unordered_map>
+
+int anagrams_match(std::vector<std::string>& anagram_pair, std::vector<std::string>& anagram_squares) {
+    int solution = 0;
+
+    for (uint64_t i = 0; i < anagram_squares.size(); ++i) {
+        std::unordered_map<char, char> char_map;
+        bool match = true;
+
+        for (uint64_t c = 0; c < anagram_pair[0].size(); ++c) {
+            bool char_in_map = char_map.find(anagram_pair[0][c]) != char_map.end();
+
+            for (std::pair<char, char> p : char_map) {
+                if (p.second == anagram_squares[i][c] && ((p.first != anagram_pair[0][c]) || !char_in_map)) {
+                    match = false;
+                    break;
+                }
+            }
+
+            if (match && !char_in_map) {
+                char_map.insert(std::pair<char, char>(anagram_pair[0][c], anagram_squares[i][c]));
+            }
+        }
+
+        if (match) {
+            std::string built;
+
+            for (uint64_t c = 0; c < anagram_pair[1].size(); ++c) {
+                built.append(&char_map.find(anagram_pair[1][c])->second);
+            }
+
+            for (std::string anagram_square : anagram_squares) {
+                if (built == anagram_square) {
+                    solution = std::max(std::max(std::stoi(built), std::stoi(anagram_squares[i])), solution);
+                }
+            }
+        }
+    }
+
+    return solution;
+}
+
+std::vector<std::vector<std::string> > find_all_anagrams(std::vector<std::string>& words) {
+    std::vector<std::vector<std::string> > anagram_pairs;
+
+    for (std::string& word : words) {
+        bool word_is_anagram = false;
+
+        for (std::vector<std::string>& anagram_pair : anagram_pairs) {
+            std::string temp1 = word; std::sort(temp1.begin(), temp1.end());
+            std::string temp2 = anagram_pair[0]; std::sort(temp2.begin(), temp2.end());
+
+            if (temp1 == temp2) {
+                word_is_anagram = true;
+                anagram_pair.push_back(word);
+                break;
+            }
+        }
+
+        if (!word_is_anagram) {
+            anagram_pairs.push_back(std::vector<std::string>({word}));
+        }
+    }
+
+    return anagram_pairs;
+}
+
+int Euler::AnagramicSquares() {
+    std::vector<std::string> words, squares;
+    std::ifstream file;
+    std::string temp;
+
+    file.open("files/p098_words.txt");
+
+    while(std::getline(file, temp, ',')) {
+        temp.erase(temp.size() - 1, 1); temp.erase(0, 1);
+        words.push_back(temp);
+    }
+
+    file.close();
+
+    for (int i = 0; i < sqrt(1000000000); ++i) {
+        squares.push_back(std::to_string(i * i));
+    }
+
+    std::vector<std::vector<std::string> > anagram_pairs = find_all_anagrams(words);
+    std::vector<std::vector<std::string> > anagram_squares = find_all_anagrams(squares);
+
+    int largest_square = 0;
+
+    for (std::vector<std::string>& anagram_pair : anagram_pairs) {
+        for (std::vector<std::string>& anagram_square : anagram_squares) {
+            if (anagram_square.size() > 1 && anagram_square[0].size() == anagram_pair[0].size() && anagram_pair.size() > 1) {
+                int solution = anagrams_match(anagram_pair, anagram_square);
+                if (solution > largest_square) {
+                    largest_square = solution;
+                }
+            }
+        }
+    }
+
+    return largest_square;
+}
diff --git a/Makefile b/Makefile
@@ -13,7 +13,7 @@ _OBJ = main.o 
 	Euler_61.o Euler_62.o Euler_63.o Euler_64.o Euler_68.o Euler_69.o Euler_70.o 
 	Euler_71.o Euler_72.o Euler_73.o Euler_74.o Euler_75.o Euler_76.o Euler_77.o Euler_79.o Euler_80.o 
 	Euler_86.o Euler_87.o Euler_90.o 
-	Euler_94.o Euler_95.o Euler_96.o Euler_100.o 
+	Euler_94.o Euler_95.o Euler_96.o Euler_98.o Euler_100.o 
 	EulerUtility.o
 
 OBJ = $(patsubst %,$(ODIR)/%,$(_OBJ))
diff --git a/main.cpp b/main.cpp
@@ -93,7 +93,8 @@ int main() {
     //std::cout << "problem 90: " << e.CubeDigitPairs() << std::endl; //in progress
     //std::cout << "problem 94: " << e.AlmostEquilateralTriangles() << std::endl; //in progress
     //std::cout << "problem 95: " << e.AmicableChains() << std::endl;
-    std::cout << "problem 96: " << e.Sudoku() << std::endl; //in progress
+    //std::cout << "problem 96: " << e.Sudoku() << std::endl; //in progress
+    std::cout << "problem 98: " << e.AnagramicSquares() << std::endl; //in progress
     //std::cout << "problem 100: " << e.ArrangedProbability() << std::endl; //in progress
 
     std::cout << "duration: " << 1000.0 * (std::clock() - start) / CLOCKS_PER_SEC << "ms" << std::endl;