July 19th, 2008 § § permalink
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:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| 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…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| #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”
July 19th, 2008 § § permalink
This one was the title of the second problem of Google Code Jam Qualification Round 2008.
This time my code is a bit messy, but I won’t adjust it for you :^D It’s the disadvantage of coding fast, at least for me. I often wrote something not necessary, someone call it gold planting, it’s just what I did in the maze problem with the draw method…
You can download my solution for the Train Timetable problem I wrote.
Here is the commend code.
1
2
| from __future__ import with_statement
from copy import copy |
Don’t ask me why I imported copy, I think I did it while testing… maybe. I don’t remember it’s not useful
The first 3 are classes but I did not spent so much time projecting their structure. Tempo just means time in italian, I didn’t want to override the python name (I know that’s the name of a lib, it’s only an excuse, I’m italian, let me name things in italian sometime :^P)
tempo is not so useful in that form… anyway converts the format ‘hh:mm’ to an int representing minutes
4
5
6
7
8
| class tempo(object):
def __init__(self, s):
a = s.split(':')
x = [int(i) for i in a]
self.m = x[0]*60 + x[1] |
Trip represents a trip, with starting and ending time.
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Trip(object):
def __init__(self,start,end):
self.start = tempo(start)
self.end = tempo(end)
self.duration = self.end.m - self.start.m
self.busy = False
def __cmp__(self,x):
return cmp(self.start.m,x.start.m)
def use(self):
self.busy = True
def isfree(self):
return self.busy == False
is_free = property(isfree) |
There is no need to put the duration attribute, but it did, thinking on it now it’s pretty useless… The interesting part is the flag busy, or is_free (just a joke with python property function…). A Trip is free if you did not use it yet. I added __cmp__ method because I’ll need to “sort” them, if trip X starts earlier than trip Y well…
It will be useful to understand what’s the first Trip to use…
A Train is identified by the time of the last thing it did (self.Time) and it has done something or not (self.init)
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Train(object):
def __init__(self,Time):
self.Time = tempo(Time)
self.init = False
def TripTrough(self, trip, turnaround):
'Returns True if the train can trip (and it does)'
if (trip.is_free and self.Time.m+turnaround <= trip.start.m) or self.init ==False:
self.init = True
self.Time = trip.end
trip.use()
return True
else:
return False |
The TripTrough method is very important (yes I know, it’s Through not Trough… my english sucks, sorry for that :^D )… Anyway… How does it work? It’s simple. It wants a trip and the turnaround time. the flag init it’s useful because if the trip starts at 0:03 and you have a turnaround of 5 you have to don’t care about the turnaround, you have no need to turn around… my check can’t work without an init flag… I don’t know if it’s clear..
Now something magical happens, I’m doing it bad I think, I’m playing with the “all name are references” of python… I changed the trip flag as the train used it, I could do it out of that method but maybe I was tired, bored, drunk, whatever… and I did it in this way :^D. I updated the time of the train too, obviously.
Table has the algorithm! Let me explain…
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
| class Table(object):
def __init__(self,A,B,T): # trip lists... and turnaround
self.A = A
self.B = B
self.T = T # turnaraund
def solver(self, starting,ending,train):
starting.sort()
s = starting
for i in s:
if train.TripTrough(i,self.T):
return self.solver(ending,starting,train)
# else...
return train
def solve(self):
tfa = []
tfb = []
check = True
while check:
freeA = [i for i in self.A if i.is_free]
freeB = [i for i in self.B if i.is_free]
#print freeA, freeB
if len(freeB) > 0 and len(freeA)>0:
mins = min(freeA),min(freeB)
elif len(freeB) == len(freeA) == 0:
break
if len(freeA)>0 and (len(freeB) == 0 or mins[0]<mins[1]): #start from A
tfa.append(self.solver(freeA,freeB,Train('00:00')))
else:
tfb.append(self.solver(freeB,freeA,Train('00:00')))
return len(tfa),len(tfb) |
- A is the list of trips starting from station A going to B
- B is the list of trips starting from station B going to A
- T is the turnaround time of the case
- solver it’s a recursive method.
It takes 3 parameters:
- starting it’s the list of the trips starting from a station
- ending it’s the list of the trips starting from the other station
- train is the train that’s traveling forward and backward
Well… I sort the trip list, in this way come first the one that will start first, then I begin to look for the first one that the train can travel through. If it can I can look (recursively part) for a return trip, just inverting starting with ending calling once again the solver method.
- solve is the method you need to call to get the final result.
You can download the solution here with the file processing too.
The algorithm it’s correct but the implementation sucks, I think I can code a better one with less line of code, I’ve just to spend some time on it… It was a time challenge and I was not thinking so much of optimization… I don’t know If I’ll post a revisited one… For now it’s all folks!
return ‘Bye’
July 18th, 2008 § § permalink
That’s was the title of the first and very funny problem of Google Code Jam Qualification Round 2008
The urban legend goes that if you go to the Google homepage and search for “Google”, the universe will implode. We have a secret to share… It is true! Please don’t try it, or tell anyone. All right, maybe not. We are just kidding.
You can find (I think you need to register) the whole problem here.
I did it recursively and for the large input I had to setrecursionlimit up to 2000. I’ll show you why…
You can download my solution here.
That’s my implementation:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| import sys
sys.setrecursionlimit(20000)
def process(se, q, switch = 0):
if len(q) == 0:
return switch
rank = {}
notin = False
for i in se:
if q.count(i)>0:
rank[i] = q.index(i)
else:
notin = i
if notin == False:
a,b = rank[se[0]],0
for i in rank:
if rank[i]>b:
a = i
b = rank[i]
switch += 1
return process(se,q[b:],switch)
else:
return switch |
In words…
se is the list ( ['Google','Yahoo',...] ) of search engines
q is the list (like the one above) of queries
- At the beginning I did no switches (switch = 0), but it’s a default value, when I’ll call it I’ll set it
- If there is no query I don’t need to switch anymore, I can return the number of switches (switch)
- rank is a dictionary. It’s just like ‘Search Engine’: ‘position of the first query with the same name of this search engine’
- if the name of a search engine does not appear in the query list I may do all searches with that search engines (the notin test)
- else I look in the dictionary for what is the search engine that appear as later as possible in the query list and I use it, I add 1 to the switches counter, and return (recursively) the process giving the same se, the current switches number but a different query list!
The new query list is just the remaining queries. Example:
se = Yeehaw, NSM, Dont Ask, B9, Googol
q = Yeehaw,Yeehaw,Googol,B9,Googol,NSM,B9,NSM,Dont Ask,Googol
Call #1
We did no switch, so switch = 0
All search engines appears in the query list… Here is the list of each se with the index of the first query with the same name:
Yeehaw: 0, NSM: 5, Dont Ask: 8, B9: 3, Googol: 2
Dont Ask has an higher index so we can use that to search up to that index with it, and process the next call with the new query list:
se = Yeehaw, NSM, Dont Ask, B9, Googol
q = Dont Ask,Googol
Call #2
We did one switch, so switch = 1
Yeehaw, NSM and B9 do not appear in the query list, I can use any of them without do any other change, I return the current number of switches ;^) Quite simple ;^)
In the big file there was a query list of 999 items Like this:
se = ['A', 'B']
q = ['A', 'B','A', 'B','A', 'B','A', 'B','A', 'B',...]
ok? It did lots of recursion and went over the limit, I had to adjust that :^D
return ‘Bye’
July 18th, 2008 § § permalink
I’ll be short.
Qualification Round has just ended.
It was very cool, there were 3 problems, I wasn’t able to solve the last, I’ll discuss with you them all in these days, now let me go to sleep, it’s 2 a.m. in Italy :^D
return ‘yawn’
July 16th, 2008 § § permalink
Hi there :^)
Let’s continue with the “Practice Problems” of GCJ, the next is a problem about perfect mazes.
This time the source code will be quite long, sorry :^D. I’m currently having some problems with wordpress and utf8 (if you know how to solve quickly please leave a comment), so the complete source code is available here.
We have to map the maze, square by square we have to know where you can move starting from that square. We use a code to do this.
Idea #1
Look at the map of “cases”. Choose one of them, any of them. To be short consider N as North, S as South and so on… Now consider (in example) E = 1 if you can move to East, else 0, and do it with the others too, then put the result in this order EWSN. It’s binary, yes. Got it? Try to convert it to hex and compare the result with the problem case-codes ;^)
I’ll import the alien-numbers to do the conversion (I know that’s simple and there are other ways, but you will see what I used to debug :^D)
I’m going to comment my implementation part by part. Let’s start.
Importing
1
2
3
| from __future__ import with_statement
from copy import deepcopy
import aliensys |
with statement with input and output files (I did know show that on the previous post)
deepcopy is very useful. Remember that in python names are just a reference. I had serious problem debugging my code due to this!
aliensys… well you can now imagine why I’m using this… but that’s not the only reason :^D
class Mode
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
| class mode(object):
def code(self):
HEX = '0123456789abcdef'
BIN = '01'
number = ''
for i in (self.e,self.w,self.s,self.n):
number += str(1*i)
return solve(number + ' ' + BIN + ' ' + HEX)
def __init__(self, e = False, w = False, s = False, n = False):
self.e = e
self.w = w
self.s = s
self.n = n
def change(self, k, val):
if k == 'e':
self.e = val
elif k == 'w':
self.w = val
elif k == 'n':
self.n = val
elif k == 's':
self.s = val
def draw(self):
MAZE = u'.???????????????'
HEX = '0123456789abcdef'
return solve(self.code()+' '+HEX+' '+MAZE)
def __str__(self):
try:
return self.code()
except AttributeError:
return 'tmpNone'
def __repr__(self):
try:
return str(self.code())
except AttributeError:
return 'tmpNone'
def draw(self):
MAZE = u'.???????????????'
HEX = '0123456789abcdef'
return solve(self.code()+' '+HEX+' '+MAZE) |
__init__ I just get EWSN and save them.
code It returns the case-code using EWSN
Now come one of the interesting parts :^)
Note that I pasted it as is, sorry for the question marks, it’s a wordpress problem with utf8, anyway it should be clear in my perfect maze solution file. Check it.
Debugging this was not simple. I used the __str__ and __repr__ because the IDLE debugger uses them, but it was not enough. I looked for utf8 symbols that do the trick, I can’t show those in this post (damned wordpress) but some aliens could use them as numeral system… and I’ve a converter to read that :^D
I can draw a “mode” of a square of the maze…
class Square
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| class sqr(object):
def __init__(self, x,y,m):
self.x = x
self.y = y
self.m = m
def move(self, d, update=True):
if d == 'e':
self.x+=1
if update: self.m.w=True
elif d == 'w':
self.x-=1
if update: self.m.e=True
elif d == 'n':
self.y-=1
if update: self.m.s=True
elif d == 's':
self.y+=1
if update: self.m.n=True
def __eq__(self, x):
return ((self.x == x.x) and (self.y == x.y))
def __cmp__(self, x):
if ((self.x == x.x) and (self.y == x.y)):
return 0
elif self.y==x.y:
return cmp(self.x,x.x)
else:
return cmp(self.y,x.y) |
We have to know the position of a square (x and y) and its mode.
We can move a square (to E,W,N or S), and from that position it could (if want) come back to the old position (the update part)
__cmp__ and __eq__ are used in the Maze class because I need to sort squares. Given a list of squares comes first the square that has the minor y and minor x, then comes the one that has the same y but greater x else a greater y and the minor x… and so on… I think it will be clearer in the next class…
ls2str
82
83
84
85
86
| def ls2str(ls):
r = ''
for i in ls:
r+=str(i)
return r |
That’s a simple function that convert a list to a string… No. str(ls) is just like print ls and that’s not what we will need ;^)
class Maze
Now the big part :^D I’ll slice it in more parts because is very long (120 lines) and not in the same order of the real file. Anyway I’m trying to save line numbers so that you can check ;^)
__init__
193
194
195
196
197
198
| def __init__(self, i2o, o2i):
self.i2o = list(i2o) # in 2 out
self.o2i = list(o2i) # out 2 in
self.head = 's'
self.sqrs = []
self.init=False |
The problem gives us two path, as string, the first is from the entrance to the exit (i2o) and the second is from the exit to the entrance (o2i). Our head is poting to S, we know no squares now, because we haven’t started yet ;^)
have_sqr
89
90
91
92
93
94
95
| def have_sqr(self, s):
check = False
for i in self.sqrs:
if s == i:
check = True
break
return check |
It’s simple, it there is already a square with the same x and y returns True, else False… it will be useful :^D
turn
96
97
98
99
100
101
102
103
104
105
106
107
108
| def turn(self, direction):
if direction == 'R':
for i in zip(list('ewsn'), list('snwe')):
if i[0] == self.head:
self.head = i[1]
return True
elif direction == 'L':
for i in zip(list('ewsn'), list('nsew')):
if i[0] == self.head:
self.head = i[1]
return True
else:
return False |
When you are walking trough the maze you don’t change square if you turn. Returns True if you turned (and change the direction, read with attention those lines), else returns False
walk
That’s one of the longest parts. We want to walk trough the maze using a path….
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| def walk(self, path, reverse=False):
pre = False
for i in path:
if pre:
pass
elif reverse:
pre = deepcopy(self.sqrs[-1])
else:
pre = sqr(0,-1,mode())
if self.turn(i) == False:
if self.have_sqr(pre) == False:
self.sqrs.append(pre)
index = self.sqrs.index(pre)
self.sqrs[index].m.change(self.head, True)
new = deepcopy(pre)
new.m = mode() # resetting modes
new.move(self.head)
pre = deepcopy(new) # remember to update pre
if self.have_sqr(new) == False: # the last ;)
self.sqrs.append(deepcopy(new))
if reverse == False: # Changing direction...
self.last = self.sqrs[-1]
for dirs in zip(list('ewns'), list('wesn')):
if self.head == dirs[0]:
self.head = dirs[1]
break |
It’s simple. Don’t panic :^)
We start from a square, the path tells what to do. While it says to turn, we turn, if it says to go we move to a new square… are you sure is it new? Check it, if not add it, else update the modes.
If B is below A and you can go from A to B you can also go from B to A, so A has S = 1 and B has N = 1 ;^)
walkall
138
139
140
141
142
143
144
| def walkall(self):
if self.init:
pass
else:
self.walk(self.i2o)
self.walk(self.o2i, True)
self.init = True |
To have a clear and correct map we need to walk using i2o and o2i too, this means to walk trough all paths…
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
| def getlist(self):
self.walkall()
m = deepcopy(self.sqrs)
for i in m:
if i == self.last:
index = m.index(i)
del m[index]
xs = [i.x for i in m]
xmin = min(xs)
xm = max(xs)
ys = [i.y for i in m]
ym = max(ys)
m.sort()
r = []
a = []
for y in xrange(0,ym+1):
a = []
for x in xrange(xmin,xm+1):
c = sqr(x,y,mode())
if 1 == 0:
pass
else:
if c in m:
i = m.index(c)
a.append(m[i].m)
del m[i]
elif xmin<x<xm:
a.append('0')
r.append(ls2str(a))
return r |
The requested output is a list of line, each one contains the modes of the squares of that maze’s associated line. We need to order self.sqrs that’s why redefined the __cmp__ method for a square.
We’ve to delete the starting and the ending point from the map too, this method is too long for me, I think there is a better way to do this… but was the first way that turned in my mind…
draw
180
181
182
183
184
185
186
187
188
189
190
191
| def draw(self):
MAZE = u'.???????????????'
HEX = '0123456789abcdef'
maxs = []
p=[]
for i in self.getlist():
l = solve(i+' '+HEX+' '+MAZE)
maxs.append(len(l))
p.append(l)
m = max(maxs)
for i in p:
print i.center(m) |
My draw idea was cool enough that I forgot I’ve already implemented in the mode class… i did it again! o_O Don’t ask me why, maybe I was drunk when I wrote that :^O
Anyway… we can draw a maze now :^) really :^D
File eater
Final part, we have an input file, and we’ve to produce an output one…
eatFile will do the trick
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
| def eatFile(path_i, path_o, show=True, draw=False):
with file(path_i, 'r') as f_in:
lines = f_in.readlines()
n = int(lines[0].replace('\n', ''))
del lines[0]
with file(path_o, 'w') as f_out:
for i in xrange(0,n):
s = lines[i].replace('\n', '').split(' ')
m = maze(s[0],s[1])
if show:
print 'Case #%d:' % (i+1)
if draw:
m.draw()
print '\n\n'
if draw:
f_out.write('Case #%d:\n' % (i+1))
for j in m.getlist():
f_out.write(j+'\n')
del m |
Working with text files is painless with python. Using the with statement I don’t have to open and close files, it’s cool :^D
The mechanism is simple:
- Get the number of lines
- For each line of the input file:
- Create a maze
- Print and draw if you have to
- write to the file output
- Finish :^D
and now the operative part….
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
| # Solving the question... (with draws :D)
import time
start = time.time()
before = time.time()
path1 = 'B2-small.in'
path2 = 'B2-small.out.txt'
eatFile(path1,path2,True,True)
print 'Small in',time.time() - before,'secs'
before = time.time()
path1 = 'B2-large.in'
path2 = 'B2-large.out.txt'
eatFile(path1,path2,True,True)
print 'Large in',time.time() - before,'secs'
print 'Both in',time.time() - start,'secs' |
lines 243 and 250 are enough but I wanted to measure the time it tooks to solve the problem :^D
On my pc the final lines were:
Small in 9.17199993134 secs
Large in 247.765999794 secs
Both in 256.983999968 secs
But I had too many thing opened while testing it that’s not a valid test, anyway try it on your computer and tell me your time ;^)
Conclusions
There few notes I’d like to leave.
I spent time, like 2 hours, to solve this. And it is not optimized (I wrote a change method for mode but I don’t use it in sqr when I should, but there are lots of these little things). I was coding thinking of the future but in the future i forgot of the past and… it’s, maybe, TOO object oriented… I’m too slow for this competition I guess… I hope someone will find this useful, my code need to be shorter!
Thanks for reading
return ‘Bye’
July 10th, 2008 § § permalink
In these days I started to study python. That’s a very cool language and I have lots of things to learn, I need exercise. What is better than google code jam to practise?
I will share with you my solution for the first of the “Practice Problems”, it’s about aliens’ numeral system :^) and I’ve, obviously, written my solution in python ;^)
I’m posting it to discuss them with you, maybe I’ll do the same when I’ll have the time to do the others. It doesn’t want to be a spoil so if you want to solve this alone just go and code, when you’ve finished you can come back and comment my code and tell me if you coded a better one :^)
Well, the text of the problem is:
Problem
The decimal numeral system is composed of ten digits, which we represent as “0123456789″ (the digits in a system are written from lowest to highest). Imagine you have discovered an alien numeral system composed of some number of digits, which may or may not be the same as those used in decimal. For example, if the alien numeral system were represented as “oF8″, then the numbers one through ten would be (F, 8, Fo, FF, F8, 8o, 8F, 88, Foo, FoF). We would like to be able to work with numbers in arbitrary alien systems. More generally, we want to be able to convert an arbitrary number that’s written in one alien system into a second alien system.
Input
The first line of input gives the number of cases, N. N test cases follow. Each case is a line formatted as
alien_number source_language target_language
There are some other things, if you want you can read the whole text here.
Ok? That’s should be not so difficult. I’m human, coder and engineering student, I hear aliens speaking every day, it’s ok. The problem is to speak with them :^)
We’re going to:
- Get the number we want convert from system1 to system2
- Convert to decimal that number from system1, we’re human and used to see decimal number :^)
- We know what number it is, we can now convert the decimal number to system2
Well try to think on how we convert from binary to decimal and viceversa, or from hex to decimal and viceversa…
Here is my implementation:
class aliensys(object):
def __init__(self, stringa):
self.symbols = list(stringa)
self.N = len(self.symbols)
def a2d(self, n):
"Convert n from alien to decimal"
s = 0
n = list(n)
n.reverse()
for i in xrange(0, len(n)):
s += self.symbols.index(n[i])*self.N**i
return s
def d2a(self, n):
"Convert n from decimal to alien"
s = ''
while n>=1:
r = n%self.N
n/=self.N
s = self.symbols[r]+s
return s
def convert(self, n, target): # target must be an aliensys
to = self.a2d(n)
return target.d2a(to)
def solve(string):
s = string.replace('\n', '')
s = s.replace('\r', '')
n, src, tgt = s.split(' ') # number, source, target
src = aliensys(src)
tgt = aliensys(tgt)
return src.convert(n,tgt)And it’s so simple to use:
>>> solve('CODE O!CDE? A?JM!.')
'JAM!'ps: did you see that? how WP-syntax is highlighting “string” and “self” on my script? They’re not keyword in pyhton, str is, it shouldn’t do that… I’ve to fix this :\
yield ‘Bye’
July 9th, 2008 § § permalink
I’m going to write about programming in next posts, that’s means I need a way to show some code here and there. My posts need a code highlighter to be clear :^)
I googled for a while to find a decent code highlighter. I found several code highlighters, some do it on the fly in JavaScript, some others do it server side, and some one let Google do it :^D. I’ve found a comparison too.
Well, I installed all of these, tried them and finally WP-syntax wins! Why?
- It’s server-side, if you do not trust me or my site who cares? you will see highlighted code anyway ;^)
- Supports a painless copy & paste, when you copy from most of the other highlighters and paste in a simple text editor the code comes with more \n and # than what the author wrote… and maybe with line numbers too!
- Supports line numbers, and the coolest part is that you can start from the line you want, it could be very useful!
- And last but not least: I like it :^D, i’ll maybe fix the css to fit with the theme when I’ll end it (that’s cool but I want one written by me :^)
The only very bad thing is that the switching from HTML visual and WYSIWYG visual is very painful, I hope they’ll improve that!
Anyway here is the proof :^)
94
95
96
97
98
99
100
101
102
103
104
105
106
107
| def fooer(count=200,start=2): # a decent foo should have at least 2 'o'
for i in xrange(start, start+count):
yield 'f' + 'o'*i
def allfoo():
ppl = ('I','You','He','She','It','We','You','They')
ippl = iter(ppl)
for s in fooer(len(ppl)):
i = ippl.next()
if i in ('He','She','It'):
s += 'es'
print i,s
allfoo() |
That’s, actually, the proof of how you can code very useless things but they are highlighted pretty well anyway :^D
return ‘Bye’
July 8th, 2008 § § permalink
I like to develop software, application in general but I prefer web applications.
Being a software developer could be the most boring and maybe painful thing to do you you don’t like to. You’ve to face everyday to problems that you don’t have and… you’ve to solve them, if you don’t get it like a challenge you get stressed from this.
I like it, really. If you do not like problem solving you may think I’m kinda mad or something, well… maybe I am :^D (but I’m not the only one)
I’ll try to run this blog and share with readers my opinions, that’s the first (and I hope the less meaningful) post and reading this in the future maybe will make me laugh, but who cares…
return ‘Bye’