Monthly Archives: March 2013

CodeJam Online Competition for Veterans 2013 C: Ocean View

Gotchas all around! 😀 In fact, this time I’ve struggled with the algorithm to solve the problem. My first attempt did work, but could only solve correctly the small input of the problem, entitled Ocean View. It’s not complicated as a problem, but this time you need to think a bit more to get there:

Ocean View is a small town on the edge of a small lake, populated by people with high self-esteem. There is only one street in this town, Awesome Boulevard, running away from the lake on the west towards the hill in the east. All of the houses in Ocean View are situated along one side of Awesome Boulevard and are numbered starting at #1 on the edge of the lake all the way up to #N at the foot of the hill.

Each resident of Ocean View wants to be able to see the lake. Unfortunately, some of the houses may be blocking the view for some of the higher numbered houses. House #A blocks the view for house #B whenever A is smaller than B, but house #A is as tall as or taller than house #B.

Tired of hearing complaints about obstructed views, the Supreme Ruler of Ocean View has decided to solve the problem using his favorite tool of governance — violence. He will order his guards to destroy some of the houses on Awesome Boulevard in order to ensure that every remaining house has a view of the lake. Of course, if he destroys too many houses, he might have a rebellion to deal with, so he would like to destroy as few houses as possible.

What is the smallest number of houses that need to be destroyed in order to ensure that every remaining house has an unobstructed view of the lake?

It needs a little bit of thinking to understand (not if you have previously worked on it), but the general concept is: you have to find the longest increasing subsequence in a list of numbers. Yes, I didn’t know how “classic” it was, it even has its own Wikipedia entry. My lack of knowledge led me to my first solution, coded in a way that it would just solve the problem, even if not optimized:

for case in range(1,int(raw_input())+1):                #For all test cases
        size = int(raw_input())                         #Get the case size
        heights = []
        paths = []

        for i in raw_input().split(" "):                #Split the case values by spaces
                heights.append(int(i))                  #Store its values as integers

        paths.append([heights[0]])                      #Starts first list with first value
        for i in range(1, size):                        #Iterate from second member on
                for path in paths:                      #For every path
                        if heights[i] > max(path):      #Is the current height bigger than my maximum?
                                path.append(heights[i]) #Append its value, so it will be crescent
                        else:
                                path.append(0)          #Else, ignore it

                paths.append(heights[:i+1])             #Create a new path with the heights so far
                cur_num = paths[-1][-1]                 #Get the current height

                for j in reversed(range(0, i)):         #Iterate down to the first height
                        if cur_num > heights[j]:        #If the next value is smaller, keep it
                                cur_num = heights[j]
                        else:
                                paths[-1][j] = 0        #If it's not smaller, ignore it

        min_houses = size
        for path in paths:
                min_houses = min(min_houses, path.count(0)) #Get the path with least ignored members

        print "Case #%d: %d" % (case, min_houses)

As I said, not a good example of resource usage, but “works”. The thing is, while brainstorming a bit with a friend (who introduced me to the Dynamic Programming concept), I’ve found that my first attempt had a little bug (didn’t took time to debug it though): it will ignore possibilities with subsequent “out-of-order” nodes:

list = [ 1, 2, 4, 3, 6, 5, 7, 8 ]
path[0] = [ 1, 2, 0, 3, 6, 0, 7, 8 ]
path[1] = [ 1, 2, 4, 0, 6, 0, 7, 8 ]
path[2] = [ 1, 2, 4, 0, 0, 5, 7, 8 ]

As you can see, there’s the not covered possibility [ 1, 2, 0, 3, 0, 5, 7, 8], enough to invalidate the solution. As it was already a bad solution, I decided to use the wikipedia algorithm to solve the problem:

'''
 L = 0
 for i = 1, 2, ... n:
    binary search for the largest positive j ≤ L
      such that X[M[j]] < X[i] (or set j = 0 if no such value exists)
    P[i] = M[j]
    if j == L or X[i] < X[M[j+1]]:
       M[j+1] = i
       L = max(L, j+1)
'''
for i in range(size):                                          #For all the sequence
                j = 0
                for k in range(length+1):                              #For all the sequence until the current length
                        if heights[pointers[k]] < heights[i]:          #Compare the values on pointers to the current value
                                j = max(j, k)                          #Get the maximum value index

                if j == length or heights[i] < heights[pointers[j+1]]: #If the value is a "keeper"
                        pointers[j+1] = i                              #Keeps its index
                        length = max(length, j+1)                      #Update the length

But, that algorithm has a minor bug: when “length == size”, the index keeping will fail, because j+1 exceeds the pointers list size. So, I’ve added a check for “j < size” before it. The bug only happens at the last iteration anyway, we don’t need to store its index anyway. Perhaps it can be “avoided” with a bigger than “size” pointer list.

The final, validated, solution becomes:

