Monthly Archive for May, 2010

Project Euler : Problem 32 – All Round Pandigital

Published on 1 year, 8 months ago in Problems. 0 Comments

The problem requires one to find a product of two numbers such that the multiplicand/multiplier/product can be written as a 1 through 9 pandigital.

An example would be: 39 * 186 = 7254

Working with paper and a pencil, one can discover that the two form of solution are:

a * bbbb = cccc

aa * bbb = cccc

So all that was required to be done was generate all 9 digit permutations of 1-9 and then check if the arrangement satisfies any of the two cases mentioned above.

public class Problem_32<I extends Integer> {
	public static void main(String[] args) {
		System.out.println(new Problem_32<Integer>().computeSum());
	}

	public int computeSum() {
		int sum = 1;
		Set<Integer> products = new HashSet<Integer>();

		Iterator<CombinatoricsVector<I>> permutationIterator = getPermutationGenerator();
		while (!permutationIterator.isDone()) {
			permutationIterator.next();
			CombinatoricsVector<I> permutation = permutationIterator.getCurrentItem();
			products.add(checkCaseA(permutation));
			products.add(checkCaseB(permutation));
		}

		for (Integer i : products)
			sum += i;

		return sum;
	}

	/**
	 * Case A :: a x bbbb = cccc
	 *
	 * @return cccc if above equality holds, -1 otherwise
	 */
	private int checkCaseA(CombinatoricsVector<I> permutation) {
		int a = permutation.getValue(0);
		int b = get4Number(permutation, 1);
		int c = get4Number(permutation, 5);

		return a * b == c ? c : -1;
	}

	/**
	 * Case B :: aa x bbb = cccc
	 *
	 * @return cccc if above equality holds, -1 otherwise
	 */
	private int checkCaseB(CombinatoricsVector<I> permutation) {
		int a = get2Number(permutation, 0);
		int b = get3Number(permutation, 2);
		int c = get4Number(permutation, 5);

		return a * b == c ? c : -1;
	}

	private int get2Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 10 + permutation.getValue(startIdx + 1);
	}

	private int get3Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 100 + permutation.getValue(startIdx + 1) * 10
		        + permutation.getValue(startIdx + 2);
	}

	private int get4Number(CombinatoricsVector<I> permutation, int startIdx) {
		return permutation.getValue(startIdx) * 1000 + permutation.getValue(startIdx + 1) * 100
		        + permutation.getValue(startIdx + 2) * 10 + permutation.getValue(startIdx + 3);
	}

	private Iterator<CombinatoricsVector<I>> getPermutationGenerator() {
		ArrayList<I> array = new ArrayList<I>();
		for (int i = 1; i < 10; i++)
			array.add((I) new Integer(i));

		Iterator<CombinatoricsVector<I>> permutationIterator = new PermutationGenerator<I>(new CombinatoricsVector<I>(
		        array)).createIterator();
		permutationIterator.first();

		return permutationIterator;
	}
}

Popularity: 14% [?]

Project Euler : Largest N Digit Pandigital Prime Number

Published on 1 year, 8 months ago in Problems. 1 Comment

Well, I did a brute force for problem 41 for Project Euler. There’s a smarter way of course, but I still haven’t implemented a Permutation Generator. That later.

I already have a good enough prime number generator. So all I did was to generate all the prime number till 7 digits long. Why did I not go any further?

8 digit pandigital numbers will sum up to 36, and the 9 digit numbers will sum up to 45. So all the pandigital 8 and 9 digit numbers will be non-prime. So we need to check till atmost the 7 digit prime numbers.

Now apart from a prime generator, I also have a prime number iterator, which can iterate forwards as well as backwards. So all I had to do was to ask my iterator to iterate backwards and check if the prime number is pandigital or not.

Obviously, my prime number iterator internally calls my sieve of Eratosthenes to generate prime numbers using java.util.BitSet.

Surprisingly, the code runs in just a few seconds! I was expecting it to take atleast a minute.

Here is my prime number iterator:


public class PrimeNumbersIterator implements Iterator<Integer> {
	private PrimeNumbers m_pNumber;
	private int m_currentIndex;
	private boolean m_reverse;

	public PrimeNumbersIterator(int upperLimit) {
		m_pNumber = new PrimeNumbers(upperLimit);
		m_reverse = false;
	}

	public boolean hasNext() {
		if (!m_reverse)
			return m_currentIndex < m_pNumber.getNumberOfPrimes() ? true : false;
		else
			return m_currentIndex >= 0 ? true : false;
	}

	public Integer next() {
		Integer prime = hasNext() ? m_pNumber.getPrime(m_currentIndex) : null;
		if (m_reverse)
			m_currentIndex--;
		else
			m_currentIndex++;

		return prime;
	}

	public void remove() {
		throw new UnsupportedOperationException();
	}

	public void reverseOrder() {
		m_reverse = !m_reverse;
		m_currentIndex = m_pNumber.getNumberOfPrimes() - 1;
	}
}

And here is a small unoptimized method to check if the number is pandigital or not:


	public static boolean isNPandigital(int number) {
		int numberOfDigits = NumberUtil.numberOfDigits(number);
		int[] digits = new int[numberOfDigits];
		Arrays.fill(digits, 0);

		while (number > 0) {
			int digit = number % 10;
			if (digit == 0 || digit > numberOfDigits || digits[digit - 1]++ == 1)
				return false;
			number /= 10;
		}

		return true;
	}

Popularity: 33% [?]

Three Manager Quotes I Liked

Published on 1 year, 8 months ago in Sports. 0 Comments

I was going through this article wherein the author has compiled a list of 50 managerial quotes.

Top 50 Managerial Quotes Of All Time

