An old algorithms assignment. On a single line there is a start and end point, as well as a collection of coins. This algorithm returns the minimum amount of time it takes to collect every coin and get to the goal. Additionally, coin increase move speed.

Assignment5.java

import java.util.ArrayList;
import java.util.Collections;

public class Assignment5 {
	// Establish useful global variables
	private static int gEnd;
	private static int gBegin;

	// helper distance function
	public static double distance(double posA, double posB, int movespeed) {
		return (Math.abs((posB - posA))) / (Math.pow(2, movespeed));
	}

	public static double minTime(int position, double count, ArrayList<Integer> coin, int movespeed, int lastPosition) {
		// copy array to make sure information isn't lost between recursive
		// calls
		ArrayList<Integer> copyCoin = new ArrayList<Integer>();
		for (int coins : coin)
			copyCoin.add(coins);
		if (copyCoin.get(position) == gEnd) {
			// base case: iterator is now at destination, simply return distance
			// from last point and bubble out
			return count += distance(gEnd, lastPosition, movespeed);
		}
		// Begin recursive calls
		if (position == 0 || position == copyCoin.size() - 1) {
			// check to see if it's an easy case where all of the coins lay
			// between the position and the destination
			// if they do, simply move to the next coin and increase move speed
			count += distance(copyCoin.get(position), lastPosition, movespeed);
			lastPosition = copyCoin.get(position);
			copyCoin.remove(position);
			if (position == 0) {
				// Destination is larger than position, move forward
				return minTime(0, count, copyCoin, movespeed + 1, lastPosition);
			}
			if (position == copyCoin.size() - 1) {
				// Destination is smaller than position, move backwards
				return minTime(copyCoin.size() - 1, count, copyCoin, movespeed + 1, lastPosition);
			}
		} else {
			// coins lay on either side, recursively check every possibility.
			// hardest case, so it comes last.
			count += distance(copyCoin.get(position), lastPosition, movespeed);
			lastPosition = copyCoin.get(position);
			copyCoin.remove(position);
			// take min of going forward and backward, recursively checks all
			// possible coin paths to the end
			return count = Math.min(minTime(position, count, copyCoin, movespeed + 1, lastPosition),
					minTime(position - 1, count, copyCoin, movespeed + 1, lastPosition));
		}
		return count;
	}

	public static double minTime(int begin, int end, int[] coin) {
		gEnd = end;
		gBegin = begin;
		// create arraylist because they're better to work with
		ArrayList<Integer> coinAL = new ArrayList<Integer>();
		coinAL.add(begin);
		coinAL.add(end);
		for (int coins : coin) {
			// trim any coins that are beyond the destination
			// no reason to go past the destination to get a coin and come back
			if (end > begin) {
				if (coins <= end)
					coinAL.add(coins);
			} else if (end < begin) {
				if (coins >= end)
					coinAL.add(coins);
			}
		}
		Collections.sort(coinAL);
		// sort, to abuse properties of sorted arraylist to save time checking
		/*
		 * print out picture, do not use for big numbers breaks java to print
		 * large numbers of dashes if (coinAL.size() > 0) { for (int i =
		 * Math.min(begin, Math.min(end, coinAL.get(0))); i<=Math.max(begin,
		 * Math.max(end, coinAL.get(coinAL.size()-1))); i++) { if (i == begin)
		 * System.out.print("B"); else if (i == end) System.out.print("X"); else
		 * if (coinAL.contains(i)) System.out.print("C"); else
		 * System.out.print("-"); } System.out.println(); } else
		 * System.out.println(
		 * "Something went wrong adding coins to the arraylist");
		 */
		// begin recursion into overloaded helper
		return minTime(coinAL.indexOf(begin), 0, coinAL, -1, begin);

	}

	public static void main(String[] args) {
		int[] coin = { 67776200, 13912236, 290708170, 261540879, 128268444, 34206289, 526149, 212040, 9508104, 394009,
				195531400, 42742140, 111770529, 49442970, 175690938, 72678600, 19665600, 15380382, 87155797, 4107808,
				1178212, 153317080, 122302593, 33941835, 54974304, 303407974, 90275616, 38652680, 436798525, 253899507,
				6759164, 28682438, 8846848, 122948536, 328801590, 11022774 };
		System.out.println("answer is " + minTime(52658275, 83738670, coin));

		int[] coin2 = { 13, 4, 5, 6, 8, 10, 16, 21, 27, 35, 45, 58, 157, 202, 260, 334, 74, 95, 122, 429, 551, 708, 910,
				1070, 1404 };
		System.out.println("answer is " + minTime(3, 0, coin2));

		int[] coin3 = { 8, 2, 18 };
		System.out.println("answer is " + minTime(10, 20, coin3));
	}
}