PCT_Concordia

BiPrimes.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.stream.Collectors;

public class BiPrimes {
	public boolean[] primes;

	public void findPrimes(int upperBound) {
		// Memoization
		if (this.primes == null) {
			this.primes = new boolean[upperBound + 1];
			Arrays.fill(primes, true);
		} else if (this.primes.length < upperBound) {
			int oldUpperBound = this.primes.length;
			this.primes = Arrays.copyOf(this.primes, upperBound + 1);
			Arrays.fill(primes, oldUpperBound, upperBound + 1, true);
		}
		// Sieve of Eratosthenes
		for (int i = 2; i * i <= upperBound; i++) {
			if (this.primes[i]) {
				for (int j = i; i * j <= upperBound; j++) {
					// Mark all multiples as non prime
					this.primes[i * j] = false;
				}
			}
		}
	}

	public int countBiPrimes(int lowerBound, int upperBound) {
		Set<Integer> biPrimes = new HashSet<Integer>();
		for (int i = 2; i * i <= upperBound; i++) {
			if (this.primes[i])
				for (int j = 2; j <= upperBound / 2; j++)
					if (this.primes[j]) {
						int value = i * j;
						if (value <= upperBound && value >= lowerBound)
							biPrimes.add(value);
					}
		}
		return biPrimes.size();
	}

	public void printPrimes() {
		for (int i = 2; i < this.primes.length; i++)
			if (primes[i])
				System.out.print(i + " ");
	}

	public static <T> void printArrayList(ArrayList<T> list) {
		System.out.println(
				list.stream().map(Object::toString).collect(Collectors.joining(" ")));
	}

	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);
		int n = Integer.parseInt(keyboard.nextLine());
		ArrayList<Integer> output = new ArrayList<Integer>();
		BiPrimes biPrimes = new BiPrimes();
		for (int i = 0; i < n; i++) {
			int lowerBound = Integer.parseInt(keyboard.nextLine());
			int upperBound = Integer.parseInt(keyboard.nextLine());
			biPrimes.findPrimes(upperBound);
			output.add(biPrimes.countBiPrimes(lowerBound, upperBound));
		}
		keyboard.close();
		printArrayList(output);
	}

}

BracketMatching.java

import java.util.Scanner;
import java.util.Stack;

public class BracketMatching {

	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);
		int n = Integer.parseInt(keyboard.nextLine());
		boolean[] results = new boolean[n];
		for (int i = 0; i < n; i++) {
			String expression = keyboard.nextLine().trim();
			Stack<Character> bracketStack = new Stack<Character>();
			for (char value : expression.toCharArray()) {
				switch (value) {
					case '[':
					case '{':
					case '(':
						bracketStack.push(value);
						break;
					case ')':
						if (bracketStack.peek() == '(')
							bracketStack.pop();
						break;
					case '}':
						if (bracketStack.peek() == '{')
							bracketStack.pop();
						break;
					case ']':
						if (bracketStack.peek() == '[')
							bracketStack.pop();
						break;
				}
			}
			if (bracketStack.isEmpty())
				results[i] = true;
		}
		keyboard.close();
		for (boolean result : results)
			System.out.println(result ? "TRUE" : "FALSE");

	}
}

FamilyTreeRelationship.java

import java.util.Scanner;

class Tree {
	public Tree left;
	public Tree right;
	public String value;

	public Tree(String value) {
		this.value = value;
		this.left = null;
		this.right = null;
	}

	public static String preOrderTraversal(Tree node) {
		if (node == null)
			return "";
		return node.value + " " + preOrderTraversal(node.left)
				+ preOrderTraversal(node.right);
	}

	public static Tree findNode(Tree root, String node) {
		Tree result = null;
		if (root == null)
			return null;
		if (root.value.equals(node))
			return root;
		if (root.left != null)
			result = findNode(root.left, node);
		if (result == null)
			result = findNode(root.right, node);
		return result;
	}

	public static void insertTreeNode(Tree root, String parent, String child) {
		Tree parentNode = findNode(root, parent);
		if (parentNode != null) {
			Tree childNode = new Tree(child);
			if (parentNode.left == null)
				parentNode.left = childNode;
			else if (parentNode.right == null)
				parentNode.right = childNode;
		}
	}

