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.

112 lines
4.5KB

  1. from math import atan2, sqrt
  2. """
  3. The first thing you had to realize in order to solve this challenge is that you
  4. could simply mirror the room and check if the beam gets where you want. Let me
  5. show you:
  6. In our case let us make a room of dimension [3,2], with the position of the
  7. target at [1,2]. For the sake of simplicity let us imagine the beam is shot at
  8. [1,2] and so we are trying to shot ourselves. We get something like this:
  9. -----
  10. |*xx|
  11. |xxx|
  12. -----
  13. If we shoot with a vector of [1,0], aka straight ahead, we will get this result:
  14. -----
  15. |*~~|
  16. |xxx|
  17. -----
  18. We can see that the beam gets back to you directly, thanks to the reflection,
  19. and that the goal is achieved! But there is another way to do that:
  20. ----- -----
  21. |*~~| |~~*|
  22. |xxx| |xxx|
  23. ----- -----
  24. We can here realize that, by putting a mirror version of the room where the beam
  25. gets, we can make a straight line instead of calculating the reflection and see
  26. that it gets to our original target, [1,2], being ourselves!
  27. The good thing with that is that it also allows us to determine the distance
  28. needed by the beam to get through, and thus we can mirror the rooms up to the
  29. maximum distance easily.
  30. The next thing to realize was that room mirrors in a pattern, see the below
  31. diagram:
  32. -----
  33. |*xx|
  34. |xxx|
  35. -----
  36. [...] ----- [...]
  37. |xxx|
  38. |*xx|
  39. -----
  40. ----- ----- ----- ----- -----
  41. |*xx| |xx*| |*xx| |xx*| |*xx|
  42. |xxx| |xxx| |xxx| |xxx| |xxx|
  43. ----- ----- ----- ----- -----
  44. -----
  45. |xxx|
  46. |*xx|
  47. -----
  48. [...] ----- [...]
  49. |*xx|
  50. |xxx|
  51. -----
  52. x always repeats in the same way, and so does y
  53. Thus we need to figure out how to calculate how to mirror one room twice and we
  54. can make an entire atlas of mirrored rooms!
  55. In our case though the function below only calculates the mirrors of the point
  56. of coordinates node across an atlas of length (distance*2)^2
  57. """
  58. def mirror_atlas(node, dimensions, distance):
  59. node_mirrored=[]
  60. for i in range(len(node)):
  61. points=[]
  62. # since it is floored we add 1, and python stops before the upper bound
  63. # so +2 in our case
  64. for j in range(-(distance//dimensions[i])-1, (distance//dimensions[i]+2)):
  65. points.append(get_mirror(j, node[i], dimensions[i]))
  66. node_mirrored.append(points)
  67. return node_mirrored
  68. # this simply calculates the mirror nth of a point in a 1D space
  69. def get_mirror(mirror, coordinates, dimensions):
  70. res=coordinates
  71. mirror_rotation=[2*coordinates, 2*(dimensions-coordinates)]
  72. if(mirror<0):
  73. for i in range(mirror, 0):
  74. res-=mirror_rotation[(i+1)%2]
  75. else:
  76. for i in range(mirror, 0, -1):
  77. res+=mirror_rotation[i%2]
  78. return res
  79. # pretty simple too: we get the angle at which the beam is needed to be to get
  80. # to the guard and store its distance. First we do that to yourself, then to the
  81. # guard and if the distance for the guard is lower than yourself then he'll be
  82. # hit first by the beam.
  83. def answer(dimensions, your_position, guard_position, distance):
  84. mirrored = [mirror_atlas(your_position, dimensions,
  85. distance),mirror_atlas(guard_position, dimensions, distance)]
  86. res=set()
  87. angles_dist={}
  88. for i in range(0, len(mirrored)):
  89. for j in mirrored[i][0]:
  90. for k in mirrored[i][1]:
  91. # position of the beam to touch the node, either yourself or the
  92. # guard
  93. beam=atan2((your_position[1]-k), (your_position[0]-j))
  94. # pythagorean theorem gets you the hypothenuse given two points
  95. # of a triangle, which is basically the distance between those
  96. # two points
  97. l=sqrt((your_position[0]-j)**2 + (your_position[1]-k)**2)
  98. if [j,k] != your_position and distance >= l:
  99. if((beam in angles_dist and angles_dist[beam] > l) or beam not in angles_dist):
  100. if i == 0:
  101. angles_dist[beam] = l
  102. else:
  103. angles_dist[beam] = l
  104. # we could find a better result later so let's just
  105. # put that in a set to sort out duplicates
  106. res.add(beam)
  107. return len(res)