Tag Archive for 'radixSort'

Problem 22 of Project Euler defines name score as the word value of a name multiplied by its position when a list of names is sorted. So, we need to sort the array first. I used Radix Sort for it. Simple implementation, it has been written below:

RadixComparator class:

package pba.common.text;

import java.util.Comparator;

/**
 * This is the Comparator class to be used for Radix Sorting.
 *
 * @author AnuvratSingh
 */
public class RadixComparator implements Comparator<String> {
	int columnNum;

	/**
	 * @param col Sorting takes place by considering the value at this column as the key
	 */
	public RadixComparator(int col) {
		columnNum = col;
	}

	/**
	 * This method compares two strings
	 *
	 * @param s1 The first string
	 * @param s2 The second string
	 * @return If length of both the strings is less than the column value, return 0. Else, if s1 is of smaller length
	 *         than column, then return -1. Else if s1 is of length greater than column, but s2 is smaller then return
	 *         1. If both are of length greater than column, then return the difference between the characters at
	 *         column. Please note, no conversion to lower case is done.
	 */
	public int compare(String s1, String s2) {
		int l2 = s2.length();

		if (s1.length() < columnNum + 1)
			return l2 < columnNum + 1 ? 0 : -1;
		else if (l2 < columnNum + 1)
			return 1;
		else
			return s1.charAt(columnNum) - s2.charAt(columnNum);
	}
}

RadixSort class:

package pba.common.tools.sort;

import java.util.Arrays;

import pba.common.text.RadixComparator;

/**
 * This class performs Radix Sort
 *
 * @author AnuvratSingh
 */
public class RadixSort {
	/**
	 * @param words The array of words which need to be sorted
	 * @param maxLength The length of the longest word in the array
	 * @return A sorted array of the words
	 */
	public static String[] sort(String[] words, int maxLength) {
		for (int i = maxLength - 1; i > -1; --i)
			Arrays.sort(words, new RadixComparator(i));
		return words;
	}

	/**
	 * @param words The array of words which need to be sorted
	 * @return A sorted array of words
	 */
	public static String[] sort(String[] words) {
		int maxLength = 0;
		for (String word : words) {
			int length = word.length();
			if (length > maxLength)
				maxLength = length;
		}

		return RadixSort.sort(words, maxLength);
	}
}

EnglishWordUtil class:

package pba.common.text;

/**
 * A class which allows manipulations with the English Words
 *
 * @author AnuvratSingh
 */
public class EnglishWordUtil {
	/**
	 * Returns the numerical value of a word which is found by summing the alphabetical position of each character in
	 * the word. For example, the word value for SKY is 19 + 11 + 25 = 55
	 *
	 * @param word the word whose numerical value is required
	 * @return the numerical value of the given word
	 */
	public static int getNumericalValue(String word) {
		String lowerCaseWord = word.toLowerCase();

		int sum = 0;
		for (int i = 0; i < lowerCaseWord.length(); i++)
			sum += lowerCaseWord.charAt(i) - 'a' + 1;

		return sum;
	}
}

Main class:

package problems_21_30;

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;

import pba.common.text.EnglishWordUtil;
import pba.common.tools.sort.RadixSort;

public class Problem_22 {
	private static final String fileName = "problem_22.in";

	public static void main(String[] args) throws IOException {
		// Read all the names from the input file
		BufferedReader bufferedReader = new BufferedReader(new FileReader(Problem_22.fileName));
		String[] words = bufferedReader.readLine().split("\",\"");

		// Correct the first and the last word which have "
		words[0] = words[0].substring(1);
		int numberOfWords = words.length;
		String lastWord = words[numberOfWords - 1];
		words[numberOfWords - 1] = lastWord.substring(0, lastWord.length() - 1);

		// Sort all the names
		String[] sortedWords = RadixSort.sort(words);

		// Find the name score sum
		int sum = 0;
		for (int i = 0; i < sortedWords.length; i++)
			sum += (i + 1) * EnglishWordUtil.getNumericalValue(sortedWords[i]);

		System.out.println(sum);
	}
}

Popularity: 8% [?]