for case in range(1,int(raw_input())+1):                               #For all test cases
        size = int(raw_input())                                        #Get the case size
        heights = []
        pointers = [0] * size                                          #Create the pointer list
        length = 0                                                     #Sequence length

        for i in raw_input().split(" "):                               #Split the case values by spaces
                heights.append(int(i))                                 #Store its values as integers

        for i in range(size):                                          #For all the sequence
                j = 0
                for k in range(length+1):                              #For all the sequence until the current length
                        if heights[pointers[k]] < heights[i]:          #Compare the values on pointers to the current value
                                j = max(j, k)                          #Get the maximum value index

                if j == length or heights[i] < heights[pointers[j+1]]: #If the value is a "keeper"
                        if j < size-1:
                                pointers[j+1] = i                      #Keeps its index
                        length = max(length, j+1)                      #Update the length

        print "Case #%d: %d" % (case, size-length)

Until the next Jam!

CodeJam Online Competition for Veterans 2013 B: Baby Height

This was supposed to be posted last night, but I was trying to make it work properly. This problem reproduces a few Python division problems and took me some time to figure it out. Actually I only knew about this when I checked the winner’s solution (also written in Python).

Without the “gotcha”, the problem is quite easy to solve, if you know how to work with feet and inches. As a metric system native, it was my first time. 😀 It’s called Baby Height, and it says, yo!

Every parent wants to know how tall their child will grow.
Dr. Spaceman’s algorithm, which we describe below
Accurately calculates, with errors very low,
Adult height of any child, with just genetics, yo!

Take the mother’s height and add it to the father’s height.
For a girl, subtract five inches; this I will highlight.
For a boy, you add five inches, or it won’t be right.
Then divide by two, and get your target in plain sight.

Dr. Spaceman is convinced that target is precise.
Plus or minus four, in inches, truly will suffice.
When a parent asks the question, looking for advice,
Dr. Spaceman’s answer is this range, and it’s concise.

Also, a minor problem gotcha is found on the Output rules:

Output

For each test case, output one line containing “Case #x: A to B“, where x is the case number (starting from 1), A is the smallest and B is the largest baby height, according to Dr. Spaceman’s algorithm. If the algorithm produces a range whose endpoints fall on fractional inches, your program should shrink the range until both endpoints can be expressed in whole inches.

I’ve overlooked that at first. 😛 Anyway, here’s the final code, validated:

from __future__ import division                            #Get python3 revised division operator

def asInches(strFeetInches):                               #Function converting Foot/inches string to inches
        nums = strFeetInches[:-1].split("\'")              #Split string on ' and remove " marks
        return int(nums[0])*12 + int(nums[1])              #1 foot = 12 inches, convert

for case in range(1,int(raw_input())+1):                   #For all test cases
        vector = []
        boy = False
        father = -1
        mother = -1

        for i in raw_input().split(" "):                   #Split the case values by spaces
                if i == "B":                               #Is it a boy?
                        boy = True
                elif i == "G":                             #Is it a girl?
                        boy = False
                elif father == -1:                         #If father is not yet known, get it
                        father = asInches(i)               #Store his height in inches
                else:                                      #Father is known, so get mother this time
                        mother = asInches(i)               #Store in inches

        height = (mother + father + (5 if boy else -5))/2  #Baby height math
        inc = 4.0                                          #Range default value

        lower = height-inc                                 #Get lower range
        if lower != int(lower):                            #If number is a fraction
                lower += 0.5                               #Reduce range size

        higher = height+inc                                #Get higher range
        if higher != int(higher):                          #If number is a fraction
                higher -= 0.5                              #Reduce range size

        print "Case #%d: %1d'%1d\" to %1d'%1d\"" % (case, lower/12, lower%12, higher/12, higher%12)

This problem represents what CodeJam is about. Not only knowing how to code, but also knowing about programming “gotchas” and avoiding them.

Happy jammin’!

CodeJam Quickie: 2013 veterans competition problem A

Howdy! Some hours until codejam starts again and I’ve decided to take some rust off. 🙂

This problem is called Hedgemony, quite simple:

Lord Cohen is a baron with the best-looking hedge in the country. His award-winning hedge consists of N bushes planted side by side in a straight line. The bushes are numbered left to right from 1 to N. The baron’s neighbours all cut their own hedges so that all of their bushes have the same height. But Lord Cohen has a secret key to his landscaping success. His gardener follows a special rule when trimming the hedge, which is why the baron’s hedge is always in its award-winning condition.

The rule is — to start on the left at bush #2 and move to the right. The gardener cuts the top of each bush to make it exactly as tall as the average of the two bushes on either side. If the bush is already as short as the average or shorter, then the gardener does not touch this bush and moves on to the next bush on the right, until the second-to-last bush. The baron is certain that this procedure is the key to success.

Quite simple, if you read the bold words. 😉 Here’s our code:

for case in range(1,int(raw_input())+1):          #For all test cases
        size = int(raw_input())                   #Get the case size (unused)
        vector = []

        for i in raw_input().split(" "):          #Split the case values by spaces
                vector.append(float(i))           #Store its values as floats

        for i in range(1,len(vector)-1):          #From second to second-to-last
                med = (vector[i-1]+vector[i+1])/2 #Get average from neighboors
                if vector[i] > med:               #Am I bigger?
                        vector[i] = med           #Then average I am

        print "Case #%d: %.6f" % (case, vector[-2])