I read only the top 10. Of those 10, there were 3 that I loved. They are:

  • Manchester United’s Sir Alex Ferguson
  • My greatest challenge is not what’s happening at the moment, my greatest challenge was knocking Liverpool right off their fucking perch. And you can print that.
  • Liverpool’s Bill Shankly
  • Some people believe football is a matter of life and death. I’m very disappointed with that attitude. I can assure you it is much, much more important than that.
  • Chelsea’s Jose Mourinho
  • Please don’t call me arrogant, but I’m European champion and I think I’m a special one.

Popularity: 2% [?]

Puzzle: Complete the C Code Block

Published on 1 year, 8 months ago in Coding. 6 Comments

A very simple and trivial question:

I am giving a C code block that you need to complete. Here it is:

if(______) {
  printf(" Fair ");
}
else {
  printf(" Isaac ");
}

The question is this:

Propose a condition for the if statement so that the output of the block is Fair Isaac.

Popularity: 6% [?]

Parsing XML Using Castor

Published on 1 year, 9 months ago in Tech. 2 Comments

Castor provides 3 ways to parse an xml file into java objects. I have used two of those, and am writing this post to give an introduction into the method.

The first way is to create java classes for each of the elements and then use the marshall and unmarshall methods to parse the xml file. Castor uses introspection techniques to map elements with fields of the java class. I have not used this method, and will not go any further.

The second and perhaps the easiest way is to give Castor the schema file and let it generate the java classes. Say you have the following schema file:

If you let Castor generate the java source files itself, the following files are generated: The Plgen class for the root element:

The Playlist class which is the child of Plgen:

And finally, the ExtensionType enum:

But I ran into trouble when I wanted to add additional behavior to the classes generated by Castor. As an example, say, I want my Playlist class to implement an interface XYZ which has a method doXYZprocess(). If I am to modify the Playlist class to make it implement the said interface, then if I make any change to the schema file in future I’ll be in trouble. I’ll have to redo all the additions. Now this is a painful task.

An alternative was to create wrapper class around the Castor generated classes and use the wrappers instead. Well, this would work, but I wanted something smarter rather than such duplication.

This is where the third method of parsing comes into picture. It addresses the exact issue as mentioned above. The idea is to use user written classes for marshalling rather than Castor generated ones. One could write a class having lots of methods and fields, bind it to an element of an xml file and have it populated by Castor while parsing the xml. Castor provides this functionality through a Mapping.

A Mapping is another xml file which instructs Castor about the Java classes and the fields that are to be used for parsing. A great degree of freedom is provided in the writing of mapping. One could specifically tell Castor to use certain getters and setters, or leave it to Castor to populate the class fields by introspection.

An example of mapping file for the above schema file would be:

Castor interprets this mapping as the root element being plgen which would get mapped to the class Plgen. This root element can contain a list of Playlist elements. So the getter and setter that Castor calls will be

public ArrayList<Playlist> getPlaylist();

public void setPlaylist(ArrayList<Playlist>);

So our Plgen class above needs to contain these two methods. Similarly, the Playlist class needs to have the following two methods to set the extensionType field:

public String getExtensionType();

public void setExtensionType(String);

Note that I am taking the enum value as a string and will use the setter to set the Enum from a string. My getter likewise will return the Enum.toString().

If you do not want the default getters and setters to be used by Castor, then you have to specify the getter and setter as attributes of the field element in t he mapping.

Castor has compiled a help page to understand the mapping option. You may like to read it here:

Castor XML Mapping

I really liked the mapping feature. It gives me a lot of freedom to write Java classes and then use the mapping to parse any xml file into these classes. This obviates the need to understand the DOM parsing model, of iterating through the xml tree and extracting the values required. The game has been simplified to writing a mapping file and letting Castor create the java objects.

I hate xmls’ NO more. :)

Popularity: 31% [?]

Latest Addition To My Collection : Philips Arcitec

Published on 1 year, 9 months ago in Miscel. 0 Comments

This is mom dad’s return gift for me on their 25th anniversary. :)

All of a sudden I had this impulsive desire to get myself an electric shaver. My search landed me on the Braun Series 7 page, and immediately I knew that I wanted one. The website has listed around 8-9 shops in Hyderabad which stock Braun products. I spent the evening calling them up one by one, only to be told that none of them have the series 7. The best one shop was able to offer me was the Series 3, otherwise others had Series 1.

Philips Arcitec

Philips Arcitec

Disappointed, I chose to settle for a Philips instead. The best model launched by Philips in shavers is the Arcitec series. Again, upon calling up a few stores I found that none of them had this. Dejected, I made up my mind to go to a few more stores and buy the best available alternative. And this is when I entered GVK Mall.

The Shoppers Stop at GVK mall is spread over 3 floors, and a small corner on the first floor has a rack which has electronic goods such as mixer, heater, press-iron, and squeezed between all these was the one thing I was desperately looking for. And what did I find when I removed the few boxes which hid the lot – Philips Arcitec!!!

Well, Arcitec comes in 6 models. Three of them are plain and 3 come with automatic cleaning system. Shaving experience is the same though. So if you want to go for the most economical choice, you would select the 1050 model, which is the most basic one. But of course, I did not have any other options there, so 1050 it was for me. The price though was too high – Rs. 13000. Well, I decided to buy it. An Arcitec is a good enough alternative to the Braun Series 7 shavers.

The booklet inside the box mentioned that it might take a couple of weeks for the skin to get used to electric shavers. But little did I know that my skin would irritate after the first shave. Perhaps, it is because I over did it, or perhaps this is what is meant by getting used to. The after-shave feeling though was great. I loved it. My Mach 3 is going to thrash can, its Arcitec from now.

Popularity: 4% [?]