Author Archives: Diogo Böhm

CodeJam Quickie: 2010 Africa – Qualification C

Whoa! Keeping up with the Africa 2010 contest, enter the Qualification C problem: T9 Spelling! It was a very fun problem and says:

The Latin alphabet contains 26 characters and telephones only have ten digits on the keypad. We would like to make it easier to write a message to your friend using a sequence of keypresses to indicate the desired characters. The letters are mapped onto the digits as shown below. To insert the character B for instance, the program would press 22. In order to insert two characters in sequence from the same key, the user must pause before pressing the key a second time. The space character ' ' should be printed to indicate a pause. For example, 2 2 indicates AA whereas 22 indicates B.

Reminds me of those days of texting through that old indestructible Nokias! Anyway, it’s not hard to do, but requires some data disposition. I chose to create a map to lists containing keys and the amount of keystrokes for every letter (including space, which would be 0), in order to simply match letters and print the sequence right along. Also, to know when to pause, I would check the last printed character before, so I can print a space and then the sequence.

Python code followsas usual:

# Build a map with the number to write and its repetition count
t9 = {
        "a" : ["2", 1], "b" : ["2", 2], "c": ["2", 3],
        "d" : ["3", 1], "e" : ["3", 2], "f": ["3", 3],
        "g" : ["4", 1], "h" : ["4", 2], "i": ["4", 3],
        "j" : ["5", 1], "k" : ["5", 2], "l": ["5", 3],
        "m" : ["6", 1], "n" : ["6", 2], "o": ["6", 3],
        "p" : ["7", 1], "q" : ["7", 2], "r": ["7", 3], "s": ["7", 4],
        "t" : ["8", 1], "u" : ["8", 2], "v": ["8", 3],
        "w" : ["9", 1], "x" : ["9", 2], "y": ["9", 3], "z": ["9", 4],
        " " : ["0", 1],
}

for case in range(1,int(raw_input())+1): # For all test cases
    message = raw_input()                # Get the list of words

    attr = t9[message[0]]                # Start with the first character
    t9str = attr[0]*attr[1]              # Initialize t9str with first T9 "word"

    for i in range(1,len(message)):      # From the second character on
        attr = t9[message[i]]            # Get the map values
        if t9str[-1] == attr[0]:         # If it's the same number as the last
            t9str += " "                 # Add a space

        t9str = t9str+attr[0]*attr[1]    # Append the new T9 "word"

    print "Case #%d: %s" % (case, t9str) # Reports results

It was the hardest of the Qualification problems, but still very easy to develop. 🙂 Fun! See ya tomorrow!

CodeJam Real Quickie: 2010 Africa – Qualification B

Hello there! Well, I can’t say anything about this problem other than it’s just super easy. Allow me to show you:

Given a list of space separated words, reverse the order of the words.

If that first sentence didn’t kill it for you, I don’t know what will. Anyway, the python code (validated, of course): 

for case in range(1,int(raw_input())+1):           # For all test cases
    words = raw_input().split(" ")                 # Get the list of words
    words.reverse()                                # Reverse word list
    print "Case #%d: %s" % (case, " ".join(words)) # Reports results, add spaces

Can’t get easier than that. And I actually had to learn that reverse() does not return the reversed list… in a perfect world, it could be solved within the print line, with:

    " ".join(raw_input().split(" ").reverse())

But, maybe next time… 😀 See ya, warned you it was real quick!

Logic voice analyzer, too much Code Jam

Hey there I was quite busy this weekend, working on so much Code Jam problems, as a way to study, but also to blog about new achievements. As an achievement, this very post is making use of Android’s excellent voice recognition feature. I’m dictating this through my cellphone while laying down on the bed, so I don’t have to type through my cheap tablet’s keyboard.

As I’ve mentioned earlier, I am working my way through Africa 2010 Code Jam challenges and I’m quite stuck at its last problem, which requires a full logic sentence analyzer in order to find out the correct results. It is a very interesting problem to solve and at the same time a very hard one. In fact, nobody solved the large inputs on the contest because of the complexities involved. The organizers claim to have solved it by using some quite obscure linear algebra methods which I’m not very familiar with, so I’ve decided to code my own version to the problem, which will be of course sub optimal but I think it can solve the problem fast enough. We’ll see.

