Archive for the ‘Coding’ Category

GCJ 2009 Round 1C: All Your Base

Did I say that maybe Googlers like aliens? Of course they do! Actually they like also to make cool, not so hidden, citations, but that’s what make this contest so fun!

Problem A was the easiest of Round 1C in Google Code Jam 2009: no doubt!

In this problem they give us a number, we don’t know in what base this number is expressed nor what is its symbols order. We have to find out what is the smallest number it could represent.

We know for sure only three things:

the number is positive
it will never start a number with a zero
it is not in base 1

The basic idea is that the same string represent a smaller number if we use a smaller base. How can we find the smallest possible base? Simple: we count how many different symbols are present in the string.

Here is my solution (click to download) in python:

#!/usr/bin/env python
#-*- coding:utf-8 -*-
 
import sys, psyco
psyco.full()
rdl = sys.stdin.readline
 
symbols = '1023456789abcdefghijklmnopqrstuvwxyz'
 
def process(case):
    """precessing case #"""
    code = rdl().replace('\n','')
    d = {}
    symbol = 0
    trans = ''
    for s in code:
        if not s in d: 
            d[s] = symbols[symbol]
            symbol += 1
        trans += d[s]
    base = len(d) if len(d) > 1 else 2
    return int(trans, base)
 
cases = int(rdl())
for case in xrange(1, cases+1):
    print "Case #%d:"%case, process(case)

Tags: base conversion, Coding, gcj, python

GCJ 2009 Round 1C: Center of Mass

Problem B of Google Code Jam 2009 was about fireflies!
firefly
Google has been so kind that has given us swarms of fireflies, how lovely can it be?
With N fireflies in the form of their starting position and their velocity vector we are asked to find out how (distance) and when (time) when their center of mass will be close to us, considering us to be in the origin O (0,0,0).

Each firefly moves at constant speed on a line, and so the center of mass will. The center of mass is simply an average of fireflies’ position, so it moves at a speed that is the… guess it: the average of fireflies’ speeds.

