import java.util.Arrays;
 
public class QuickSortMain {
 
    private static int array[];
 
    public static void sort(int[] arr) {
 
        if (arr == null || arr.length == 0) {
            return;
        }
        array = arr;
        quickSort(0, array.length-1);
    }
 
    private static void quickSort(int left, int right) {
 
        int i = left;
        int j = right;
        // find pivot number, we will take it as mid
        int pivot = array[left+(right-left)/2];
 
        while (i <= j) {
            /**
             * In each iteration, we will increment left until we find element greater than pivot
             * We will decrement right until we find element less than pivot
             */
            while (array[i] < pivot) { i++; } while (array[j] > pivot) {
                j--;
            }
            if (i <= j) {
                exchange(i, j);
                //move index to next position on both sides
                i++;
                j--;
            }
        }
        // call quickSort() method recursively
        if (left < j)
            quickSort(left, j);
        if (i < right)
            quickSort(i, right);
    }
 
    private static void exchange(int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
 
    public static void main(String a[]){
        int[] input = {33,21,45,64,55,34,11,8,3,5,1};
        System.out.println("Before Sorting : ");
        System.out.println(Arrays.toString(input));
        sort(input);
        System.out.println("==================");
        System.out.println("After Sorting : ");
        System.out.println(Arrays.toString(array));
 
    }
}

import static java.lang.System.*;
import java.util.Arrays;        

public class MergeSort{

private static int passCount;

public static void mergeSort(int[] list)
{
    passCount=0;
    mergeSort(list, 0, list.length);
}

private static void mergeSort(int[] list, int front, int back)  //O( Log N )
{
    int mid = (front+back)/2;
    if(mid==front) return;
    mergeSort(list, front, mid);
    mergeSort(list, mid, back);
    merge(list, front, back);

}

private static void merge(int[] list, int front, int back)  //O(N)
{
   int dif = back-front;
   int[] temp = new int[dif];
   int beg = front, mid = (front+back)/2;
   int saveMid = mid;
   int spot = 0;

   while(beg < saveMid && mid < back) {
      if(list[beg] < list[mid]) {
         temp[spot++] = list[beg++];
      } else {
         temp[spot++] = list[mid++];
      }
   }
   while(beg < saveMid)
      temp[spot++] = list[beg++];
   while(mid < back)
      temp[spot++] = list[mid++];
   for(int i = 0; i < back-front; i++) {
      list[front+i] = temp[i];
   }
    System.out.println("pass " + passCount++ + " " + Arrays.toString(list) + "\n");
  }
  
  
    public static void main(String args[])
    {
        mergeSort(new Comparable[]{ 9, 5, 3, 2 });
        System.out.println("\n");
        
        mergeSort(new Comparable[]{ 19, 52, 3, 2, 7, 21 });
        System.out.println("\n");
        
        mergeSort(new Comparable[]{ 68, 66, 11, 2, 42, 31});
        System.out.println("\n");
    }
  
 }

import java.util.Scanner;

/* In Heaven, the seed is tall and the oak small / It's input vital 
	* "The al-Madinatian," verse 236-37 
	* tinyurl.com/17snqkfv
	* email answer to [email protected]
	**/

public class Main
{
	public static void main(String args[])
	{
		int x = 0;
		int a, c, m = 10000;
		
		Scanner in = new Scanner(System.in);
		
		System.out.println("Please enter a seed, maximum 3000000:");
		x = in.nextInt();
		
		System.out.println("Please input a number, maximum 29:");
		a = in.nextInt();
		
		System.out.println("Please input a number, maximum 999999:");
		c = in.nextInt();
		
		char menu = 'y';
		while(menu != 'n')
		{
			x = (a*x + c) % m;
			
			System.out.println("The next number is " + x + "\nWould you like another? (y/n)");
			menu = in.next().charAt(0);
		}
	}
}

//██╗  ░█████╗░███╗░░░███╗  ██████╗░░█████╗░███████╗██████╗░░█████╗░██╗░░░░░██╗░░░██╗░██████╗
//██║  ██╔══██╗████╗░████║  ██╔══██╗██╔══██╗██╔════╝██╔══██╗██╔══██╗██║░░░░░██║░░░██║██╔════╝
//██║  ███████║██╔████╔██║  ██║░░██║███████║█████╗░░██║░░██║███████║██║░░░░░██║░░░██║╚█████╗░
//██║  ██╔══██║██║╚██╔╝██║  ██║░░██║██╔══██║██╔══╝░░██║░░██║██╔══██║██║░░░░░██║░░░██║░╚═══██╗
//██║  ██║░░██║██║░╚═╝░██║  ██████╔╝██║░░██║███████╗██████╔╝██║░░██║███████╗╚██████╔╝██████╔╝
//╚═╝  ╚═╝░░╚═╝╚═╝░░░░░╚═╝  ╚═════╝░╚═╝░░╚═╝╚══════╝╚═════╝░╚═╝░░╚═╝╚══════╝░╚═════╝░╚═════╝░

import java.util.ArrayList;
import java.util.Iterator;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		char[] variables = setVariables(in);
		int[] minTerms = setMinTerms(in);
		String[] binaryMinTerms = decimalToBinary(variables, minTerms);
		