If you’re wondering how could I achieve this level of writing through dictation, well… the bad news is every once in a while I have to stop and correct some misbehavior on the detection of my voice. Still it is very productive, and since I don’t want to stop dictating to correct my words, I’m actually thinking a lot before speaking in order to avoid detection dead ends.

Well, that’s it for today, I hope I can make my blog posts about the code jam problems I’ve already solved, and have a continuous chain of blog posts for this week. See ya 🙂

CodeJam Quickie: 2010 Africa – Qualification A

I didn’t knew that this contest existed! 😀 Well, found it on the front page, looking to be solved, so, let’s go! Its summary:

You receive a credit C at a local store and would like to buy two items. You first walk through the store and create a list L of all available items. From this list you would like to buy two items that add up to the entire value of the credit. The solution you provide will consist of the two integers indicating the positions of the items in your list (smaller number first).

It’s quite simple, and by smaller number first, they mean the position of the items, not its value. From that, the solution is trivial (already validated for the inputs):

 

for case in range(1,int(raw_input())+1):      # For all test cases

    credit = int(raw_input())                 # Get the test's credit
    raw_input()                               # Discard the number of items
    strItems = raw_input().split(" ")         # Get the items as strings
    items = []
    for item in strItems:
        items.append(int(item))               # Convert the items to integers

    out = False
    i = 0
    j = i+1
    for i in range(0,len(items)-1):           # first item can be any of the items, but the last
        for j in range(i+1,len(items)):       # the second will be any of the items after the first
            if items[i] + items[j] == credit:
                out = True                    # Found, get out
                break
        if out: break

    print "Case #%d: %d %d" % (case, i+1, j+1)# Reports results

Pretty easy! 😀 See you next post!

Some cleanup

Hey there, it’s hard to find time with Dexter and Breaking bad finales approaching! But they’ve already been dealt with for this week, so, more free time! 😀 Getting more tasks done, and not missing midnight, is quite an achievement for me.

Also, made a new commit from some of today and yesterday’s code on the new game, implemented a rough hitbox scheme, and still trying to debug it, works ok on bullets but not on enemies… perhaps it’s not a good approach to override a sprite’s rect() and I should implement my own collision functions, that look for hitboxes instead of them. Still, I can finally hit monsters and kill them (after the brief immunity period)!

I’m thinking about doing some cleanup tomorrow, on older posts, saw some code out of code tags, gonna check it out. I miss the CodeJam times, gotta do some more of those problems. Quite some work ahead!

 

Whoa… and we’re back!

Bah, the last couple of days almost made me die at HabitRPG, mostly because I must complete tasks before midnight (!) and I’ve got used to updating before going to sleep… and that was already late. I had something like 5HP left to avoid losing my beloved belongings, but tonight I made up and the experience gave me a new level (which restores all health), so I’m saved! 🙂 In a boring note, I could still have bought and used a potion, had the money to.

Been quite entertained with the new project, now I’m getting along with method encapsulation and developing resources as I need to. JAWS is awesome, but it lacks some features, such as hitboxes, and correctly being able to tell if a given element is partially inside the viewport … but I’m already implementing them, or didn’t look further into its code (the documentation is not as helpful as I need). JavaScript, in all its freedom, is a nice language but can be a pain sometimes too. Kudos to the guys that develop such great VMs to run all sorts of things, that must indeed be quite a challenge!

That’s it for today, just wanted to put some things out. Still gotta check Evernote everyday to get new blog subjects. I have so much to write about, but the lack of posts exists because I sometimes lack motivation to start the post… once I start writing, words flow nicely. 🙂

More on JavaScript classes, function warzone

Just like Python, JavaScript tends to create things once you mention them and they don’t yet exist. In my opinion, that’s a bit more harmful than useful, because there’s danger in accidentally creating new variables and values when you assumed it would be already holding a known value. Coming from a C/C++/Java background, I would expect some kind of error for the operation:

<html>
<body onload="testFunction()">
<div id="content"></div>

<script>
function testFunction() {
    function Test() {
        var somevar=1;
    };

    var test = new Test();
    test.somevar += 10;

    document.getElementById("content").innerHTML = ""+test.somevar;
}
</script>
</body>
</html>

