Robert Eisele
Engineer, Systems Architect and DBA

Codingame: Shadows of the Knight - Episode 1

The Goal

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...

Rules

Before each jump, the heat-signature device will provide Batman with the direction of the bombs based on Batman current position:

  • U (Up)
  • UR (Up-Right)
  • R (Right)
  • DR (Down-Right)
  • D (Down)
  • DL (Down-Left)
  • L (Left)
  • UL (Up-Left)

Your mission is to program the device so that it indicates the location of the next window Batman should jump to in order to reach the bombs' room as soon as possible.

Buildings are represented as a rectangular array of windows, the window in the top left corner of the building is at index (0,0).

Note

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.

Game Input

The program must first read the initialization data from standard input. Then, within an infinite loop, read the device data from the standard input and provide to the standard output the next movement instruction.
Initialization input

Line 1 : 2 integers W H. The (W, H) couple represents the width and height of the building as a number of windows.

Line 2 : 1 integer N, which represents the number of jumps Batman can make before the bombs go off.

Line 3 : 2 integers X0 Y0, representing the starting position of Batman.

Input for one game turn
The direction indicating where the bomb is.
Output for one game turn
A single line with 2 integers X Y separated by a space character. (X, Y) represents the location of the next window Batman should jump to. X represents the index along the horizontal axis, Yrepresents the index along the vertical axis. (0,0) is located in the top-left corner of the building.
Constraints
1 ≤ W ≤ 10000
1 ≤ H ≤ 10000
2 ≤ N ≤ 100
0 ≤ X, X0 < W
0 ≤ Y, Y0 < H
Response time per turn ≤ 150ms
Response time per turn ≤ 150ms

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

Batman:Come on Joker, give it up, I know you're hiding in here somewhere, you can't escape from me.
Joker:Oh, but I think I can Batman! Just look behind you. See these buildings over there? In each one of them there is a room full of hostages trapped with my sweet little Joker-BOMBS. They are about to go off any minute now in a marvellous firework! KA-BOOOM!!!
Batman:Damn you Joker, you won't get away with this.
Joker:So what will it be Batman? Do you want to waste time chasing me or will you try to save the poor, poor hostages? I'd hurry if I were you...Ha-ha-ha
Batman:Alfred, I don't have time to check all the buildings' windows: I need a gadget to help me.
Alfred:Certainly sir. I have the perfect device: it can track the bombs heat signature. I'm sending it to you as soon as I'm done reprogramming it.
Joker:So long Batman! Ha-ha-ha OH-OH-OH...

Go to overview

All images are copyright to Codingame