We can easily get the center of mass initial position P (x1,y1,z1) and velocity vector V (vx, vy, vz), it moves on a line of parametric equation r:
$From tex.nigma.be: r=\left\{\begin{array}{ccc}x=x1+vx*t\\y=y1+vy*t\\z=z1+vz*t\end{array}\right.<br />$

where t, the parameter, is time. As time goes, the center of mass will move accordingly to its velocity.

Here is a simple draw I did with C.a.R.:
minimum distance

The minimum distance d is the distance from O to Q, and it’s easy to see the right triangle PQO.

Now, we have $From tex.nigma.be: \vec{v}$ , let $From tex.nigma.be: \vec{b}=\vec{0-P}$ and $From tex.nigma.be: k=\overline{PQ}=|\vec{b}|cos\theta$

We can get $cos theta$ from the dot product $From tex.nigma.be: \vec{v}\cdot\vec{b}=|\vec{v}||\vec{b}|cos\theta$ :

$cos theta=v.b/(|v||b|)$

From trigonometry we have $k$

k depends on how many seconds have passed since the start as x = x0 + v*t so we need to solve $k=t|v|$ in t: $t=k/|v|$

Finally, we can find d with the Pythagorean theorem: $From tex.nigma.be: d=\sqrt{|\vec{b}|^2-k^2}$

And now we solve the problem with a bit of good python! First the whole solution (click to download) then the comments:

#!/usr/bin/python
import sys
rdl = sys.stdin.readline
 
def dot(x,y):
    return sum([a*b for a,b in zip(x,y)])
 
def mod(x):
    return sum([i*i for i in x])**.5
 
def process(case):
    fireflies = int(rdl())
    x,y,z, vx,vy,vz = 0,0,0, 0,0,0
 
    for firefly in xrange(fireflies):
        tx,ty,tz, tvx,tvy,tvz = map(int,rdl().split())
        x,y,z, vx,vy,vz = x+tx,y+ty,z+tz, vx+tvx,vy+tvy,vz+tvz
 
    x,y,z, vx,vy,vz = [1.*i/fireflies for i in [x,y,z, vx,vy,vz]]
 
    p = [x,y,z]
    v = [vx,vy,vz]
    b = [-i for i in p]
 
    if mod(v) == 0: return mod(p), 0.
 
    k = dot(v,b)/mod(v)
    t = k/mod(v)
 
    if t<0: return mod(p), 0
 
    if k**2 > mod(b)**2: d = 0
    else: d = (mod(b)**2 - k**2)**0.5
 
    return d, t    
 
 
cases = int(rdl())
for case in xrange(1, cases+1):
    print "Case #%d:"%case, '%.8f %.8f'%process(case)

Here we go, rdl is an alias for the long sys.stdin.readline, and dot(x,y) computes $dot product$ and mod(x) computes $abs$ .

def process(case):
    fireflies = int(rdl())
    x,y,z, vx,vy,vz = 0,0,0, 0,0,0
 
    for firefly in xrange(fireflies):
        tx,ty,tz, tvx,tvy,tvz = map(int,rdl().split())
        x,y,z, vx,vy,vz = x+tx,y+ty,z+tz, vx+tvx,vy+tvy,vz+tvz
 
    x,y,z, vx,vy,vz = [1.*i/fireflies for i in [x,y,z, vx,vy,vz]]

process is the core function of the problem. In the first part we get the number of fireflies, and initialize center of mass’ postion and velocity to 0.
Then we sum all the fireflies positions and velocity, finally we divide them for the number of fireflies, that’s the average!

21
22
23

    p = [x,y,z]
    v = [vx,vy,vz]
    b = [-i for i in p]

do you remember $From tex.nigma.be: \vec{b}=\vec{0-P}$ ? zero - x is just -x.

    if mod(v) == 0: return mod(p), 0.
 
    k = dot(v,b)/mod(v)
    t = k/mod(v) 
 
    if t<0: return mod(p), 0

If the center of mass is still, it doesn’t move or mathematically if all velocity’s components are null, or we had the minimum possible distance in the past (t<0) the minimum distance we'll have in the future is just the distance from the starting point... at t=0.

    if k**2 > mod(b)**2: d = 0
    else: d = (mod(b)**2 - k**2)**0.5
 
    return d, t

This should be not useful in a world where computers do maths correctly. Unfortunately it doesn’t always happen in our world. If k^2 and mod(b)^2 are equal or very close it may happen that k**2 > mod(b)**2, in that case the real distance is 0. normally we use the pythagorean theorem.

38
39
40

cases = int(rdl())
for case in xrange(1, cases+1):
    print "Case #%d:"%case, '%.8f %.8f'%process(case)

This could be a sort of template now for google code jam problems, the first line is the number of cases, then we print each case result.

Did you solve this? Did you do anything simpler? Or harder? Let me know!

Tags: math gcj python geometry

GCJ 2009: Alien Language

Aliens are here again, after their numbers it’s the language turn. Googlers must like them very much, this was the first problem for the qualification round:

You can find the original text here (registration may be required)

Here is my solution in python:

#!/usr/bin/python
import sys
import re
import psyco
psyco.full()
rdl = sys.stdin.readline
 
def process(case):
    """precessing case #"""
    pattern = rdl().replace('(','[').replace(')',']')
    count = 0
    reg = re.compile(pattern)
    for w in words:
        if reg.match(w): count += 1
    return str(count)
 
L, D, cases = [int(i) for i in rdl().split()]
words = [rdl() for dumb in xrange(D)]
for case in xrange(1, cases+1):
    print "Case #%d:"%case, process(case)

The problem was about simple pattern matching, so what tool is better than regex? I simply replaced each ( with a [ and each ) with a ], made a list of words and testing all words against each pattern.

Compiling each regex before the for loop make time of execution drop from 9s to 3s for large input files. This one was very very simple to solve this way.

How did/would you solve this?

Tags: Coding, gcj, regex

How to turn off your computer, later!

James is 15 and he’s having his first experiences with Linux. He’s just started to download a new distro from BitTorrent bit hey, it’s 8.13 am and he is supposed to be at school by 8.30… Has he to turn off the computer before going to school? Try to ask his mother! But he wants to try the new distro as he come back, what can he do in order to finish his download AND turn the computer off as it finish? Suppose his client doesn’t allow him to.

sleep 30m && poweroff -n

How cool is that? You tell “sleep 30 minutes then just poweroff!”
It isn’t the only way, try to do “man shutdown” to see more info.

For who is concerned about
Sudo make me a sandwich

Remember that:
nigma@nigma-desktop:~$ sudo whoami && sleep 1 && whoami [sudo] password for nigma: root nigma nigma@nigma-desktop:~$

so you need to be root before doing these things, but this time for real:
nigma@nigma-desktop:~$ sudo su root@nigma-desktop:/home/nigma# whoami root

It’s a nice way to make your computer do something after a little bit, and it’s quick to type.

return `whoami`

Tags: commandline, linux

A geeky toy, for a geeky boy.

I’m sure all of you know what the rubik’s cube is, if you don’t… I mean, really? man what was you thinking until now? Well If you REALLY don’t know it then you should at least google for it. Wikipedia will work as well.

rubik's cube

I always thought it was a logic puzzle, and after some unsuccessful tries I decided to cheat, googled for “rubik’s cube solution” and I found out a beautiful site, which explains everything you need to solve the cube in a very simple and fast way, it is of course the Lars Petrus method.

Once learnt a solution method there is no more “logic” in it. Where is the fun part? What’s the challenge?
I was terribly wrong. It is not a logic-puzzle, it is a memory-puzzle, and a hand-dexterity-puzzle.

You need to remember the moves of your solving methods, they are almost always the same (in the petrus method there are 4 basic moves), but the most challenging part is how fast can you solve the cube?

Hey “how-fast” sounds damn challenging, how can you measure that? You’ll need a stopwatch. If you are at least half geeky as I am you’d be already on google at the moment and starting to type something like “online stopwatch” or “online timer”.

There are tons of them, but all have a very annoying interface that make you use the mouse. Given that you are a very good speedcuber you don’t want to loose 0.3s to start to solve and an other 0.3s to stop the timer, do you?

Well I wouldn’t care as I need 1′30”+ to solve the cube, but I found fun to code a stopwatch designed to work with Miss Spacebar instead of your loveable mice.

the simple nigma timer is written in simple html/css/js and as a very simple interface, I hope you’ll enjoy it.

return ”

Tags: Coding, fun, UI

How to convert Microsoft Word .doc files to PDF from command line

I know lot of people need it, Google is full of requests by hundred, maybe thousands of users asking for a doc2pdf converter or this kind of thing. I need it too. It is useful to have all files in pdf format (and maybe all merged in one file only) and if you have a lot of files to convert by hand, believe me, you’re not going to have a nice day.

The easy way

It is pretty easy:

$ abiword --to=pdf filename.doc

I don’t think there is so much to explain here. It converts filename.doc to filename.pdf and saves it in the current directory. It was too easy. Why should you need an hard way? I don’t know, I’m sure I need one. Unfortunately abiword’s Microsoft doc file support is not so good, in fact it lacks of the math and image/clipart features. I’m not sure if this affects all versions of abiword but it is sure for the one that comes with ubuntu (actually it doesn’t come with it, you’ve to apt-get install it).

Anyway I really need to see plots and formulas. What you said? OpenOffice supports them. Check it out. Yes I know that, OpenOffice can read almost always plots and images in doc files. Bad luck seems to be here again, OpenOffice lacks of the same command line interface abiword has, so the only way is to open doc files one by one and click on the Export as PDF button. It is very frustrating. So, here is the hard way.

The hard way

Short version (for whom doesn’t like read me be but want to read so much): check the Python-UNO site.

Long version. You need to know what Python-UNO is

The Python-UNO bridge allows to

use the standard OpenOffice.org API from the well known python scripting language.

to develop UNO components in python, thus python UNO components may be run within the OpenOffice.org process and can be called from Java, C++ or the built in StarBasic scripting language.

create and invoke scripts with the office scripting framework (OOo 2.0 and later).

You can find the most current version of this document from http://udk.openoffice.org/python/python-bridge.html

Oh no! I’ll have to download this Python-UNO, read manuals to learn how to use those API and who knows if it’ll work…… No. Just don’t panic. I’m going to tell you something that will make this a not-so-hard way. The first thing is that if you have installed OpenOffice you’re at 50% of the work, in fact Pyhton-UNO comes with OpenOffice since version 1.1.

Pyhton-UNO comes with OpenOffice since version 1.1. You don’t have to download and install anything
Pyhton-UNO’s guys are so cool that in their code examples there is all of what we need.

From the examples page you can download the ooextract.py script. It has a very simple usage, we need to use it in this way:

$ openoffice -invisible "-accept=socket,host=localhost,port=2002;urp;"
$ python ooextract.py --pdf filename.doc

The result is almost the same of the one of the easy way but this will use OpenOffice for the conversion, so it will do it better. You also may like to write a little shell script to automate the conversion of a bunch of files, so there it is a very simple version:

#!/bin/bash

openoffice -invisible "-accept=socket,host=localhost,port=2002;urp;"
for i in *.doc; do
	python ooextract.py --pdf $i
done

Remember to kill OpenOffice when it ends :o) OpenOffice has now batteries included.

