Radicalii, bată-i vina

Pe HackerRank, un site despre care am vorbit mai mult pe celălalt blog, poți rezolva mici probleme de programe din domenii cât mai diverse.

Un Watson complet lipsit de inspirație îl provocă pe marele detectiv Sherlock Holmes să calculeze câte dintre numerele dintr-un interval dat au o rădăcină întreagă.

Watson gives two integers (A and B) to Sherlock and asks if he can count the number of square integers between A and B (both inclusive).

De exemplu, în intervalul [3, 9] se găsesc două astfel de numere 4 și 9 (radical din 4 este 2, radical din 9 este 3).

Soluțiile pot fi trimise într-o varietate generoasă de limbaje de programare iar dacă rezultatul obținut e cel corect, primești puncte virtuale cu care poți face un mare nimic sau poți acumula insigne cu care poți face alt nimic. Dar provocările sunt simpatice și nu necesită mult efort ci doar multă atenție.

În cazul de față soluția pare la mintea cocoșului. E genul de problemă pe care ai da-o unui începător în programre și chiar face parte din categoria problemelor ușoare pe site. Dar ce e mișto la programare e că până și problemele triviale pot pune... probleme.

O abordare naivă sau directă, depinde cum privim lucrurile, ar fi să extragem pur și simplul radicalul fiecărui număr din interval și dacă e un întreg, să incrementăm rezultatele găsite.

Totul e ok până când ajungi să evaluezi intervaluri mai exotice iar sistemul fie rămâne fără memorie fie timpul necesar calculelor e mai mare decât cel permis de provocare.

O abordare ceva mai șmecherească ar fi să calculezi doar primul radical, să îl rotunjești la o valoare întreagă, după care să îl incrementezi cu 1 și să îi calculezi pătratul până când acest pătrat iese din interval. Nu numai că o ridicare la pătrat e mai puțin solicitantă decât o extragere de rădăcină (cred), dar intervalul se parcurge mult mai rapid.

Zis și făcut doar că folosind acest algoritm deși dispar problemele legate de performanță nu sunt trecute decât 5 din 9 teste. Iar ca să vezi valorile de interval pentru care programul tău nu a trecut testul trebuie să folosești punctele strânse cu mult sârg iar tu, ca un programator zgârcit ce ești, nu vrei și pace să le cheltui!

Așa că te holbezi la monitor ca vițelul în poarta nouă și încerci să te bazezi pe experiență și pe intuiție și să recitești toate condițiile pentru a putea prinde potențialele cazuri specifice unde o dai în bară (de exemplu, e totul ok când intervalul testat e între 4 și 4?)

Dacă mi-ar fi zis cineva că în loc să mă joc o partidă de Dota2, să mă uit la ceva pe Netflix sau pur și simplu să mă culc o să stau sa calculez rădăcini în cod aș fi zis că își bate joc de mine. Dar în seara asta se pare că doar radicalii sunt întregi, nu și eu la minte...

[10 minutes later edit...]