Codingame Solution: Shadows of the Knight - Episode 1

Batman will look for the hostages on a given building by jumping from one window to another using his grapnel gun. Batman's goal is to jump to the window where the hostages are located in order to disarm the bombs. Unfortunately he has a limited number of jumps before the bombs go off...

For some tests, the bombs' location may change from one execution to the other: the goal is to help you find the best algorithm in all cases.

The tests provided are similar to the validation tests used to compute the final score but remain different.

The direction indicating where the bomb is.

Solution

Imagine a rectangular box with the size of the house. We have no idea where the Joker is hiding, but we get pretty good feedback for every move we make. If we get the feedback below and right, it means that we can exclude everything from the top left. So, based on the feedback, we first adjust the coordinates of the rectangular bounding box - for all the other direction analogously.

Now the trick part. Where is the best position to jump to? With the adjusted bounding box, the best we can do is always go right into the middle of that box. This is a 2D bisection, or binary search, which completes in \(O(\log n)\). Let our bounding box be defined as \(x_1=0, y_1=0, x_ 2=W-1, y_2=H-1\). After the update of the bounding box with the feedback we got, the coordinate \((x, y)\) of Batman can be calculated with the left coordinate, plus half the span of the bounding box:

\[ (x, y) = \left(x_1 + \frac{1}{2}(x_2 - x_1), y_1 + \frac{1}{2}(y_2 - y_1)\right) \]

This works since we work with integers, so halfing the search space on a discrete grid must converge eventually. Bringing together this knowledge, an implementation in C# can then look as follows:

using System;

class Player {

  static void Main(string[] args) {

    string[] inputs = Console.ReadLine().Split(' ');
    int W = int.Parse(inputs[0]); // width of the building.
    int H = int.Parse(inputs[1]); // height of the building.
    int N = int.Parse(Console.ReadLine()); // maximum number of turns before game over.
    inputs = Console.ReadLine().Split(' ');
    int x = int.Parse(inputs[0]);
    int y = int.Parse(inputs[1]);

    int x1 = 0;
    int y1 = 0;
    int x2 = W - 1;
    int y2 = H - 1;

    while (true) {

      string BOMB_DIR = Console.ReadLine(); // the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)

      if (BOMB_DIR.Contains("U")) {
        y2 = y - 1;
      } else if (BOMB_DIR.Contains("D")) {
        y1 = y + 1;
      }

      if (BOMB_DIR.Contains("L")) {
        x2 = x - 1;
      } else if (BOMB_DIR.Contains("R")) {
        x1 = x + 1;
      }

      x = x1 + (x2 - x1) / 2;
      y = y1 + (y2 - y1) / 2;

      Console.WriteLine(x + " " + y);
    }
  }
}

Synopsis