In this context, somevar might not exist yet, and still, you’re adding 10 to its value! By printing it is possible to check that this var is a NaN, and no errors are issued. To properly (as I eventually found out by trying) get and set its value, one must create getter and setter functions, to “publicly interface” in other contexts:

<html>
<body onload="testFunction()">
<div id="content"></div>

<script>
function testFunction() {
    function Test() {
        var somevar=1;

        this.getSomevar = function() {
            return somevar;
        };

        this.setSomevar = function(value) {
            somevar = value;
        };
    };

    var test = new Test();
    test.setSomevar(test.getSomevar() + 10);

    document.getElementById("content").innerHTML = ""+test.getSomevar();
}
</script>
</body>
</html>

But hey, be careful when using “this”, its context is related to the current function, not the “class”, as one would think coming from a Java mindset. Using “this” inside class functions can cause undesired effects, such as defining new variables inside the “method” context and again we’ll run into the NaN problem:

<html>
<body onload="testFunction()">
<div id="content"></div>

<script>
function testFunction() {
    function Test() {
        var somevar=1;

        this.getSomevar = function() {
            return this.somevar;
        };

        this.setSomevar = function(value) {
            this.somevar = value;
        };
    };

    var test = new Test();
    test.setSomevar(test.getSomevar() + 10);

    document.getElementById("content").innerHTML = ""+test.getSomevar();
}
</script>
</body>
</html>

Pushed some updates to the game on github. 🙂

Classes in JacaScript? There’s a way

I was messing with my game prototype when something came along: how do I create objects in this thing? Many of the examples I’ve seen were quite weird, with functions creating new instances of things and being used to define objects. But what about real classes? Inheritance? After all, is there a standard in JavaScript?

Looks like it doesn’t, and many approaches seem to consist in implementing custom sugar functionality or using some weird techniques (from a C++/Java/Python developer’s point of view). I still want to check the examples to establish a memory footprint, because, apart from “static” (in JavaScript, prototype) functions there is no such thing as static beside a “global variable” (that might even contain a function). JavaScript is indeed an easy but weird language. 🙂

Anyway, my project was pushed to GitHub today, there is some basic functionality but not much beside some test bench. I’m working now to reach an architectural model for my objects with shallow inheritances to assure it “stays small” and following some best practices. The JavaScript/HTML5 Netbeans plugin is awesome! Also took some time to try jVI again, I’m more productive with it even with its performance penalty.

 

DVenn: venn diagrams with a cup of coffee

Long time ago, at one college night class, I was quite amazed that my teacher would have to draw over and over again Venn diagrams to explain logic problems and exercises. That class had a projector that was mainly used to display PPS slides. Since I was already quite proficient at Java and Swing development, I started to develop an application to help him by rendering the diagrams based on a logic expression without the need to draw the whole thing on the blackboard.

dvenn

That application was called DVenn and I guess it still helps him on classes. It can present up to 4-way diagrams and automatically adjust the render based on the number of variables. We published a paper about it and presented at some event. I’ve put it on github. I guess it’s still in portuguese, but there’s not much to translate even, so it should be easy to port around.

Looking at the code right now, it seems quite bulky for what it does, but I’m OK with it. Perhaps some day I’ll do some refactoring and call it done.

Don’t break the owl

Well, I’m struggling to create original content for the blog, but I’m doing my best to write every day (okay, not my best, it’s not the plan to kill myself for it… for now :). Seinfeld’s “Don’t break the chain” is a nice perseverance exercise, and here I am, trying not to break it.

I’ve also been dedicating at least a lesson everyday on Duolingo, and its awesome Android app. HabitRPG says I’m “green” with a score of 1.6 at it, so I guess it’s been ok. Plan to finish the English module, which I’m halfway through, and then starting a different language (perhaps German or even Spanish, to improve some of my beginner level). I highly recommend it if you’re interested in studying new languages, since it can evaluate some of your spelling (at the Web app), has reminders to bug you to study everyday (and avoid hurting the owl’s feelings) and is gamified, so you can actually compete with friends while studying. 🙂

I’ll put some subjects at my Keep so I don’t need to just write about something on the spot. I can do it, but lacks quality… anyway, baba, the chain lives to see another day.