Triangle Trilemma

We are asked to write a program to classify triangles, this is an easy one, easy is good because at this time all we need is just one successful solution for the Qualification Round, of course our chances to qualify are higher if we start with the easy problem at the contest.

Click here to download the problem statement.

Step 1: Analyzing the problem

We are given 3 points (six integer values) that may or may not define a triangle.

First, we need to validate if the given points are not collinear, in the following picture we have 3 collinear points, something you have to notice is that for this case the distances (x1-x2) and (x1-x3) are proportional to the (y1-y2) and (y1-y3) respectively.

Collinearity can be represented by the following equation:

(x1 - x2) / (y1 - y2) == (x1 – x3) / (y1 – y3)

But having a difference in the divisor is too risky because in some cases it can give you a division by 0 (zero) exception, so we will rewrite it as:

(x1 - x2) * (y1 – y3) == (x1 – x3) * (y1 - y2)

Collinear means, not a triangle. Notice that this is also validating if two of the points are the same, because in that case the three are collinear.

Now we need to know if the triangle is rectangle, obtuse or acute.

s1 = (x1-x2) *(x1-x2) + (y1-y2)* (y1-y2) // Side 1 ^ 2
s2 = (x1-x3) *(x1-x3) + (y1-y3)* (y1-y3) // Site 2 ^2
s3 = (x3-x2) *(x3-x2) + (y3-y2)* (y3-y2) // Site 3 ^2

Validating if its "right"

s1 == s2 + s3 || s2 == s1 + s3 || s3 == s1 + s2

Validating if its "obtuse"

s1 > s2 + s3 || s2 > s1 + s3 || s3 > s1 + s2

The triangle is "acute" otherwise.

Validating if its "isosceles"

s1 == s2 || s2 == s3 || s1 == s3

Otherwise is "scalene"

Step 2: Start Coding

Here we will focus on coding the logical part, we'll assume that we already have load all the input data in a string[][] array, you can find how we got that array in the previous article "Training for Google Code Jam 2008 with ActionScript3".

Now we need to implement the a function that receives the input data array and returns an output data array, everything we put in this output array will be shown in our output textarea.

// This functions implements the logic of your solution
private function TransformInput(inputData:Array):Array{
	var outputData:Array = []; // Output lines
	// For this problem we need to validate every row of data
	var N:int = parseInt(inputData[0][0]);
	// We start with i = 1 because first row have the number of cases
	for(var i:int=1; i <= N; i++){
		var x1:int =  parseInt(inputData[i][0]);
		var y1:int =  parseInt(inputData[i][1]);
		var x2:int =  parseInt(inputData[i][2]);
		var y2:int =  parseInt(inputData[i][3]);
		var x3:int =  parseInt(inputData[i][4]);
		var y3:int =  parseInt(inputData[i][5]);
		
		var TriangleType1:String = "triangle"; // triangle or not a triangle, by default 'triangle'
		var TriangleType2:String = ""; // right, obtuse or acute
		var TriangleType3:String = ""; // isosceles or scalene 
		
		// Validating collinearity
		if( (x1 - x2) * (y1 - y3) == (x1 - x3) * (y1 - y2) ){
			TriangleType1 = "not a triangle";
			// Adds a new line to the output
			outputData.push(StringUtil.substitute("Case #{0}: {1}", i, TriangleType1)); 
		}
		else{
			// Is it right, obtuse or acute?
			var s1:int = (x1-x2) * (x1-x2) + (y1-y2) * (y1-y2) // Side 1 ^2
			var s2:int = (x1-x3) * (x1-x3) + (y1-y3) * (y1-y3) // Site 2 ^2
			var s3:int = (x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) // Site 3 ^2
			
			if(s1 == s2 + s3 || s2 == s1 + s3 || s3 == s1 + s2)
				TriangleType2 = "right";
			else
				if(s1 > s2 + s3 || s2 > s1 + s3 || s3 > s1 + s2)
					TriangleType2 = "obtuse";
				else
					TriangleType2 = "acute";
			
			// Is it isosceles or scalene?
			if(s1 == s2 || s2 == s3 || s1 == s3)
				TriangleType3 = "isosceles";
			else
				TriangleType3 = "scalene";
			// Adds a new line to the output
			outputData.push(StringUtil.substitute("Case #{0}: {1} {2} {3}", 
													i, 
													TriangleType3,
													TriangleType2,
													TriangleType1)); 
		}
	}
	return outputData;
}

Working Solution

The Price is Wrong

We have to make a program that tells what is the smallest set of prices needed to change in order to have a growing price list. This time we need to think a little bit more, why? because if we don't think before coding our program can be dealing with 2 at the power of 64 iterations a total of 18446744073709551616 iteration which is hard even if your PC have the best processor in the market.

Click here to download the problem statement.

This solution was posted by Igor Naverniouk, in the Google Code Jam Group at Google Groups the author of the python code is Jeff Tamer. I'm not python fluent so I could have misunderstood the logic.

Step 1: Analyzing the problem

Here we have two lists, the first with a product's name and the second with our first guess of the product's prices, both lists are ordered based on the actual prices, and we need to change the smallest set of prices.

