My solutions for google foobar
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 

111 lines
4.5 KiB

from math import atan2, sqrt
"""
The first thing you had to realize in order to solve this challenge is that you
could simply mirror the room and check if the beam gets where you want. Let me
show you:
In our case let us make a room of dimension [3,2], with the position of the
target at [1,2]. For the sake of simplicity let us imagine the beam is shot at
[1,2] and so we are trying to shot ourselves. We get something like this:
-----
|*xx|
|xxx|
-----
If we shoot with a vector of [1,0], aka straight ahead, we will get this result:
-----
|*~~|
|xxx|
-----
We can see that the beam gets back to you directly, thanks to the reflection,
and that the goal is achieved! But there is another way to do that:
----- -----
|*~~| |~~*|
|xxx| |xxx|
----- -----
We can here realize that, by putting a mirror version of the room where the beam
gets, we can make a straight line instead of calculating the reflection and see
that it gets to our original target, [1,2], being ourselves!
The good thing with that is that it also allows us to determine the distance
needed by the beam to get through, and thus we can mirror the rooms up to the
maximum distance easily.
The next thing to realize was that room mirrors in a pattern, see the below
diagram:
-----
|*xx|
|xxx|
-----
[...] ----- [...]
|xxx|
|*xx|
-----
----- ----- ----- ----- -----
|*xx| |xx*| |*xx| |xx*| |*xx|
|xxx| |xxx| |xxx| |xxx| |xxx|
----- ----- ----- ----- -----
-----
|xxx|
|*xx|
-----
[...] ----- [...]
|*xx|
|xxx|
-----
x always repeats in the same way, and so does y
Thus we need to figure out how to calculate how to mirror one room twice and we
can make an entire atlas of mirrored rooms!
In our case though the function below only calculates the mirrors of the point
of coordinates node across an atlas of length (distance*2)^2
"""
def mirror_atlas(node, dimensions, distance):
node_mirrored=[]
for i in range(len(node)):
points=[]
# since it is floored we add 1, and python stops before the upper bound
# so +2 in our case
for j in range(-(distance//dimensions[i])-1, (distance//dimensions[i]+2)):
points.append(get_mirror(j, node[i], dimensions[i]))
node_mirrored.append(points)
return node_mirrored
# this simply calculates the mirror nth of a point in a 1D space
def get_mirror(mirror, coordinates, dimensions):
res=coordinates
mirror_rotation=[2*coordinates, 2*(dimensions-coordinates)]
if(mirror<0):
for i in range(mirror, 0):
res-=mirror_rotation[(i+1)%2]
else:
for i in range(mirror, 0, -1):
res+=mirror_rotation[i%2]
return res
# pretty simple too: we get the angle at which the beam is needed to be to get
# to the guard and store its distance. First we do that to yourself, then to the
# guard and if the distance for the guard is lower than yourself then he'll be
# hit first by the beam.
def answer(dimensions, your_position, guard_position, distance):
mirrored = [mirror_atlas(your_position, dimensions,
distance),mirror_atlas(guard_position, dimensions, distance)]
res=set()
angles_dist={}
for i in range(0, len(mirrored)):
for j in mirrored[i][0]:
for k in mirrored[i][1]:
# position of the beam to touch the node, either yourself or the
# guard
beam=atan2((your_position[1]-k), (your_position[0]-j))
# pythagorean theorem gets you the hypothenuse given two points
# of a triangle, which is basically the distance between those
# two points
l=sqrt((your_position[0]-j)**2 + (your_position[1]-k)**2)
if [j,k] != your_position and distance >= l:
if((beam in angles_dist and angles_dist[beam] > l) or beam not in angles_dist):
if i == 0:
angles_dist[beam] = l
else:
angles_dist[beam] = l
# we could find a better result later so let's just
# put that in a set to sort out duplicates
res.add(beam)
return len(res)