This is getting interesintg... Project Euler is taking all my brains out now.. every question seems simple when solved. but how to start
Problem:
http://projecteuler.net/index.php?section=problems&id=98
My approach checks for all the perfect squares first and then checks to anagrams... Here is the solution...
int maxmaxmaxmax=0;
String input = (new DataInputStream(new FileInputStream(new File("words.txt")))).readLine();
StringTokenizer st = new StringTokenizer(input, ",");
ArrayList list = new ArrayList();
while (st.hasMoreTokens()) {
list.add(st.nextToken().replace("\"", ""));
}
long now = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
char[] word1 = list.get(i).toCharArray();
Arrays.sort(word1);
for (int j = 0; j < list.size(); j++) {
if (i == j)
continue;
char[] word2 = list.get(j).toCharArray();
if (word1.length != word2.length)
continue;
Arrays.sort(word2);
boolean isAnagram = true;
for (int k = 0; k < word1.length; k++) {
if (word1[k] != word2[k]) {
isAnagram = false;
break;
}
}
if (!isAnagram) continue;
boolean isPalindrome = true;
for (int m = 0; m < word1.length; m++) {
if (list.get(i).charAt(m) != list.get(j).charAt(
word1.length - m - 1)) {
isPalindrome = false;
break;
}
}
if (isPalindrome) break;
int max = (int) Math.floor((Math.pow(10, word1.length) - 1));
int min = (int) Math.ceil(Math.pow(10,(word1.length - 1)));
for (int number = min; number < max; number++) {
if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) { // perfect
String squareNumber = ""+number;
int[] square = new int[word1.length];
for (int m=0; m
square[m] = Integer.parseInt(""+squareNumber.charAt(m));
HashMap tempMapping = new HashMap();
int[] digits = new int[10];
int[] disWord = new int[26];
for (int m=0; m<10; m++){
digits[m]=0;
}
for (int m=0; m
tempMapping.put(""+list.get(i).charAt(m),square[m]);
digits[square[m]] = 1;
disWord[(int)list.get(i).charAt(m)-65] = 1;
}
int countDistinctDigit=0;
int countDistinctLetter=0;
for (int m=0; m<10; m++)
if (digits[m]==1)
countDistinctDigit++;
for (int m=0; m<26; m++)
if (disWord[m]==1)
countDistinctLetter++;
if (countDistinctDigit != countDistinctLetter) continue;
String tempValue="";
for (int m=0; m
tempValue+=(tempMapping.get(""+list.get(j).charAt(m)));
}
if (tempValue.charAt(0)=='0')
continue;
int number2 = Integer.parseInt(tempValue);
if (Math.sqrt(number2) - Math.floor(Math.sqrt(number2)) == 0) { //YAPS
int tempMax=(number>number2)?number:number2;
if (tempMax>maxmaxmaxmax){
System.out.println(list.get(i)+"-"+number+" vs "+list.get(j)+"-"+number2+" has max = "+tempMax+"(ans) its sqrt ="+Math.sqrt(tempMax));
}
maxmaxmaxmax=(tempMax>maxmaxmaxmax)?tempMax:maxmaxmaxmax;
}
}
}
}
}
System.out.println("Total Time Taken = "+(System.currentTimeMillis() - now)/1000 +" sec");
Problem:
http://projecteuler.net/index.php?section=problems&id=98
My approach checks for all the perfect squares first and then checks to anagrams... Here is the solution...
int maxmaxmaxmax=0;
String input = (new DataInputStream(new FileInputStream(new File("words.txt")))).readLine();
StringTokenizer st = new StringTokenizer(input, ",");
ArrayList
while (st.hasMoreTokens()) {
list.add(st.nextToken().replace("\"", ""));
}
long now = System.currentTimeMillis();
for (int i = 0; i < list.size(); i++) {
char[] word1 = list.get(i).toCharArray();
Arrays.sort(word1);
for (int j = 0; j < list.size(); j++) {
if (i == j)
continue;
char[] word2 = list.get(j).toCharArray();
if (word1.length != word2.length)
continue;
Arrays.sort(word2);
boolean isAnagram = true;
for (int k = 0; k < word1.length; k++) {
if (word1[k] != word2[k]) {
isAnagram = false;
break;
}
}
if (!isAnagram) continue;
boolean isPalindrome = true;
for (int m = 0; m < word1.length; m++) {
if (list.get(i).charAt(m) != list.get(j).charAt(
word1.length - m - 1)) {
isPalindrome = false;
break;
}
}
if (isPalindrome) break;
int max = (int) Math.floor((Math.pow(10, word1.length) - 1));
int min = (int) Math.ceil(Math.pow(10,(word1.length - 1)));
for (int number = min; number < max; number++) {
if (Math.sqrt(number) - Math.floor(Math.sqrt(number)) == 0) { // perfect
String squareNumber = ""+number;
int[] square = new int[word1.length];
for (int m=0; m
square[m] = Integer.parseInt(""+squareNumber.charAt(m));
HashMap
int[] digits = new int[10];
int[] disWord = new int[26];
for (int m=0; m<10; m++){
digits[m]=0;
}
for (int m=0; m
tempMapping.put(""+list.get(i).charAt(m),square[m]);
digits[square[m]] = 1;
disWord[(int)list.get(i).charAt(m)-65] = 1;
}
int countDistinctDigit=0;
int countDistinctLetter=0;
for (int m=0; m<10; m++)
if (digits[m]==1)
countDistinctDigit++;
for (int m=0; m<26; m++)
if (disWord[m]==1)
countDistinctLetter++;
if (countDistinctDigit != countDistinctLetter) continue;
String tempValue="";
for (int m=0; m
tempValue+=(tempMapping.get(""+list.get(j).charAt(m)));
}
if (tempValue.charAt(0)=='0')
continue;
int number2 = Integer.parseInt(tempValue);
if (Math.sqrt(number2) - Math.floor(Math.sqrt(number2)) == 0) { //YAPS
int tempMax=(number>number2)?number:number2;
if (tempMax>maxmaxmaxmax){
System.out.println(list.get(i)+"-"+number+" vs "+list.get(j)+"-"+number2+" has max = "+tempMax+"(ans) its sqrt ="+Math.sqrt(tempMax));
}
maxmaxmaxmax=(tempMax>maxmaxmaxmax)?tempMax:maxmaxmaxmax;
}
}
}
}
}
System.out.println("Total Time Taken = "+(System.currentTimeMillis() - now)/1000 +" sec");