Well this has been an interesting exercise, although probably a bit of a waste of a day, but a super geek saturday.

A reminder of the good old student programming assignments.
http://www.facebook.com/hackercup/problems.php?round=4

This hacker cup is in 4 round, pre-selection first with 3 tasks. Only need one correct though to get to next round.

Here are my 3 answers, not really sure if this will be enough to qualify, I have doubts on the peg game, since I never seem to really ever get the same results… And although my code is probably not the cleanest. I am pretty confident that it should qualify my me.

1) double square.

Example output:

1
2
0
1
1

Probably like most people, I started by attempting brute force, before realizing that we could optimize by limiting the results with squares and using the results as the keys of an array to speed up the result.his is my code:

<?php
function get_list_of_squares(){
for($i=0;$i<=sqrt(2147483647);$i++)
{
$list[$i]=$i*$i;
}
return $list;
}
$rHandle = fopen(‘input.txt’, ‘r’);
$oHandle = fopen(‘output.txt’, ‘w’);
$string = “”;
while(!feof($rHandle)){
$string .= fread($rHandle, filesize(‘input.txt’));
}
fclose($rHandle);
$numbers = preg_split(‘%[\s,]+%’, $string);
$nb_results = array_shift($numbers);
$numbers2 = array_flip($numbers);
$list = get_list_of_squares();
$list = array_flip($list);
$r = array();
foreach($list as $sq => $id )
{
foreach($numbers2 as $key => $value)
{
if($sq > $key) continue;
if(array_key_exists($key – $sq, $list) &&  !isset( $r[$key][$key - $sq] )  )
{
echo “\n$key = ” . $sq . ” + ” . ($key – $sq) ;
$r[$key][$sq]=$key – $sq;
}
}
}
foreach($numbers as $key )
{
echo $key . “: :” . count( $r[$key] ). “\n”;
fwrite($oHandle, count($r[$key]) . “\n”);
}
fclose($oHandle);
?>

x.x.x.x.x
 x...x.x
x...x.x.x
 x.x...x
x.x.x.x.x
 G  

'x' indicates a peg, '.' indicates empty space.

Example output

0 0.375000
1 1.000000
1 1.000000
0 1.000000
0 0.500000

The final exercise was probably the most difficult, but probably because I havn’t done this type of algorithm for a long time. I clearly remember doing this in my “networks” course in my first year of masters, this we had to do in “c” but I have to say I was not very focused in this course for some reason.

Anyway here is my answer, although It is likely to be a little buggy since I didn’t follow a simple algorithm like there must have been if I could remember my course.

<?php
function check_init($val){
 if(!isset($val)) $val = 0;
 return $val;
}

$rHandle = fopen('input.txt', 'r');
$oHandle = fopen('output.txt', 'w');
 $string = "";
 while(!feof($rHandle)){
 $string = fread($rHandle, filesize('input.txt'));
 $text .= $string;
 }
 fclose($rHandle);
 $lines = preg_split('/[\n]+/', $text);
 $nb_lines_to_check = $lines[0];
 foreach($lines as $index => $line){
 if($index == 0) {
 echo "line 1: amount of games: " . $line;
 continue;
 }
 $values = preg_split('/[\s]+/', $line);
 if( count($values) <= 1 ) continue;
 $rows = $values[0];
 $cols = $values[1];
 $target = $values[2];
 $nb_holes = $values[3];    
 $holes = array();
 $coord = array_splice($values, 4);
 $starting_val = $cols - 1;
 for($i=0;$i<$nb_holes;$i++){
 $id = $coord[$i*2] . ":" . ($coord[$i*2 +1]);
 $holes[$id] = true;
 }
 $results = array();
 echo "\ngame $index: ". $rows ."x". $cols . "\ntarget: c " . $target . " : ". $nb_holes . " holes\n";
 for($y=0; $y < $rows; $y++){
 $distance = $rows - $y;
 $shift = $y % 2;
 for($x=0; $x + $shift < $cols; $x++)     {
 if($target -$x > $distance) continue;
 for($start=0; $start < $starting_val; $start++) {
 if($y == 0)
 {   if($start == $x)
 {            $results[$start][$y][$x] =  1;                    }
 else{        $results[$start][$y][$x] =  0;               }
 continue;
 }
 $prev_left = isset($results[$start][$y-1][$x-1+$shift]) && $results[$start][$y-1][$x-1+$shift] > 0 ? $results[$start][$y-1][$x-1+$shift]/2 : 0;
 $prev_right = isset($results[$start][$y-1][$x + $shift]) && $results[$start][$y-1][$x + $shift] > 0 ? $results[$start][$y-1][$x + $shift] / 2 : 0;
 if($x == 0) {    $prev_left = $prev_left * 2;   }
 elseif( ($x + $shift) == ($cols - 1) ){
 $prev_right = $prev_right * 2;            }
 if(isset($holes[$y . ":". $x])){
 $prev_left =0;
 if($results[$start][$y-1][$x-1+$shift] > 0)
 $results[$start][$y + 1][$x-1+$shift] = $results[$start][$y-1][$x-1+$shift];
 }
 $next_x =$x+1;
 if(isset($holes[$y . ":". $next_x])){
 $prev_right =0;             
 }
 if(isset($results[$start][$y][$x])){
 $new_value = $results[$start][$y][$x] + $prev_right + $prev_left;
 $results[$start][$y][$x] =  $new_value ;
 }
 else
 {     $results[$start][$y][$x] =  $prev_right + $prev_left ;      }
 }
 }
 }
 $proba = 0;
 foreach($results as $starting => $test){
 if($proba < $test[$rows -1][$target] ){
 $winner = $starting;
 $proba = $test[$rows -1][$target];
 }
 }
 fwrite($oHandle, sprintf("%s %7.6f\n", $winner, round($proba, 6)) );
 }
 fclose($oHandle);
?>

3) The Studious student:

Example output
cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy

<?php
function cmp($a, $b){
if($a == $b){    return 0; }
if(preg_match(“/^$a/”, $b) == true)
{    return 1;    }
return($a < $b)? -1 : 1;
}

$rHandle = fopen(‘input.txt’, ‘r’);
$oHandle = fopen(‘output.txt’, ‘w’);
$string = “”;
while(!feof($rHandle)){
$string = fread($rHandle, filesize(‘input.txt’));
$text .= $string;
}
fclose($rHandle);
$lines = preg_split(‘%[\n,]+%’, $text);
$nb_lines_to_check = $lines[0];
foreach($lines as $index => $line)
{
if($index == 0) {
continue;
}
$words = preg_split(‘/[\s]+/’, $line);
$ordered =  array_splice($words, 1);
usort($ordered, “cmp”);
foreach($ordered as $key => $item)
{
echo $item;
fwrite($oHandle, $item);
}
echo “\n”;
fwrite($oHandle, “\n”);
}
fclose($oHandle);
?>

You can download the code here, and try it for yourself if you like:

http://www.cyber-netics.com/hackercup.tar.gz