W10D3.js

//The share price for a company over a week's trading is as follows:
//[128, 97, 121, 123, 98, 97, 105]. If you had to buy shares in the company
//on one day, and sell the shares on one of the following days, write an
//algorithm to work out what the maximum profit you could make would be.
function best_profit(prices) {
	if (!prices.length) return 0;
	//Algorithm: Step through potential selling days. If the price
	//is lower than our current buying day, switch to a new buying
	//day. If the price diff between buying and selling days is
	//greater than our current best, it's our new best.
	var buy = prices[0], sell = prices[0], profit = 0;
	for (var i = 1; i < prices.length; ++i) {
		sell = prices[i];
		if (sell < buy) buy = sell;
		if (sell - buy > profit) profit = sell - buy;
	}
	return profit;
}

//Tests for best_profit
//1) The sample array
console.log(best_profit([128, 97, 121, 123, 98, 97, 105]));

//2) Randomly generated prices, dancing around a progression
function generate_prices(start, step, spread, length) {
	var ret = [];
	while (length--) {
		ret.push(start + Math.floor(Math.random()*spread - spread/2));
		start += step;
	}
	return ret;
}
for (var i = 0; i < 10; ++i) {
	var prices = generate_prices(100, 2, 10, 10);
	console.log("Profit", best_profit(prices), "from", prices);
}
for (var i = 0; i < 10; ++i) {
	var prices = generate_prices(100, -2, 10, 10);
	console.log("Profit", best_profit(prices), "from", prices);
}


//Imagine that you wanted to find what the highest floor of a 100 story
//building you could drop an egg was, without the egg breaking. But you only
//have two eggs. Write an algorithm to work out which floors you should drop
//the eggs from to find this out in the most efficient way.
function egg_drop_practical(maxheight) {
	//Anyone who's worked with eggs knows that even a first-floor drop
	//will break an unprotected egg. So don't bother dropping them. Just
	//assume the answer is 0, and enjoy the eggs. :)
	console.log("Fry both eggs and eat them for lunch.");
	return 0;
}
function egg_drop_binary(maxheight) {
	//Okay, this one's for real. Attempt to drop eggs from different
	//heights, and see if they break. Depends on a function drop_egg(h)
	//that returns true if the egg broke, or false if it did not; this
	//function is not implemented here.
	//Optimized for the smallest number of attempts.
	var minheight = 0; ++maxheight;
	while (maxheight > minheight + 1) {
		var height = Math.floor((maxheight + minheight) / 2);
		if (drop_egg(height)) {
			//Oops, egg broke.
			maxheight = height;
		} else {
			//Whew, egg didn't break.
			minheight = height;
		}
	}
	return minheight;
}
function egg_drop_linear(maxheight) {
	//This time, optimize for the smallest number of _failures_. Again,
	//depends on drop_egg(h). Note that this ignores the risk of an egg
	//cracking without completely smashing - it pretends that a "safe"
	//drop lets you reuse the egg.
	for (var height = 1; height <= maxheight; ++height)
		if (drop_egg(height)) return height - 1;
	return maxheight;
}

function egg_drop_triangle(maxheight) {
	//Thirdly, optimizing for number of drops, relying on the fact that
	//we can afford to smash one egg and keep on dropping.
	//Algorithm from http://datagenetics.com/blog/july22012/index.html
	var jump = Math.floor(Math.sqrt(2 * maxheight));
	var floor = jump;
	while (floor <= maxheight && !drop_egg(floor)) {
		// Jump up one less floor each time (because we have done one
		// extra drop).
		if (jump > 1) --jump;
		floor += jump;
	}

	// When it breaks, go back to the highest known good floor
	floor -= jump;

	// Then work up one floor at a time
	while (++floor <= maxheight && !drop_egg(floor)) ;
	return floor - 1;
}

//Tests for egg drop functions. We attempt both algorithms with a variety of
//egg strengths (defined by changing the real_max). The binary search will
//finish a lot more quickly than the linear one will, but it's likely to get
//a few splots along the way.....
var real_max;
function drop_egg(height) {
	console.log("["+real_max+"] Dropping egg from "+height+"...",
		height>real_max ? "SPLOT" : "Safe");
	return height > real_max;
}
console.log("================"); real_max = 0;
console.log("Practical:", egg_drop_practical(100));
console.log("----------------");
console.log("Binary:", egg_drop_binary(100));
console.log("----------------");
console.log("Linear:", egg_drop_linear(100));
console.log("----------------");
console.log("Triang:", egg_drop_triangle(100));
console.log("================"); real_max = 17;
console.log("Binary:", egg_drop_binary(100));
console.log("----------------");
console.log("Linear:", egg_drop_linear(100));
console.log("----------------");
console.log("Triang:", egg_drop_triangle(100));
console.log("================"); real_max = 96;
console.log("Binary:", egg_drop_binary(100));
console.log("----------------");
console.log("Linear:", egg_drop_linear(100));
console.log("----------------");
console.log("Triang:", egg_drop_triangle(100));
console.log("================"); real_max = 200;
console.log("Binary:", egg_drop_binary(100));
console.log("----------------");
console.log("Linear:", egg_drop_linear(100));
console.log("----------------");
console.log("Triang:", egg_drop_triangle(100));
console.log("================");

//Imagine you are looking for a book in a library with a Dewey Decimal
//index. How would you go about it? Can you express this process as a
//searching algorithm?
function find_book(library, dewey, title) {
	//Libraries are generally organized into separate sections for
	//fiction/non-fiction, and often for children's vs adult's. We
	//assume that the 'library' we've been given is the appropriate
	//section. Furthermore, we're going to pretend that this library
	//isn't divided into shelves, despite literally EVERY library I
	//have ever used having more than one shelf - no point making
	//this more complicated than it needs to be. :) And one more
	//short-cut: we assume that Dewey Decimal values can be compared
	//for equality and inequality with each other. The foibles of
	//binary floating-point are outside the scope of this question;
	//you're welcome to use fixed-point or string representations of
	//Dewey call codes. Oh, and we're looking for a book based on
	//title alone, despite the possibility of collisions.
	var start = 0, end = library.length;
	while (start < end) {
		var middle = Math.floor((start + end) / 2);
		if (library[middle].dewey == dewey) {
			//Found the right code. Great! Did we find the book?
			if (library[middle].title == title) return library[middle];
			//Nope. Linearly search around for the book we want.
			for (var idx = middle + 1; library[idx].dewey == dewey; ++idx)
				if (library[idx].title == title) return library[idx];
			for (var idx = middle - 1; library[idx].dewey == dewey; --idx)
				if (library[idx].title == title) return library[idx];
			//Well, we found the right section, but the book isn't
			//here. Guess someone else has borrowed it. Sorry!
			return null;
		}
		if (library[middle].dewey < dewey)
			start = middle + 1;
		else
			end = middle - 1;
	}
	//We don't have anything of that Dewey code, so that book isn't
	//available. Sorry! Try another library.
	return null;
}