Tags: bash, Coding, commandline, how-to, openoffice, pdf, python

GCJ - Practice Contest - Old Magician

Wow, an other practice contest came out :^D here’s the first problem, very simple solution :^)

from __future__ import with_statement
 
def solve(w,b):
    return "BLACK" if b%2==1 else "WHITE"
 
def eatFile(fin, fout):
    with file(fin,'r') as f1:
        N = int(f1.readline().replace("\n",''))
        with file(fout,'w') as f2:
            for case in xrange(1,N+1):
                w,b = [int(i) for i in f1.readline().replace("\n",'').split(' ')]
                s = solve(w,b)            
                #print "Case #%d: %s" % (case, s)
                f2.write("Case #%d: %s\n" % (case, s))
 
eatFile('A-large-practice.in','A-large-practice.out.txt')

Tags: Coding, gcj, Google Code Jam

GCJ 2008 - Round 1A: Minimum Scalar Product

This one was really really really too simple. The easiest problem of round 1. Unfortunately I didn’t took part at 1A, I did 1B and 1C and I did not pass :^( Anyway I’ll keep doing those problem just to have some fun :^)

def solve(a,b):
    a.sort()
    b.sort(reverse = True)
    return sum([i[0]*i[1] for i in zip(a,b)])

You have to pass a and b as lists, or if you prefer vectors… I think there is no more to comment here… I did it just thinking about it and I find the solution out in about 3 minutes, but I discovered that mathematicians already thought about that and gave it a name :^D