	public static char checkChildRelation(Tree root, String child,
			String parent) {
		Tree parentNode = findNode(root, parent);
		if (parentNode.left != null && parentNode.left.value.equals(child))
			return 'T';
		else if (parentNode.right != null && parentNode.right.value.equals(child))
			return 'T';
		else
			return 'F';
	}

	public static char checkDescendantRelation(Tree root, String person1,
			String person2) {
		Tree ancestorNode = findNode(root, person2);
		String traversedTreeResult = preOrderTraversal(ancestorNode).trim();
		if (traversedTreeResult.contains(person1))
			return 'T';
		else
			return 'F';
	}

	public static char checkSiblingRelation(Tree root, String person1,
			String person2) {
		char result = 'F';
		if (root == null)
			return 'F';
		if (root.left != null && root.right != null) {
			if ((root.left.value.equals(person1)
					&& root.right.value.contentEquals(person2))
					|| (root.right.value.equals(person1)
							&& root.left.value.contentEquals(person2)))
				return 'T';
		}
		if (root.left != null)
			result = checkSiblingRelation(root.left, person1, person2);
		if (result == 'F' && root.right != null)
			result = checkSiblingRelation(root.right, person1, person2);
		return result;
	}

	public static char checkRelation(Tree root, String person1, String relation,
			String person2) {
		switch (relation) {
			case "child":
				return checkChildRelation(root, person1, person2);
			case "parent":
				return checkChildRelation(root, person2, person1);
			case "sibling":
				return checkSiblingRelation(root, person1, person2);
			case "ancestor":
				return checkDescendantRelation(root, person2, person1);
			case "descendant":
				return checkDescendantRelation(root, person1, person2);

		}
		return 'F';
	}
}

public class FamilyTreeRelationship extends TranscriptNamePrinting {
	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);
		int n = keyboard.nextInt();
		Tree root = null;
		keyboard.nextLine();
		for (int i = 0; i < n; i++) {
			String parent = keyboard.next();
			String child = keyboard.next();
			keyboard.nextLine();
			if (i == 0) {
				root = new Tree(parent);
			}
			Tree.insertTreeNode(root, parent, child);
		}
		n = keyboard.nextInt();
		keyboard.hasNextLine();
		String relationResult = "";
		for (int i = 0; i < n; i++) {
			String person1 = keyboard.next();
			String relation = keyboard.next();
			String person2 = keyboard.next();
			keyboard.nextLine();
			relationResult += " "
					+ Tree.checkRelation(root, person1, relation, person2);
		}
		keyboard.close();
		System.out.println(relationResult.trim());
		System.out.println(Tree.preOrderTraversal(root).trim());
	}
}

GameOfLife.java

import java.util.Scanner;

public class GameOfLife {
	public boolean state[][];
	public int rows, columns;
	public int generations;
	public final int BOUNDARY = 2;

	public GameOfLife() {
		Scanner keyboard = new Scanner(System.in);
		String[] splitInput = keyboard.nextLine().split("\\W+");
		this.rows = Integer.parseInt(splitInput[0]);
		this.columns = Integer.parseInt(splitInput[1]);
		this.state = new boolean[rows + BOUNDARY][columns + BOUNDARY];
		for (int i = 1; i < this.rows + 1; i++) {
			String[] cells = keyboard.nextLine().split("");
			int j = 1;
			for (String cell : cells)
				this.state[i][j++] = cell.equals("@");
		}
		this.generations = Integer.parseInt(keyboard.nextLine());
		keyboard.close();

	}

	public int getNumberOfNeighbours(int row, int column) {
		int count = 0;
		// Count living cells in all directions from the current cell
		if (this.state[row - 1][column - 1])
			count++;
		if (this.state[row - 1][column])
			count++;
		if (this.state[row - 1][column + 1])
			count++;
		if (this.state[row][column - 1])
			count++;
		if (this.state[row][column + 1])
			count++;
		if (this.state[row + 1][column - 1])
			count++;
		if (this.state[row + 1][column])
			count++;
		if (this.state[row + 1][column + 1])
			count++;
		return count;
	}

