Fighting with computers

Computers are not always friendly.

Friday, August 29, 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.

Friday, August 22, 2008

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 really required to use 64-bit integers), but it was just unfeasible for the large dataset (as computing time will huge for 100000 trees). A new approach has to be found somehow.

The key observation was that for a triangle to be valid the sum of x and y coordinates of vertices has to lead to a number multiple of 3. If we add three different numbers, the result will be a multiple of 3 if: a) all of them are multiples of 3 or b) one of them is a multiple and the others add up to a multiple too c) none of them are but the three numbers lead to a remainder of 1 when divided by three.

So then, why don't we count the number of trees with each coordinate x and y being either 0, 1 or 2 when we perform the modulo 3 operation. This way we will have a 3x3 matrix totaling the count of each type of coordinate of all our trees.

Next observation is that for a triangle to be created we will use three trees, each one belonging to each one of these nine (3x3) bins. But not all the combinations are possible. For example, if I choose three trees from bin 0,0 then these are trees which coordinates (both x and y) are multiples of 3. So when we add them we are going to have a triangle whose center will be on the grid. But if we choose a triangle from 0,0 bin and two from 1,1 bin then the resulting tree won't be a valid one.

I've used the following 'bc' code to print the valid combinations:

c=0; for(i=0;i<9;i++)for(j=0;j<9;j++)for(k=0;k<9;k++) if((i%3+j%3+k%3)%3==0 && (i/3+j/3+k/3)%3==0) {print c++," ",i," ",j," ",k,"\n";}

A careful observation of the combinations will show you that only rows, columns and diagonals are the combinations that render a valid tree. These and, whenever possible, to choose the three trees from the same bin (i.e. 1,1)

So what is left is to read the trees coordinates, count them appropriately and to sum the different combinations. There are only two cases: 1) you take the three trees from the same bin, then this subtotal is (x)*(x-1)*(x-2)/6 or 2) each bin comes from a different bin, and then the subtotal is x*y*z (x,y,z are the values of each bin, for example x is the count of bin 0,0 y the count of 1,1 and z the count of 2,2).

Of course, pondering all that took longer than lunch time :-)

I did have a lot of fun too with the Number Sets problem, but I will write about it another day.

Update: I've just noticed that Code Jam site has added a nice entry named "Contest analysis" where a comment on each problem's solution is provided (so you can skip my comments and go straight to the real thing :-) Highly recommended!!

Saturday, August 09, 2008

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 is even better than MT.

I'm quite sure I'm not helping you out on your next car buying decision but I hope now you're aware of the many choices available for your car's transmission.

Monday, August 04, 2008

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 it is simpler to get the problem solved.

Update: My code loops from n,m to 0,0 for x2,y3 while the x,y value was x*y>a and then it does the opposite (from 0,0 to n,m) for the x3,y2 values till the desired area was met.