As we know that Facebook's online programming contest known as "Hacker Cup" is going on. I solved first question yesterday and wanted to share the algorithm with you. I will certainly not share the code until the Contest ends. I will edit the same post once the contest gets over.
But For now I can tell you that I have used brute force algorithm with an optimization which will give me result in lesser complexity. I tried to formulate a mathematical equation but failed to solve it mathematically because of the space problem. A space will not occur in case of new line is added.
Edit[3:40 PM 22-January-2012] ::
Anyways wait for the hacker cup to end only then I can conceal my algorithm. For now I can give you a hint that use brute force with doing some range based optimization or find the maximum size a font can have to accommodate all characters and then decrease font size and check if it is fitting into the billboard.
Edit[6:23 PM 22-January-2012] ::
Well because of overwhelming page views of this particular post in past 3 hours. I will elaborate my algorithm a little bit more.
take an example:
10 20 MUST BE ABLE TO HACK
Lets not treat this as sentence and lets assume that each character is a square and we have to accommodate each square We will have a formula
C(h)² - (H/h)*(h)² ≤ W*H
where C is number of characters in the sentence H is Height of billboard and W is width of billboard. 'h' would be the font size we need to get.
Remember by using this equation you will get maximum size that can be attained by the font but not the actual once you will get 'h' you will iterate each time that is it the correct solution and each time reducing h by 1. finally you will get the maximum font size which can be accommodated on the billboard.
So in our example :
C = 20
H = 20
W = 10
putting it in our equation
20*h*h - H*h ≤ 200
we can find integer h can be 3 at max.
now we will check is 3 is working as brute-force testing function if it fails we will test it for 2 and bingo we will get our right answer.
Edit[4:18 PM 24-January-2012] ::
Source code of my solution for more clarity
##############
#Puneet Singh#
##############
use POSIX;
open(MYINPUTFILE, "<$ARGV[0]");
# This is a Perl code by the way
@text=<MYINPUTFILE>;
$T= shift(@text);
$p=0;
foreach (@text)
{
$line=$_;
@parse=split(/[\n]/,$line);
$Width = shift(@parse);
$Height = shift(@parse);
$test= join(" ",@parse);
$changed=0;
#print $line;
$a = ($test =~ tr/[a-zA-Z0-9]//);
$b = ($test =~ tr/[ ]//) + 1;
$c = ($test =~ tr/[a-zA-Z0-9 ]//);
$x = int(($Height+sqrt($Height*$Height+(4*$c*$Width*$Height)))/(2*$c));
print $x;
$lineno = int($Height/$x);
$mciol = int($Width/$x);
$chars = $line*$mciol;
#print $x." ".$test." ".$mciol." ".$lineno." ". $b." ". $a."\n";
while(!check($test,$mciol,$lineno, $b, $a))
{
#print $x." ".$test." ".$mciol." ".$lineno." ". $b." ". $a."\n";
$x--;
$lineno = int($Height/$x);
$mciol = int($Width/$x);
$chars = $line*$mciol;
}
$p++;
#print $mciol." ";
print "Case #$p: ".$x."\n";
}
sub check{
$line=$_[0];
$maxchars = $_[1];
$lines = $_[2];
$wordcount = $_[3];
$charcount = $_[4];
@parse=split(/[]/,$line);
for($i=0;$i<$lines;$i++)
{
$word=shift(@parse);
#print "$word";
$cnt=($word =~ tr/[a-zA-Z0-9 ]//);
#print " --- ".$cnt ." --- ". $maxchars;
if($cnt > $maxchars)
{
return 0;
}
$word=@parse[0];
$newcnt=$cnt+($word =~ tr/[a-zA-Z0-9 ]//)+1;
$first=0;
while($newcnt<=$maxchars)
{
$word=shift(@parse);
#print " $word";
$word=@parse[0];
$newcnt=$newcnt+($word =~ tr/[a-zA-Z0-9 ]//)+1;
$cnt=$cnt+($word =~ tr/[a-zA-Z0-9 ]//);
}
out:
if($cnt == $charcount)
{
goto loop;
}
#print " ::: ".$newcnt;
$cnt=0;
#print "\n";
}
loop:
$last = @parse[0];
if($last)
{
return 0;
}
else
{
return 1;
}
}
Only 3 isn't the correct answer for this, it's 2. When running 3 through that formula it comes back true.
ReplyDeleteI think you will understand my algo more clearly by reading my code which I posted now as the qualification round is over
ReplyDeleteNo doubt what you submitted was correct, but that formula in the blog isn't correct. Additionally your submitted code is not the same as the source code you published here.
ReplyDeleteSubmitted Code:
#print $line;
$a = ($test =~ tr/[a-zA-Z0-9]//);
$b = ($test =~ tr/[ ]//) + 1;
$c = ($test =~ tr/[a-zA-Z0-9 ]//);
$x = int(sqrt($Width*$Height/$c));Blog Code: #print $line;
$a = ($test =~ tr/[a-zA-Z0-9]//);
$b = ($test =~ tr/[ ]//) + 1;
$c = ($test =~ tr/[a-zA-Z0-9 ]//);
$x = int(($H+sqrt($H*$H+(4*$c*$Width*$Height)))/(2*$c));
Sorry last post wasn't formatted right.
ReplyDeleteSubmitted Code:#print $line;$a = ($test =~ tr/[a-zA-Z0-9]//);$b = ($test =~ tr/[ ]//) + 1;$c = ($test =~ tr/[a-zA-Z0-9 ]//);$x = int(sqrt($Width*$Height/$c));
Blog Code:
#print $line;$a = ($test =~ tr/[a-zA-Z0-9]//);$b = ($test =~ tr/[ ]//) + 1;$c = ($test =~ tr/[a-zA-Z0-9 ]//);$x = int(($H+sqrt($H*$H+(4*$c*$Width*$Height)))/(2*$c));
Yes that was a mistake (the code I submitted) . I corrected it afterwords but what is once submitted I can't change it. though my submitted code gives me right answer for the time being but it is not complete it can give sometimes incorrect answer sometimes.
ReplyDeleteI will update this post to explain the basis of my theory and formula.