		ArrayList<Group> groups = computeSuccessiveGroups(minTerms, binaryMinTerms);
		
		displayInput(variables, minTerms);
		printPIs(groups, variables);
	}
	
	private static char[] setVariables(Scanner in) {
		System.out.print("Enter the number of variables: ");
		int numVariables = in.nextInt();
		char[] variables = new char[numVariables];
		
		System.out.print("Enter each variable separated by spaces: ");
		for(int i = 0; i < numVariables; i++) {
			variables[i] = in.next().charAt(0);
		}
		return variables;
	}
	
	private static int[] setMinTerms(Scanner in) {
		System.out.print("Enter the number of min terms: ");
		int numMinTerms = in.nextInt();
		int[] minTerms = new int[numMinTerms];
		
		System.out.print("Enter each min term separated by spaces: ");
		for(int i = 0; i < numMinTerms; i++) {
			minTerms[i] = in.nextInt();
		}
		return minTerms;
	}
	
	private static String[] decimalToBinary(char[] variables, int[] minTerms) {
		String[] binaryMinTerms = new String[minTerms.length];
		for(int i = 0; i < minTerms.length; i++) {
			binaryMinTerms[i] = Integer.toBinaryString(minTerms[i]);
			if(binaryMinTerms[i].length() < variables.length) {
				String zeros = "";
				int len = binaryMinTerms[i].length();
				while(len < variables.length) {
					zeros = zeros.concat("0");
					len++;
				}
				binaryMinTerms[i] = zeros + binaryMinTerms[i];
			}
		}
		return binaryMinTerms;
	}
	
	private static void displayInput(char[] variables, int[] minTerms) {
		System.out.print("Function: f(");
		for(int i = 0; i < variables.length; i++) {
			if(i == variables.length-1)
				System.out.print(variables[i]);
			else
				System.out.print(variables[i] + ", ");
		}
		System.out.print(") = SIGMAm(");
		for(int i = 0; i < minTerms.length; i++) {
			if(i == minTerms.length-1)
				System.out.print(minTerms[i]);
			else
				System.out.print(minTerms[i] + ", ");
		}
		System.out.println(")");
	}
	
	private static ArrayList<Group> computeSuccessiveGroups(int[] minTerms, String[] binaryMinTerms) {
		ArrayList<Group> groups = new ArrayList<Group>();
		for(int i = 0; i < minTerms.length; i++)
			groups.add(new Group(Integer.toString(minTerms[i]), binaryMinTerms[i]));
		
		int sizeBeforeRemoval = 0, currentSize;
		while(sizeBeforeRemoval != groups.size()) {
			currentSize = groups.size();
			for(int i = 0; i < currentSize; i++) {
				for(int j = i+1; j < currentSize; j++) {
					if(differences(groups.get(i).binary, groups.get(j).binary) == 1) {
						String combinedBin = combineBinary(groups.get(i).binary, groups.get(j).binary);
						
						groups.get(i).grouped = true;
						groups.get(j).grouped = true;
						
						if(isUniqueBin(groups, combinedBin)) {
							String newTuple = groups.get(i).decimal + "," + groups.get(j).decimal;
							groups.add(new Group(newTuple, combinedBin));
						}
						else break;
					}
				}
			}
			
			sizeBeforeRemoval = groups.size();
			
			Iterator<Group> iter = groups.iterator();
			while(iter.hasNext()) {
				Group next = iter.next();
				if(next.grouped)
					iter.remove();
			}
		}
		return groups;
	}
	
	private static int differences(String a, String b) {
		int diff = 0;
		
		for(int i = 0; i < a.length(); i++)
			if(a.charAt(i) != b.charAt(i))
				diff++;
		
		return diff;
	}
	
	private static String combineBinary(String a, String b) {
		String combined = "";
		for(int i = 0; i < a.length(); i++) {
			if(a.charAt(i) != b.charAt(i))
				combined = combined.concat("-");
			else
				combined = combined.concat(Character.toString(a.charAt(i)));
		}
		return combined;
	}
	
	private static boolean isUniqueBin(ArrayList<Group> groups, String s) {
		for(int i = 0; i < groups.size(); i++)
			if(groups.get(i).binary.equals(s))
				return false;
		
		return true;
	}
	
	private static void printPIs(ArrayList<Group> groups, char[] variables) {
		System.out.println("Prime Implicants: ");
		for(int i = 0; i < groups.size(); i++)
			System.out.println(groups.get(i).decimal + " | " + binaryToMinTerm(variables, groups.get(i).binary));
	}
	
	private static String binaryToMinTerm(char[] variables, String s) {
		String minTerm = "";
		
		for(int i = 0; i < s.length(); i++) {
			if(s.charAt(i) != '-') {
				if(s.charAt(i) == '0')
					minTerm = minTerm.concat(Character.toString(variables[i]) + "'");
				else
					minTerm = minTerm.concat(Character.toString(variables[i]));
			}
		}
		
		return minTerm;
	}
}

