So I am currently doing the google Foobar Challenge and as it turns out the newest one is in Python 2.7 and not in 3.8 anymore. I did not read up on this, shame on me, so I developed in 3.8 and have now encountered some anomalies which I am uncertain where they are coming from. I have already found out that there might be differences between the integer and the float division but I don't know if thats really the root of my problem. (I btw cant use from_future_)
On to the code:
import math
from math import gcd
def findmultiples(coordinates, list, dim):
coords = coordinates[:]
while (coordinates[0] <= dim[0] and coordinates[1] <= dim[1]) and (coordinates[0] >= -dim[0] and coordinates[1] >= -dim[1]):
if tuple(coordinates) in list:
list.remove(tuple(coordinates))
coordinates[0] = coordinates[0] + coords[0]
coordinates[1] = coordinates[1] + coords[1]
return list
def solution(dim, your_position, trainer_position, distance):
coordinate = [(x,y) for x in range(-dim[0] , dim[0]+1) for y in range(-dim[1] , dim[1]+1)]
coordinate.sort()
result = []
for i in range(1):
for x,y in coordinate:
y_position = your_position[:]
t_position = trainer_position[:]
beam_position = your_position[:]
distancetraveled = 0
if x == 0 and y == 0:
continue
denom = gcd(x,y)
x = x/denom
y = y/denom
while True:
distancetraveled += math.sqrt((x * x) + (y * y))
if(distancetraveled > distance):
break
beam_position[0] += x # add x coordinate
beam_position[1] += y
if (beam_position[0] > dim[0] or beam_position[0] <0 ): # Check if out of bounds along x-axis
t_position[0] = dim[0] - t_position[0] # Mirror the t_position along the y-axis
y_position[0] = dim[0] - y_position[0] # Mirror y_position along the y-axis
beam_position[0] = (beam_position[0] + dim[0]) % (2*dim[0])
if (beam_position[1] > dim[1] or beam_position[1] <0 ): # Check if out of bonds along y-axis
t_position[1] = dim[1] - t_position[1] # Mirror the t_position along the x-axis
y_position[1] = dim[1] - y_position[1] # Mirror y_position along the x-axis
beam_position[1] = (beam_position[1] + dim[1]) % (2*dim[1])
if (beam_position[0] == t_position[0] and beam_position[1] == t_position[1]):
coordinate = findmultiples([x,y], coordinate, dim)
count = 1
result.extend((x,0) for x in range(count))
break
if(beam_position == y_position):
coordinate = findmultiples([x,y], coordinate, dim)
break
return len(result)
It's rather short and the only difference I had to do (at least I thought so) to be able to run this on Python 2.7 was to change the second import to from fractions import gcd but apparently this does not work, as for some reason the program takes forever in line 10 coordinates[0] = coordinates[0] + coords[0]. I have so far not been able to finish the cProfile test I was running so I am currently assuming that the program is stuck there.
Now the differences I can observer (Because the program finishes) is with this solution([3,2], [1,1], [2,1], 4) the result comes back as 7 in Python 2.7(The correct result btw) and as 6 in 3.9. The second test with solution([300,275], [150,150], [185,100], 500) has of yet still not finished. I tried measuring timings with cProfile but the first test finishes too fast as for me to be able to see anything useful. (0.000s vs 0.001s)
I tried googling around and I was only able to find the difference and not too much more without diving into the 6.5k pages of Python 2.7.13 Documentation.
I hope someone can help me. Cheers
Edit: cProfile actually finished but without telling me a whole lot(Edit: It did actually tell me that findmultiples is called a whole lot more in this version, than it is in the other version:
ncalls tottime percall cumtime percall filename:lineno(function)
1 3.905 3.905 1417.093 1417.093 4.1.py:16(solution)
689 1408.263 2.044 1412.459 2.050 4.1.py:5(findmultiples)
26 0.000 0.000 0.000 0.000 4.1.py:51(<genexpr>)
1 0.012 0.012 1417.105 1417.105 <string>:1(<module>)
330463 0.208 0.000 0.208 0.000 fractions.py:18(gcd)
1 0.000 0.000 0.000 0.000 {len}
3638301 0.499 0.000 0.499 0.000 {math.sqrt}
1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}
13 0.000 0.000 0.000 0.000 {method 'extend' of 'list' objects}
687 4.197 0.006 4.197 0.006 {method 'remove' of 'list' objects}
1 0.015 0.015 0.015 0.015 {method 'sort' of 'list' objects}
616 0.007 0.000 0.007 0.000 {range}
It took nearly 40 times as long as it did in Python 3.8. 1417s vs 37s with the main difference being that find multiples was called about 30 times more often. Which would explain the brunt of the difference. I was able to find the problem(at least I think I did). For some reason the list.remove() as well as the gcd() functions worked a bit differently. I changed them to this:
index = list.index(tuple(coordinates))
list.pop(index)
list.insert(index, (0,0))
.
.
.
.
denom = gcd(x,y)
x = x/abs(denom)
y = y/abs(denom)
And now the code seems to be working the same in Python3.x and Python 2.x. Funnily enough in 2.x it is now about 20% faster but I can't be bothered to figure out why
