0plus1 Blog

Most of the programmers now about the Hacker Challenge from Facebook. I will now explain my take on it using php.
The reason I’m doing this is because this contest is an epic fail (read here the reasons why) full of bug, with really confused rules badly explained (I’m looking at you 6 minutes time limit with no warning and the code/no-code in the reply question). Anyway it’s still an interesting programming puzzle..

Let us start with the text of the problem:

Double Squares
A double-square number is an integer X which can be expressed as the sum of two perfect squares. For example, 10 is a double-square because 10 = 3² + 1². Your task in this problem is, given X, determine the number of ways in which it can be written as the sum of two squares. For example, 10 can only be written as 3² + 1² (we don’t count 1² + 3² as being different). On the other hand, 25 can be written as 5² + 0² or as 4² + 3².

Input
You should first read an integer N, the number of test cases. The next N lines will contain N values of X.
Constraints
0  <  X  <  2147483647
1  < N  < 100
Output
For each value of X, you should output the number of ways to write X as the sum of two squares.

Facebook right at the top of the page gives you an hint: Too hard for brute force, switching to dp
This is because the problems that have been given are fairly easy to code using brute force, but hard to do the smart way, since we are using php here the smart way is the only way to go (you’ll see the reason in a while).

Let’s start.

First thing is to read the input, easy one.. since I like multidimensional arrays I did it like this:

function fromTxtToArray($filename){
	$fh = fopen($filename, "rb");
	$data = fread($fh, filesize($filename));
	fclose($fh);

	$array = explode("\n",$data);
	$rows = $array[0];
	unset($array[0]);

	return array('rows' => $rows, 'data' => $array);
}

Then we have the main cycle (I discarded completely the rows because I like foreach better than for):

$data = fromTxtToArray('input.txt');
foreach ($data['data'] as $k => $v){
    //?????
}

Now that the main logic is out of the way let’s work the problem, starting with the:

bruteforcing method

function scompose($number){
	$array = array();

	if ($number % 2 == 0) {
		$stop = $number/2;
	} else {
		$stop = round($number/2, 0, PHP_ROUND_HALF_DOWN);
	}

	for($i=0;$i<=$number;$i++){

		if($i>$stop){
			break;
		}
		$num1 = $number-$i;
		$num2 = $i;

		if(isPerfect($num1)&&isPerfect($num2)){
			$array[] = array('num1'=>$num1,'num2'=>$num2);
		}
	}

	return $array;
}

$data = fromTxtToArray('input.txt');

set_time_limit(0);

foreach ($data['data'] as $k => $v){
     echo count(scompose($v))."\n";
}

Basically what this does is to cycle the number in order to get all of his possible couple of addends, it does this simply by subtracting $i from the number and taking $i as the other addend. Now this will create a real issue because doing so will give you repeated couples (eg: take five you’ll get 0,5;1,4;2,3;3,2;4,1;5,0) this is wrong since the problem text clearly states that there shouldn’t be repetition. To avoid this we have to divide the number by two, rounding him down in case it’s odd, using this value we can break the cycle when we get to that point. After that we check if both of the addends of the numbers are perfect squares if so we put them in an array, when the cycle stops we count the array and we are done. The missing functions are these:

//Avoids problem with the buggy is_int native php function
function betterIs_int($int){

	if(is_numeric($int) === true){
		if((int)$int == $int){
			return true;
		} else {
			return false;
		}
	}else{
		return false;
	}
}
//Check if the square root of a number is an integer (perfect square)
function isPerfect($int){
	if(betterIs_int(sqrt($int))){
		return true;
	} else {
		return false;
	}
}

I actually let this thing run for fun with the input.txt file and I stopped it after 14 minutes! It works with the examples though, just use this:

$data['data']= array('10','25','3','0','1');

Let’s move to the:

Dynamic programming

If you are not acquainted with this methodology please read here and here.

The problem we had with the brute force was that the for cycle was very very loooong, we have to find a better way to approach this! See we are checking every couple to see if they’re perfect square what about a method where we can rule out directly if there are? First we have to find the highest possible square root of the number, since we cannot exceed this number we have less cases to test. Then we cycle $i from 0 to the maxsquare and we check if the square root of the difference between the number and the square of $i is an integer, if it is we have a winning couple! But wait we still have a problem, the couples are once again repeated! We have to divide them by 2.

