Rizky Wardana

Facebook Hacker Cup 2013 Qualification Round - Beautiful Strings Problem

2013-01-29T00:00:00-08:00

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:

Order the letter by count. Since 'C' and 'c' is the same, worth to lowercase all letters.
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!

Read from stdin in Python for Common Algorithm Challenges

2013-01-23T00:00:00-08:00

Read from stdin in Python for Common Algorithm Challenges

23 Jan 2013 - West Java

There are many sites dedicated to host algorithm challenges (e.g UVa Online Judge, Top Coder, Sphere online judge (spoj)). I love spoj because they offer various languages for solution submission. Previously, I learned algorithm in UVa online judge using C++ (i.e. the most popular one in UVa beside Java). Common problem encourage us to read from stdin and there two common patterns:

Read each line as a test case
Read first line as N and N test cases follow.

For the first pattern, a typical problem might be looked like:

# Input. Read each line as x, y and print the sum
3 2
7 8
10 15

# Expected output
5
15
25

And you can solve the problem in C++ using the following:

#include <cstdio>

int main() {
    int x, y;

    while (scanf("%d", &x) != EOF) {
        scanf("%d", &y);
        printf("%d\n", x + y);
    }
}

So how we can do the above in Python? Well, fortunately we can use sys.stdin like below:

import sys

def main():
  for line in sys.stdin:
    x, y = line.split(' ')
    print int(x) + int(y)


if __name__ == '__main__':
  main()

I'm not sure whether this approach is the Pythonic-way. But worked for me pretty well. Let me know in case if you have a better approach.

For the last problem pattern, below is a typical one:

# Input. Read first line as N, N lines follow
# for each test case. For example we still
# asked to sum two ints on each test case.
3
3 2
7 8
10 15

# Expected outupt
5
15
25

It's possible to use previous approach and checking the singular value per line. Or, you can read the first line, which is N, once and loop until N.

import sys

def main():
  n = int(sys.stdin.readline())

  for i in range(n):
    x, y = sys.stdin.readline().strip().split(' ')
    print int(x) + int(y)


if __name__ == '__main__':
  main()

Hope it helps!

Things I did when I Learned Python For the First Time

2013-01-20T00:00:00-08:00

Things I did when I Learned Python For the First Time

20 Jan 2013 - West Java

When I decided to learn Python, I was looking for online tutorial that easy to grasp. I found following free books helped a lot:

These two books are easy to understand. You need to avoid copy-paste whenever code is presented. This will help you to familiarize Python syntax.

After that I was looking for code convention in Python. I found David's Goodger' Presentation is much enjoyable to read than PEP 8 Guide. But I recommend you to read both.

So what's next? Of course, type more code in Python. I started by writing solution for simple problem in Python. Simple problems can be your homework or known algorithm that you can find in Wikipedia. You already know code convention, but you need to know common structure for Python project. To get common structure that comforts best-practice, I searched popular Python-projects in Github, found some awesome projects and trying to understand the structure.

I know this will take time, months or even years. But there's no shortcut to be a Python's Guru.

I hope this post will help you to start learning Python. Happy learning!

Hello World

2013-01-20T00:00:00-08:00

Hello World

20 Jan 2013 – West Java

Hello World! This is my first post on my Jekyll-powered blog. What motivated me to blog like a hacker was, of course, Tom Preston-Werner’s post. My blog is cloned from Tom’s blog with tweaked layout and styles. So here’s what I did to get my blog up:

$ mkdir rizkywardana.github.com
$ cd rizkywardana.github.com
$ git clone https://github.com/mojombo/mojombo.github.com .
$ rm -rf _site
$ rm -rf _posts/*

After that, I created rizkywardana.github.com repository, added remote origin, as usual, on my local repo, and tweaked the layout and stylesheet. If you need to tweak more, jump into Jekyll wiki.

So what’s I’m going to write on this blog? Well, I’m thinking to write about my experiences learning Python and algorithm.