You can search on wikipedia for Rearrangement inequality. I mean, 4 lines of fully readable python… it was quite simple, wasn’t it?

return YAWN;

Tags: Coding, gcj, Google Code Jam

Symfony without ssh and pear

I’m currently working on a new project and I wanted to study something new to do it. It will be a web application, written in php. No matter what it will be useful for but I’ve found symfony, a great php framework. I read The Book in these 3 days, I’ll start tomorrow developing my app, I should be able to finish the model part in few days, I hope symfony helps :^)

Use it in local is quite simple, there are lot of tutorials and how-to on the symfony site. The painful part is to use it on a common hosting service.

In fact a very powerful tool of symfony is the command line interface, and you usually don’t have ssh support on your hosting service. There is a great tutorial here to make things work, and it’s quite simple, really! I did it today, now it’s working both on the server and on my pc. Look at it ;^)

return ‘bye’;

Tags: symfony

GCJ 2008: Fly Swatter

Consider this:

Believe it or not, but that’s a racquet! In fact the third problem of the Qualification Round of Google Code Jam 2008 is about balls and racquets (or rackets if you prefer)… well… actually it’s about probability :^D

You can find the whole text of the problem here, I’m reporting just the interesting part (IMHO):

Problem

What are your chances of hitting a fly with a tennis racquet?

To start with, ignore the racquet’s handle. Assume the racquet is a perfect ring, of outer radius R and thickness t (so the inner radius of the ring is R-t).

The ring is covered with horizontal and vertical strings. Each string is a cylinder of radius r. Each string is a chord of the ring (a straight line connecting two points of the circle). There is a gap of length g between neighbouring strings. The strings are symmetric with respect to the center of the racquet i.e. there is a pair of strings whose centers meet at the center of the ring.

The fly is a sphere of radius f. Assume that the racquet is moving in a straight line perpendicular to the plane of the ring. Assume also that the fly’s center is inside the outer radius of the racquet and is equally likely to be anywhere within that radius. Any overlap between the fly and the racquet (the ring or a string) counts as a hit.

The input file consists in N lines containing values of f, R, t, r and g separated by spaces.

I’m now trying to explain my approach. The probability we’re looking for it’s given by total_hitting_area/total_racquet_area, or 1 - total_not_hitting_area/total_racquet_area…

total racquet area it’s simple:

I’ll call it big, and it’s given by pi*R^2

The problem is the other area. I’ll try to calculate the not hitting area. Calculus gives a solution to get area of any kind of shape: integrals, but I don’t think it’s necessary to use them in this case. First for all we need to simplify. I don’t care about the ball, I’ll care about the center of the ball. The center of the ball has to be a distance f (the ball radius) from the border of the racquet in order to donot hit it…

This is so the interesting area:

I’ll call it small, and has a radius of R-t-f so the area is given by pi*(R-t-f)^2

The probability of the center of the ball to be in the small area is given by small/big, and I call it q1

Now consider this:

The two red areas are identical, they are both composed by the same amount of green and white area, I can consider any of them as a square, its area is given by (g+2*r)^2

Note that small is composed by squares. Some of them are cut off, but that’s should not be a problem… it should…

Now consider an hole:

