Projecteuler.net – Problem 26 – Java

http://projecteuler.net/problem=26

I found this Wikipedia section to be invaluable for this problem. The algorithm forms the cyclic sequence using prime numbers.


public class Euler26 {

	static int b = 10;		// number base

	public static void main(String[] args) {

		int longestLength = 0;
		int longestNumber = 0;

		for (int p = 7; p < 1000; p++) {

			if (checkIfPrime(p)) {
				StringBuilder cyclicNumber = new StringBuilder();
				int r = 1;
				int x, d;

				// calculates the next digit of our cyclic number
				// then appends it to our string
				do {
					x = r * b;
					d = (int) Math.floor(x / p);
					r = x % p;
					cyclicNumber.append(d);
				} while (r != 1);

				// we are looking for the longest cyclic number
				if (cyclicNumber.length() > longestLength) {
					longestLength = cyclicNumber.length();
					longestNumber = p;
				}
			}
		}
		System.out.println(longestNumber);
	}

    private static boolean checkIfPrime(long num) {

        if (num == 1) { return false; }

        for (long i = 2; i <= Math.sqrt(num); i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }

}
Posted in Java, Project Euler | Leave a comment

r/dailyprogrammer – [Easy] Roll the Dies

This is my solution to a programming challenge found at reddit.com/r/dailyprogrammer. This problem can be found at Roll the Dies.

Josh


public class Easy {
	public static void main(String[] args) {
		for (int i : rollDice("4d6")) {		// example data
			System.out.print(i + " ");
		}
	}

	private static int[] rollDice(String s) {
		String diceData[] = s.split("d");
		int[] result = new int[Integer.parseInt(diceData[0])];
		for (int i = 0; i < result.length; i++) {
			result[i] = (int)(Math.random() * Integer.parseInt(diceData[1]) + 1);
		}
		return result;
	}
}
Posted in Java, r/dailyprogrammer | Leave a comment

r/dailyprogrammer – [Easy] Longest Two-Character Sub-String

This is my solution to a programming challenge found at reddit.com/r/dailyprogrammer. This problem can be found at longest two character substring. My solution was to step through each position of the string and place whatever character that position holds into a temporary Set. A Set will only contain unique items so if I end up with more than two I know my substring holds more than two unique characters.

Josh


import java.util.HashSet;
import java.util.Set;

public class DailyProgrammer129 {

    public static void main(String[] args) {
        String s = args[0];
        String longest = "";

        for (int i = 0; i < s.length(); i++) {
            Set<Character> tempSet = new HashSet<Character>();

            for (int j = i; j < s.length(); j++) {
                tempSet.add(s.charAt(j));       

                if (tempSet.size() <= 2 && s.substring(i,j+1).length() > longest.length()) {
                    longest = s.substring(i,j+1);
                }
            }
        }
        System.out.println(longest);
    }
}
Posted in Java, r/dailyprogrammer | Leave a comment

Merge Sort Algorithm

A basic implementation of a merge sort algorithm.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 4.54 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh


/**
 * A very basic Merge Sort class implemented from a pseudocode
 * algorithm found on Wikipedia
 *
 * This class will only sort an int[].
 *
 * @author Joshua Weise
 * @see http://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation
 */
public class MergeSort {

	// array of numbers
	private int[] data;

	public MergeSort(int[] data) {
		this.data = data;
	}

	/**
	 * starts the recursive mergeSort method
	 */
	public void sort() {
		data = mergeSort(data);
	}

	/**
	 * Recursively splits the initial data array and calls
	 * the merge method to sort and recombine the data
	 * @param m		numbers to sort
	 * @return		new sorted array
	 */
	private int[] mergeSort(int[] m) {

		if (m.length <= 1) { return m; }

		int[] left = new int[m.length / 2];
		int[] right = new int[m.length - left.length];
		int middle = m.length / 2;

		for (int i = 0; i < middle; i++) {
			left[i] = m[i];
		}

		for (int i = 0; i < right.length; i++) {
			right[i] = m[i + left.length];
		}

		left = mergeSort(left);
		right = mergeSort(right);

		return merge(left, right);
	}

	/**
	 * Merges two number arrays while also putting them in order
	 * @param left		numbers to sort and merge
	 * @param right		numbers to sort and merge
	 * @return			new sorted and merged array
	 */
	private int[] merge(int[] left, int[] right) {
		int[] result = new int[left.length + right.length];
		int x = 0;

		while (left.length > 0 || right.length > 0) {
			if (left.length > 0 && right.length > 0) {
				if (left[0] <= right[0]) {
					result[x] = left[0];
					x++;
					left = shiftLeft(left);
				} else {
					result[x] = right[0];
					x++;
					right = shiftLeft(right);
				}
			} else if (left.length > 0) {
				result[x] = left[0];
				x++;
				left = shiftLeft(left);
			} else if (right.length > 0) {
				result[x] = right[0];
				x++;
				right = shiftLeft(right);
			}
		}
		return result;
	}

