Some programming problems

I am not a big fan of programming competions, but i do love good challenges and interesting problems. Google Code Jam (https://code.google.com/codejam/) is comming soon and i decide to participate in a normal way. I am not that hardcore programmer 24/7.

For practice I did two problems: File Fix-it and All Your Base. As i was so lazy, i used Python. I want to comment my reasoning for solving each of the problems.

  • File Fix-It: The problem consisted on on telling the minimum number of mkdirs (it creates folders one by one) to create the given directories. In each case was given the already done directories and the ones we needed to create. Creating directories can be viewed as building a tree. I simulated that using a dictonary.
#!/usr/bin/python
# -*- coding: utf-8 -*-

from sys import stdin

def add_directory(directory_hash, path, done):
    directory = ''
    created_directories = 0
    for node in path.split('/')[1:]:
        directory += '/' + node
        if not directory_hash.has_key(directory):
            directory_hash[directory] = True
            created_directories += 1
    return 0 if done else created_directories

if __name__ == "__main__":
    ncases = int(stdin.readline())

    for ncase in xrange(ncases):
        case = stdin.readline()
        done_nodes, left_nodes = map(int, case.split(' '))

        directory_hash = dict()

        for done_node in xrange(done_nodes):
            add_directory(directory_hash, stdin.readline().replace('\n',''), True)

        created_directories = 0

        for left_node in xrange(left_nodes):
            created_directories += add_directory(directory_hash, stdin.readline().replace('\n',''), False)

        print 'Case #' + str(ncase + 1) + ': ' +  str(created_directories)
  • All Your Base: A little more complicated problem. The input was an alphanumeric string and the output a mapping each symbol of it to de minimum number, in any base, expresed as a decimal. The minimum base was 2 and the first symbol can’t be 0. The solution was quite simple, map the first symbol to 1, after that, map from left to right each diferent symbol to 0, then 2, then 3 and so on. Finally change the number to base 10.
#!/usr/bin/python
# -*- coding: utf-8 -*-

from sys import stdin

if __name__ == "__main__":
    ncases = int(stdin.readline())

    for ncase in xrange(ncases):
        case = stdin.readline()

        mapped_number = 0
        symbol_number = dict()
        symbol_number[case[0]] = 1

        for symbol in case[1:-1]:
            if not symbol_number.has_key(symbol):
                symbol_number[symbol] = mapped_number
                mapped_number = 2 if mapped_number ==  0 else mapped_number + 1

        if mapped_number == 0:
            symbol_number[case[0]] = 1
            case.replace(case[0], '1')
            mapped_number = 2

        to_pow = len(case) - 3
        result_decimal = 1 * pow(mapped_number, to_pow + 1)

        for symbol in case[1:-1]:
            result_decimal += (pow(mapped_number, to_pow) * symbol_number[symbol])
            to_pow -= 1

        print 'Case #' + str(ncase + 1) + ': ' +  str(result_decimal)

Both handled the large inputs and are quite efficient. The teaching here is that before doing any code is important to reason how to solve the problem.
Lets see how i perform in the Code Jam :3.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s