GCJ: Alien Numbers

July 10th, 2008 § 3 comments

In these days I started to study python. That’s a very cool language and I have lots of things to learn, I need exercise. What is better than google code jam to practise?

I will share with you my solution for the first of the “Practice Problems”, it’s about aliens’ numeral system :^) and I’ve, obviously, written my solution in python ;^)

I’m posting it to discuss them with you, maybe I’ll do the same when I’ll have the time to do the others. It doesn’t want to be a spoil so if you want to solve this alone just go and code, when you’ve finished you can come back and comment my code and tell me if you coded a better one :^)

Well, the text of the problem is:

Problem

The decimal numeral system is composed of ten digits, which we represent as “0123456789” (the digits in a system are written from lowest to highest). Imagine you have discovered an alien numeral system composed of some number of digits, which may or may not be the same as those used in decimal. For example, if the alien numeral system were represented as “oF8″, then the numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). We would like to be able to work with numbers in arbitrary alien systems. More generally, we want to be able to convert an arbitrary number that’s written in one alien system into a second alien system.

Input

The first line of input gives the number of cases, N. N test cases follow. Each case is a line formatted as

alien_number source_language target_language

There are some other things, if you want you can read the whole text here.

Ok? That’s should be not so difficult. I’m human, coder and engineering student, I hear aliens speaking every day, it’s ok. The problem is to speak with them :^)

We’re going to:

  • Get the number we want convert from system1 to system2
  • Convert to decimal that number from system1, we’re human and used to see decimal number :^)
  • We know what number it is, we can now convert the decimal number to system2

Well try to think on how we convert from binary to decimal and viceversa, or from hex to decimal and viceversa…

Here is my implementation:

class aliensys(object):
    def __init__(self, stringa):
        self.symbols = list(stringa)
        self.N = len(self.symbols)
    def a2d(self, n):
	"Convert n from alien to decimal"
        s = 0
        n = list(n)
        n.reverse()
        for i in xrange(0, len(n)):
            s += self.symbols.index(n[i])*self.N**i
        return s
    def d2a(self, n):
	"Convert n from decimal to alien"
        s = ''
        while n>=1:
            r = n%self.N
            n/=self.N
            s = self.symbols[r]+s
        return s
    def convert(self, n, target): # target must be an aliensys
        to = self.a2d(n)
        return target.d2a(to)
 
 
def solve(string):
    s = string.replace('\n', '')
    s = s.replace('\r', '')
    n, src, tgt = s.split(' ') # number, source, target
    src = aliensys(src)
    tgt = aliensys(tgt)
    return src.convert(n,tgt)

And it’s so simple to use:

>>> solve('CODE O!CDE? A?JM!.')
'JAM!'

ps: did you see that? how WP-syntax is highlighting “string” and “self” on my script? They’re not keyword in pyhton, str is, it shouldn’t do that… I’ve to fix this :\

yield ‘Bye’

Tagged , , ,

§ 3 Responses to GCJ: Alien Numbers"

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>