-
Notifications
You must be signed in to change notification settings - Fork 4
/
TowerOfCubes.java
107 lines (98 loc) · 3.59 KB
/
TowerOfCubes.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
import static java.util.Arrays.stream;
import static java.util.stream.Collectors.toList;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
public class TowerOfCubes {
private static final BufferedReader reader = new BufferedReader(
new InputStreamReader(System.in));
final static int[] map = new int[] { 1, 0, 3, 2, 5, 4 };
final static String[] toString = new String[] { "front", "back",
"left", "right", "top", "bottom" };
final List<String> tower = new ArrayList<>();
final int[][] table;
final int[][][] refs;
int height = 0;
int colorIdx = 0;
int head = 0;
TowerOfCubes(List<List<Integer>> cubes) {
table = new int[cubes.size()][6];
refs = new int[cubes.size()][6][2];
buildUpTable(cubes);
buildUpTower();
}
private void buildUpTower() {
int currentColorIdx = colorIdx;
while (true) {
tower.add((head + 1) + " " + toString[currentColorIdx]);
int[] ref = refs[head][currentColorIdx];
if (ref == null) {
break;
}
head = ref[0];
currentColorIdx = ref[1];
}
}
private static int indexOf(int start, int value, List<Integer> array) {
for (int i = start; i < array.size(); ++i) {
if (array.get(i) == value) {
return i;
}
}
return -1;
}
private void buildUpTable(List<List<Integer>> cubes) {
for (int current = cubes.size() - 1; current >= 0; --current) {
List<Integer> cube = cubes.get(current);
for (int j = 0; j < 6; ++j) {
int color = cube.get(map[j]);
int max = 1;
refs[current][j] = null;
for (int i = current + 1; i < cubes.size(); ++i) {
int topColorIndex = -1;
while ((topColorIndex = indexOf(topColorIndex + 1, color,
cubes.get(i))) != -1) {
if (max < table[i][topColorIndex] + 1) {
max = table[i][topColorIndex] + 1;
refs[current][j] = new int[] { i, topColorIndex };
}
}
}
table[current][j] = max;
if (height < max) {
colorIdx = j;
height = max;
head = current;
}
}
}
}
public static void main(String[] args) throws IOException {
String currentLine;
int caseNo = 1;
while ((currentLine = reader.readLine()) != null) {
while (currentLine.trim().isEmpty()) {
currentLine = reader.readLine();
}
int n = Integer.parseInt(currentLine.trim());
if (n == 0) {
break;
}
List<List<Integer>> cubes = new ArrayList<>();
for (int i = 0; i < n; ++i) {
cubes.add(stream(
reader.readLine().trim().split(" "))
.filter(x -> !x.equals(""))
.map(Integer::parseInt)
.collect(toList()));
}
System.out.println("Case #" + (caseNo++));
TowerOfCubes toc = new TowerOfCubes(cubes);
System.out.println(toc.height);
toc.tower.stream().forEach(System.out::println);
System.out.println();
}
}
}