Home ›

facebook Hacker Cup 2012 Qualification Round - alphabet soup

Christian Harms's picture
by Christian Harms on Tue, 01/24/2012 - 21:57
in

This year qualification round had three problem. The easy one was Alphabet Soup - classic character counting problem.

Image

problem description

Alfredo Spaghetti really likes soup, especially when it contains alphabet pasta. Every day he constructs a sentence from letters, places the letters into a bowl of broth and enjoys delicious alphabet soup.

Today, after constructing the sentence, Alfredo remembered that the Facebook Hacker Cup starts today! Thus, he decided to construct the phrase "HACKERCUP". As he already added the letters to the broth, he is stuck with the letters he originally selected. Help Alfredo determine how many times he can place the word "HACKERCUP" side-by-side using the letters in his soup.

Image

solution in javascript

First you have to count all digits from the input line. For the result you have to get the lowest character count for the word HACKERCUP - but keep in mind that C is twice in the string.

  1. function task(input){
  2.         var map = {};
  3.        
  4.         //Count chars
  5.         for(var i=0;i<input.length;i++){
  6.                 var char = input[i];
  7.                 if(!map[char]){
  8.                         map[char] = 1;
  9.                 }else{
  10.                         map[char] = map[char]+1;
  11.                 }
  12.         }
  13.  
  14.         //Check check HackerCup
  15.         var testStr = "HACKERCUP";
  16.         var wordCount = 0;
  17.        
  18.         while(true){
  19.                 for(var i=0;i<testStr.length;i++){
  20.                         var char = testStr[i];
  21.                         if(map[char]>0){
  22.                                 map[char] = map[char]-1;
  23.                         }else{
  24.                                 return wordCount;
  25.                         }
  26.                 }
  27.                 wordCount++;
  28.         }
  29.         return input;
  30. }

This solution (here only the solve-function) from tobias made the qualification point! I built an improved solution with more javascript-like usage of the object. For shorter and improved code I used the no-go with statement to get the Math.min( H,A,C,K,E,R,C,U,P )-result. You can test the code live on codejamer.com.

input data result data 
5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP
 
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1

  1. ({
  2.   //using the codejamer.com framework
  3.   init: function(input) {
  4.     input.shift();
  5.     return input;
  6.   },
  7.   task: function(input, return) {
  8.     var i, d = {}, h = "HACKERCUP";
  9.    
  10.     //init the digit counter
  11.     for (i=0; i < h.length; i++){ d[h[i]]=0; }
  12.  
  13.     //count all characters
  14.     for (i=0; i < input.data.length; i++){
  15.       d[input.data[i]] += (input.data[i] in d);
  16.     }
  17.     d.C = Math.floor(d.C/2);
  18.  
  19.     //get the minimal word count for HACKERCUP
  20.     with (d) return ('Case #' + input.index + ': ' + Math.min( H,A,C,K,E,R,C,U,P ));
  21.   }
  22. })

top score solution in java

The top score coder had used java or c++ for solving the problem. The code in the TOP10 is larger than the short javascript solution but works the same way. On place 9 I found a readable java version with a simple array for the 26 defined characters.

  1. import java.util.Scanner;
  2. public class AlphabetSoup {
  3.         public static void main(String[] args) {
  4.                 Scanner in = new Scanner(System.in);
  5.                 int t = in.nextInt();
  6.                 in.nextLine();
  7.                 for (int c = 1; c <= t; c++) {
  8.                         String s = in.nextLine();
  9.                         int[] ct = new int[26];
  10.                         for (int i = 0; i < s.length(); i++) {
  11.                                 if (s.charAt(i)==' ') continue;
  12.                                 int cc = s.charAt(i)-'A';
  13.                                 ct[cc]++;
  14.                         }
  15.                         int min = 10000;
  16.                         min = Math.min(min, ct['H'-'A']);
  17.                         min = Math.min(min, ct['A'-'A']);
  18.                         min = Math.min(min, ct['C'-'A']/2);
  19.                         min = Math.min(min, ct['K'-'A']);
  20.                         min = Math.min(min, ct['E'-'A']);
  21.                         min = Math.min(min, ct['R'-'A']);
  22.                         min = Math.min(min, ct['U'-'A']);
  23.                         min = Math.min(min, ct['P'-'A']);
  24.                         System.out.printf("Case #%d: %d%n", c, min);
  25.                 }
  26.         }
  27. }

Next part will be my winning entry for the billboard entry.

Comments

Anonymous's picture
You wrote a blog post on
Anonymous (not verified) - Wed, 01/25/2012 - 17:27

You wrote a blog post on counting the number of letters in a word?

Christian's picture
read the article carefully
Christian (not verified) - Thu, 01/26/2012 - 07:17

It is a blogpost about counting random sorted word-letters in a string - because this was the problem asked in the facebook hackercup.