import javax.mail.*;
import javax.mail.internet.*;
import java.util.*;
 
public void postMail( String recipients[ ], String subject, String message , String from) throws MessagingException
{
    boolean debug = false;
 
     //Set the host smtp address
     Properties props = new Properties();
     props.put("mail.smtp.host", "smtp.example.com");
 
    // create some properties and get the default Session
    Session session = Session.getDefaultInstance(props, null);
    session.setDebug(debug);
 
    // create a message
    Message msg = new MimeMessage(session);
 
    // set the from and to address
    InternetAddress addressFrom = new InternetAddress(from);
    msg.setFrom(addressFrom);
 
    InternetAddress[] addressTo = new InternetAddress[recipients.length]; 
    for (int i = 0; i < recipients.length; i++)
    {
        addressTo[i] = new InternetAddress(recipients[i]);
    }
    msg.setRecipients(Message.RecipientType.TO, addressTo);
    
 
    // Optional : You can also set your custom headers in the Email if you Want
    msg.addHeader("MyHeaderName", "myHeaderValue");
 
    // Setting the Subject and Content Type
    msg.setSubject(subject);
    msg.setContent(message, "text/plain");
    Transport.send(msg);
}

//Leif Messinger
//Solves wordle
//Needs a list of wordle words, newline separated and 5 characters each

import java.util.*;
import java.io.File;
import java.io.FileNotFoundException;

class WordleSolver {

	public static void printPointer(int position){
		for(int i = 0; i < position; ++i){
			System.out.print(" ");
		}
		System.out.print("^");
	}

	public static void main(String[] args) throws FileNotFoundException{
		if(args.length < 1) return;
		File dictionary = new File(args[0]);
		Scanner sc = new Scanner(dictionary);
		ArrayList<String> possibleWords = new ArrayList<String>();
		while(sc.hasNextLine()){
			possibleWords.add(sc.nextLine());
		}

		Scanner input = new Scanner(System.in);

		while(possibleWords.size() > 0){
			//Choose a word out of the possible words
			final int randomIndex = (int)(Math.random() * possibleWords.size());
			String chosenWord = possibleWords.get(randomIndex);
			possibleWords.remove(randomIndex);

			System.out.println("Is it correct?");
			for(int i = 0; i < chosenWord.length(); ++i){
				System.out.println(chosenWord);
				printPointer(i);
				System.out.println(" y/n?");
				if(input.nextLine().toLowerCase().contains("y")){
					//Filter by correct character
					for(int possibleWord = possibleWords.size() - 1; possibleWord >= 0; --possibleWord){ //Has to be backwards for removing entries, also has to be int not unsigned
						if(possibleWords.get(possibleWord).charAt(i) != chosenWord.charAt(i)){
							possibleWords.remove(possibleWord);
						}
					}
				}
			}
			System.out.println("Is it misplaced?");
			//Stores a count of every letter misplaced
			short[] misplacedCounts = new short[('z'-'a')+1]; //Praise be the garbage collector
			for(int i = 0; i < chosenWord.length(); ++i){
				System.out.println(chosenWord);
				printPointer(i);
				System.out.println(" y/n?");
				if(input.nextLine().toLowerCase().contains("y")){
					//Filter to make sure there's at least as many letters as needed
					++misplacedCounts[(chosenWord.charAt(i) - 'a') - 1];
					for(int possibleWord = possibleWords.size() - 1; possibleWord >= 0; --possibleWord){	//Has to be backwards for removing entries, also has to be int not unsigned
						int count = 0;
						for(int j = 0; j < possibleWords.get(possibleWord).length(); ++j){
							if(possibleWords.get(possibleWord).charAt(j) == chosenWord.charAt(i))
								++count;
						}
						//If there's not enough of the character that we need, then we remove that from the list of possible characters
						if(count < misplacedCounts[(chosenWord.charAt(i) - 'a') - 1]){
							possibleWords.remove(possibleWord);
						}
					}
					//Also filter out words where that letter doesn't belong there
					for(int possibleWord = possibleWords.size() - 1; possibleWord >= 0; --possibleWord){ //Has to be backwards for removing entries, also has to be int not unsigned
						if(possibleWords.get(possibleWord).charAt(i) == chosenWord.charAt(i)){
							possibleWords.remove(possibleWord);
							continue;	//Breaks the current word and moves on in the loop
						}
					}
				}
			}
		}
	}
}