Projecteuler.net – Problem 43 – Java

http://projecteuler.net/problem=43

I recycled some code from the previous problem I worked on that used Lexicographic permutations. This will just cycle through all the possibilities without repeats and maintain the ‘pandigital-ness’ of the number we are starting with.

If I find any other problems that I can use my getNextLexicographicPermutation() method I might put that code into its own class and add some getters/setters, etc. to make it more robust.

I’m really digging Java so far.

Josh

public class euler43 {	
	
	public static void main(String[] args) {		
		
		long sum = 0;
		String num = "0123456789";
		
		for (long q = 123456789; q <= 9876543210l; q++) {
			
			if (num == "last") {
				break;
			}
			
			boolean test = true;
		
			// break the number down into pieces
			int n1 = Integer.parseInt(num.substring(1,4));
			int n2 = Integer.parseInt(num.substring(2,5));
			int n3 = Integer.parseInt(num.substring(3,6));
			int n4 = Integer.parseInt(num.substring(4,7));
			int n5 = Integer.parseInt(num.substring(5,8));
			int n6 = Integer.parseInt(num.substring(6,9));
			int n7 = Integer.parseInt(num.substring(7,10));
			
			// test each piece according to the problem
			if (n1%2 != 0) { test = false; }
			if (n2%3 != 0) { test = false; }
			if (n3%5 != 0) { test = false; }
			if (n4%7 != 0) { test = false; }
			if (n5%11 != 0) { test = false; }
			if (n6%13 != 0) { test = false; }
			if (n7%17 != 0) { test = false; }
			
			if (test == true) {
				sum+=Long.parseLong(num);
			}
			
			// get the next permutation
			num = getNextLexicographicPermutation(num);
		
		}
		
		System.out.println(sum);
		
	}	
	
	/**
	 * Generates the next lexicographic permutation of a given number
	 * @param a String containing the number to be permutated
	 * @return String contains the next permutation
	 */
	private static String getNextLexicographicPermutation(String a) {
					
		int largestIndexK = -1;			// if this stays negative, we are at last permutation
		int largestIndexL = 0;
		char[] b = a.toCharArray();		// holds the next permutation as we build it
		
		// Find the largest index k such that a[k] < a[k + 1]. 
		// If no such index exists, the permutation is the last permutation.
		for (int k = 0; k < a.length() - 1; k++) {
			if (a.charAt(k) < a.charAt(k + 1)) {
				largestIndexK = k;
			}		
		}
		
		if (largestIndexK == -1) {
			//System.out.println("last permutation");
			return "last";
		} 
		
		// Find the largest index l such that a[k] < a[l]. 
		// Since k + 1 is such an index, l is well defined and satisfies k < l.
		for (int l = 0; l < a.length(); l++) {
			if (a.charAt(largestIndexK) < a.charAt(l)) {
				largestIndexL = l;
			}
		}
						
		// Swap a[k] with a[l]. 
		b[largestIndexK] = a.charAt(largestIndexL);
		b[largestIndexL] = a.charAt(largestIndexK);
				
		// Reverse the sequence from a[k + 1] up to and including the final element a[n].
		String s = new String(b).substring(largestIndexK + 1);		
		int x = 1;
		for (int i=s.length(); i > 0; i--) {
			b[largestIndexK + x] = s.charAt(i - 1);			
			x++;			
		}
		
		a = new String(b);		
				
		return a;
	}
		
}
This entry was posted in Java, Project Euler. Bookmark the permalink.

Leave a Reply