Tech and thoughts
alex
This user hasn't shared any biographical information
Posts by alex
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;
Zend Certified
Nov 18th
As of this week I’m a Zend certified engineer. There were a lot to write about since my last post, but I felt that this one needs to be mentioned as soon as possible.
It feels great and I want to read this when I will be demotivated. Hope I can pass this good energy I feel right now.
Impresii ZF Mobilio
Apr 30th
A aparut din scurt o invitatie pentru conferinta dedicata universului tehnologiei mobile ZF Mobilio si am vrut sa profit de ea. Pana acum putin timp ma consideram un outsider si chiar si acum nu ma intersectez cu domeniul decat in masura in care trebuie sa iau in considerare particularitatile de utilizare ale site-urilor pe anumite platforme mobile.
Chiar prima dintre ideile pe care le-am extras de la un reprezentant al unei agentii din Italia, dar si de la altii este ca cel mai bine se lucreaza cu oameni specializati pe diversele ramuri, adica programator/dezvoltator de Android, programator de Ios etc.
Conferinta a fost ok, dar nu a iesit neaparat din grupul conferintelor de gen la care am mai fost, s-au prezentat idei si date valoroase/chestii bune(nefumate), dar si destula umplutura.
As pune la puncte negative lipsa neanuntata a lui Dan Bulucea de la Google, pe care as fi fost interesat sa il vad ca reprezentat al unuia dintre cei doi jucatori importanti pe aceasta piata. A lipsit si Bogdan Naumovici, dar nu o consider o pierdere, poate era prea ocupat sa explice prin alte parti cat de bune sunt cianurile de la Rosia Montana.
– Desi a parut un pic infumurat Mihai Mafteianu de la Cronian Group mi s-a parut cel mai realist si mai la obiect din prima zi. El a punctat ca piata aplicatiilor de mobil nu exista inca in Romania si nici nu are sanse atata timp cat nu vor exista servicii de date la viteze si preturi rezonabile pentru Romania. Desi a fost combatut, ceilalti cumva au intarit ideea plasand piata numai in zona aplicatiilor de bussiness dedicate sau a celor foarte simple si cu venituri modeste la o scara de pana in cateva mii de euro.
De la restul am vazut obisnuitele prezentari cu valente de vanzari si/sau futurologie usor incetosata dar cu perspective roz inaltatoare. Au fost prezentate si cateva cazuri de succes printre care cel al concursului Mini Cooper GetAway regasit la 3 vorbitori.
– Am retinut promisiunile pentru suportul complet HTML5 (incluzand tot suportul pentru CSS3, Javascript), trecut de Windows pe primul plan in urmatorii ani. Nu ma entuziasmez prea mult inainte de vreme pentru ca au fost apostrofari chiar din sala pe chestiuni concrete legate de lipsa de suport pentru aplicatiile din Romania in Marketul lor sau suspendare vechilor versiuni de mobile fara o alternativa pentru clientii romani. Totusi la nivel global ma astept ca Windows sa mai aiba un cuvant de spus pe mobile.
– Am testat un Nokia Lumia, si pare destul de ok pentru 5 minute de butonat. Probabil daca eram la inceput ca si utilizator de smart-phone l-as fi luat serios in considerare, pacat ca Nokia nu s-a miscat mai bine in anii trecuti si s-au incapatanat sa ramana in universul lor restrans. Daca nu ar fi iesit din proiectul Android cred ca le-ar fi fost mult mai bine acum. Chiar si acum daca ar avea un Nokia cu Android ar mai salva situatia.
Si in a doua zi, au fost cateva lucruri interesante de urmarit. Am aflat ca se mai lucreaza si cu Flash pentru jocuri de mobil. Desi a fost blamat in ultima perioada, eu cred ca este necesar Flashul sau ceva asemanator care sa faciliteze accesul designerilor(creatorilor grafici) in mediul mobil.
– A existat si o prezentare mult prea detaliata si generala(gen referat) a mediului mobil pe toate laturile lui cu ceva exemple din strainatate si Romania. Am retinut aplicatia Speed Taxi despre care mai auzisem.
– Studiul GFK a surprins un instantaneu la inceputul lunii aprilie a zonei mobile asa mica cum este ea. Mai mult a fost o intarire a ce ma puteam astepta ca din publicul comercial peste 18 ani telefonul este folosit preponderent de publicul masculin, in jurul varstei de 35 ani, foarte putin pentru aplicatii(3-4 aplicatii zilnic), mai mult pentru email, muzica, retele sociale si jocuri si ca sunt mai multe telefoane cu Android.
Dar atat la noi cat si in afara pentru aplicatii si in general daca vrei sa faci bani din aplicatii e bine sa te orientezi spre Apple, iOS.
– Prezentari interesante au avut si Liviu Nistoran care si-a laudat tableta EvoTab2 pe care am inteles si de la George Buhnici ca merita sa o testezi si cei de la Revo Solution, amandoi prezentatorii avand si ceva in spate care sa legitimeze vorbele lor.
De la Revo am aflat ca au trebuit sa simplifice un simulator pentru ca era prea avansat si nu prindea la public, ceea ce impreuna si cu alte pareri subliniaza ca mai importante decat programarea sunt conceptul produsului si marketingul eficient si suficient.
Multi am inteles ca asteapta cu ceva mai mult interes RoNewMedia, dar sunt convins si din alte experiente ca nu te poti lumina prea mult cand este o aria extinsa de domenii si multi participanti.
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
Example input
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.
yum: TypeError: rpmdb open failed on Centos
Dec 13th
I had this error and found the solution here.
#rm /dev/urandom #mknod -m 644 /dev/urandom c 1 9
Works like a charm.
Because it seems to me that I used a similar fix for other problem some time ago I wrote it to remember it.
Universe hypotheses
Oct 26th
I was reading an article on space.com “7 Surprising Things About the Universe” and inspired by the late Steve Jobs (RIP), I decided to stay hungry, stay foulish (probably more foulish than hungry) and post my own thoughts on the Universe. I’ll probably make it a serial.
The above article contains more hypotheses than proven facts, but when you talk about the Universe as a whole, there is a lot of uncertainty. The main ideas are around the Big Bang Theory.
Among other things I picked the following ideas as a base for my reasoning:
1. The Universe is expanding – this is the main idea discovered by Hubble that Universe is not static but the distance between the galaxies is increasing. And this was confirmed by other observations from 1920 when it was discovered first. So I’ll take this hypothesis as the base.
2. From 1 resulted The universe has a start therefore an age and even an order of size is aproximated. This is viewed like a very rapid expansion from a very small point which gave the name Big Bang.
Here comes the first objection (viewed in a Discovery science documentary) -> Maybe is oscilating between a minimum and a maximum size (is pulsating).
3. This year Nobel price was given for the discovery that the expanding of the Universe is accelerating. This revives the geometric models of the General Theory of Relativity
4. There are presented three geometrical models of the Universe based on the balance between the aformentioned expansion and the gravity: sphere, curbed but open(as a saddle) and flat.
The sphere model was also imagined by Einstein which saw the Universe as a 4 dimensions sphere (the 4th dimension being the time).
Here comes my first personal idea: I think there is no straight line in the real universe. The infinite straight line which stands at the base of euclidian geometry has no representation in nature.
A lot of the math we use it’s based on this flat earth logic. We use this absolute concepts of line, plane, parallelism but they cannot exist in nature. Stars are round, planets are round and they move on curved trajectories, galaxies are spiraled, at small scale nothing seems to be described as infinitly straight.
So I think the flat model can be disregarded.
As for the math, there is non-euclidean geometry which challenges the postulates of Euclid, but it’s a sort of declination of the first in a somehow hypothetical space.
I think there is a real need for a new math. Something unified that better integrates the applicable knowledge earned until modern days and eases the work with complex concepts and understanding of large structures.
A way to do this will be to shift focus from the paradigm of reducing everything to a few basic absolute/abstract concepts (some of them arguable like the concept of infinite) and to search for some complex tools (custom symbols) to better illustrate real world objects and interactions.
My hypothesis is that Universe has a start and an end, therefore the time has a start and an end, but the Universe has no age. The start and the end are much likely the same. I think the shape of the Universe is close to a seashell (spiral) and this form contains the time.
I’ll try to elaborate in later writings in a more specific manner ideas and work variants, and maybe someone will engage in a constructive discution.
Internet Explorer problem with nested menus over picture
Jul 11th
Couple of days ago I found a rendering problem in Internet Explorer when testing a nested vertical submenu. Click on the picture below and you will see that when you hover the vertical submenus you cannot click on the lower items. The submenu disappears when you scroll over the little spaces between the list items. On Firefox and Chrome you’ll not see this problem.
Internet Explorer bugs are not that rare but this shows in IE8 and the new IE9, and I couldn’t find a fix on the internet.
Here you can see the demo for the hover bug in IE (IE9 inclusive) . The bug is not showing when I remove the test image which the menu overlays.
I tried some tweaks at the margin and padding, z-index and zoom with no result. If this is a known bug or you know other fix than that the one posted below please let me know.
My solution
The solution I found was to put a background to the hover state of the nested menu (#menu ul ul:hover) . I used an 1 by 1 transparent gif (the old days spacer) as a background.
Here is the fixed version using a background with transparent gif. It solves the problem in IE9 and down to IE7.
The bug and the solution seems to remain valid even for the IE10 as I can test it in the preview.
And, if you know some place that rewards this kind of descoveries for IE please point me to it.
Lucreaza pentru ARCA in concursul Google Lunar Xprize
May 16th
Daca te pricepi la programare pentru simulatoare de zbor sau in general ai experienta cu enginuri 3D poti ajuta ARCA sa trimita rachete inspre luna un concursul Google Lunar Xprize. Citeste pe forum pentru mai multe detalii https://www.arcaspace.com/forum/viewtopic.php?f=11&t=14&start=0#p107
Trebuie introduse datele si formulele lor in simulatorul X-plane dar este bun si orice motor de joc cum ar fi Unreal Engine.
E posibil sa mai apara si alte taskuri punctuale in care poti fi de folos.Pentru ca eu am insistat pe ideea implicarii comunitatii voi populariza si voi sustine cu ce pot aceste demersuri.
If you have some experience in the flight simulator programming area you are welcomed to help ARCA team in the Google Lunar Xprize challenge. The forum thread in romanian here https://www.arcaspace.com/forum/viewtopic.php?f=11&t=14&start=0#p107
Experience with the X-plane flight simulator is most wanted for customisation with their formulas and data, but also experience with 3D game engine like Unreal Engine is good.
Html comments bug on Firefox
Mar 4th
I discovered a bug in Firefox for the html comments. The html comments are broken by a double hyphen “–“.
On the bugzilla it was argued that is not a bug and the implementation is according to the standards http://www.w3.org/TR/html4/intro/sgmltut.html#h-3.2.4 .
The problem is that most web developers are probably not aware of this standard and this could lead to some unexpected results.
In the current version of Firefox (3.6.14) a “–” will close the comment and all that is after will be rendered normally.
In other browsers this will not happen and in the future version Firefox 4 also this will not be a problem, but the standard remains valid.
In Firefox 4 the double hyphen is still interpreted but the comment is closed at the next “>”.
A good practice is to not use html comments for user input expecting that will not show in browser.
If you do need to do that, be aware that functions as php’s htmlentities does not convert double hyphens.
Apparently WordPress knows about this so I can’t show you an example.
Article on choosing PHP framework for a web project
Nov 30th
I recently published the article “Choosing the Open-Source Framework for Web Application Development” in an online science journal called Open Source Science JournalThe journal it’s published in english four times a year and the authors are mainly, but not restricted to, teachers or candidates for a doctor’s degree in the Academy of Economic Studies ASE.
The article presents a methodology to choose an open-source framework for a web project.
Based on the specific requirements of the project some indicators are calculated to choose the framework and there are also the results of the implementation in a specific project. This article is focused on PHP frameworks but the method is not restricted by the language.
The choice may be different depending on the project (I choosed Zend framework) and some evaluations can’t be made in an objective manner, but this is a good example on how to construct a decision when you choose an open-source framework.