Wednesday, February 20, 2013

FB Hacker Cup 2013 Question ( Solved )

QUESTION from FaceBOOK Hacker Cup 2013!!

When John was a little kid he didn't have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could... he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.

The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn't care about whether letters are uppercase or lowercase, so that doesn't affect the beauty of a letter. (Uppercase 'F' is exactly as beautiful as lowercase 'f', for example.)

You're a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

Input
The input file consists of a single integer m followed by m lines.

Output
Your output should consist of, for each test case, a line containing the string "Case #x: y" where x is the case number (with 1 being the first case in the input file, 2 being the second, etc.) and y is the maximum beauty for that test case.

Constraints
5 ≤ m ≤ 50
2 ≤ length of s ≤ 500

Example inputExample output

5
ABbCcc
Good luck in the Facebook Hacker Cup this year!
Ignore punctuation, please :)
Sometimes test cases are hard to make up.
So I just go consult Professor Dalves

Case #1: 152
Case #2: 754
Case #3: 491
Case #4: 729
Case #5: 646



################ SOLUTIONS ##################

#Python -- By Subir Sutradhar
#
# Find Beauty
#
import re
from collections import Counter
def beauty(getstring):
string = getstring.lower()
collector = []
for i in string:
collector.append(i)
collector.sort()
k = ''.join(collector)
fString = re.findall(r'[a-z]+', k)
final = ''.join(fString)
app = Counter(final)
counts = app.values()
counts.sort(reverse=True)
l = len(counts)
starter = 26
result = 0
for i in range(0,l):
result = result + (starter * counts[i])
try:
if counts[i+1] <= counts[i]:
starter = starter - 1
except Exception as e:
pass
return result

getbeauty = ['5',
'ABbCcc',
'Good luck in the Facebook Hacker Cup this year!',
'Ignore punctuation, please ',
'Sometimes test cases are hard to make up.',
'So I just go consult Professor Dalves']
for i in getbeauty:
print i
print
counter = 1
for i in getbeauty:
b = beauty(i)
if b == 0:
pass
else:
print "Case #"+str(counter)+" "+str(b)
counter +=1


>>>


<?php
/*

PHP -- By Ider Aghbal

*/

while(1) {
$in = trim(readline("\n\n****************************\n\n\t[+] Give me an input file\t: "));
if($in == '') die('Good Bye ');
if(is_file($in)) {
$content = file($in);
$count_lines = trim($content[0]);
if(is_numeric($count_lines)) {
if(count($content) < $count_lines-1) $count_lines = count($content)-1;
for($i = 1; $i <= $count_lines; $i++){
$line = strtolower(preg_replace("/[^a-z]/i","",$content[$i]));
$letters = array_count_values(str_split($line));
arsort($letters);
$beauties = 26;
$beauty = 0;
foreach ($letters as $count) {
$beauty += $count*$beauties;
$beauties--;
}
echo "\n [+] Case #$i: $beauty";
}
}
else echo "\n[-] The first line should be a number!";
}
else echo "\n[-] Please provide a valid file name!";
}
?>


>>>

'C' -- By Alok Saini

#include<stdio.h>
#include<string.h>
void sort(int *a)
{
int i,j;
for(i=0;i<=25;i++)
{
for(j=i+1;j<=25;j++)
{
if(a[j] > a[i])
{
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
}
}
int main()
{
int n,ns,i,j,k;
char str[500][500];
int a[26];
memset(a,0,26);
int ans=0,c=26;
scanf("%d *[^\n]",&ns);
for(i=0;i<ns;i++)
{
fgets(str[i],sizeof(str[i]),stdin);
}
for(i=0;i<ns;i++)
{
for(j=0;str[i][j]!=0;j++)
{
if((str[i][j] < 123)&&(str[i][j] > 96))
{
a[str[i][j]-97]++;
}
else if((str[i][j] < 91)&&(str[i][j] >64))
{
a[str[i][j]-65]++;
}
}
sort(a);
for(k=0;k<=25;k++)
{
if(a[k] != 0)
{
ans += (a[k]*c);
c--;
}
}
printf("Case #%d: %d\n",i+1,ans);
ans=0;
c=26;
memset(a,0,26);
}
return 0;
}


>>>

/*

'Java' -- By Watson Mist

*/

import java.util.*;
import java.io.*;
public class John{
public static void main(String aa[])
{
try{
File f = new File("file.txt");
Scanner console = new Scanner(f);
int n = console.nextInt();
for(int k=0;k<=n;k++){ // loop started

String input = console.nextLine();
char []str=input.toCharArray();
int count=0;
char ch;
Map<Character,Integer> charCounter=new HashMap<Character,Integer>();
// filtering the alphabets
for(int i=0;i<input.length();i++)
{
ch = str[i];
if (Character.isLetter(ch))
{ ch= Character.toLowerCase(ch);
if(charCounter.containsKey(ch))
charCounter.put(ch,charCounter.get(ch)+1);
else
charCounter.put(ch,1);
}
}
//sorting the input in array in ascending order
List <Integer> list = new ArrayList<Integer>();
for (Character m : charCounter.keySet())
list.add(charCounter.get(m));
Collections.sort(list);
// assigning the beauty in decreasing order and adding them
int beauty=26,sum=0;
for(int i=list.size()-1;i>=0;i--,beauty--)
sum=sum+(list.get(i)*beauty);
if(sum!=0)
System.out.println("Case #"+k+": "+sum);
}//loop ended
}catch(Exception ex){System.out.println(ex);}
}
}