	public boolean[][] cloneState() {
		boolean[][] duplicateState = new boolean[rows + BOUNDARY][columns
				+ BOUNDARY];
		for (int i = 0; i < this.rows + BOUNDARY; i++) {
			duplicateState[i] = this.state[i].clone();
		}
		return duplicateState;
	}

	public void simulateGeneration() {
		// Cloning state prevents modification till all cells are simulated
		boolean[][] duplicateState = this.cloneState();
		for (int i = 1; i < this.rows + 1; i++)
			for (int j = 1; j < this.columns + 1; j++) {
				int neighbours = getNumberOfNeighbours(i, j);
				if (this.state[i][j]) {
					// Death
					if (neighbours < 2 || neighbours > 3)
						duplicateState[i][j] = false;
				} else {
					// Birth
					if (neighbours == 3)
						duplicateState[i][j] = true;
				}
			}
		this.state = duplicateState;
	}

	public int countLivingCells() {
		int count = 0;
		for (int i = 1; i < this.rows + 1; i++)
			for (int j = 1; j < this.columns + 1; j++)
				if (this.state[i][j])
					count++;
		return count;
	}

	public static void main(String[] args) {
		GameOfLife gof = new GameOfLife();
		for (int i = 0; i < gof.generations; i++)
			gof.simulateGeneration();
		System.out.println(gof.countLivingCells());
	}

}

Hashing.java

import java.util.Arrays;
import java.util.Scanner;
import java.util.*;

public class Hashing {
	int size;
	Hashtable<Integer, Integer> hashtable;
	public Hashing(int size) {
		this.size = size;
		this.hashtable = new Hashtable<Integer, Integer>(size);
	}

	public int calculateHash(int i) {
		// Negative roll-over
		if (i < 0)
			i = i + this.size;
		int j = i % this.size;
		System.out.print(j + " ");
		return j;
	}

	public void addHashValue(int i) {
		int value = i;
		int j = this.calculateHash(value);
		boolean direction = false;
		while (this.hashtable.containsKey(j)) {
			int digitRemoved = value % 10;
			value /= 10;
			if (value == 0) {
				for (int index = 0; i < this.size; index++) {
					int offset = direction ? index : -index;
					int key = this.calculateHash(j + offset);
					if (!this.hashtable.containsKey(key)) {
						j = key;
						break;
					}
				}
			} else {
				int offset = value % this.size;
				boolean isEven = (digitRemoved % 2 == 0);
				offset = isEven ? -offset : offset;
				j = this.calculateHash(j + offset);
				direction = !isEven;
			}
		}
		this.hashtable.put(j, i);
		System.out.println();
	}

	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);
		int size = Integer.parseInt(keyboard.nextLine());
		Hashing hashing = new Hashing(size);
		int[] values = Arrays.stream(keyboard.nextLine().split("\\s+|-1"))
				.mapToInt(Integer::parseInt).toArray();
		for (int value : values) {
			hashing.addHashValue(value);
		}
		keyboard.close();
	}

}

HorizontalVerticalIntersections.java

import java.util.Scanner;

public class HorizontalVerticalIntersections {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner keyboard = new Scanner(System.in);
		String[] splitInput = keyboard.nextLine().split("\\W+");
		int v = Integer.parseInt(splitInput[0]);
		int h = Integer.parseInt(splitInput[1]);
		// X Y1 Y2
		int[][] verticalLines= new int[v][3];
		// Y X1 X2
		int[][] horizontalLines= new int[h][3];
		
