# Codingame Solution: Shadows of the Knight - Episode 1

## The Goal

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

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

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

**Output**for one game turn

`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,

`Y`represents the index along the vertical axis. (0,0) is located in the top-left corner of the building.

**Constraints**

`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...*”

All images are copyright to Codingame