CodinGame is an awesome site to practice coding and participate in coding competitions. This week I helped Batman save countless people by helping him find his way to bombs in order to disarm them!
The setup was classic Batman. The Joker has planted a bomb somewhere inside of a building. Batman's heat gun can detect the heat signature of the bomb and gives a reading of what direction it's in. Batman is on the outside of the building and can shoot his grappling gun to zip to another window. The problem is that the bomb is about to go off and his heat gun only lets him know what direction the bomb is relative to the gun! My goal was to save several Gotham buildings and individuals by zeroing in on the bomb within a max number of steps.
Mission Accomplished!
CodinGame is great because it gives you a fun little scenario to play along with. It puts practical meaning to whatever problem you're trying to solve. Also, they have cool animations that show you the result of your program. If you write a bad program for Batman's bomb navigation system, you can see it when running through the test cases (a concerned citizen watching remarks, "Why does batman always go to the bottom of the building and just sit there while there's a bomb to disarm?".) In one of the competitions I participated in, I had to design the pod racer that finished the race the fastest. I was competing in real time against others writing their own programs to out-race me.
The Batman problem was an interesting problem based on it's 2D environment. I initially thought it would require a graph solution, with the windows as nodes and edges as the grappling paths between them, but a binary search algorithm, adapted to work in two dimensions, turned out to get the job done.
The problem reminded me back to the days of studying physics and math using vectors.
The problem simplifies if you break the problem down into each of the dimensions. Breaking the batman problem down into finding the right height and finding the right distance from the left side of the building breaks the problem into two separate binary search problems. The key was to jump to the other half of either the vertical or horizontal dimension and check whether the bomb is still on the same side, in which case we can jump again in the same direction to further cut the field in half, or jump back towards where we came from, half way to the point of where we were before the last jump.
https://www.codingame.com/training/medium/shadows-of-the-knight-episode-1
No comments:
Post a Comment