0plus1 Blog

Here we go with another problem. Here’s the test

Studious Student

You’ve been given a list of words to study and memorize. Being a diligent student of language and the arts, you’ve decided to not study them at all and instead make up pointless games based on them. One game you’ve come up with is to see how you can concatenate the words to generate the lexicographically lowest possible string.

Input

As input for playing this game you will receive a text file containing an integer N, the number of word sets you need to play your game against. This will be followed by N word sets, each starting with an integer M, the number of words in the set, followed by M words. All tokens in the input will be separated by some whitespace and, aside from N and M, will consist entirely of lowercase letters.

Output

Your submission should contain the lexicographically shortest strings for each corresponding word set, one per line and in order.

Constraints

1 <= N <= 100
1 <= M <= 9
1 <= all word lengths <= 10

Basically we have to find the composed string that is the lexicographically‘s shortest. So where is the issue here? The issue is that the problem states that you have to find the shortest possible composed string, so order each of the words cannot be simply ordered and combined because that may or may not be the correct solution (we will go there later). The easiest way to do this is to recursively test each of the possible permutations of the words against each other, this is the bruteforcing method. Let’s see.

Bruteforcing Method

First we have to parse the input:

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

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

	$i = 0;
	$return = array();
	foreach ($array as $k => $v){
		$return[$i] = explode(' ',trim($v));
		unset($return[$i][0]);
		$i++;
	}
    return array('rows' => $rows, 'data' => $return);
}

Then we have to permutate each of the words we have been given and then sort them (php sort luckily automagically sorts strings lexicographically) returning the first one.

//source of this function -> http://docstore.mik.ua/orelly/webprog/pcook/ch04_26.htm
function permute($items, $perms = array()) {

	global $permutations;

    if (empty($items)) {
        $permutations[] = join('', $perms);
    }  else {
		for ($i = count($items)-1; $i >= 0; --$i) {
		     $newitems = $items;
             $newperms = $perms;
             list($foo) = array_splice($newitems, $i, 1);
             array_unshift($newperms, $foo);
             permute($newitems, $newperms);
         }
		 return $permutations;
    }
}

function sortAndKill($array){
	sort($array,SORT_STRING);
	return $array[0];
}

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

set_time_limit(0);

foreach ($data['data'] as $k => $v){
	$permutations = array();
   	$combinations = permute($v);
	echo sortAndKill($combinations)."\n";
	unset($permutations);
}

This works perfectly with the example, sadly with the real output it will take too long (I let it run for more than 20 minutes with no result). If you wanna test it just copy and paste the test input into a txt file.

5
6 facebook hacker cup for studious students
5 k duz q rc lvraw
5 mybea zdr yubx xe dyroiy
5 jibw ji jp bw jibw
5 uiuy hopji li j dcyi

It’s obvious that we have to switch to dp.

Dynamic Programming

What is the problem here? Is that we have too many cases to test, we have to find a way to exclude obviously wrong cases. We can start by ordering the words we have been given and see the results.

function lexiOrder($array){
	sort($array,SORT_STRING);
    $string = false;
    foreach ($array as $k => $v){
        $string .= trim($v);
    }
    return $string;
}

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

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

It works! No wait a minute..

The string: bwjijibwjibwjp is wrong it should be: bwjibwjibwjijp this is because while ji comes before jibw merging them togheter will return jijibw while the correct one is jibwji (b comes before j) the standard sorting will not work anymore.. we have to use usort.

function letterwalk($a,$b){

    if ($a == $b) {
        return 0;
    }
    for ($i=0;$i<10;$i++){

        $lettera = substr($a, $i, 1);
        $letterb = substr($b, $i, 1);

		if ($lettera < $letterb){
			return -1;
		} elseif($lettera > $letterb) {
			return 1;
		}
    }
}

//usort($array, "letterwalk");

So what is this? It’s a function to walk and compare sequentially every single letter of the word against each other. But wait we still get the same result as before! This is because comparing ji agains jibw will fail because b will get compared to null. To avoid this we have to edit the function:

function letterwalk($a,$b){

    if ($a == $b) {
        return 0;
    }
    for ($i=0;$i<10;$i++){

        $lettera = substr($a, $i, 1);
        $letterb = substr($b, $i, 1);

        if($lettera && $letterb) {
            if ($lettera < $letterb){
                return -1;
            } elseif($lettera > $letterb) {
                return 1;
            }
        } else {
            if($lettera==$letterb){
                return 0;
            } elseif ($lettera < $letterb) {
                return 1;
            } else {
                return -1;
            }
        }
    }
}

Finally the example works! But we are not finished yet. The problem is that there may be case where a shorter string must go AFTER the longest one.
to clarify:

ji / jibw

jibwji is the correct answer, so ji must go after jibw.

but

aa / aabb

aaaabb is the correct answer, aa must go before aabb

How do we test this? We can sort them in two different ways! So here we have the final solution:

function lexiOrder($array,$mode){

	if ($mode == 'letter'){
		usort($array, "letterwalk");
	} elseif ($mode == 'word'){
		sort($array,SORT_STRING);
	}

    $string = false;
    foreach ($array as $k => $v){
        $string .= trim($v);
    }
    return $string;
}

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

$result = false;
foreach ($data['data'] as $k => $v){

	$order_l = lexiOrder($v,'letter');
	$order_w = lexiOrder($v,'word');

	$order_f = array($order_l,$order_w);
	sort($order_f,SORT_STRING);

	$result .= $order_f[0]."\n";
}
echo $result;

BUT!! What about if we find a case with two couples like this:

ji jibw
aa aabb

The correct order would be:

aaaabb jibwji

Since our code now can only test two cases (the shortest before and the shortest after) should we find such a case the algotithm will fail since it will only have:

aaaabb jijibw
aabbaa jibwji

to test, neither of them are correct. We are takling the problem from the wrong perspective. We need to be smart. Let’s analyse the strings.

ji jibw -> jibwji Because the j comes after the b
aa aabb -> aaaabb because the a comes before the b

So..

ji jibw -> jiJ jibw
aa aabb -> aaA aabb

We also know that words are between 1 and 10 chars so we can safely pad them to

ji jibw -> jiJJJJJJJJ jibwJJJJJJ
aa aabb -> aaAAAAAAAA aabb
AAAAAA

aaaabb jijibw
aabbaa jibwji

This way the strings can be sorted with a simple php sort!

function padAndOrder($array){
	foreach ($array as $k => $v) {
        echo $strings[$k] = str_pad($v, 10 + strlen($v), substr($v,0,1));
    }

	sort($strings, SORT_STRING);

	$return = false;
    foreach ($strings as $k => $v) {
        $return .= substr($v, 0, -10);
    }
	return $return;
}

Once again enjoy! I’m doing this to share my method (and the way I’ve come to it) so that it may inspire other, there are maybe thousand of better ways to do this, it’s just my take. Peace.

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!