function firstDraft($number){

    if($number==0||$number==1){
	        return 1;
	}

	$result=0;

	$maxsquare = floor(sqrt($number));

	for ($i=0; $i<$maxsquare;$i++) {

		$difference = sqrt($number-($i*$i));

		if (betterIs_int($difference)) {
			$result++;
		}
	}
	return ceil($result/2);
}

Wait! Divide them by two? Why? We could just calculate the half square root of the number and trim down the cases to test! And so..

function dp($number){

    if($number==0||$number==1){
	        return 1;
	}

	$result=0;

	$halfmaxsquare = ceil(sqrt($number/2));

	for ($i=0; $i<$halfmaxsquare;$i++) {

		$difference = sqrt($number-($i*$i));

		if (betterIs_int($difference)) {
			$result++;
		}
	}
	return $result;
}

$data = fromTxtToArray('input.txt');

foreach ($data['data'] as $k => $v){
	echo dp($v)."\n";
}

No need to set time limit here
enjoy!

Please note that this article can be applied to any non utf-8 encoding.

I recently needed to send data using ajax to an MSSql 2000 database (which requires windows-1252).
As you may know javascript sends data encoded in utf-8 (utf-16 to be more precise), this must be accepted as a fact thus making the use of a php function to convert the encoding before sending to the database. Here is the snippet I use:

function convertor($array){
	if (is_array($array) && count($array) > 0){
		foreach ($array as $k => $v){
			$return[$k] = mb_convert_encoding($v, "iso-8859-1","UTF-8");
		}
	} elseif (!empty($array)) {
		$return = mb_convert_encoding($array, "iso-8859-1","UTF-8");
	} else {
		return false;
	}
	return $return;
}

Basically what it does is to check if we have an array or a single value then proceed to convert it to the desired encoding (in my case iso-8859-1), after converting the values these can be safely stored into the database.

I have also to add that I’ve encountered some jquery plugins that messes with the encoding of the strings. To be on the safe side you may use this line:

unescape(encodeURIComponent(string))

We recently had to create a select reserved only to contries from the european union, here’s the array with the standard countries codes:

$eu_countries = array(
  "AT" => "Austria",
  "BE" => "Belgium",
  "BG" => "Bulgaria",
  "CY" => "Cyprus",
  "CZ" => "Czech Republic",
  "DK" => "Denmark",
  "EE" => "Estonia",
  "FI" => "Finland",
  "FR" => "France",
  "DE" => "Germany",
  "GR" => "Greece",
  "HU" => "Hungary",
  "IE" => "Ireland",
  "IT" => "Italy",
  "LV" => "Latvia",
  "LT" => "Lithuania",
  "LU" => "Luxembourg",
  "MT" => "Malta",
  "NL" => "Netherlands",
  "PL" => "Poland",
  "PT" => "Portugal",
  "RO" => "Romania",
  "SK" => "Slovakia (Slovak Republic)",
  "SI" => "Slovenia",
  "ES" => "Spain",
  "SE" => "Sweden",
  "GB" => "United Kingdom"
);

source

Today I wrote a script that needed to manipulate several multidimensional arrays, some of them pretty deep.

The standard php function print_r is an hellish mess, browsing through the marvellous php.net documentation I’ve found several examples to beautify the output of print_r (just to give credit: “Bob” and “Everett” were my inspiration) since no one actually did it the way I wanted I made a custom one myself:

function print_rr($array){
    foreach($array as $key=>$value){
       if(is_array($value)){
          $id = md5(rand());
          echo '[<a href="#" onclick="return expandParent(\''.$id.'\')">'.$key.'</a>]<br />';
          echo '<div id="'.$id.'" style="display:none;margin:10px;border-left:1px solid; padding-left:5px;">';
          print_rr($value, $count);
          echo '</div>';
       } else {
       echo "<b>$key</b>: ".$value."<br />";
       }
    }
echo '<script language="Javascript">
function expandParent(id){toggle="block";if(document.getElementById(id).style.display=="block"){toggle="none"}document.getElementById(id).style.display=toggle};
</script>';
}

Feel free to use it anyway you like it.