Showing posts from August, 2008

Another challenging problem

Code Jam round 3 seems to be quite more challenging than previous rounds. I was not able to complete Polygonovich's professor problem in two hours. I was quite happy with the use of java.awt.Polygon object, mostly because it includes a contains method that seemed quite useful for this problem. However solving the problem took longer than expected too, as I wanted a method that worked nicely for both the small and large problems.

In the mean time I constructed the whole set of graphs for the small dataset. You may find it interesting. Vacation time is over though, so I'll be back to work soon I still I have some problems pending.

Keeping me entertained

I thought the Crop Triangles Code Jam problem will be gone in no time. It looked simple the morning I started with it and I was expecting to have it all done by lunch time.

The basic idea is that you have an integer coordinate system (or grid) and in certain points of the grid there are some trees located. If you use those trees as vertices to make triangles ... how many different triangles can be created?

Well, the answer to that is actually quite simple using combinatoric numbers, but they added a restriction: the center of a valid triangle has to be located on a grid coordinate, if not do not count that triangle. A triangle with vertices (x1,y1) (x2,y2) and (x3,y3) has a center at coordinate ((x1+x2+x3)/3,(y1+y2+y3)/3)

My first solution was to simulate the system. Given all the available trees, I will go though all the different combinations and after checking each one a counter will give me the valid answer.

That idea worked nicely for the small dataset (once I realized that Case #9 r…

CVT vs MT vs AT vs AMT

I've always owned manual transmission (MT) cars, but while living in USA I drove automatic transmission (AT) cars most of the time (manual transmission is not very popular over there).

When I recently bought a car I was offered a continuously variable transmission (CVT) that, instead of gears, uses an steel belt and two variable-diameter pulleys. The system works nicely and it may even offer a set of "simulated" fixed transmission rates. While the fuel economy is not as good as MT it gets quite close.

For many years AT cars exhibited worse fuel economy than their MT counterparts. I've always found weird that, but I am not a mechanical engineer 8but wikipedia tells me it's because of torque converter mostly). Now it seems some manufacturers, probably feeling the pressure from regulators due to the high cost of petrol, are delivering a new technology (maybe not so new) dubbed as automatic manual transmission (AMT). The good thing about AMT is that its fuel economy …

Solving Triangle Areas

Vacation time is a good moment to ... keep on trying things at the computer. At least this is what I am doing now, as have been having a look at the Code Jam Round 2 problems. Again interesting problems that I have not been able to solve in two hour time. Amazingly, some guys did it with flying colors and using a bit more than one hour!

I have already done the Star Wars problem, though I would complain that there is not such a thing as "receiver power" (even on a spaceship) but "receiver sensitivity". However the problem was challenging and fun (I did a minimum search in 3D space and it worked).

I'm dealing now with the Triangle Areas problem, that though manageable in complexity it is a bit of a challenge to get right. A few ideas can help, the first one is how to know the triangle area out of set of vertices coordinates. The second observation is that if we keep one vertex at (0,0) then the area of the triangle is just 0.5*(x2*y3-x3*y2). With this idea in mind …