We believe that three things lead to success:
Practice, Practice and Practice!
Code Abbey
Cody Abbey is a neat site with coding challenges, similar to Project Euler, but less focused on math and heavier on the gamification.
Like many sites with programming challenges, there is an inductive learning aspect to help the user succeed. The problems are listed in order of “blessing” for completion. Blessing is somewhat correlated to their difficulty.
Most of the earlier problems are pretty easy but this problem gave me more than a little trouble.
The Problem
The gist of the problem is if you have two printers, that prints one page in time and that prints one page in time, how much time does it take to print pages. Simple math right?
function completionTime(X, Y, N) {
return (X * Y * N) / (X + Y);
}
completionTime(1, 1, 5); // 2.5
completionTime(3, 5, 4); // 7.5The Catch
The example with provided answers didn’t match up with the output from the function.
input data:
2
1 1 5
3 5 4
answer:
3 9The problem is pretty subtle and took more time than I’d like to admit to find. The clue lies in the fact that the answer times are whole numbers.
completionTime(...) returns how much time it would take if the printers could contribute partial pages. If we were solving for the amount of time two hoses could fill a bucket together our function would work. In this case, our printers work on pages independently and rather than combining pages, each printer should only contribute whole pages.
The completionTime, , is still useful for finding the answer. It can be used to determine the number of pages each printer should print. At , both printers would be working on the last page to be printed, so the answer lies in one of 2 possible scenarios:
Solutions
Spoilers Below
So the solution to the problem becomes solving for the amount of time each scenario would take (the max of either machine in that scenario), and finding the min time of the two.
Written out as code we have:
function optimalCompletionTime(X, Y, N) {
return (X * Y * N) / (X + Y);
}
function completionTime(X, Y, N) {
var ot, An1, Bn1, An2, Bn2, t1, t2;
ot = optimalCompletionTime(X, Y, N);
// Scenario 1
An1 = Math.floor(ot/X),
Bn1 = N - An1, // N = An1 + Bn1 => Bn1 = N - An1.
t1 = Math.max(X * An1, Y * Bn1),
// Scenario 2
An2 = Math.ceil(ot/X),
if (An1 === An2) return t1; // Shortcut out if Scenario 1 and 2 are the same.
Bn2 = N - An2, // N = An2 + Bn2 => Bn2 = N - An2.
t2 = Math.max(X * An2, Y * Bn2);
// Return faster of the 2 scenarios.
return Math.min(t1, t2);
}
completionTime(1,1,5) // 3
completionTime(3,5,4) // 9
# Time O(1)Dynamic Programming
One of the perks for solving a problem on Code Abbey is being able to see other people’s solutions. I came across one that I like a lot which uses dynamic programming.
This solution is fairly easy to visualize when put in an OOP context so let’s start there.
function Printer(rate) {
var rate = rate; // Time per page.
var pages = 0;
// Amount of time required to print all the queued pages.
this.finishTime = function() {
return pages * rate;
};
// The time at which an additional page would finish printing.
this.next = function() {
return this.finishTime() + rate;
};
this.queuePage = function() {
pages++;
};
}The Printer class is constructed with a rate - time to print 1 page and functions: queuePage - adds pages to be printed, finishTime - returns the time to finish queued pages, and next - returns the finish time if another page is queued.
With this class we can break down the problem into finding the printer that will result in the lowest finish time for each page we need to print. For the first page, we check all the values that are returned for next(), on that printer we queue a page by calling queuePage().
When we repeat this process as many times as pages to be printed. The value returned by next() takes into account the pages that were queued on printers from previous iterations.
The final result is the highest finishTime() after all the pages have been queued. That is the printer that will finish last, giving us the total required time.
function completionTime(X, Y, N) {
var printerX = new Printer(X), printerY = new Printer(Y), next;
while (N--) {
// Queue page on printer that would result in the lowest finish time.
next = printerX.next() <= printerY.next() ? printerX : printerY;
next.queuePage();
}
// After all pages are queued, return highest finish time.
return Math.max(printerX.finishTime(), printerY.finishTime());
}
completionTime(1,1,5) // 3
completionTime(3,5,4) // 9The class helped when figuring out the logic for solving the problem but it can be replaced with an array.
function completionTime(X, Y, N) {
var times = [0, 0];
while (N--) {
if (times[0] + X <= times[1] + Y)
times[0] = times[0] + X;
else
times[1] = times[1] + Y;
}
return Math.max.apply(null, times);
}
completionTime(1,1,5) // 3
completionTime(3,5,4) // 9This solution can also be adapted to solve for time required when there are variable number of producers:
function zeroFilledArray(size) {
return Array.apply(null, Array(size)).map(Number.prototype.valueOf,0);
}
function completionTime(rates, N) {
var len = rates.length, times = zeroFilledArray(len), next;
while (N--) {
next = 0;
for (var i = 1; i < len; i++) {
next = times[i] + rates[i] <= times[next] ? i : next;
}
times[next] = times[next] + rates[next];
}
return Math.max.apply(null, times);
}
completionTime([1,1,1],7) // 3
completionTime([1,1,1],6) // 2
completionTime([1,1,1],5) // 2
completionTime([1,1,1],4) // 2
completionTime([1,1,1],3) // 1
# Time O(nk)