Tag Archives: technology

Code Jam 2010 Africa – Problem C

Whoa, that was a tough problem. Ironically it’s called Qualification Round:

You’ve just advanced from the Qualification Round of Google Code Jam Africa 2010, and you want to know how many of your fellow contestants advanced with you. To give yourself a challenge, you’ve decided only to look at how many people solved each problem.

The Qualification Round consisted of P problems; the ith problem was fully solved by Scontestants. Contestants had to solve C problems in order to advance to the next round. Your job is to figure out, using only that information, the maximum number of contestants who could have advanced.

Well, at first it seems pretty simple, but there is quite some math involved. The first case of the example input is easy to solve, but the second will most likely get you scratching your head thinking “where the #$%* that number came from” (at least I did). 🙂 Well the secret is that you should not look at the inputs as they are, but instead, find the maximum amount of solved problem combinations there are.

I studied a bit but still could not solve it, and surrendered by checking the contest analysis. It was quite complicated to understand, until they wrote about a clever solution from the winning candidate: it consisted in lowering the possible scores to max at the division of the scores by the amount of needed problems. Just do it (don’t ask why) until there are no scores over the result of that division. That same result will be the answer. Creepy! Python code time:

for case in range(1,int(raw_input())+1):          # For all test cases
    info = map(int, raw_input().split(" "))       # Get test case information
    problems = info[0]                            # Fetch number of problems
    needed = info[1]                              # Fetch number of needed problems to pass
    results = info[2:]                            # Fetch results for each problem

    qualified = 0                                 # Initialize our results

    if (problems == needed):                      # For this case, we can expect
        results.sort()                            # as many contestants as the
        qualified = results[len(results)-needed]  # least solved problem

    else:                                         # For this case, we use a solution
        out = False                               # similar to the winning one
        while not out:
            out = True
            qualified = sum(results)/needed       # Reduce the number of possible qualifiers
            for i in range(len(results)):         # And for all results
                if results[i] > qualified:        # Limit their values to the current qualifiers
                    results[i] = qualified
                    out = False                   # Until they all "match" the qualifiers number

    print "Case #%d: %s" % (case, str(qualified)) # Report results

Interestingly enough, this code is smaller than the last, and solves a more complicated problem (at least in my opinion). I don’t think I could have done a better job on this one. 🙂 That’s the beauty in learning!

CodeJam Quickie: 2010 Africa – Problem B

Howdy! This time, problems started getting more and more complex, and that’s good, because I like the challenge! The next problem is Get to Work:

You work for a company that has E employees working in town T. There are N towns in the area where the employees live. You want to ensure that everyone will be able to make it to work. Some of the employees are drivers and can drive P passengers. A capacity of P == 1 indicates that the driver can only transport themselves to work. You want to ensure that everyone will be able to make it to work and you would like to minimize the number of cars on the road.

You want to calculate the number of cars on the road, with these requirements:

  • Every employee can get to town T.
  • The only way an employee may travel between towns is in a car belonging to an employee.
  • Employees can only take rides from other employees that live in the same town.
  • The minimum number of cars is used.

Find whether it is possible for everyone to make it to work, and if it is, how many cars will end up driving to the office.

Whoa, that’s way more complex than the other problems, but still, not that hard! What we need to do is: check who are drivers and passengers for each town (since they can only help same town buddies), if the total capacity of cars from a town is inferior to the number of passengers, the problem cannot be solved and so, reported as “IMPOSSIBLE”. If we can carry everyone, start filling the cars from the “minivan” (can carry more passengers) to the “mini cooper”. 😀 That way we can make sure there are fewer cars on the road.

Some rough, but commented, and validated (!) python code follows:

for case in range(1,int(raw_input())+1):                  # For all test cases
    town_len, office = map(int, raw_input().split(" "))   # Get amount of towns and office

    carriers = [[] for x in xrange(town_len)]             # Create new lists for every town
    capacities = town_len * [0]                           # Initialize "capacity of transportation"
    payload = town_len * [0]                              # Initialize "cargo" for each town

    for i in range(int(raw_input())):                     # Get and go through employee list
        town, capacity = map(int, raw_input().split(" ")) # Get the current employee info
        if town == office:                                # If employee is from office town
            continue                                      #   No need to commute, ignore

        town -= 1                                         # Adjust "town" to zero-based index
        payload[town] += 1                                # Employee needs to commute, count

        if capacity != 0:                                 # If employee has a car
            capacities[town] += capacity                  # Add to our capacities for the town
            carriers[town].append(capacity)               # Append its car capacity

    resultStr = ""                                        # Create our result string

    for i in range(town_len):                             # For all towns
        if capacities[i] < payload[i]:                    # If we can't carry everyone
            resultStr = "IMPOSSIBLE "                     #   declare it impossible, give up
            break;

        cars = 0                                          # We can carry, start with 0 cars
        carriers[i].sort()                                # Sort and reverse the car list
        carriers[i].reverse()
        for car in carriers[i]:                           # So we can start from the bigger ones
            if (payload[i] <= 0):                         # If we're carrying everybody already
                break                                     #  we're done for this town

            payload[i] -= car                             # Else, fill a car, report as being used
            cars += 1

        resultStr += str(cars)+" "                        # Add this town filled vehicles

    print "Case #%d: %s" % (case, resultStr[:-1])         # Report results, remove last space

As the last problem, the same can be told about this code. There are many ways to improve its performance, but this way it can already solve the large inputs in an instant. Bitbangers apart, it solves the problem and everybody gets happy. Also, I think it is quite clear to understand, even more with the comments. 🙂 Bye!

CodeJam Quickie: 2010 Africa – Problem A

Hey there! So, another day, another problem! This time, it is called Odd Man Out, and it is quite simple to “get”:

You are hosting a party with G guests and notice that there is an odd number of guests! When planning the party you deliberately invited only couples and gave each couple a unique number C on their invitation. You would like to single out whoever came alone by asking all of the guests for their invitation numbers.

Well, just get the number that’s not duplicated! There are many ways to do this, be it counting the occurrences of every member of the list and finding the “odd man”, or the way I did, which is basically some push and pop into a new list. Python code follows:

for case in range(1,int(raw_input())+1):        # For all test cases
    raw_input()                                 # Discard the guest list size
    guests = raw_input().split(" ")             # Get the list of guest IDs

    guestList = []                              # Create an empty guest list

    for guest in guests:                        # For all guests
        if guestList.count(guest) > 0:          # If it's already on the final list
            guestList.remove(guest)             #    if is a couple, remove
        else:                                   # If it's not in the list yet
            guestList.append(guest)             #    Add its ID

    print "Case #%d: %s" % (case, guestList[0]) # Reports results

Needless to say, I bet there are many ways to improve this algorithm, but for this problem it performs decently, so no worries (unless you’re a hardcore bit banger). 🙂 See you tomorrow!

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!

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.