	/**
	 * removes the leftmost array item by returning a new array
	 * with everything but that item
	 * @param x		array of numbers
	 * @return		new array of numbers
	 */
	private int[] shiftLeft(int[] x) {
		int[] y = new int[x.length - 1];
		for (int i = 1; i < x.length; i++) {
			y[i-1] = x[i];
		}
		return y;
	}

	// return data
	public int[] getData() {
		return data;
	}

}
Posted in Java, Sorting Algorithms | Leave a comment

Selection Sort Algorithm

A simple example of the selection sort algorithm.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 4.72 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh


/**
 * A very basic Selection Sort class.
 *
 * This class will only sort an int[].
 *
 * @author Joshua Weise
 */
public class SelectionSort {

	// array of numbers
	private int[] data;

	public SelectionSort(int[] data) {
		this.data = data;
	}

	// selection sort data
	public void sort() {
		// move right through our array
		for (int i = 0; i < data.length; i++) {
			// assign the first location as our assumed smallest number
			int smallest = i;
			// loop through the rest of array checking for smaller numbers
			for (int j = 1+i; j < data.length; j++) {
				if (data[j] < data[smallest]) {
					smallest = j;
				}
			}
			// swap number locations
			swap(i, smallest);
		}
	}

	// swaps data in place at locations a and b in the array
	private void swap(int a, int b) {
		int z = data[a];
		data[a] = data[b];
		data[b] = z;
	}

	// return data
	public int[] getData() {
		return data;
	}
}
Posted in Java, Sorting Algorithms | Leave a comment

Insertion Sort Algorithm

A Java example of the insertion sort algorithm.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 1.53 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh


/**
 * A very basic Insertion Sort class.
 *
 * This class will only sort an int[].
 *
 * @author Joshua Weise
 */
public class InsertionSort {

	// array of numbers
	private int[] data;

	public InsertionSort(int[] data) {
		this.data = data;
	} 

	// Insertion sort data
	public void sort() {
		for (int i = 1; i < data.length; i++) {
			// the value we are moving left
			int y = data[i];
			// the array location we could move our value into
			int z = i;
			// loop until we find the farthest left we can move our value into
			// moving the other values out of the way right as we go
			while (z > 0 && y < data[z-1]) {
				data[z] = data[z - 1] ;
				z--;
			}
			// put our original value into its new position
			data[z] = y;
		}
	}

	// return data
	public int[] getData() {
		return data;
	}

}
Posted in Java, Sorting Algorithms | Leave a comment

Bubble Sort Algorithm

A basic example of the bubble sort algorithm in Java.

Running a test file of 100000 randomly ordered integers through this algorithm takes about 15.8 seconds on my system. I will be using the same test file for comparison against other sorting algorithms.

Josh


/**
 * A very basic Bubble Sort class.
 *
 * Sorting algorithm uses a common optimization to avoid
 * resorting already sorted items at the end of the array.
 *
 * This class will only sort an int[].
 *
 * @author Joshua Weise
 */
public class BubbleSort {

	// array of numbers
	private int[] data;

	public BubbleSort(int[] data) {
		this.data = data;
	}

	// bubble sort data
	public void sort() {
		for (int i = data.length; i >= 0; i--) {
			for (int j = 0; j < i-1; j++) {
				if (data[j] > data[j+1]) {
					swap(j, j+1);
				}
			}
		}
	}

	// return data
	public int[] getData() {
		return data;
	}

	// swaps data in place at locations a and b in the array
	private void swap(int a, int b) {
		int z = data[a];
		data[a] = data[b];
		data[b] = z;
	}
}
Posted in Java, Sorting Algorithms | Leave a comment

Projecteuler.net – Problem 63 – Java

http://projecteuler.net/problem=63

This one seemed straight forward and doable with very little code. I like that. Simply solve the math then compare the length of the result to power value.

Josh


import java.math.BigInteger;

public class Euler63 {

	/**
	 * The 5-digit number, 16807=7^5, is also a fifth power.
	 * Similarly, the 9-digit number, 134217728=8^9, is a ninth power.
	 * How many n-digit positive integers exist which are also an nth power?
	 */
	public static void main(String[] args) {

		int numberOfSolutions = 0;

		for (Integer number = 1; number <= 100; number++) {
			for (int power = 1; power <= 100; power++) {

				BigInteger value = new BigInteger(number.toString()).pow(power);
				int length = value.toString().length();

				if (power == length) {
					numberOfSolutions++;
				}
			}
		}

		System.out.println(numberOfSolutions);					

	}

}
Posted in Java, Project Euler | Leave a comment

Projecteuler.net – Problem 46 – Java

http://projecteuler.net/problem=46

Lots of code follows. Not as slim as it might have been if I did it in a procedural way. But I’m trying to make and reuse as much code as possible for later problems.

What I’ve done is generate composite numbers, get all the primes that are in that number, then solve the equation with those numbers and check is my result is a whole number. If there are no whole numbers for a particular odd composite number, then I’ve found an instance where Goldbach’s conjecture no longer holds true.

One thing to keep in mind. When I solved the equation in the way I wanted, I ended up have to divide by square roots. Precision becomes an issue if you don’t simplify the equation. Just remember that sqrt(18) / sqrt(2) simplies to sqrt(18 / 2), or sqrt(9). If you do the former, no matter how precise you try to be, (think BigDecimal with a massive number of precision digits) you will not get 3 as a result.

Josh

This is my main class.

import java.util.ArrayList;

public class Euler46 {

