psychicheuristic.java

/**	PA1 - psychicheuristic.java
 * 	@author	Chris Jung, Meelad Dawood
 *  @date	October 9, 2017
 *  Dr. Glick, COMP 480
 */

import java.io.*;
import java.util.*;

/**	Class "TicketComparator"
 * 	Compares the Integer values of Strings, returns the comparison result.
 * 	For use when sorting the final results in lex order.
 * 
 */
class TicketComparator<E> implements Comparator<E>
{
	public int compare(Object a, Object b)
	{
		String aa = (String)a;
		String bb = (String)b;
		String[] aarr = aa.split(" ");
		String[] barr = bb.split(" ");
		for (int i = 0; i < aarr.length; i++)
		{
			int check1 = Integer.parseInt(aarr[i]);
			int check2 = Integer.parseInt(barr[i]);
			//System.out.println("");
			int toReturn = check1 - check2;
			if (toReturn < 0)
				return -1; 
			else if (toReturn > 0)
				return 1;
		}
		return 0;
	}
}

/**	Class "Combination" 
 * 	Holds information about a combination of numbers, generated by the "j" parameter:
 * 	ID for the number generated, HashSet "numbers" for the combination number.
 * 
 * 	Contains information about a "checked" state. If "checked", object has been "covered"
 * 	during heuristic check. Also added "contains" method, which compares the contents of
 * 	two Combination objects and returns the number of matching values. 
 */
class Combination 
{ 
	private static int IDCounter = 0; 
	private int ID; 
	private TreeSet<Integer> numbers = new TreeSet<Integer>();
	private boolean checked = false;
	public Combination ()
	{
		this.ID = IDCounter++;
	}
	public void addNumber (int n) 
	{
		numbers.add(n);
	}
	public int getID () { return this.ID; }
	public TreeSet<Integer> getNumbers()
	{
		return numbers;
	}
	public void setChecked() { this.checked = true; } 
	public boolean isChecked() { return this.checked; }
	public int contains (TreeSet<Integer> b)
	{
		// How many numbers of this instance of Combination does b contain?
		if (b.isEmpty() || this.numbers.isEmpty()) return 0;
		TreeSet<Integer> temporary = new TreeSet<Integer>(numbers);
		int startSize = temporary.size();
		temporary.removeAll(b);
		return (startSize - temporary.size());
	}
}

public class psychicheuristic
{
	static int smallest = Integer.MAX_VALUE;
	static ArrayList<Combination> possibilities = new ArrayList<Combination>(); 
	public static void main (String [] args)
	{
		// Get input from file
		if (args.length != 2)
		{
			System.out.println("Wrong number of arguments.");
			System.exit(1);
		}
		int n = 0, k = 0, j = 0, l = 0;	
		String inputName = args[0], outputName = args[1];
		
		try 
		{
			File inFile = new File(inputName);
			Scanner in = new Scanner(inFile);
			n = in.nextInt(); 
			j = in.nextInt();
			k = in.nextInt(); 
			l = in.nextInt();
			in.close();
		}
		catch (FileNotFoundException d)
		{
			System.out.println("File not found!");
		}
		
		// Sanitize inputs		
		if (n < k || k < j || j < l || n == 0 || k == 0 || j == 0 || l == 0) 
		{
			System.out.println("Bad values for n, j, k, l!");
			System.exit(1); 
		}
			
		// Generate Combinations based on j
		int[] elements = new int[n];
		for (int index = 0; index < n; index++)
			elements[index] = index + 1; 
		int[] givenData = new int[n];
		generateRecursive(elements, givenData, 0, n-1, 0, j);
	
		// Heuristic (Greedy) Search the set of Combination objects for Ticket sets that 
		// cover it all. Return the Tickets (TreeSets) to a LinkedList
		LinkedList<TreeSet<Integer>> results = generateTickets(l, k, n);
		ArrayList<String> resultStrings = new ArrayList<String>(); 
		
		// Collect the results and convert to strings for printing
		for (TreeSet<Integer> d: results)
		{
			LinkedList<Integer> dd = new LinkedList<Integer>(); 
			for (Integer ddd: d)
				dd.add(ddd);
			Collections.sort(dd);
			String entry = dd.toString();
			entry = entry.replaceAll("([\\[,\\]])", "");
			resultStrings.add(entry);
		}	
		resultStrings.sort(new TicketComparator<String>());

		// Print results to output file
		try
		{
			File out = new File (outputName);
			PrintWriter print = new PrintWriter (out);
			print.println(results.size());
			for (String a: resultStrings)
			{
				print.println(a);
			}
			print.close();
		}
		catch (Exception exception) 
		{
			System.out.println("Unable to print to file");	
		}
	}
	
