Monday, October 12, 2015

PHP algorithm problem

Since I started to study PHP I focused on OOP, good practices, tools (Composer, Git), frameworks, integrating with other technologies etc. I was looking over a job listing and in order to be able to send your CV they were asking to solve a problem:

"Function f(n) counts how many times  character "1" appears in numbers from 1 to n.
 Example:  f(1)=1, f(2)=1, f(12)=5.
Question: What is the next "n" value for  which  f(n)=n?"

I've learned a lot about algorithms in high school and university using Pascal and C to implement them, but I never used PHP for this kind of task.

I wrote a small program and as usually opened the browser to see the results.

 <?php

function f($n)
{
    $count=0;
    for($i=1;$i<=$n;$i++)
    {
        $count+=substr_count((string)$i,'1');
    }
    return $count;
}
$n=2;
while(f($n)!=$n)
{   
    echo "n=". $n ." f(n)= " .f($n) ."<br>";
    $n++; 
}

 
The code was generating correctly the results for f(n) but after 200s  stopped without finding the number I was looking for:

n=6149 f(n)= 2885
n=6150 f(n)= 2886
n=6151 f(n)= 2888
n=6152 f(n)= 2889
n=6153 f(n)= 2890
Fatal error: Maximum execution time of 200 seconds exceeded in C:\Program Files (x86)\EasyPHP-DevServer-14.1VC11\data\localweb\test\index3.php on line 8

 ( I had set the maximum execution time to 200 seconds some times ago when I was doing a script which was downloading RSS feeds ).

OK, I will modify the script to save the output on a text file and I  will execute it from command line: C:\mypath\php script.php

$myfile = fopen("f(n).txt", "a") or die("Unable to open file!");
function f($n)
{
    $count=0;
    for($i=1;$i<=$n;$i++)
    {
        $count+=substr_count((string)$i,'1');
    }
    return $count;
}
$n=2;
while(f($n)!=$n)
{   

    fwrite($myfile,"n=". $n ." f(n)= " .f($n) .PHP_EOL );
    $n++;
   
}
fclose($myfile);


After I while I checked and the script was still runnig!!!  I started to think it is a trick question, maybe there is no number which solves the equation.

Maybe recursion will be faster??!! ... I did a recursive version of the script and using microtime() function I compared the speed for n=100  with the iterative version:

<?php
$time_start = microtime(true);

function f($n)
{
    if($n==1) {
        return 1;
    } else {
        return substr_count((string)$n,'1') + f($n-1);
    }
}
$n=2;

while(f($n)!=$n)
{   
    echo "n=". $n ."  f(n)=" . f($n) ."<br>";
    $n++;
    if($n==100) break;
}

$time_end = microtime(true);
$execution_time = ($time_end - $time_start);
echo "execution time=". $execution_time . "<br>";


Result for recursive:
     n=99 f(n)=20
     execution time=0.15200901031494


Result for iteration:

    n=99 f(n)=20
    execution time=0.054003000259399


So recursivity  is not the answer ...I need to rethink the way how I compute f(n) using the values already obtained and not taking it from scratch at each iteration.
Below is the solution, I used saving to file and execute  the script from command line because I was thinking that sill will take a lot of time, but no, it was lightning fast:

<?php
$myfile = fopen("rapid.txt", "a") or die("Unable to open file!");
$time_start = microtime(true);
$fn=1;
$n=2;
while($fn!=$n)
{   
    $n++;
    $fn=$fn + substr_count((string)$n,'1');
    fwrite($myfile,"n=". $n ." f(n)= " .$fn .PHP_EOL );
}

$execution_time = (microtime(true) - $time_start);
fwrite($myfile, $execution_time);
fclose($myfile);


Result:
    n=199981 f(n)= 199981
    3.6452090740204


I am not sure how relevant is this script for the activity at the respective job, but it was nice to  revisit algorithms.

No comments:

Post a Comment