Pages

Wednesday, September 9, 2009

Euler Problem 37 solution

Time (s): ~0.599
package margusmartseppcode.From_30_to_39;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Problem_37 {

 static Integer cint(String nr) {
  return Integer.parseInt(nr);
 }

 static boolean isLTP(String mem, Set<Integer> primes) {
  int n = mem.length();
  if (n < 1)
   return true;
  return primes.contains(cint(mem)) && isLTP(mem.substring(1), primes);
 }

 static boolean isRTP(String mem, Set<Integer> primes) {
  int n = mem.length();
  if (n < 1)
   return true;
  return primes.contains(cint(mem))
    && isRTP(mem.substring(0, n - 1), primes);
 }

 static boolean isTP(String mem, Set<Integer> primes) {
  return isLTP(mem, primes) && isRTP(mem, primes);
 }

 private static void bTP(Integer mem, Set<Integer> primes,
   Set<Integer> truncatable) {
  if (primes.contains(mem)) {
   if (isTP(""+mem, primes))
    truncatable.add(mem);
   TruncatablePrimes(mem, primes, truncatable);
  }
 }

 private static void TruncatablePrimes(Integer elem, Set<Integer> primes,
   Set<Integer> truncatable) {
  String[] o = new String[] { "1", "2", "3", "4", "5", "6", "7", "8", "9" };
  String s = "" + elem;

  for (String pos : o) {
   bTP(cint(s + pos), primes, truncatable);
   bTP(cint(pos + s), primes, truncatable);
  }
 }

 public static void main(String[] args) throws FileNotFoundException {
  Set<Integer> truncatable = new HashSet<Integer>();
  Set<Integer> primes = new HashSet<Integer>();
  Scanner sc = new Scanner(new File("primes1m.txt"));
  int sum = 0;

  for (String tmp = sc.next(); sc.hasNext(); tmp = sc.next())
   primes.add(Integer.parseInt(tmp));

  for (Integer elem : new Integer[] { 3, 7 })
   TruncatablePrimes(elem, primes, truncatable);

  for (Integer elem : truncatable)
   sum += elem;

  System.out.println(sum);
 }
}

No comments:

Post a Comment