I am currently studying in depth object oriented programming, and a way I found to do this interactively is through CodinGame projects. I am currently trying to solve the Shadow of the Knight - 1 puzzle, but I am stuck in the binary search algorithm.
In this game/puzzle, the player must navigate through a building to locate points of interest. The building is represented as a rectangular array of windows, with the top-left window at index (0,0). The game involves a series of turns where, before each jump, the player receives information about the direction of the bombs relative to their current window position.
There are a certain amount of initialization inputs:
Line 1: Two integers W and H represent the width and height of the building in terms of windows. Line 2: One integer N denotes the maximum number of jumps allowed before the bombs detonate. Line 3: Two integers X0 and Y0 represent the starting position of the player.
Game Turn Input:
The program enters an infinite loop where, during each game turn, it receives input indicating the direction of the bombs. Possible directions include U (Up), UR (Up-Right), R (Right), DR (Down-Right), D (Down), DL (Down-Left), L (Left), and UL (Up-Left).
For each turn, the program must output a single line with two integers X and Y, separated by a space character. These values represent the coordinates of the next window the player should jump to. X indicates the index along the horizontal axis, and Y indicates the index along the vertical axis.
Building Representation:
The building is represented as a rectangular 2D array (list) of windows. The dimensions of this array are determined by W (width) and H (height) obtained during initialization. This list ideally needs to be ordered, for a proper binary search algorithm to work.
The challenge lies in designing an algorithm that efficiently uses the bomb direction information to guide the player through the building, considering the changing locations of bombs and hostages across different executions. The solution must balance accuracy and speed within the specified constraints.
Now, judging by its instructions, I want to work on an approach that:
The issue I have is with my binary search algorithm, which I am not quite sure is working well, and I would like some help in finding a better way to formulate it:
import sys
import math
class Jumper():
def __init__(self):
self.grid = []
self.jumps = 0
self.current_position = (0, 0)
def create_grid(self):
w, h = [int(i) for i in input().split()]
self.grid = [[0 for _ in range(w)] for _ in range(h)]
self.jumps = int(input()) # maximum number of turns before game over.
x0, y0 = [int(i) for i in input().split()]
self.current_position = (x0, y0)
def search(self, L, e):
"""Assumes L is a list, the elements of which are in ascending order.
Returns True if e is in L and False otherwise."""
def binary_search(L, e, low, high):
if high == low:
return L[low] == e
mid = (low+high)//2
if L[mid] == e:
return True
elif L[mid] > e:
if low == mid:
return False
else:
return binary_search(L,e,low,mid-1)
else:
return binary_search(L,e,mid+1,high)
if not L:
return False
else:
return binary_search(L,e,0,len(L)-1)
def jump_to_position(self):
while True:
bomb_dir = input() # the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)
# the location of the next window Batman should jump to.
print("0 0")
batman = Jumper()
batman.read_inputs()
batman.search()
This is an example of the output from the game:
Game information:
Locate the bombs, save the hostages!
Batman is on window (2,3)
The bombs are located below and to the right of Batman
Game information:
Timeout: your program did not provide an input in due time.
Batman is on window (2,3)
The bombs are located below and to the right of Batman
Considering these instructions and my approach, I think what I am doing wrong is having a binary search algorithm that only works on 1-Dimensional list, and that my list is not getting ordered.
I would like to find a way to store in an orderly manner the w,h inputs in the self.grid, and modify the search function so that it can process the inputs in the right order and always give me the most optimal search.
A couple of things are going on here.
L[mid_h][mid_w] == e instead of L[mid] == e since your matrix is currently a list of horizontal rows).All that said, the binary search process still works but you'll need to rethink the setup some and you likely can't copy-paste code from somewhere (I'll try to balance giving clear code info without spoiling the puzzle for you).
Addressing the issues in order:
A binary search doesn't have to use a list (you can if you want). All that matters is that you have an upper and lower bound and a way to determine if the value you select is too high, too low, or equal to what you are seeking. If you need some help stepping back from the nitty-gritty of code, GeeksforGeeks has a pretty code-agnostic review for you. Mostly, you just need to consider the game's while loop as your stepping loop and any variable (or, in your case, object property) updating should happen there. That means that, rather than being able to do the whole search within a method, perhaps your replace your "search" method with a "jump" or "next_jump" method that takes the direction input as an argument and returns the next coordinates to check.
(and 3) Since a binary search doesn't work in 2D, you'll actually be doing 2 simultaneous binary searches, so your can save your x and y ranges separately, rather than using a grid, to make your checks make sense. Your jump method can take the input in and return the needed output each time.
Combining those ideas would give you something like:
class Jumper:
def __init__(self):
w, h = [int(i) for i in input().split()]
self.x_range, self.y_range = list(range(w)), list(range(h))
self.jumps = int(input())
self.current_position = [int(i) for i in input().split()]
def jump(self, direction):
# Split text into >, <, == standins for x and y separately
dir_map = {'U': (0, -1), 'UR': (1, -1), 'UL': (-1, -1), # Up means decrease y
'D': (0, 1), 'DR': (1, 1), 'DL': (-1, 1), # Down means increase y
'R': (1, 0), 'L': (-1, 0), '': (0, 0)}
horiz, vert = dir_map[direction]
next_x, next_y = self.current_position
# X Binary Search Step
if horiz > 0: # Need to move right
self.x_range = [x for x in self.x_range if x > self.current_position[0]]
elif horiz < 0: # Need to move left
self.x_range = [x for x in self.x_range if x < self.current_position[0]]
else: # horiz == 0 Do Nothing
self.x_range = [self.current_position[0]]
next_x = (max(self.x_range) + min(self.x_range))//2
# Y Binary Search Step
# TODO: Do the same but with next_y instead of next_x and use vert instead of horiz
# Update self AKA actually jump
# assert self.current_position != [next_x, next_y] # Quick check to avoid infinite loops
self.current_position = [next_x, next_y]
return tuple(self.current_position)
If the above made sense, you should be able to now run the game more like this:
# Initialize jumper and game
batman = Jumper()
# game loop
while True:
bomb_dir = input() # the direction of the bombs from batman's current location (U, UR, R, DR, D, DL, L or UL)
# the location of the next window Batman should jump to.
x, y = batman.jump(direction = bomb_dir)
print(f'{x} {y}')