tag:blogger.com,1999:blog-29632375.post1998565404885242573..comments2015-07-26T10:48:18.008-07:00Comments on vexorian's blog: To solve Google Codejam: Hall of Mirrors Ivexoriannoreply@blogger.comBlogger5125tag:blogger.com,1999:blog-29632375.post-67357258436953760122012-04-20T17:25:51.705-07:002012-04-20T17:25:51.705-07:00Once you know a point is within the path of the li...Once you know a point is within the path of the light, and the horizontal and vertical mirrors it crosses it is possible to get the squared distance in integral form. (Similar logic to D-small)<br /><br />Somehow I thought 64 bits would get an overflow even with continual reductions. Uh, know I see that I was considering the effect of lcm too well.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-68453400065699273392012-04-20T17:13:41.554-07:002012-04-20T17:13:41.554-07:00Rather than scaling, I just used a fraction class ...Rather than scaling, I just used a fraction class based on 2 64 bit numbers - it was fast enough and using continual reduction it never overflows given the constraints of the problem.<br />I was less concerned about floating point numbers being problematic due to the question of whether they hit an intersection or not - my concern was the final distance calculation cutoff. I was sure that there was a right triangle a,b,c where c was within epsilon above an integer. However I was completely wrong, simple test code shows nothing which would match a relative epsilon of even 0.01%Tilpsnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-26222762187556395392012-04-17T14:50:03.946-07:002012-04-17T14:50:03.946-07:00There is a trick to avoid all the complications ar...There is a trick to avoid all the complications around floating point numbers.<br /><br />I took the same approach you initially had for D-small in the competition, reasoning that there was a limited set of coprime starting vectors you had to try.<br /><br />Then for each of these I scaled the grid by LCM(vy,vx)/vx in the x direction and similar for the y plus an extra factor of 2 to allow the starting point to fall on a scaled grid line.<br /><br />The movement vector in your scaled grid then just becomes of the form (1,1) (-1,1) etc. Starting vectors like (1,0) are special cases.<br /><br />Then for each step of the ray tracing you know the next point of interest will be on a 'real' horizontal or vertical grid line (i.e a grid line in the original grid) and the other co-ordinate will be on one of the scaled grid lines.<br /><br />I calculated the next vertical and next horizontal intersection 'real' intersection and moved to the nearest, checked the mirror config at that point and reversed the unit direction vectors as appropriate.<br /><br />Distance travelled so far also becomes an integer calc so everything is exact. Runs in about 5s on my laptop.<br /><br />Totally agree about visual debugging being incredibly useful for a problem like this, I ended up with loads of scaled grids drawn all over my jotter pad trying to track down index out of range exceptions. SVG is a good tip, your code for you diagrams makes that look like the way forward.cwnoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-17361074782984325922012-04-17T06:10:00.927-07:002012-04-17T06:10:00.927-07:00It does depend on the shape of the maze and your l...It does depend on the shape of the maze and your location. Because they affect how long the angle you try takes to bounce back to your location and in D-large the light can get destroyed.<br /><br />This was actually annoying to me as well. When I was first trying to solve D-small I thought that the light needed to come back to you in exactly the opposite angle, but I was getting very different results in the third example.vexoriannoreply@blogger.comtag:blogger.com,1999:blog-29632375.post-11375257768742038942012-04-17T05:20:54.555-07:002012-04-17T05:20:54.555-07:00Thank you for beautiful and detailed explanation! ...Thank you for beautiful and detailed explanation! I've stuck with the very description of the problem, namely with "how many images of yourself can you see". I already understand the analysis, but it's still counterintuitive to me that "distinct angles" and "number of images of yourself" is the same thing, and even more counterintuitive thing is that this number doesn't depend of the shape of the maze.Ilya Perskynoreply@blogger.com