public
anonymous / Challenge115.java
Created

  • Download Gist
Challenge115.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.InputMismatchException;
import java.util.List;
import java.util.Scanner;
 
/**
* Linear Time Solution
*
* 14 <br>
* 10 -8 2 1 4 -9 6 1 9 -10 -5 2 3 7 <br>
* 7 <br>
*
* @author SplashAttacks
*/
public abstract class Challenge115 {
@SuppressWarnings("serial")
private static class CountingHashMap extends HashMap<Integer, Integer> {
public Integer put(Integer key) {
int count = 1;
if (containsKey(key)) {
count = get(key) + 1;
}
return super.put(key, count);
}
 
/**
* Returns the key.
*
* @param key
* @return
*/
@Override
public Integer remove(Object key) {
Integer intKey = (Integer) key;
Integer count = get(intKey);
if (count == null) {
return null;
} else if (count == 1) {
return super.remove(intKey);
} else {
put(intKey, --count);
return count;
}
}
}
 
private static class Criteria {
private final List<Integer> array;
 
public Criteria(List<Integer> array) {
this.array = array;
}
 
public List<Pair<Integer, Integer>> getPairs(int number) {
return process(number);
}
 
private List<Pair<Integer, Integer>> process(int number) {
CountingHashMap countingMap = new CountingHashMap();
for (Integer element : array) {
countingMap.put(element);
}
List<Pair<Integer, Integer>> result = new ArrayList<Pair<Integer, Integer>>();
for (Integer element1 : array) {
Integer element2 = number - element1;
if (countingMap.remove(element1) != null
&& countingMap.remove(element2) != null) {
result.add(new Pair<Integer, Integer>(element1, element2));
}
}
return result;
}
 
@Override
public String toString() {
return "Criteria [array=" + Arrays.toString(array.toArray()) + "]";
}
}
 
private static class Pair<U, T> {
private final U element1;
private final T element2;
 
public Pair(U element1, T element2) {
this.element1 = element1;
this.element2 = element2;
}
 
public U getElement1() {
return element1;
}
 
public T getElement2() {
return element2;
}
 
@Override
public String toString() {
return "(" + element1 + ", " + element2 + ")";
}
}
 
private static class RobotInput extends Challenge115 {
private List<Integer> array;
 
public RobotInput(Integer... array) {
this.array = new ArrayList<Integer>(Arrays.asList(array));
}
 
@Override
public List<Integer> getArray() {
return array;
}
 
public void setArray(List<Integer> array) {
this.array = array;
}
}
 
private static class UserInput extends Challenge115 {
@Override
public List<Integer> getArray() {
int arraySize;
String stringArray;
try (Scanner scanner = new Scanner(System.in)) {
System.out.println("Array Size: ");
arraySize = Integer.parseInt(scanner.nextLine().trim());
System.out.println("Array: ");
stringArray = scanner.nextLine();
}
List<Integer> result = new ArrayList<Integer>();
for (String element : stringArray.split(" ")) {
result.add(Integer.parseInt(element.trim()));
}
if (arraySize != result.size()) {
throw new InputMismatchException("Given array size "
+ arraySize + " does not match array size "
+ result.size() + ".");
}
System.out.println("Array: " + Arrays.toString(result.toArray()));
return result;
}
 
public void go() {
int number;
try (Scanner scanner = new Scanner(System.in)) {
System.out.println("Enter number: ");
System.out.println(scanner.nextLine());
number = scanner.nextInt();
}
go(number);
}
}
 
public static void main(String[] args) {
Challenge115 challenge = new RobotInput(10, -8, 2, 1, 4, -9, 6, 1, 9,
-10, -5, 2, 3, 7);
challenge.go(7);
challenge.go(2);
// UserInput challenge = new UserInput();
// challenge.go();
}
 
private Criteria criteria;
 
public abstract List<Integer> getArray();
 
public void go(int number) {
if (criteria == null) {
setNewCriteria();
}
System.out.println("Looking for " + number + " pairs.");
for (Pair<Integer, Integer> pair : criteria.getPairs(number)) {
System.out.println(pair);
}
}
 
public void setNewCriteria() {
this.criteria = new Criteria(getArray());
}
 
public void setNewCriteria(List<Integer> array) {
this.criteria = new Criteria(array);
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.