Debugging help facebook hacakathon problemset

Question

I am trying to implement one of the simpler questions that was on the facebook hackathon 2013 http://argote.mx/?p=353"> here .

Excerpt: 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.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?

I've implemented my own solution based on mapping individual letters to a particular number.

Here's the code:

package samplecodes;

import java.io.BufferedReader;
import java.io.FileReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;

public class StringBeauty {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        ArrayList<String> input= new ArrayList<String>();
        try{

            FileReader f1 = new FileReader(args[0]);
            BufferedReader f = new BufferedReader(f1);
            String newLine;
            while ((newLine=f.readLine()) != null){
                   StringTokenizer st = new StringTokenizer(newLine);
                   while (st.hasMoreTokens()) {
                      String string= st.nextToken(); 
                      input.add(string);

                   }

                   for(String i: input)
                       System.out.println("input "+i);
                   ///printLower(input);

                   calculateStringBeauty(input);
                   input.clear();


}

        }

            catch(Exception e){
                e.printStackTrace();
        }
    }


    public static void calculateStringBeauty(ArrayList<String> input){

        /** mapping based on analysing input string**/

        HashMap<Character,Integer> map= new HashMap<Character,Integer>();
        map.put( Character.valueOf('a'),24);
        map.put( Character.valueOf('b'),25);
        map.put( Character.valueOf('c'),26);
        map.put( Character.valueOf('d'),1);
        map.put( Character.valueOf('e'),2);
        map.put( Character.valueOf('f'),3);
        map.put( Character.valueOf('g'),4);
        map.put( Character.valueOf('h'),5);
        map.put( Character.valueOf('i'),6);
        map.put( Character.valueOf('j'),7);
        map.put( Character.valueOf('k'),8);
        map.put( Character.valueOf('l'),9);
        map.put( Character.valueOf('m'),10);
        map.put( Character.valueOf('n'),11);
        map.put( Character.valueOf('o'),12);
        map.put( Character.valueOf('p'),13);
        map.put( Character.valueOf('q'),14);
        map.put( Character.valueOf('r'),15);
        map.put( Character.valueOf('s'),16);
        map.put( Character.valueOf('t'),17);
        map.put( Character.valueOf('u'),18);
        map.put( Character.valueOf('v'),19);
        map.put( Character.valueOf('w'),20);
        map.put( Character.valueOf('x'),21);
        map.put( Character.valueOf('y'),22);
        map.put( Character.valueOf('z'),23);
        int sum=0;
        for(String i: input){
        i=i.toLowerCase();
        //  System.out.println("i "+i);
        char[] array= i.toCharArray();

        for(char a: array){
        if(map.containsKey(a))
            sum+=map.get(a);
        else
            continue;
        }

        }
        System.out.print(sum);
        System.out.println();

        }
}

My solution seems to work perfectly for one of the test cases e.g . ABbCcc -> 152, this maps correctly However So I just go consult Professor Dalves -> 392 (according to my code). But is expected to return a beauty value of 646 according to the test case provided.

Any help in debugging my code or suggestions to improve my algorithm would be appreciated.

Answer 1

First of all, thank you for screwing with my mind :P

Now, the basic premiss as I understand it is, the more a character appears the more beautiful it becomes.

So with that in mind, you need to find away to calculate the number of times a single character appears. I was thinking of trying some fancy regular expression, but my regular expression skills are rather poor :P

Instead, I choose to create a simple object that mapped the character to the occurrence. In fact you don't actually need the character, but I used it for debug. You could simply get away with a Map<Character, Integer> instead....

You could also, just as easily use an int[] array of 26 elements. Each element represents a character (ie a == 0 and z == 25)

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Hack {

    public static void main(String[] args) {
        new Hack();
    }

    public Hack() {
        System.out.println("152 = " + getBeauty("ABbCcc"));
        System.out.println("754 = " + getBeauty("Good luck in the Facebook Hacker Cup this year!"));
        System.out.println("491 = " + getBeauty("Ignore punctuation, please :)"));
        System.out.println("729 = " + getBeauty("Sometimes test cases are hard to make up."));
        System.out.println("646 = " + getBeauty("So I just go consult Professor Dalves\t"));
    }

    protected int getBeauty(String value) {

        int sum = 0;
        value = value.toLowerCase();
        char[] values = value.toCharArray();
        Map<Character, Beauty> mapBeauty = new HashMap<>(26);
        for (char c : values) {
            if (Character.isLetter(c)) {
                Beauty beauty = mapBeauty.get(c);
                if (beauty == null) {
                    beauty = new Beauty(c);
                    mapBeauty.put(c, beauty);
                }
                beauty.add();
            }
        }

        List<Beauty> beauties = new ArrayList<>(mapBeauty.values());
        Collections.sort(beauties);
        int weight = 26;
        for (Beauty beauty : beauties) {
            int bweight = weight * beauty.getOccurance();
//            System.out.println(beauty.getValue() + " @ " + beauty.getOccurance() + " x " + weight + " = " + bweight);
            sum += bweight;
            weight--;
        }

        return sum;

    }

    public class Beauty implements Comparable<Beauty> {

        private char value;
        private int occurance;

        public Beauty(char value) {
            this.value = value;
            occurance = 0;
        }

        public char getValue() {
            return value;
        }

        public void add() {
            occurance++;
        }

        public int getOccurance() {
            return occurance;
        }

        @Override
        public int compareTo(Beauty o) {
            return o.getOccurance() - getOccurance();
        }

    }

}

Which outputs ...

152 = 152
754 = 754
491 = 491
729 = 729
646 = 646