Tech and thoughts

# Posts tagged contest

## HackerCup Facebook 2014

Feb 18th

In November I rediscovered the coding contest from Facebook after some years. This was after a period of returning to algorithm study also in the first stages of the contest is more about understanding the problem than knowing algorithms. I solved one of the problem from the qualifications round which is written below. In the next round I looked a bit over one of the problem and figured it out a solution but I didn’t finalize it.

The problem from the sounds like that:

* You want to write an image detection system that is able to recognize different geometric shapes. In the first version of the system you settled with just being able to detect filled squares on a grid.*

* You are given a grid of N×N square cells. Each cell is either white or black. Your task is to detect whether all the black cells form a square shape. *

*Input*

* The first line of the input consists of a single number T, the number of test cases. *

* Each test case starts with a line containing a single integer N. Each of the subsequent N lines contain N characters. Each character is either “.” symbolizing a white cell, or “#” symbolizing a black cell. Every test case contains at least one black cell. *

*Output*

* For each test case i numbered from 1 to T, output “Case #i: “, followed by YES or NO depending on whether or not all the black cells form a completely filled square with edges parallel to the grid of cells. *

*Constraints*

* 1 ≤ T ≤ 20*

*1 ≤*

**N**≤ 20

And my solution was:

function fromTxtToArray($filename) { $fh = fopen($filename, "rb"); $data = fread($fh, filesize($filename)); fclose($fh); $array = explode("\n",$data); array_pop($array); $rows = $array[0]; unset($array[0]); return array('rows' => $rows, 'data' => $array); } function Square($input) { $square = array(); $response = 'NO'; $size = array_shift($input); foreach ($input as $keyRow => $row) { if (isset($square['size']) && $square['size'] > 1) { if($response == 'YES' && substr_count($row, '.') != $size) { return 'NO'; } if($row != $input[$square['row']] && $response == 'NO') { return 'NO'; } //we have a square if ($keyRow - $square['row'] == $square['size'] - 1) { //square $response = 'YES'; } continue; } $cols = str_split($row); //detect a possible square and define its coordinates foreach ($cols as $keyCol => $col) { if (($col == '#') && empty($square)) { $square['row'] = $keyRow; $square['col'] = $keyCol; $square['size'] = 1; $response = 'YES'; continue; } if ($col == '#' && $cols[$keyCol - 1] == '#') { $square['size']++; $response = 'NO'; } elseif ($col == '#') { return 'NO'; } } } return $response; } $source = fromTxtToArray('square_detector.txt'); $i = 0; $output = ''; $case = array(); $cases = array(); foreach ($source['data'] as $k => $v){ if(is_numeric($v)) { if($k > 1) array_push($cases, $case); $case = array(); } $case[] = $v; } array_push($cases, $case); do{ $output .= 'Case #' . ($i + 1) . ': ' . Square($cases[$i])."\n"; //die; $i++; }while($i < $source['rows']); $fp = fopen('output_square_detector.txt', 'w'); fwrite($fp, $output); fclose($fp); echo $output;

## Facebook Hacker cup 2012 Alphabet soup problem

Jan 26th

This weekend I participated at the anual coding contest organised by Facebook. It is the second edition and there are still enough things to improve. Although I did well on programming I didn’t qualified for the next round because of a stupid mistake, which I’ve done it twice.

The last problem (“Alphabet soup”) was the easiest and it enounces like that:

*Alfredo Spaghetti really likes soup, especially when it contains alphabet pasta. Every day he constructs a sentence from letters, places the letters into a bowl of broth and enjoys delicious alphabet soup.*

*Today, after constructing the sentence, Alfredo remembered that the Facebook Hacker Cup starts today! Thus, he decided to construct the phrase “HACKERCUP”. As he already added the letters to the broth, he is stuck with the letters he originally selected. Help Alfredo determine how many times he can place the word “HACKERCUP” side-by-side using the letters in his soup.*

*Input*

*The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with a sequence of upper-case letters and spaces: the original sentence Alfredo constructed.*

*Output*

*Output T lines, one for each test case. For each case, output “Case #t: n”, where t is the test case number (starting from 1) and n is the number of times the word “HACKERCUP” can be placed side-by-side using the letters from the sentence.*

*Constraints*

*1 < T ≤ 20**Sentences contain only the upper-case letters A-Z and the space character**Each sentence contains at least one letter, and contains at most 1000 characters, including spaces*

5 WELCOME TO FACEBOOK HACKERCUP CUP WITH LABEL HACKERCUP BELONGS TO HACKER QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG MOVE FAST BE BOLD HACK THE HACKERCUP

Example output

Case #1: 1 Case #2: 2 Case #3: 1 Case #4: 0 Case #5: 1

I solved it in PHP, but I tested with the data from the page pasted into a file on my computer. In less than a half an hour you can figure it out , program and test it, but I hadn’t a good setup for reading the file and when I runned the file downloaded from facebook, it gave me an extra 21 line when the number of test cases was mentioned as 20. So, because I tested few days before a problem from last year which had a separation between the number of test cases and the data, I hastly modified the program to remove a line after the number of cases.

In short, I had a the correct result without the first line and numbered whith 1 in minus. Here is my solution:

<?php function fromTxtToArray($filename){ $fh = fopen($filename, "rb"); $data = fread($fh, filesize($filename)); fclose($fh); $array = explode("\n",$data); $rows = $array[0]; unset($array[0]); echo $rows; // I realised afterwards that $rows != count($data); return array('rows' => $rows, 'data' => $array); } function Alphabet($input){ $target = Array(); $cazul = str_split($input); $map = array_count_values($cazul); //the builtin function does all the job //print_r($map); each letter whith the number of occurences $target['H'] = isset($map['H'])?$map['H']:0; $target['A'] = isset($map['A'])?$map['A']:0; $target['C'] = isset($map['C'])?(floor($map['C']/2) ):0; //there are 2 C in the word $target['K'] = isset($map['K'])?$map['K']:0; $target['E'] = isset($map['E'])?$map['E']:0; $target['R'] = isset($map['R'])?$map['R']:0; $target['U'] = isset($map['U'])?$map['U']:0; $target['P'] = isset($map['P'])?$map['P']:0; $low = min($target); return $low; } $data = fromTxtToArray('alphabet_soup.txt'); $i = 1; $output = ''; foreach ($data['data'] as $k => $v){ $output .= 'Case #' . $i . ': ' . Alphabet(trim($v))."\r\n"; $i++; if($i > $data['rows']) break; //the stupid condition which I omitted } $fp = fopen('output_soup.txt', 'w'); fwrite($fp, $output); fclose($fp); echo $output;

The problems are quite original and except of this they are not trivial to solve. There are a lot of very good programmers and I didn’t have high hopes to get to the finals. But I’m sory that I’ve solved two problems and I failed for such a stupid mistake.

UPDATE :The other problem I solved it wrong, although it worked on the test dataset.