This is represented as follows:

x1, x2, x3, ..., xi, ..., xn // Product names
y1, y2, y3, ..., yi, ..., yn // Product prices

And don't forget that one condition is the statement is that y_i have to be minor than y_i+1 because the list is ordered.

What we need is to know which of the prices have to be changed, in general if y_i have to be changed or not, this is a yes or not question, as the problem statement says, for the large data set we can get a maximum of 64 items; another thing we need to know is what is the price of the last price that wasn't changed as a reference to evaluate if the price is actually growing.

For y_i we will try both cases, the case when it changes, and the another where it doesn't change, with this we don't have to worry about y_i because we have covered it in all cases, good news is that we just reduced the number of items by one, bad news is that this way we are still trying with all cases (2ⁿ) =(.

In the image we can analyze graphically what is happening with the items when we decide to use both cases for y_i, in this small graphic we have FOUR! times the same subtree for y_i+2 and EIGHT! times the same subtree for y_i+3, imaging this, your program is processing the item y_i+3 8 times, and the only information to vary the result is the last price that wasn't changed, then instead of calculating everything 8 times, we can process it the first time, save the result in a cache (we can use a variable for this) and if in the other 7 times we have same the scenario (same last price that wasn't changed) we read the cache instead of calculating everything again =), of course if is not the same scenario we need to calculate the new result and save it in the cache variable.

Step 2: Start Coding

We were talking about evaluating the behavior for item y_i, y_i+1, y_i+2 and so on, doesn't it sound like a recursive function?

// We will use a recursive function to solve this problem
private function Solve(itemsNames:Array, itemPrices:Array, currentPosition:int, lastPriceNotChanged:int, cache:Array):Array{
	var answer:Array  = [];
	if(currentPosition == itemsNames.length) return []; // We reached the end of the list
															// and return an empty answer.
	// First we look in the cache (we may have answer already)
	var savedAnswer:Array = SearchAnswer(currentPosition, lastPriceNotChanged, cache);
	// If a saved answer is found, return it.
	if(savedAnswer) return savedAnswer; 
	
	// If we got here we haven't return any answer yet, so it's time to calculate.
	
	// We need to calculate the answer for both cases
	
	// Current price changes
	answer = Solve(itemsNames, itemPrices, currentPosition + 1, lastPriceNotChanged, cache);
	
	// if the price changes, this item is part of the solution, so we add it to the answer.
	answer.push(itemsNames[currentPosition]);
	// The answer needs to be sorted.
	answer = answer.sort();
	
	// Current price doesn't change
	// This happend only if the lastPriceNotChanged is minor than the current item price
	if(lastPriceNotChanged < itemPrices[currentPosition] ){
		// Solve again but this time the current item is not part of the solution.
		var tmpAnswer:Array = Solve(itemsNames, itemPrices, currentPosition + 1, itemPrices[currentPosition], cache);
		
		// First priority is to find the smallest set
		// Second it have to be lexicographically first
		if(answer.length > tmpAnswer.length ){
			answer = tmpAnswer;
		}
		if(answer.length == tmpAnswer.length && answer.join(" ") > tmpAnswer.join(" ")){
			answer = tmpAnswer;
		}
	}
	//trace(StringUtil.substitute("{0}-{1}-{2}", currentPosition, answer.length, answer.join(":")));
	// We save the answer in the cache before return it.
	if(answer && answer.length > 0){
		// Please, read carefully
		// I'm storing the answer as a string because all objects in ActionScript3
		// are passed by reference, that doesn't happen with primitive types like String
		cache.push([currentPosition, lastPriceNotChanged, answer.join(" ")]);
	}
	
	return answer;
}

// This function return the saved answer if it exists.
private function SearchAnswer(position:int, price:int, cache:Array):Array {
	for(var i:int = 0; i < cache.length; i++){
		if(cache[i][0] == position && cache[i][1] == price){
			return cache[i][2].split(" "); // Return the stored answer
		}
	}
	return null;
}

Now we call the recursive function for each case in the input file and we are done!.

// This functions implements the logic of your solution
private function TransformInput(inputData:Array):Array{
	var outputData:Array = []; // Output lines
	// Read number of cases.
	var N:int = inputData[0][0];
	// We start with i = 1 because first row have the number of cases
	for(var i:int=1; i <= 2*N; i++){
		var cache:Array = [];
		var itemPrices:Array = [];
		for(var j:int = 0; j < (inputData[i+1] as Array).length; j++){
			itemPrices.push(parseInt(inputData[i+1][j]));
		}
		var answer:Array = Solve(inputData[i], itemPrices, 0, 0, cache);
		i++; // we add 1 to i, because each case is completed 
			 // by two imput lines
			 
		// Add a line to the output
		outputData.push(StringUtil.substitute("Case #{0}: {1}", i/2 as int, answer.join(" ")));
	}
	return outputData;
}

Final notes

First, translating this from Python to ActionScript3 took me a while because I wasn't aware that in ActionScript3 all objects are passed by reference to functions and procedures. The good news for me is that I'll participate in the contest with C# =P which is good because I'm just starting to learn ActionScript3.

Working Solution