/*
PROBLEM:
Given:
- ratings[i]: Rating of movie i
- titles[i]: Title of movie i
- similar[i]: Adjacency list of movie i
- start: Starting movie ID
- k: Number of recommendations
Return up to K highest-rated reachable movie IDs.
RULES:
1. Exclude the starting movie.
2. Higher rating comes first.
3. If ratings tie, lexicographically smaller title wins.
4. If titles also tie, smaller movie ID wins.
5. Handle cycles, duplicate edges, and self-loops.
APPROACH: BFS + SIZE-K MIN-HEAP
1. Start BFS from the starting movie.
2. Use visited to avoid processing movies multiple times.
3. Maintain a min-heap of at most K movies.
4. Keep the WORST selected movie at the heap root:
- Lower rating is worse.
- If ratings tie, alphabetically larger title is worse.
- If titles tie, larger movie ID is worse.
5. For each reachable movie (excluding start):
- If heap size < K, insert it.
- Otherwise, compare it with the heap root.
- If the new movie is better, remove the root and insert it.
6. Extract all K movies from the heap.
7. Reverse the extracted order to get best to worst.
TIME COMPLEXITY:
O(V + E + R * L * log(K+1) + K * L * log(K+1))
V = number of movies
E = number of edges
R = reachable movies excluding start
K = min(k, R)
L = maximum movie title length
- BFS: O(V + E)
- Heap operations: O(L * log(K+1)) each
- Processing R candidates: O(R * L * log(K+1))
- Extracting K movies: O(K * L * log(K+1))
SPACE COMPLEXITY:
O(V + K)
- visited: O(V)
- BFS queue: O(V)
- Min-heap: O(K)
- Result: O(K)
- Custom title comparator: O(1)
*/
// ==========================================
// CUSTOM TITLE COMPARISON
// ==========================================
// Returns:
// -1 if str1 comes before str2
// 1 if str1 comes after str2
// 0 if both are identical
function compareTitles(str1, str2) {
const minLen = Math.min(str1.length, str2.length);
for (let i = 0; i < minLen; i++) {
if (str1[i] < str2[i]) return -1;
if (str1[i] > str2[i]) return 1;
}
if (str1.length < str2.length) return -1;
if (str1.length > str2.length) return 1;
return 0;
}
// ==========================================
// GENERIC MIN-HEAP
// ==========================================
class MinHeapPq {
constructor(compareFn) {
this.compareFn = compareFn;
this.heap = [];
}
size() {
return this.heap.length;
}
front() {
return this.heap.length > 0 ? this.heap[0] : null;
}
swap(i, j) {
[this.heap[i], this.heap[j]] =
[this.heap[j], this.heap[i]];
}
enqueue(val) {
this.heap.push(val);
let i = this.heap.length - 1;
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (
this.compareFn(this.heap[i], this.heap[parent]) >= 0
) {
break;
}
this.swap(i, parent);
i = parent;
}
}
dequeue() {
if (this.heap.length === 0) return null;
if (this.heap.length === 1) {
return this.heap.pop();
}
const root = this.heap[0];
this.heap[0] = this.heap.pop();
let i = 0;
while (true) {
const left = 2 * i + 1;
const right = 2 * i + 2;
let smallest = i;
if (
left < this.heap.length &&
this.compareFn(
this.heap[left],
this.heap[smallest]
) < 0
) {
smallest = left;
}
if (
right < this.heap.length &&
this.compareFn(
this.heap[right],
this.heap[smallest]
) < 0
) {
smallest = right;
}
if (smallest === i) break;
this.swap(i, smallest);
i = smallest;
}
return root;
}
}
// ==========================================
// SOLUTION: BFS + SIZE-K MIN-HEAP
// ==========================================
function topRatedSimilarMoviesHeap(
ratings, titles, similar, start, k
) {
if (k === 0) return [];
const visited = Array(ratings.length).fill(false);
const q = [start];
let head = 0;
// Negative => a is worse than b
// Positive => a is better than b
// Zero => same movie ranking
const compareFn = (a, b) => {
// Lower rating is worse
if (ratings[a] !== ratings[b]) {
return ratings[a] - ratings[b];
}
// Alphabetically larger title is worse
const titleComparison = compareTitles(
titles[a], titles[b]
);
if (titleComparison !== 0) {
return -titleComparison;
}
// Larger movie ID is worse
return b - a;
};
const minHeap = new MinHeapPq(compareFn);
visited[start] = true;
// STEP 1: BFS
while (head < q.length) {
const curr = q[head++];
// STEP 2: Maintain top K movies
if (curr !== start) {
if (minHeap.size() < k) {
minHeap.enqueue(curr);
} else if (
compareFn(curr, minHeap.front()) > 0
) {
// New movie is better than the worst
minHeap.dequeue();
minHeap.enqueue(curr);
}
}
// STEP 3: Explore neighbors
for (const next of similar[curr]) {
if (!visited[next]) {
visited[next] = true;
q.push(next);
}
}
}
// STEP 4: Extract worst to best
const result = [];
while (minHeap.size() > 0) {
result.push(minHeap.dequeue());
}
// STEP 5: Return best to worst
return result.reverse();
}
// ==========================================
// TEST CASES (IDEONE-READY)
// ==========================================
const tests = [
{
name: "Normal + alphabetical rating ties",
ratings: [80, 95, 95, 90],
titles: [
"Avatar", "Titanic",
"Inception", "Interstellar"
],
similar: [[1, 2, 3], [], [], []],
start: 0,
k: 2,
expected: [2, 1]
},
{
name: "Same rating + same title",
ratings: [50, 90, 90, 90],
titles: [
"Start", "Avatar",
"Avatar", "Batman"
],
similar: [[2, 3, 1], [], [], []],
start: 0,
k: 3,
expected: [1, 2, 3]
},
{
name: "Cycles + duplicates + prefix titles",
ratings: [100, 95, 95, 95, 999],
titles: [
"Start", "Avatar", "Av",
"Avengers", "Other"
],
similar: [
[1, 1, 2],
[0, 3],
[1],
[3],
[]
],
start: 0,
k: 3,
expected: [2, 1, 3]
},
{
name: "No reachable movies",
ratings: [100, 90],
titles: ["Start", "Avatar"],
similar: [[], []],
start: 0,
k: 1,
expected: []
},
{
name: "k = 0",
ratings: [50, 90],
titles: ["Start", "Avatar"],
similar: [[1], []],
start: 0,
k: 0,
expected: []
}
];
for (const test of tests) {
const actual = topRatedSimilarMoviesHeap(
test.ratings,
test.titles,
test.similar,
test.start,
test.k
);
const passed =
JSON.stringify(actual) ===
JSON.stringify(test.expected);
console.log(
`${passed ? "PASS" : "FAIL"} - ${test.name}`
);
console.log("Expected:", JSON.stringify(test.expected));
console.log("Actual: ", JSON.stringify(actual));
console.log();
}
Ci8qClBST0JMRU06CkdpdmVuOgotIHJhdGluZ3NbaV06IFJhdGluZyBvZiBtb3ZpZSBpCi0gdGl0bGVzW2ldOiBUaXRsZSBvZiBtb3ZpZSBpCi0gc2ltaWxhcltpXTogQWRqYWNlbmN5IGxpc3Qgb2YgbW92aWUgaQotIHN0YXJ0OiBTdGFydGluZyBtb3ZpZSBJRAotIGs6IE51bWJlciBvZiByZWNvbW1lbmRhdGlvbnMKClJldHVybiB1cCB0byBLIGhpZ2hlc3QtcmF0ZWQgcmVhY2hhYmxlIG1vdmllIElEcy4KClJVTEVTOgoxLiBFeGNsdWRlIHRoZSBzdGFydGluZyBtb3ZpZS4KMi4gSGlnaGVyIHJhdGluZyBjb21lcyBmaXJzdC4KMy4gSWYgcmF0aW5ncyB0aWUsIGxleGljb2dyYXBoaWNhbGx5IHNtYWxsZXIgdGl0bGUgd2lucy4KNC4gSWYgdGl0bGVzIGFsc28gdGllLCBzbWFsbGVyIG1vdmllIElEIHdpbnMuCjUuIEhhbmRsZSBjeWNsZXMsIGR1cGxpY2F0ZSBlZGdlcywgYW5kIHNlbGYtbG9vcHMuCgpBUFBST0FDSDogQkZTICsgU0laRS1LIE1JTi1IRUFQCgoxLiBTdGFydCBCRlMgZnJvbSB0aGUgc3RhcnRpbmcgbW92aWUuCjIuIFVzZSB2aXNpdGVkIHRvIGF2b2lkIHByb2Nlc3NpbmcgbW92aWVzIG11bHRpcGxlIHRpbWVzLgozLiBNYWludGFpbiBhIG1pbi1oZWFwIG9mIGF0IG1vc3QgSyBtb3ZpZXMuCjQuIEtlZXAgdGhlIFdPUlNUIHNlbGVjdGVkIG1vdmllIGF0IHRoZSBoZWFwIHJvb3Q6CiAgIC0gTG93ZXIgcmF0aW5nIGlzIHdvcnNlLgogICAtIElmIHJhdGluZ3MgdGllLCBhbHBoYWJldGljYWxseSBsYXJnZXIgdGl0bGUgaXMgd29yc2UuCiAgIC0gSWYgdGl0bGVzIHRpZSwgbGFyZ2VyIG1vdmllIElEIGlzIHdvcnNlLgo1LiBGb3IgZWFjaCByZWFjaGFibGUgbW92aWUgKGV4Y2x1ZGluZyBzdGFydCk6CiAgIC0gSWYgaGVhcCBzaXplIDwgSywgaW5zZXJ0IGl0LgogICAtIE90aGVyd2lzZSwgY29tcGFyZSBpdCB3aXRoIHRoZSBoZWFwIHJvb3QuCiAgIC0gSWYgdGhlIG5ldyBtb3ZpZSBpcyBiZXR0ZXIsIHJlbW92ZSB0aGUgcm9vdCBhbmQgaW5zZXJ0IGl0Lgo2LiBFeHRyYWN0IGFsbCBLIG1vdmllcyBmcm9tIHRoZSBoZWFwLgo3LiBSZXZlcnNlIHRoZSBleHRyYWN0ZWQgb3JkZXIgdG8gZ2V0IGJlc3QgdG8gd29yc3QuCgpUSU1FIENPTVBMRVhJVFk6Ck8oViArIEUgKyBSICogTCAqIGxvZyhLKzEpICsgSyAqIEwgKiBsb2coSysxKSkKClYgPSBudW1iZXIgb2YgbW92aWVzCkUgPSBudW1iZXIgb2YgZWRnZXMKUiA9IHJlYWNoYWJsZSBtb3ZpZXMgZXhjbHVkaW5nIHN0YXJ0CksgPSBtaW4oaywgUikKTCA9IG1heGltdW0gbW92aWUgdGl0bGUgbGVuZ3RoCgotIEJGUzogTyhWICsgRSkKLSBIZWFwIG9wZXJhdGlvbnM6IE8oTCAqIGxvZyhLKzEpKSBlYWNoCi0gUHJvY2Vzc2luZyBSIGNhbmRpZGF0ZXM6IE8oUiAqIEwgKiBsb2coSysxKSkKLSBFeHRyYWN0aW5nIEsgbW92aWVzOiBPKEsgKiBMICogbG9nKEsrMSkpCgpTUEFDRSBDT01QTEVYSVRZOgpPKFYgKyBLKQoKLSB2aXNpdGVkOiBPKFYpCi0gQkZTIHF1ZXVlOiBPKFYpCi0gTWluLWhlYXA6IE8oSykKLSBSZXN1bHQ6IE8oSykKLSBDdXN0b20gdGl0bGUgY29tcGFyYXRvcjogTygxKQoqLwoKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIENVU1RPTSBUSVRMRSBDT01QQVJJU09OCi8vID09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PQoKLy8gUmV0dXJuczoKLy8gLTEgaWYgc3RyMSBjb21lcyBiZWZvcmUgc3RyMgovLyAgMSBpZiBzdHIxIGNvbWVzIGFmdGVyIHN0cjIKLy8gIDAgaWYgYm90aCBhcmUgaWRlbnRpY2FsCgpmdW5jdGlvbiBjb21wYXJlVGl0bGVzKHN0cjEsIHN0cjIpIHsKICAgIGNvbnN0IG1pbkxlbiA9IE1hdGgubWluKHN0cjEubGVuZ3RoLCBzdHIyLmxlbmd0aCk7CgogICAgZm9yIChsZXQgaSA9IDA7IGkgPCBtaW5MZW47IGkrKykgewogICAgICAgIGlmIChzdHIxW2ldIDwgc3RyMltpXSkgcmV0dXJuIC0xOwogICAgICAgIGlmIChzdHIxW2ldID4gc3RyMltpXSkgcmV0dXJuIDE7CiAgICB9CgogICAgaWYgKHN0cjEubGVuZ3RoIDwgc3RyMi5sZW5ndGgpIHJldHVybiAtMTsKICAgIGlmIChzdHIxLmxlbmd0aCA+IHN0cjIubGVuZ3RoKSByZXR1cm4gMTsKCiAgICByZXR1cm4gMDsKfQoKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIEdFTkVSSUMgTUlOLUhFQVAKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CgpjbGFzcyBNaW5IZWFwUHEgewogICAgY29uc3RydWN0b3IoY29tcGFyZUZuKSB7CiAgICAgICAgdGhpcy5jb21wYXJlRm4gPSBjb21wYXJlRm47CiAgICAgICAgdGhpcy5oZWFwID0gW107CiAgICB9CgogICAgc2l6ZSgpIHsKICAgICAgICByZXR1cm4gdGhpcy5oZWFwLmxlbmd0aDsKICAgIH0KCiAgICBmcm9udCgpIHsKICAgICAgICByZXR1cm4gdGhpcy5oZWFwLmxlbmd0aCA+IDAgPyB0aGlzLmhlYXBbMF0gOiBudWxsOwogICAgfQoKICAgIHN3YXAoaSwgaikgewogICAgICAgIFt0aGlzLmhlYXBbaV0sIHRoaXMuaGVhcFtqXV0gPQogICAgICAgICAgICBbdGhpcy5oZWFwW2pdLCB0aGlzLmhlYXBbaV1dOwogICAgfQoKICAgIGVucXVldWUodmFsKSB7CiAgICAgICAgdGhpcy5oZWFwLnB1c2godmFsKTsKCiAgICAgICAgbGV0IGkgPSB0aGlzLmhlYXAubGVuZ3RoIC0gMTsKCiAgICAgICAgd2hpbGUgKGkgPiAwKSB7CiAgICAgICAgICAgIGNvbnN0IHBhcmVudCA9IE1hdGguZmxvb3IoKGkgLSAxKSAvIDIpOwoKICAgICAgICAgICAgaWYgKAogICAgICAgICAgICAgICAgdGhpcy5jb21wYXJlRm4odGhpcy5oZWFwW2ldLCB0aGlzLmhlYXBbcGFyZW50XSkgPj0gMAogICAgICAgICAgICApIHsKICAgICAgICAgICAgICAgIGJyZWFrOwogICAgICAgICAgICB9CgogICAgICAgICAgICB0aGlzLnN3YXAoaSwgcGFyZW50KTsKICAgICAgICAgICAgaSA9IHBhcmVudDsKICAgICAgICB9CiAgICB9CgogICAgZGVxdWV1ZSgpIHsKICAgICAgICBpZiAodGhpcy5oZWFwLmxlbmd0aCA9PT0gMCkgcmV0dXJuIG51bGw7CgogICAgICAgIGlmICh0aGlzLmhlYXAubGVuZ3RoID09PSAxKSB7CiAgICAgICAgICAgIHJldHVybiB0aGlzLmhlYXAucG9wKCk7CiAgICAgICAgfQoKICAgICAgICBjb25zdCByb290ID0gdGhpcy5oZWFwWzBdOwogICAgICAgIHRoaXMuaGVhcFswXSA9IHRoaXMuaGVhcC5wb3AoKTsKCiAgICAgICAgbGV0IGkgPSAwOwoKICAgICAgICB3aGlsZSAodHJ1ZSkgewogICAgICAgICAgICBjb25zdCBsZWZ0ID0gMiAqIGkgKyAxOwogICAgICAgICAgICBjb25zdCByaWdodCA9IDIgKiBpICsgMjsKICAgICAgICAgICAgbGV0IHNtYWxsZXN0ID0gaTsKCiAgICAgICAgICAgIGlmICgKICAgICAgICAgICAgICAgIGxlZnQgPCB0aGlzLmhlYXAubGVuZ3RoICYmCiAgICAgICAgICAgICAgICB0aGlzLmNvbXBhcmVGbigKICAgICAgICAgICAgICAgICAgICB0aGlzLmhlYXBbbGVmdF0sCiAgICAgICAgICAgICAgICAgICAgdGhpcy5oZWFwW3NtYWxsZXN0XQogICAgICAgICAgICAgICAgKSA8IDAKICAgICAgICAgICAgKSB7CiAgICAgICAgICAgICAgICBzbWFsbGVzdCA9IGxlZnQ7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGlmICgKICAgICAgICAgICAgICAgIHJpZ2h0IDwgdGhpcy5oZWFwLmxlbmd0aCAmJgogICAgICAgICAgICAgICAgdGhpcy5jb21wYXJlRm4oCiAgICAgICAgICAgICAgICAgICAgdGhpcy5oZWFwW3JpZ2h0XSwKICAgICAgICAgICAgICAgICAgICB0aGlzLmhlYXBbc21hbGxlc3RdCiAgICAgICAgICAgICAgICApIDwgMAogICAgICAgICAgICApIHsKICAgICAgICAgICAgICAgIHNtYWxsZXN0ID0gcmlnaHQ7CiAgICAgICAgICAgIH0KCiAgICAgICAgICAgIGlmIChzbWFsbGVzdCA9PT0gaSkgYnJlYWs7CgogICAgICAgICAgICB0aGlzLnN3YXAoaSwgc21hbGxlc3QpOwogICAgICAgICAgICBpID0gc21hbGxlc3Q7CiAgICAgICAgfQoKICAgICAgICByZXR1cm4gcm9vdDsKICAgIH0KfQoKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIFNPTFVUSU9OOiBCRlMgKyBTSVpFLUsgTUlOLUhFQVAKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09CgpmdW5jdGlvbiB0b3BSYXRlZFNpbWlsYXJNb3ZpZXNIZWFwKAogICAgcmF0aW5ncywgdGl0bGVzLCBzaW1pbGFyLCBzdGFydCwgawopIHsKICAgIGlmIChrID09PSAwKSByZXR1cm4gW107CgogICAgY29uc3QgdmlzaXRlZCA9IEFycmF5KHJhdGluZ3MubGVuZ3RoKS5maWxsKGZhbHNlKTsKICAgIGNvbnN0IHEgPSBbc3RhcnRdOwogICAgbGV0IGhlYWQgPSAwOwoKICAgIC8vIE5lZ2F0aXZlID0+IGEgaXMgd29yc2UgdGhhbiBiCiAgICAvLyBQb3NpdGl2ZSA9PiBhIGlzIGJldHRlciB0aGFuIGIKICAgIC8vIFplcm8gICAgID0+IHNhbWUgbW92aWUgcmFua2luZwoKICAgIGNvbnN0IGNvbXBhcmVGbiA9IChhLCBiKSA9PiB7CiAgICAgICAgLy8gTG93ZXIgcmF0aW5nIGlzIHdvcnNlCiAgICAgICAgaWYgKHJhdGluZ3NbYV0gIT09IHJhdGluZ3NbYl0pIHsKICAgICAgICAgICAgcmV0dXJuIHJhdGluZ3NbYV0gLSByYXRpbmdzW2JdOwogICAgICAgIH0KCiAgICAgICAgLy8gQWxwaGFiZXRpY2FsbHkgbGFyZ2VyIHRpdGxlIGlzIHdvcnNlCiAgICAgICAgY29uc3QgdGl0bGVDb21wYXJpc29uID0gY29tcGFyZVRpdGxlcygKICAgICAgICAgICAgdGl0bGVzW2FdLCB0aXRsZXNbYl0KICAgICAgICApOwoKICAgICAgICBpZiAodGl0bGVDb21wYXJpc29uICE9PSAwKSB7CiAgICAgICAgICAgIHJldHVybiAtdGl0bGVDb21wYXJpc29uOwogICAgICAgIH0KCiAgICAgICAgLy8gTGFyZ2VyIG1vdmllIElEIGlzIHdvcnNlCiAgICAgICAgcmV0dXJuIGIgLSBhOwogICAgfTsKCiAgICBjb25zdCBtaW5IZWFwID0gbmV3IE1pbkhlYXBQcShjb21wYXJlRm4pOwoKICAgIHZpc2l0ZWRbc3RhcnRdID0gdHJ1ZTsKCiAgICAvLyBTVEVQIDE6IEJGUwogICAgd2hpbGUgKGhlYWQgPCBxLmxlbmd0aCkgewogICAgICAgIGNvbnN0IGN1cnIgPSBxW2hlYWQrK107CgogICAgICAgIC8vIFNURVAgMjogTWFpbnRhaW4gdG9wIEsgbW92aWVzCiAgICAgICAgaWYgKGN1cnIgIT09IHN0YXJ0KSB7CiAgICAgICAgICAgIGlmIChtaW5IZWFwLnNpemUoKSA8IGspIHsKICAgICAgICAgICAgICAgIG1pbkhlYXAuZW5xdWV1ZShjdXJyKTsKICAgICAgICAgICAgfSBlbHNlIGlmICgKICAgICAgICAgICAgICAgIGNvbXBhcmVGbihjdXJyLCBtaW5IZWFwLmZyb250KCkpID4gMAogICAgICAgICAgICApIHsKICAgICAgICAgICAgICAgIC8vIE5ldyBtb3ZpZSBpcyBiZXR0ZXIgdGhhbiB0aGUgd29yc3QKICAgICAgICAgICAgICAgIG1pbkhlYXAuZGVxdWV1ZSgpOwogICAgICAgICAgICAgICAgbWluSGVhcC5lbnF1ZXVlKGN1cnIpOwogICAgICAgICAgICB9CiAgICAgICAgfQoKICAgICAgICAvLyBTVEVQIDM6IEV4cGxvcmUgbmVpZ2hib3JzCiAgICAgICAgZm9yIChjb25zdCBuZXh0IG9mIHNpbWlsYXJbY3Vycl0pIHsKICAgICAgICAgICAgaWYgKCF2aXNpdGVkW25leHRdKSB7CiAgICAgICAgICAgICAgICB2aXNpdGVkW25leHRdID0gdHJ1ZTsKICAgICAgICAgICAgICAgIHEucHVzaChuZXh0KTsKICAgICAgICAgICAgfQogICAgICAgIH0KICAgIH0KCiAgICAvLyBTVEVQIDQ6IEV4dHJhY3Qgd29yc3QgdG8gYmVzdAogICAgY29uc3QgcmVzdWx0ID0gW107CgogICAgd2hpbGUgKG1pbkhlYXAuc2l6ZSgpID4gMCkgewogICAgICAgIHJlc3VsdC5wdXNoKG1pbkhlYXAuZGVxdWV1ZSgpKTsKICAgIH0KCiAgICAvLyBTVEVQIDU6IFJldHVybiBiZXN0IHRvIHdvcnN0CiAgICByZXR1cm4gcmVzdWx0LnJldmVyc2UoKTsKfQoKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Ci8vIFRFU1QgQ0FTRVMgKElERU9ORS1SRUFEWSkKLy8gPT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09Cgpjb25zdCB0ZXN0cyA9IFsKICAgIHsKICAgICAgICBuYW1lOiAiTm9ybWFsICsgYWxwaGFiZXRpY2FsIHJhdGluZyB0aWVzIiwKICAgICAgICByYXRpbmdzOiBbODAsIDk1LCA5NSwgOTBdLAogICAgICAgIHRpdGxlczogWwogICAgICAgICAgICAiQXZhdGFyIiwgIlRpdGFuaWMiLAogICAgICAgICAgICAiSW5jZXB0aW9uIiwgIkludGVyc3RlbGxhciIKICAgICAgICBdLAogICAgICAgIHNpbWlsYXI6IFtbMSwgMiwgM10sIFtdLCBbXSwgW11dLAogICAgICAgIHN0YXJ0OiAwLAogICAgICAgIGs6IDIsCiAgICAgICAgZXhwZWN0ZWQ6IFsyLCAxXQogICAgfSwKICAgIHsKICAgICAgICBuYW1lOiAiU2FtZSByYXRpbmcgKyBzYW1lIHRpdGxlIiwKICAgICAgICByYXRpbmdzOiBbNTAsIDkwLCA5MCwgOTBdLAogICAgICAgIHRpdGxlczogWwogICAgICAgICAgICAiU3RhcnQiLCAiQXZhdGFyIiwKICAgICAgICAgICAgIkF2YXRhciIsICJCYXRtYW4iCiAgICAgICAgXSwKICAgICAgICBzaW1pbGFyOiBbWzIsIDMsIDFdLCBbXSwgW10sIFtdXSwKICAgICAgICBzdGFydDogMCwKICAgICAgICBrOiAzLAogICAgICAgIGV4cGVjdGVkOiBbMSwgMiwgM10KICAgIH0sCiAgICB7CiAgICAgICAgbmFtZTogIkN5Y2xlcyArIGR1cGxpY2F0ZXMgKyBwcmVmaXggdGl0bGVzIiwKICAgICAgICByYXRpbmdzOiBbMTAwLCA5NSwgOTUsIDk1LCA5OTldLAogICAgICAgIHRpdGxlczogWwogICAgICAgICAgICAiU3RhcnQiLCAiQXZhdGFyIiwgIkF2IiwKICAgICAgICAgICAgIkF2ZW5nZXJzIiwgIk90aGVyIgogICAgICAgIF0sCiAgICAgICAgc2ltaWxhcjogWwogICAgICAgICAgICBbMSwgMSwgMl0sCiAgICAgICAgICAgIFswLCAzXSwKICAgICAgICAgICAgWzFdLAogICAgICAgICAgICBbM10sCiAgICAgICAgICAgIFtdCiAgICAgICAgXSwKICAgICAgICBzdGFydDogMCwKICAgICAgICBrOiAzLAogICAgICAgIGV4cGVjdGVkOiBbMiwgMSwgM10KICAgIH0sCiAgICB7CiAgICAgICAgbmFtZTogIk5vIHJlYWNoYWJsZSBtb3ZpZXMiLAogICAgICAgIHJhdGluZ3M6IFsxMDAsIDkwXSwKICAgICAgICB0aXRsZXM6IFsiU3RhcnQiLCAiQXZhdGFyIl0sCiAgICAgICAgc2ltaWxhcjogW1tdLCBbXV0sCiAgICAgICAgc3RhcnQ6IDAsCiAgICAgICAgazogMSwKICAgICAgICBleHBlY3RlZDogW10KICAgIH0sCiAgICB7CiAgICAgICAgbmFtZTogImsgPSAwIiwKICAgICAgICByYXRpbmdzOiBbNTAsIDkwXSwKICAgICAgICB0aXRsZXM6IFsiU3RhcnQiLCAiQXZhdGFyIl0sCiAgICAgICAgc2ltaWxhcjogW1sxXSwgW11dLAogICAgICAgIHN0YXJ0OiAwLAogICAgICAgIGs6IDAsCiAgICAgICAgZXhwZWN0ZWQ6IFtdCiAgICB9Cl07Cgpmb3IgKGNvbnN0IHRlc3Qgb2YgdGVzdHMpIHsKICAgIGNvbnN0IGFjdHVhbCA9IHRvcFJhdGVkU2ltaWxhck1vdmllc0hlYXAoCiAgICAgICAgdGVzdC5yYXRpbmdzLAogICAgICAgIHRlc3QudGl0bGVzLAogICAgICAgIHRlc3Quc2ltaWxhciwKICAgICAgICB0ZXN0LnN0YXJ0LAogICAgICAgIHRlc3QuawogICAgKTsKCiAgICBjb25zdCBwYXNzZWQgPQogICAgICAgIEpTT04uc3RyaW5naWZ5KGFjdHVhbCkgPT09CiAgICAgICAgSlNPTi5zdHJpbmdpZnkodGVzdC5leHBlY3RlZCk7CgogICAgY29uc29sZS5sb2coCiAgICAgICAgYCR7cGFzc2VkID8gIlBBU1MiIDogIkZBSUwifSAtICR7dGVzdC5uYW1lfWAKICAgICk7CiAgICBjb25zb2xlLmxvZygiRXhwZWN0ZWQ6IiwgSlNPTi5zdHJpbmdpZnkodGVzdC5leHBlY3RlZCkpOwogICAgY29uc29sZS5sb2coIkFjdHVhbDogICIsIEpTT04uc3RyaW5naWZ5KGFjdHVhbCkpOwogICAgY29uc29sZS5sb2coKTsKfQo=