I’ll call the red area gap, it’s a little square with sides long g-2*f as I subtract 2 times the ball radius. In fact the center of the ball has to be at least at a distance of f from the sides of the white area in order to do not hit a string. So a gap is (g-2*f)^2

The probability of the center of the ball to pass through a gap contained in a square is given by gap/square and I’ll call it q2

In order to do not hit the racquet to events have to happen at the same time:

The center of the ball has to be in the small area
The center of the ball has to be in a gap area

These to events have probability q1 and q2 respectively.
The probability they are both verified is q = q1 * q2, and that’s the not successful case.

The successful case is p = 1 - q… the probability we were looking for…

It should work… it should… But it doesn’t.

I tried an other approach so. I calculate how many squares there are in the small area. That number is nos = small/square (where nos stands for number of squares)

We know there are as many gap as squares, that’s just because there is one gap inside each square.

In this way I can calculate the total gap area, that is just nos*gap and I call it totalgap…

Do you remember the 1 - total_not_hitting_area/total_racquet_area… well the total_not_hitting_area is just our totalgap!

So we have q = totalgap/big… and p = 1 - q

I’ve found the same p as the one above… and it’s wrong.

I went so close the solution but there is something wrong, just to show you, these are the sample cases:
0.25 1.0 0.1 0.01 0.5 0.25 1.0 0.1 0.01 0.9 0.00001 10000 0.00001 0.00001 1000 0.4 10000 0.00001 0.00001 700 1 100 1 1 10

The Google’s results for these cases are:
Case #1: 1.000000 Case #2: 0.910015 Case #3: 0.000000 Case #4: 0.002371 Case #5: 0.573972

But mines are:
Case #1: 1.000000 Case #2: 0.920132 Case #3: 0.000000 Case #4: 0.002364 Case #5: 0.573156

They are so close.

You can download my solution file by clicking here.
That’s my implementation in python:

def solve(f,R,t,r,g):
    if 2*f >= g: return 1.0
    t += f
    g -= 2*f
    r += f
 
 
    big = pi*R**2
    small = pi*(R-t)**2
    square = (2*r+g)**2
    gap = g**2
 
    # Way 1
 
    q1 = 1.0 * small/big
    q2 = 1.0 * gap/square
    q = q1*q2
 
 
    # Way 2
    '''
    nos = 1.0*small/square
    totalgap = gap*nos
    q1 = 1.0 * small/big
    q2 = 1.0 * totalgap/small
 
    q = q1*q2
    '''
 
 
    if 0 <= q:
        if q <= 1:
            p = 1-q
        else:
            p = 0.0
    else:
        p = 1.0
    #print 1-q
    return p
 
 
def sfs(s):
    'solve from string'
    s = s.replace('\n', '').split(' ')
    f,R,t,r,g = [float(i) for i in s]
    return solve(f,R,t,r,g)

I did one in C too, I was thinking python did something wrong with math…

#include <stdio.h>
#define pi 3.1415926535897931
 
double solve(double f,double R,double t,double r,double g)
{
    double big,small,square,gap,q1,q2,q,p;
 
    if (2*f >=g )
    {
         return 1;
    }
 
    t = t + f;
    g = g - 2*f;
    r = r +f;
 
    big = pi*R*R;
    small = pi*(R-t)*(R-t);
    square = (2*r+g)*(2*r+g);
    gap = g*g;
 
    q1 = small/big;
    q2 = gap/square;
    q = q1*q2;
 
    if (0<=q)
    {
        if (q<=1)
        {
            p = 1-q;
        } else p = 0;
    } else p = 1;
 
    return p;
}
 
int main()
{
    printf("Case #1: %lf\n",solve(0.25, 1.0, 0.1, 0.01, 0.5));
    printf("Case #2: %lf\n",solve(0.25, 1.0, 0.1, 0.01, 0.9));
    printf("Case #3: %lf\n",solve(0.00001, 10000, 0.00001, 0.00001, 1000));
    printf("Case #4: %lf\n",solve(0.4, 10000, 0.00001, 0.00001, 700));
    printf("Case #5: %lf\n",solve(1, 100, 1, 1, 10));
}

There’s no need to say that the result was the very same.

I don’t know what’s wrong with my approach, all the others’ code I read used something involving integrals, sometime already solved and they just did the “definite” part.

Did you read someone’s code that is not using integrals but pure geometry and probability approach?
I think it’s possible, I think there is something very bastard I’m missing… don’t know what… do you?

return “grr”

Tags: Coding, gcj, Google Code Jam, mistakes

« Older Entries

nigma

waiting for slogan

Categories

Archives

Blogroll

University

Meta