Facebook Hacker Cup 2013 Qualification Round - Beautiful Strings Problem

29 Jan 2013 - West Java

The problem can be found here

TLDR

Given a string (case insensitive), find the maximum possible beauty of the string. A beauty of each letter is an integer between 1 and 26. For example:

# Input
ABbCcc

# Output
152

Since we're asked to find the maximum possible, I think the solution below would be acceptable:

  1. Order the letter by count. Since 'C' and 'c' is the same, worth to lowercase all letters.
  2. The most common letters weighted to 26, the 2nd one to 25, etc.

In the example above it would be:

letter  count  weight (count*weight)
c       3      26      78
b       2      25      50
a       1      24      24
                       152 (sum)

Example Input and Output

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

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

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.

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

Solution in Python

First, you need to know how to read input from stdin and output to stdout with given format. You can read my post on how to read from stdin in Python. It should be something like:

m = int(sys.stdin.readline())
for i in range(m):
    # Read each test case here
    # and output the result

    # Assuming y will hold the result

    print "Case: %d %d" % (i+1, y)

On each iteration, read a test case with readline and strip the heading and trailing whitespaces. Also, make sure we later process only alphabet that already in lowercase.

s = [l for l in sys.stdin.readline().strip().lower() if l in ALPHABET]

Now we need to get the counts on each letter. There's collections module with Counter class to easily count hashtable objects. Here's an example what Counter can do:

>>> from collections import Counter
>>> Counter('abbccc')
Counter({'c': 3, 'b': 2, 'a': 1})
>>> Counter(['a', 'b', 'b', 'c', 'c', 'c'])
Counter({'c': 3, 'b': 2, 'a': 1})
>>> Counter(['a', 'b', 'b', 'c', 'c', 'c']).most_common()
[('c', 3), ('b', 2), ('a', 1)]

See, how easily is that! Now we need to iterate the Counter object, which sorted already, and count the beauty of each letter and sum it. Inside the for loop, the code would be:

b, y = 26, 0
    s = [l for l in sys.stdin.readline().strip().lower() if l in ALPHABET]
    s = Counter(s).most_common()
    for k, v in s:
        y = y + v * b
        b = b - 1

The y is the maximum-beauty to be printed. Now the final result of the code is looked like:

#!/usr/bin/env python
 
import string
import sys
 
from collections import Counter
 
ALPHABET = string.ascii_lowercase
 
def main():
    m = int(sys.stdin.readline())
    for i in range(m):
        b, y = 26, 0
        s = [l for l in sys.stdin.readline().strip().lower() if l in ALPHABET]
        s = Counter(s).most_common()
        for k, v in s:
            y = y + v * b
            b = b - 1
 
        print "Case #%d: %d" % (i+1, y)
 
 
if __name__ == '__main__':
    main()

Now chmod +x the file above. Download the input file (or, you can use example input above). And run it:

$ cat input.txt | ./beautiful_strings.py

Hope it helps!

Comments

comments powered by Disqus