		for(int i = 0; i < v; i++) {
			splitInput = keyboard.nextLine().split("\\W+");
			verticalLines[i][0] = Integer.parseInt(splitInput[0]);
			verticalLines[i][1] = Integer.parseInt(splitInput[1]);
			verticalLines[i][2] = Integer.parseInt(splitInput[2]);
		}
		for(int i = 0; i < h; i++) {
			splitInput = keyboard.nextLine().split("\\W+");
			horizontalLines[i][0] = Integer.parseInt(splitInput[0]);
			horizontalLines[i][1] = Integer.parseInt(splitInput[1]);
			horizontalLines[i][2] = Integer.parseInt(splitInput[2]);
		}
		int count = 0;
		for(int i = 0; i < v; i++) {
			int minYV = Math.min(verticalLines[i][1],verticalLines[i][2]);
			int maxYV = Math.max(verticalLines[i][1],verticalLines[i][2]);
			int x = verticalLines[i][0];
			for(int j = 0; j < h; j++) {
				int minXH = Math.min(horizontalLines[j][1],horizontalLines[j][2]);
				int maxXH = Math.max(horizontalLines[j][1],horizontalLines[j][2]);
				int y = horizontalLines[j][0];
				if((x >= minXH && x <= maxXH) && (y >= minYV && x <= maxYV))
					count++;
			}
		}
		System.out.println(count);
	}

}

SnakesAndLadder.java

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class SnakesAndLadder {

	public Map<Integer, Integer> snakesAndLadders;
	public int[] plays;

	public SnakesAndLadder() {
		Scanner keyboard = new Scanner(System.in);
		int numberOfSnakesAndLadders = Integer.parseInt(keyboard.nextLine().trim());
		this.snakesAndLadders = new HashMap<Integer, Integer>();
		for (int i = 0; i < numberOfSnakesAndLadders; i++) {
			String[] rawInput = keyboard.nextLine().split(" ");
			int input1 = Integer.parseInt(rawInput[0]);
			int input2 = Integer.parseInt(rawInput[1]);
			this.snakesAndLadders.put(input1, input2);

		}
		int numberOfPlays = Integer.parseInt(keyboard.nextLine());
		this.plays = Arrays.stream(keyboard.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
	}

	public int finalPosition(int play) {
		if (!this.snakesAndLadders.containsKey(play))
			return play;
		return finalPosition(this.snakesAndLadders.get(play));
	}

	public static void main(String[] args) {

		SnakesAndLadder sal = new SnakesAndLadder();
		int positionOfA = 1, positionOfB = 1;
		for (int j = 0; j < sal.plays.length; j++) {
			if (j % 2 == 0) {
				if (positionOfA + sal.plays[j] <= 100)
					positionOfA += sal.plays[j];

				if (positionOfA == 100) {
					System.out.println("A " + positionOfA);
					return;
				}
				positionOfA = sal.finalPosition(positionOfA);

			} else {
				if(positionOfB + sal.plays[j] < 100)
				positionOfB += sal.plays[j];
				if (positionOfB >= 100) {
					System.out.println("B " + positionOfB);
					return;
				}
				positionOfB = sal.finalPosition(positionOfB);
			}
		}
		if (positionOfA > positionOfB)
			System.out.println("A " + positionOfA);
		else
			System.out.println("B " + positionOfB);
	}

}

TranscriptNamePrinting.java

import java.util.Scanner;

public class TranscriptNamePrinting {

	public static boolean lastLetterContainsVowel(String word) {
		char lastCharacter = word.charAt(word.length() - 1);
		switch (Character.toLowerCase(lastCharacter)) {
			case 'a':
			case 'e':
			case 'i':
			case 'o':
			case 'u':
				return true;
			default:
				return false;
		}
	}

	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);
		String studentName = keyboard.nextLine();
		keyboard.close();
		String[] nameList = studentName.split(" ");
		switch (nameList.length) {
			case 1:
				System.out.println(nameList[0]);
				break;
			case 2:
				if (lastLetterContainsVowel(nameList[1])) {
					System.out.println(String.join(" ", nameList[1], nameList[0]));
				} else {
					System.out.println(String.join(" ", nameList));
				}
				break;
			case 3:
				System.out
						.println(String.join(" ", nameList[2], nameList[0], nameList[1]));
				break;
		}

	}

}

UniqueWordCount.java

import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class UniqueWordCount {
	public static void main(String[] args) {
		Scanner keyboard = new Scanner(System.in);
		String[] words = keyboard.nextLine().toLowerCase().split("\\W+");
		keyboard.close();
		Set<String> uniqueWords = new HashSet<String>(Arrays.asList(words));
		System.out.println(uniqueWords.size());
	}
}