Evolving with smaller and clearer code. Tested with both (small and large) input sets, won at first shot. 🙂

Hope I can see you in the competition!

Best Gnome 2 replacement so far? KDE 4.

Since Ubuntu changed to Unity and Gnome 3 took over everything, I found myself without a nice DE to use. Gnome 2 was perfect for me, I could customize it the way I wanted it to feel (I still use it at work, but there we’re forced to use some “ancient” 10.04 LTS Ubuntu), so that I can keep my productivity and use the most of screen sizes. It was a powerful, standard and lightweight solution.

Gnome 3 changed everything, now I can’t use my screen the way I want to. That irremovable top panel, the shell itself, the HOTKEYS changed and no way around these things was provided! It was not supposed to get out-of-the-way and help you, but force you to relearn how to work (for me, in a bad oriented way) with no variety… after all, “you can’t know what’s best for you”.

Unity suffers from the same thing. People define what they think a newcomer would think to be easy to use and apply all over the system. It IS OK to do it, BUT LET EXPERIENCED users CUSTOMIZE the experience! I can’t stress that enough.

And so, a crusade for the new best Desktop Environment was started, and I’ve tried almost anything that calls itself a Linux DE. My rules were simple:

  • Must be able to leave all vertical space free to windows (no top/bottom panels);
  • Must not feel bloated (be it with excessive animations or effects);
  • Must handle two monitors decently;
  • Must be able to create hotkeys.
  • Must not differ that much from the basic window and support icon clicking (I share my home desktop, so it must function without “magic”);
  • Have compositing (Optional);

Unity and Gnome shell were out because of the vertical space and the bloat feeling. I also could not edit many hotkeys for them to work the way I’m more productive. Awesome and Fluxbox variants are just too far from what people are used to, so no to them. XFCE and LXDE are OK, but they feel weird and incomplete. XFCE does not seem to help you at all when customizing. The more you modify, the more unstable it gets. Cynnamon is Gnome 3 placing the top bar on the bottom. Enlightenment seems to have learned nothing, feels like I’m using the old 6.10 version again. If they’re aiming “vintage”, they should have placed a desktop cube and fire animations by default.

MATE, that would be the best candidate, is just too unstable and incompatible with updated Gnome apps. It’s not ready yet, but I’ll definitely keep an eye on it.

I didn’t look back at KDE after the 4.0 fiasco. At that time, it was too unstable for it to be released, BUT, for my relief, it was already at 4.10, and now it’s TOO WONDERFUL! 😀 Everything, EVERYTHING WORKS AS EXPECTED and can be customized! I love it! Of course I had to learn new places to create the things I wanted to, but that would also happen with the other DEs. As a plus, it has features I would need to use other applications to have working in the past.

Needless to say, after that many DE installs my Ubuntu could be considered trash. Preferences were thrown and thrown again on the garbage, a thousand alternative utilities were installed, a terminal application for each DE, the login screen showed alternatives no longer installed. Add that to my root partition being mounted as read-only because of ReiserFS tree corruption (I didn’t even know it could happen, I thought it was just perfect) and you can see me reinstalling the whole system, not only the root system, but all HOME stuff too (preference screwups, anyone?), with Kubuntu 12.10. This time it’s mature enough, EXT4 as the file system.

I’m now posting from it, and was pretty fast to install AND customize. Around 4 hours to have it all working (games and development stuff all ready-to-use). KDE is still good as it was before (it was the main preference after Gnome 2), but nowadays it’s also what Gnome left behind.

CodeJam is in 3 days, let’s code!

http://code.google.com/codejam

I’ll never be ready enough for this, I guess, but once again I’ll try to quickly code solutions to CodeJam challenges. It’s exciting to do it again. Couldn’t finish my “all problems solved” section of the blog, but I’ve practiced some more, and am more experienced after all.

Let’s see how it goes. I think I’ll start with Python because I find it easy to output working code, and a wonder when it comes to manipulate data sets. 🙂 Can’t wait for it to start.

Project hosting, tough choice

Howdy 🙂

it’s 10PM once again, and I’ve decided to restart posting. Really it’s been really hard to focus energy into posting content. Let’s see how it goes. I was planning a deep analysis into many different services and their offerings, guided by this wikipedia entry, but, as a colleague once said: “who DOESN’T use GitHub nowadays”?

I love Free and Open Source Software and advocate its use, but I don’t really care if the host I’m using holds proprietary software. I work in a closed-source business company (in fact, we use plenty Open Source software to produce our proprietary products), and I don’t think every software MUST be free, but COULD, with a different business model.

I’d like to have a defect control system with it (such as Bugzilla) and I’d love to have my projects featuring a nice front page introduction, perhaps even some examples of its use. A wiki system would also be nice, but I could live without it. I don’t need a build system, mailing lists or forums for my projects. There are also lots of alternatives for team management, so I don’t need it (especially on single-man projects such as mine).

So, not only GitHub matches my needs, but also Sourceforge, Google Code (without web-page hosting), Launchpad (without web and wiki), JavaForge, GNU Savannah and some other less known choices. But, it’s friends’ good experience with it that guides my choice this time, and I can always change if there’s a better solution. 🙂

To GitHub!