Facebook Hacker Cup – Solución Studious Student

En el tercer problema de la ronda de clasificación de la Facebook Hacker Cup se nos pedía lo siguiente:

Nos dan un fichero de entrada de la siguiente manera:
– Primera línea: un entero con el conjunto de líneas a tratar
– Resto de líneas: un entero con el número de palabras en la fila y las palabras, separadas por espacios

Y para cada línea se nos pedía montar el string más pequeño posible combinando las palabras de la fila.

Resumiendo para una entrada como:

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

La salida esperada es

cupfacebookforhackerstudentsstudious
duzklvrawqrc
dyroiymybeaxeyubxzdr
bwjibwjibwjijp
dcyihopjijliuiuy

Este problema no es muy difícil y es solucionable incluso por fuerza bruta.

Sin embargo, lo solucioné con una de las novedades de PHP5.3: Los closures y usando la función usort.

Os dejo la respuesta que creo que me quedó bastante mona:

#!/usr/bin/php
<?php
if($_SERVER['argc'] != 2) die('Filename must be provided' . PHP_EOL);
 
$sFileName = $_SERVER['argv'][1];
$fd = fopen($sFileName, 'r');
$lines = (int)trim(fgets($fd));
 
for($l=0;$l<$lines;$l++) {
    $line = trim(fgets($fd));
    $words = explode(' ', $line);
    $numwords = array_shift($words);
 
    usort($words, function($a,$b) {
        return (($a.$b) > ($b.$a));
    });
 
    echo implode('', $words).PHP_EOL;
}
?>

La parte más interesante es usort espera un segundo parámetro “Callable” que al final no es más que una función que recibe dos parámetros (que son dos elementos del array) y devolvemos:
-1 si a lo consideramos menor que b
0 si consideramos a igual a b
1 si consideramos a mayor que b

En este caso, solo devolvemos 0 o 1.
Y solamente importa el 1, que se da cuando $a.$b > $b.$a -> $a se considera mayor que $b

Y la pregunta final de facebook era:

Input:
20
9 z dvqgfh wqx vnajabkqvs sdwkc dlhcnc ezrcvsc teje gzwwj
9 eavcqvv wyuh mkfq not evhlpur eidqnartht pesgphnnlq t ztvu
9 s minpax ax zit cyax zitax minp zitaxminp cy
9 izqht h qpbdayaifl pjsoie sujccnm umj dralemrspo euswuti m
6 facebook hacker cup for studious students
9 gm souyd fsrd bjnnuknqs rvncvkvssd gxfl wjmeagyob pahil nkfrcuhjh
9 qxwd bejf wfaua rvkorigcm psdflr utgcsj iaolpoazv hmzczeg hqktnql
5 k duz q rc lvraw
9 i hsmh hsmheh xgi eh xg xgeh xnfc ihsmh
9 o zt da wv brorejctww fu phnej ynrdkylwys ekggrmehcl
9 rnnabb ldk ndhn rnnaldk zeabbbb zeabb zea rnna bb
9 dcn csmzj krnc vkcoume wvpva yqoexwujwp v cxepgptf xb
9 wehfri kclm ri qgca gt qgcagt qgcagt wehf qgcagtqgca
9 m xmnz mlk vlk lk iwkf lkiwkf vm v
9 rgh woqg dmabatgbt qrvpcrx eluunoi sy w wnthqxgkg aimallazuc
9 ld r d lo rlo rlol l rd ix
9 hdfeax d s uxnnrzko nxpcu v njxqbnh aaqzeeb kxpkw
9 a yncoklkc ek yyfqebh je edzhujjc gpmb ktqimdtw opka
9 u ufmu ufmuqfy vmc ufm uqfy z vmcu qfy
9 iccrmcrm mwp sil iccrmcrm ic odo iccrm crm odocrm

Output:
dlhcncdvqgfhezrcvscgzwwjsdwkctejevnajabkqvswqxz
eavcqvveidqnarthtevhlpurmkfqnotpesgphnnlqtwyuhztvu
axcyaxcyminpaxminpszitaxminpzitaxzit
dralemrspoeuswutihizqhtmpjsoieqpbdayaiflsujccnmumj
cupfacebookforhackerstudentsstudious
bjnnuknqsfsrdgmgxflnkfrcuhjhpahilrvncvkvssdsouydwjmeagyob
bejfhmzczeghqktnqliaolpoazvpsdflrqxwdrvkorigcmutgcsjwfaua
duzklvrawqrc
ehhsmhehhsmhihsmhixgehxgixgxnfc
brorejctwwdaekggrmehclfuophnejwvynrdkylwyszt
bbldkndhnrnnabbrnnaldkrnnazeabbbbzeabbzea
csmzjcxepgptfdcnkrncvkcoumevwvpvaxbyqoexwujwp
gtkclmqgcagtqgcagtqgcagtqgcaqgcariwehfriwehf
iwkflkiwkflkmlkmvlkvmvxmnz
aimallazucdmabatgbteluunoiqrvpcrxrghsywnthqxgkgwoqgw
dixldllordrlolrlor
aaqzeebdhdfeaxkxpkwnjxqbnhnxpcusuxnnrzkov
aedzhujjcekgpmbjektqimdtwopkayncoklkcyyfqebh
qfyufmufmuqfyufmuuqfyuvmcuvmcz
crmiccrmcrmiccrmcrmiccrmicmwpodocrmodosil

Terminado esto, el próximo post retomará los arrays!

You may also like...