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:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:

import java.util.*;

public class Riddle {

    public static void main(String[] args) {
        List<Pair> combinations = new ArrayList<>();
        initialFill(combinations);
        filterUniqueProducts(combinations, false, true);
        reduceBySecondsStatement(combinations);
        filterUniqueProducts(combinations, true, false);
        filterUniqueSums(combinations);
        printSolutions(combinations);
    }


    private static void initialFill(List<Pair> possibleSolutions) {
        for (int i = 2; i <= 1000; i++) {
            for (int j = 2; j <= i; j++) {
                possibleSolutions.add(new Pair(j, i));
            }
        }
        System.out.println("Fill successfull");
    }

    /**
     * Sucht aus einer Liste von möglichen Lösungspaaren jene heraus, die ein eindeutiges Produkt unter den
     * gegebenen Lösungen haben. Ist findUnique true, enthält possibleSolutions nach Aufruf der Methode nur noch
     * Lösungen mit eindeutigem Produkt, andernfalls genau jene, die kein eindeutiges Produkt haben.
     * @param possibleSolutions
     * @param findUnique
     * @param withoutGaps
     */
    private static void filterUniqueProducts(List<Pair> possibleSolutions, boolean findUnique, boolean withoutGaps) {
        final List<Pair> notUniqueProductsPairs = new ArrayList<>();
        final List<Pair> uniqueProductsPairs = new ArrayList<>();
        final Set<Integer> knownProducts = new TreeSet<>();
        for (int i = possibleSolutions.size() - 1; i >= 0; i--) {
            final Pair currentSolution = possibleSolutions.get(i);
            final int currentProduct = currentSolution.getProduct();
            if (knownProducts.contains(currentProduct)) {
                notUniqueProductsPairs.add(currentSolution);
                possibleSolutions.remove(i);
                continue;
            }
            boolean foundProductAgain = false;
            final int currentB = currentSolution.b;
            for (int j = currentB - 1; j >= 2; j--) {
                if (j * j < currentProduct) {
                    break;
                }
                for (int k = j; k >= 2; k--) {
                    if (j * k < currentProduct) {
                        break;
                    }
                    if (j * k == currentProduct) {
                        if (withoutGaps || possibleSolutions.contains(new Pair(k, j))) {
                            foundProductAgain = true;
                            break;
                        }
                    }
                }
                if (foundProductAgain) {
                    break;
                }
            }
            if (foundProductAgain) {
                knownProducts.add(currentProduct);
                notUniqueProductsPairs.add(currentSolution);
            } else {
                uniqueProductsPairs.add(currentSolution);
            }
            possibleSolutions.remove(i);
        }
        if (findUnique) {
            possibleSolutions.addAll(uniqueProductsPairs);
            System.out.println("Filtering for unique-product-pairs complete, " + possibleSolutions.size() + " solutions left.");
        } else {
            possibleSolutions.addAll(notUniqueProductsPairs);
            System.out.println("Filtering for not-unique-product-pairs complete, " + possibleSolutions.size() + " solutions left.");
        }
        possibleSolutions.sort(Comparator.naturalOrder());
    }
    
    private static void reduceBySecondsStatement(List<Pair> possibleSolutions) {
        Set<Pair> treeSetOfPossibleSolutions = new TreeSet<>(possibleSolutions);
        Set<Integer> knownBadSums = new TreeSet<>();
        Set<Integer> knownGoodSums = new TreeSet<>();
        for (int i = possibleSolutions.size() - 1; i >= 0; i--) {
            final Pair currentSolution = possibleSolutions.get(i);
            final int currentSum = currentSolution.getSum();
            if (knownBadSums.contains(currentSum)) {
                possibleSolutions.remove(i);
                continue;
            }
            if (knownGoodSums.contains(currentSum)) {
                continue;
            }
            boolean foundBadSum = false;
            for (int j = 2; j <= currentSum / 2; j++) {
                if (!treeSetOfPossibleSolutions.contains(new Pair(j, currentSum - j))) {
                    knownBadSums.add(currentSum);
                    foundBadSum = true;
                    possibleSolutions.remove(i);
                    break;
                }
            }
            if(!foundBadSum) {
                knownGoodSums.add(currentSum);
            }
        }
        System.out.println("Second reduction complete, " + possibleSolutions.size() + " solutions left.");
    }

    /**
     * Sucht aus einer Liste von möglichen Lösungspaaren jene heraus, die eine eindeutige Summe haben. 
     * Nach Aufruf der Methode enthälst die übergebene Liste nur noch jene Lösungspaare
     * @param possibleSolutions
     */
    private static void filterUniqueSums(List<Pair> possibleSolutions) {
        final List<Pair> uniqueSumPairs = new ArrayList<>();
        final Set<Integer> knownSums = new TreeSet<>();
        for (int i = possibleSolutions.size() - 1; i >= 0; i--) {
            final Pair currentSolution = possibleSolutions.get(i);
            final int currentSum = currentSolution.getSum();
            if (knownSums.contains(currentSum)) {
                possibleSolutions.remove(i);
                continue;
            }
            boolean foundSumAgain = false;
            final int currentB = currentSolution.b;
            for (int j = currentB - 1; j >= 2; j--) {
                if (2 * j < currentSum) {
                    break;
                }
                for (int k = j; k >= 2; k--) {
                    if (j + k < currentSum) {
                        break;
                    }
                    if (j + k == currentSum && possibleSolutions.contains(new Pair(k, j))) {
                        foundSumAgain = true;
                        break;
                    }
                }
                if (foundSumAgain) {
                    break;
                }
            }
            if (foundSumAgain) {
                knownSums.add(currentSum);
            } else {
                uniqueSumPairs.add(currentSolution);
            }
            possibleSolutions.remove(i);
        }
        possibleSolutions.addAll(uniqueSumPairs);
        possibleSolutions.sort(Comparator.naturalOrder());
        System.out.println("Filtering for unique-sum-pairs complete, " + possibleSolutions.size() + " solutions left.");
    }


    private static void printSolutions(List<Pair> solutions) {
        for (Pair solution : solutions) {
            System.out.println(solution);
        }
    }

    private static class Pair implements Comparable<Pair> {
        final int a;
        final int b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        int getSum() {
            return a + b;
        }

        int getProduct() {
            return a * b;
        }

        @Override
        public int compareTo(Pair other) {
            if (this.b == other.b) {
                return Integer.compare(this.a, other.a);
            }
            return Integer.compare(this.b, other.b);
        }

        @Override
        public boolean equals(Object o) {
            if (o == this) {
                return true;
            }
            if (o instanceof Pair) {
                Pair oAsPair = (Pair) o;
                if (this.a == oAsPair.a && this.b == oAsPair.b) {
                    return true;
                }
            }
            return false;
        }

        @Override
        public int hashCode() {
            return 961 + 31 * a + b;
        }

        @Override
        public String toString() {
            return "(" + a + ", " + b + ")";
        }
    }
}