1 import java
.util
.AbstractMap
.SimpleEntry
;
2 import java
.util
.Arrays
;
3 import java
.util
.Collections
;
4 import java
.util
.Comparator
;
5 import java
.util
.LinkedList
;
8 * Class that implements the pet problem solver.
10 * @author Mart Lubbers, s4109503
12 public class LubbersSolver
implements IPetproblemSolver
{
14 public int[] solve(int n
, int m
, int[][] compatibility
) {
15 // Create initial result list of of length n and fill with -1
16 int[] result
= new int[n
];
17 Arrays
.fill(result
, -1);
19 // Create the lists that define the sums of the rows and columns
20 LinkedList
<SimpleEntry
<Integer
, Integer
>> rows
= new LinkedList
<SimpleEntry
<Integer
, Integer
>>();
21 LinkedList
<SimpleEntry
<Integer
, Integer
>> cols
= new LinkedList
<SimpleEntry
<Integer
, Integer
>>();
24 int[] col_sums
= new int[m
];
25 for (int i
= 0, sum
= 0; i
< n
; i
++) {
26 for (int j
= 0; j
< m
; j
++) {
27 sum
+= compatibility
[i
][j
];
28 col_sums
[j
] += compatibility
[i
][j
];
30 rows
.add(new SimpleEntry
<Integer
, Integer
>(i
, sum
));
32 for (int i
= 0; i
< m
; i
++) {
33 cols
.add(new SimpleEntry
<Integer
, Integer
>(i
, col_sums
[i
]));
35 //Sort the lists so the rows and columns with the least amount of positive compatibilities
36 Comparator
<SimpleEntry
<Integer
, Integer
>> comp
= new Comparator
<SimpleEntry
<Integer
, Integer
>>() {
38 public int compare(SimpleEntry
<Integer
, Integer
> a
, SimpleEntry
<Integer
, Integer
> b
) {
39 return a
.getValue().compareTo(b
.getValue());
42 Collections
.sort(rows
, comp
);
43 Collections
.sort(cols
, comp
);
45 /* 1. Find the row or column with the lowest sum(least available matches)
46 * Because the rows and columns are sorted on value the first item is the lowest
47 * 2. Find the match with the lowest sum and still positive compatibility for that row or column
48 * 3. Select smallest from those indices
50 SimpleEntry
<Integer
, Integer
> MINIMUM
= new SimpleEntry
<Integer
, Integer
>(-1, Integer
.MAX_VALUE
);
51 while (!(rows
.isEmpty() || cols
.isEmpty())) {
52 //1. Find the row or column with the lowest sum(least available matches)
53 SimpleEntry
<Integer
, Integer
> row_l
= rows
.peekFirst();
54 SimpleEntry
<Integer
, Integer
> col_l
= cols
.peekFirst();
56 //2. The row is the lowest
57 if (row_l
.getValue() < col_l
.getValue()) {
58 //Remove the current lowest row sum
60 //3. Find smallest column that has compatibility 1
61 SimpleEntry
<Integer
, Integer
> smallest
= MINIMUM
;
62 for (SimpleEntry
<Integer
, Integer
> e
: cols
) {
63 if (e
.getValue() < smallest
.getValue() && compatibility
[row_l
.getKey()][e
.getKey()] == 1) {
67 //No pets left that have a positive compatibility
68 if (smallest
.getKey() == -1) {
71 cols
.remove(smallest
);
72 result
[row_l
.getKey()] = smallest
.getKey();
73 //2. The column is the lowest
75 //Remove the current lowest column sum
77 //3. Find smallest row that has compatibility 1
78 SimpleEntry
<Integer
, Integer
> smallest
= MINIMUM
;
79 for (SimpleEntry
<Integer
, Integer
> e
: rows
) {
80 if (e
.getValue() < smallest
.getValue() && compatibility
[e
.getKey()][col_l
.getKey()] == 1) {
84 //No pets left that have a positive compatibility
85 if (smallest
.getKey() == -1) {
88 rows
.remove(smallest
);
89 result
[smallest
.getKey()] = col_l
.getKey();