1. Lars Viklund
  2. euler

Commits

Lars Viklund  committed f8f617b

Solved problem #98.

  • Participants
  • Parent commits efa2da2
  • Branches default

Comments (0)

Files changed (6)

File Windows/Windows.vcxproj

View file
     <ClInclude Include="..\src\094.h" />
     <ClInclude Include="..\src\095.h" />
     <ClInclude Include="..\src\096.h" />
+    <ClInclude Include="..\src\098.h" />
     <ClInclude Include="..\src\099.h" />
     <ClInclude Include="..\src\102.h" />
     <ClInclude Include="..\src\104.h" />

File Windows/Windows.vcxproj.filters

View file
     <ClInclude Include="..\src\096.h">
       <Filter>Header Files\Problems</Filter>
     </ClInclude>
+    <ClInclude Include="..\src\098.h">
+      <Filter>Header Files\Problems</Filter>
+    </ClInclude>
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="..\src\main.cc">

File src/094.h

View file
+#pragma once
 #include "problem.h"
 #include "primes.h"
 

File src/096.h

View file
+#pragma once
 #include "problem.h"
 
 struct Puzzle : std::vector<int>

File src/098.h

View file
+#pragma once
+#include "problem.h"
+#include "spam.h"
+
+template <>
+void Problem<98>()
+{
+	std::map<std::string, std::vector<std::string>> groups;
+	
+	std::ifstream is("../data/words.txt");
+	std::string chunk, word, key;
+	while (std::getline(is, chunk, ','))
+	{
+		key = word = chunk.substr(1, chunk.size() - 2);
+		std::sort(key.begin(), key.end());
+		groups[key] += word;
+	}
+	
+	long bestSquare = 0;
+	mpz_class square;
+
+	for (auto I = groups.begin(); I != groups.end(); ++I)
+	{
+		auto const& key = I->first;
+		auto& words = I->second;
+		if (words.size() == 1)
+			continue;
+		std::set<char> letters(key.begin(), key.end());
+		std::vector<char> vec(letters.begin(), letters.end());
+		std::vector<int> digits = list_of(0)(1)(2)(3)(4)(5)(6)(7)(8)(9);
+		
+		std::map<char, int> lookup;
+		do
+		{
+			int off = 0;//for (int off = 0; off < digits.size() - vec.size() + 1; ++off)
+			{
+				for (int i = 0; i < vec.size(); ++i)
+				{
+					lookup[vec[i]] = digits[i + off];
+				}
+				std::multiset<long> squares;
+				for (auto I = words.begin(); I != words.end(); ++I)
+				{
+					if (lookup[I->front()] == 0)
+						continue;
+					int num = 0;
+					for (auto J = I->begin(); J != I->end(); ++J)
+					{
+						num *= 10;
+						num += lookup[*J];
+					}
+
+					//std::cerr << *I << ": " << num;
+					
+					square = num;
+					if (mpz_perfect_square_p(square.get_mpz_t()))
+					{
+						squares += num;
+						//std::cerr << "** ";
+					}
+					else
+						;//std::cerr << "   ";
+				}
+				if (squares.size() > 1)
+				{
+					auto top = *squares.rbegin();
+					if (top > bestSquare)
+						bestSquare = top;
+				}
+				//std::cerr << std::endl;
+			}
+		}
+		while (std::next_permutation(digits.begin(), digits.end()));
+	}
+	std::cout << "The highest square is " << bestSquare << std::endl;
+}

File src/main.cc

View file
-#include "094.h"
+#include "098.h"
 
 int main()
 {
-	Problem<94>();
+	Problem<98>();
 }