	/**	generateTickets
	 * 	Generates TreeSets of Tickets based on the range of Combinations generated by j. 
	 * 	Follows this procedure:
	 * 	1	Take the first "unchecked" Combination and add to ticket.
	 * 	2	Search all "unchecked" tickets. 
	 * 		If the number requiredToContain matches...
	 * 			(...and the Ticket has space, add the contents of the Combination (up to k values))
	 * 		then "check" off the Combination.
	 * 	3	When a Ticket is full and Combinations are all scanned, add the Ticket to LinkedList.
	 * 	4	Repeat until all Combinations are "checked". 
	 * 
	 * @param requiredToContain		Number of Integers required to contain (j)
	 * @param ticketSize			Size of ticket (k)
	 * @param n						Number of values to check (n)
	 * @return						LinkedList with result tickets (TreeSets)
	 */
	static LinkedList<TreeSet<Integer>> generateTickets (int requiredToContain, int ticketSize, int n)
	{
		LinkedList<TreeSet<Integer>> toReturn = new LinkedList<TreeSet<Integer>>();
		boolean cont = true;
		while (cont)
		{
			// Create new ticket
			TreeSet<Integer> ticket = new TreeSet<Integer>();
			boolean denyEntry = false;
			for (int index = 0; index < possibilities.size(); index++)
			{
				Combination toCheck = possibilities.get(index);
				if (!toCheck.isChecked()) 
				{
					if (ticket.isEmpty()) 
					{
						// If the ticket is empty, get numbers of the first unchecked ticket
						TreeSet<Integer> numb = toCheck.getNumbers();
						Iterator<Integer> it = numb.iterator();
						while (ticket.size() < ticketSize && it.hasNext())
						{
							ticket.add(it.next());
						}
						toCheck.setChecked();
						if (ticket.size() == ticketSize)
							denyEntry = true;
					}
					else if (requiredToContain - (ticketSize - ticket.size()) <= toCheck.contains(ticket)) // Don't ask
					{
						// Ticket matches requiredToContain values or more
						if (!denyEntry) 
						{
							// Ticket is not full, add the Combination's numbers to it
							TreeSet<Integer> numb = toCheck.getNumbers();
							Iterator<Integer> it = numb.iterator();
							while (ticket.size() < ticketSize && it.hasNext())
							{
								ticket.add(it.next());
							}
							if (ticket.size() == ticketSize)
								denyEntry = true;
						}
						// Check off Combination
						toCheck.setChecked();
					}
					
				}
				
			}
			
			// An empty ticket signifies that all Combinations are "checked"
			if (!ticket.isEmpty())
			{
				if (ticket.size() < ticketSize)
				{
					// If the final ticket is not full, add valid values to complete it with k values
					for (int addExtra = 1; addExtra <= n && ticket.size() < ticketSize; addExtra++)
					{
						if (!ticket.contains(addExtra)) ticket.add(addExtra);
					}
				}
				toReturn.add(ticket);
			}
			else cont = false;
		}
		return toReturn;
	}
	
	/**	generateRecursive
	 * 	Recursively generates a set of Ticket objects or Combination objects based on values for input.
	 * 	Stores values in "possibilities" or "everything"
	 * 	@param arr		Placeholder array for integers
	 * 	@param data		Data to cover
	 * 	@param start	Starting point for generation
	 * 	@param end		Ending point for generation
	 * 	@param index	Current index
	 * 	@param r		Number until the end (calculated later)
	 * 	@param ticket	true if generating Ticket objects, false if Combination objects
	 */
	static void generateRecursive(int arr[], int data[], int start, int end, int index, int r)
	{
		if (index == r)
		{
			Combination toAdd = new Combination();
			for (int j=0; j<r; j++)
			{
				toAdd.addNumber(data[j]);
			}
			possibilities.add(toAdd);
	
		}
		for (int i=start; i<=end && end-i+1 >= r-index; i++)
		{
			data[index] = arr[i];
			generateRecursive(arr, data, i+1, end, index+1, r);
		}
	}
}