Project Euler – Problem 61

Problem 61:
Triangle, square, pentagonal, hexagonal, heptagonal, and octagonal numbers are all figurate (polygonal) numbers and are generated by the following formulae:

Triangle	 	P3,n=n(n+1)/2	 	1, 3, 6, 10, 15, ...
Square	 		P4,n=n2	 		1, 4, 9, 16, 25, ...
Pentagonal	 	P5,n=n(3n-1)/2	 	1, 5, 12, 22, 35, ...
Hexagonal	 	P6,n=n(2n-1)	 	1, 6, 15, 28, 45, ...
Heptagonal	 	P7,n=n(5n-3)/2	 	1, 7, 18, 34, 55, ...
Octagonal	 	P8,n=n(3n-2)	 	1, 8, 21, 40, 65, ...

The ordered set of three 4-digit numbers: 8128, 2882, 8281, has three interesting properties.

The set is cyclic, in that the last two digits of each number is the first two digits of the next number (including the last number with the first).

Each polygonal type: triangle (P3,127=8128), square (P4,91=8281), and pentagonal (P5,44=2882), is represented by a different number in the set.
This is the only set of 4-digit numbers with this property.

Find the sum of the only ordered set of six cyclic 4-digit numbers for which each polygonal type: triangle, square, pentagonal, hexagonal, heptagonal, and octagonal, is represented by a different number in the set.

public class Mapping {
	public char[] number;
	public int p;
	public Mapping(int p, char[] array){
		this.p = p;
		this.number = array;
	}
	public String toString(){
		return p+" "+String.valueOf(number);
	}
}

import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map.Entry;
import java.util.Vector;
 
 
class runner2
{	
	private static int triangle(int n){
		return (n+1)*n/2;
	}
	private static int square(int n){
		return n*n;
	}
	private static int pentagonal(int n){
		return (3*n-1)*n/2;
	}
	private static int hexagonal(int n){
		return (2*n-1)*n;
	}
	private static int heptagonal(int n){
		return (5*n-3)*n/2;
	}
	private static int octagonal(int n){
		return n*(3*n-2);
	}
	private static void setup(HashMap<Integer, Vector<char[]>> store){
		for(int i=3;i<9;i++){
			store.put(i, new Vector<char[]>(50));
		}
		for(int i=2; i<300; i++){
			int cur; 
			cur = triangle(i); if(1000 <= cur && cur <= 9999) store.get(3).add((""+cur).toCharArray());
			cur = square(i); if(1000 <= cur && cur <= 9999) store.get(4).add((""+cur).toCharArray());
			cur = pentagonal(i); if(1000 <= cur && cur <= 9999) store.get(5).add((""+cur).toCharArray());
			cur = hexagonal(i); if(1000 <= cur && cur <= 9999) store.get(6).add((""+cur).toCharArray());
			cur = heptagonal(i); if(1000 <= cur && cur <= 9999) store.get(7).add((""+cur).toCharArray());
			cur = octagonal(i); if(1000 <= cur && cur <= 9999) store.get(8).add((""+cur).toCharArray());
		}
	}
	private static HashSet<Mapping> generateMapping(HashMap<String, HashSet<Mapping>> maps, HashMap<Integer, Vector<char[]>> original_Store, String endsWith) {
		if(maps.containsKey(endsWith)) return maps.get(endsWith);
		HashSet<Mapping> result = new HashSet<Mapping>(25);
		char y1 = endsWith.charAt(0), y2 = endsWith.charAt(1);
 
		for(Entry<Integer, Vector<char[]>> entry : original_Store.entrySet()){
			int key = entry.getKey();
			Vector<char[]> arr = entry.getValue();
			for(char[] curStr : arr){
				if(curStr[0] == y1 && curStr[1] == y2){
					result.add(new Mapping(key, curStr));
				}
			}
		}
		maps.put(endsWith, result);
 
		return result;
	}
 
	private static boolean isCyclical(boolean[] done, String original_startsWith, String curEnd, HashMap<String, HashSet<Mapping>> maps){
		boolean exitRecur = true;
		for(boolean x:done){if(!x){exitRecur = false; break;}}
		if(exitRecur){return curEnd.equals(original_startsWith);}
 
		HashSet<Mapping> mapSet = generateMapping(maps, original_Store, curEnd);
		for(Mapping curMapping: mapSet){
			if(done[curMapping.p]) continue;//we already used from that bucket.
			boolean[] doneclone = Arrays.copyOf(done, done.length);
			doneclone[curMapping.p] = true;
 
			if(isCyclical(doneclone, original_startsWith, curMapping.number[2]+""+curMapping.number[3], maps)){
				System.out.println(curMapping.toString());
				return true;
			}
		}
		return false;
	}
 
	static HashMap<Integer, Vector<char[]>> original_Store = new HashMap<Integer, Vector<char[]>>(6);
	public static void main (String[] args) throws java.lang.Exception
	{
		long time = System.currentTimeMillis();
 
		HashMap<String, HashSet<Mapping>> maps = new HashMap<String, HashSet<Mapping>>(500);
		setup(original_Store);
		System.out.println("time: "+(System.currentTimeMillis() - time));
 
		Vector<char[]> currentV = original_Store.get(3);
		boolean[] done = {true, true, true, true, false, false, false, false, false};
		for(int i=0;i<currentV.size(); i++){
			char[] cur = currentV.get(i);
			if(isCyclical(done, cur[0]+""+cur[1], cur[2]+""+cur[3], maps)){
				System.out.println("3 "+String.valueOf(cur));
				break;
			}
		}
 
 
		System.out.println("time: "+(System.currentTimeMillis() - time));
	}
}


Note: Runs in 15ms on my PC… 😀
Note2: My original code included a lexicographic-ordered permutation for isCyclical in combination with an ugly nested (6 layers) of for-loop.
Execution time was less than desired … to say the least.