	public static void main(String[] args) {

		ArrayList<Long> primes;
		Prime p = new Prime();
		Composite c = new Composite();		

		for (int i = 3; i < 10000; i=i+2) {
			c.setNumber(i);
			p.setNumber(i);
			primes = p.getPrimes();

			if (c.isComposite()) {

				ArrayList<Double> x = new ArrayList<Double>();
				for (long factor : primes) {

					double n = Math.sqrt(((p.getNumber() - factor) / 2));
					//System.out.println(n);
					if (n%1 == 0) {
						// add found values to list
						x.add(n);
					}
				}

				// if our list is empty, we found a value that Goldbach's
				// conjecture fails at.
				boolean y = x.isEmpty();
				if (y) {
					System.out.println(c.getNumber());
					// break out once we find the first result
					break;
				}
			}

		}

	}

}

This class contains a method that checks if a number is composite. It didn’t need to be a class object, but I’m looking for future flexibility.

import java.util.ArrayList;

/*
 * A composite number is a positive integer that has at least one positive
 * divisor other than one or itself. In other words a composite number is
 * any positive integer greater than one that is not a prime number.
 */

public class Composite {

	private long number;

	public void setNumber(long number) {
		this.number = number;
	}

	public long getNumber() {
		return number;
	}

	public boolean isComposite() {

		// composite numbers must be positive and greater than one
		if (number <= 1) {
			return false;
		}

		// check if number can be factorized
		// if true, number is composite and not prime
		Prime p = new Prime(number);
		ArrayList<Long> factors = new ArrayList<Long>();
		factors = p.getPrimeFactors();

		if (factors.isEmpty()) {
			return false;
		}

		return true;
	}

}

And this contains some Prime related stuff I’ve used before. There may be some unused stuff in here for this particular problem. I didn’t look too closely.

import java.util.ArrayList;

public class Prime {

	private long number;

	public Prime() { }

	public Prime(long number) {
		this.number = number;
	}

	// set number
	public void setNumber(long number) {
		this.number = number;
	}

	// get number
	public long getNumber() {
		return number;
	}

	/***
	 * Prime Factorization of positive long int greater than 1.
	 * Ex: The Prime Factorization of 8 returns [2, 2, 2]. (2 * 2 * 2 = 8 )
	 * @return  ArrayList<Long>
	 */
	public ArrayList<Long> getPrimeFactors() {
		long num = number;
		ArrayList<Long> prime_factors = new ArrayList<Long>();

		// define a maximum search range, result is truncated
		long maximum = (num / 2);

		if (checkIfPrime(num)) { return prime_factors; }

		for (long i = 2; i <= maximum; ++i) {
			if (num%i == 0) {
				prime_factors.add(i);

				// reduce the range the loop searches based on the prime factor that is found
				num = num / i;
				i = 1;
				maximum = num / 2;
			}
		}

		prime_factors.add(num);

		return prime_factors;
	}

	private boolean checkIfPrime(Long num) {

		if (num == 1) { return false; }

		for (long i = 2; i <= Math.sqrt(num); i++) {
			if (num % i == 0) {
				return false;
			}
		}

		return true;
	}

	public ArrayList<Long> getPrimes() {
		ArrayList<Long> primes = new ArrayList<Long>();

		// define a maximum search range, result is truncated
		for (long i = 2; i < number; i++) {

			if (checkIfPrime(i)) {
				primes.add(i);
			}

		}

		return primes;
	}

}
Posted in Java, Project Euler | Leave a comment

Projecteuler.net – Problem 44 – Java

http://projecteuler.net/problem=44

I populated a Set with a range of Pentagonal numbers that I thought might contain the result. Then I check if the Sums and Differences are already in the Set. This method is not optimum as it will end up checking pairs twice due to how I iterated through the Set.

Josh

import java.util.HashSet;
import java.util.Set;

public class Euler44 {

	public static void main(String[] args) {

		boolean eD;		// .contains result for Set
		boolean eS;		// .contains result for Set

		// build and Set of Pentagonal numbers
		Set<Long> p = new HashSet<Long>();

		for (int i = 1; i < 5000; i++) {
			Long x = new Long((i * ((3 * i) - 1) / 2));
			p.add(x);
		}

		for (Long element1 : p) {
			for (Long element2 : p) {

				Long elementSum = new Long(element1 + element2);
				Long elementDifference = new Long(Math.abs(element2 - element1));

				eD = p.contains(elementDifference);
				eS = p.contains(elementSum);

				if (eD && eS) {
					System.out.println(elementDifference);

				}
			}
		}	

	}

}
Posted in Java, Project Euler | Leave a comment