Finds a moving target within a given space

https://youtu.be/XEt09iK8IXs?t=1264

Ben Awad did a mock interview with a React developer, and asked this question. There are a set of 100 holes (0-99). A rabbit is located in one of these holes. Every time you check a hole, the rabbit jumps to an adjacent (to its position) hole. The goal is to come up with an algorithm to find the rabbit.

Rather than focus on the algorithm, I wanted to try to create a working model of this scenario (I think I did implement the correct search, though). I created a Rabbit class that will keep track of where it is and determine how it should move. To properly test the search algorithm, I needed more than just random movement. It's possible the rabbit could just move back and forth between the same two holes forever, and randomly choosing left or right will practically never produce that behavior. To that end, I gave it 4 movement styles that it will choose at random and do constantly for the duration of the run:

Random - Randomly choose left or right

Range - Same as random, but it will stay within a given range

Up - The rabbit will always move right (unless it's at the furthest-right hole)

Down - Opposite of Up

That certainly doesn't cover every possible movement behavior the rabbit could exhibit, but I figured it was variable enough for a simple test simulation. Actually, I'm pretty sure the search works regardless of how the rabbit moves, but it was worth creating the functionality for learning purposes; I'm still a beginner. For range movement, I picked a range that is 20% (unless it's too close to the 1st or last hole) the size of the "space" (the number of holes).

import random
import logging

LOG_FORMAT = '%(levelname)s %(asctime)s - %(message)s'
DATE_FORMAT = '%Y-%m-%d %H:%M:%S'
logging.basicConfig(filename='log.log', filemode='w', level=logging.INFO, format=LOG_FORMAT, datefmt=DATE_FORMAT)

class Rabbit:
"""
A class to represent a rabbit

...

Attributes
----------
space : int
The number of holes to which the rabbit can travel
start : int
the start position of the rabbit
pos : int
The current position of the rabbit
style : int
A number representing one of the 4 possible movement behaviors of the rabbit {1: 'random', 2: 'range',
3: 'up', 4: 'down'}
max_pos : int
The number of the furthest-right hole to which the rabbit can travel
min_pos : int
The number of the furthest-left hole to which the rabbit can travel
range_set : bool
Indicates whether a range has been set to restrict the rabbit's movement
style_list : list
A list of available movement methods

Methods
-------
move_random()
Increments or Decrements the rabbit's current position by 1, randomly
move_range()
Calculates 10% the size of the space attribute, updates max_pos to the current position
plus the 10% figure, updates min_pos to the current position minus the 10% figure,
and then Increments or Decrements the rabbit's current position by 1, randomly
move_up()
Increments the rabbit's current position by 1
move_down()
Decrements the rabbit's current position by 1
move()
Calls the appropriate movement method based on style and style_list
"""
def __init__(self, space: int):
self.space = space
self.start = random.choice([i for i in range(space)])
self.pos = self.start
self.style = random.choice([0, 1, 2, 3])
self.max_pos = space - 1
self.min_pos = 0
self.range_set = False
self.style_list = [self.move_random, self.move_range, self.move_up, self.move_down]

def move_random(self):
"""Increments or Decrements the rabbit's current position by 1, randomly"""
self.pos += random.choice([1, -1])

def move_range(self):
"""Calculates 10% the size of the space attribute, updates max_pos to the current position
plus the 10% figure, updates min_pos to the current position minus the 10% figure,
and then Increments or Decrements the rabbit's current position by 1, randomly"""
if not self.range_set:
self.max_pos = self.pos + min(int(self.space * .1), self.max_pos - self.pos)
self.min_pos = self.pos - min(int(self.space * .1), self.pos)
self.range_set = True
self.move_random()

def move_up(self):
"""Increments the rabbit's current position by 1"""
self.pos += 1

def move_down(self):
"""Decrements the rabbit's current position by 1"""
self.pos -= 1

def move(self):
"""Increments or decrements the rabbit's position if it is at the first or last
hole, respectively. Otherwise, it calls the appropriate movement method based on the current
style, using style_list"""
if self.pos == self.max_pos:
self.move_down()
return

if self.pos == self.min_pos:
self.move_up()
return

self.style_list[self.style]()

def main(space_size: int):
"""Compares the rabbit's current position to the current position being checked. If they are not equal,
the rabbit's position is updated based on its current movement style"""
r = Rabbit(space_size)
found = False
step = 0
check_pos = 0
check_inc = 1
found = check_pos == r.pos
if found:
break
check_pos += check_inc
r.move()
step += 1
if check_pos == space_size - 1 or check_pos == 0:
check_inc *= -1
check_pos += check_inc

logging.info(f"""\n
Range: {r.min_pos} : {r.max_pos}
Rabbit start on : {r.start}
Rabbit found on step: {step}
Style: {r.style_list[r.style].__name__}
Rabbit found: {found}
""")

return found

main(100)


• This algorithm is not guaranteed to find the rabbit. What if it always moves to the hole that you just checked? Sep 4, 2022 at 15:08
• @iuvbio Starting at zero and incrementing by 1 each turn will always find the rabbit when it starts on an even hole. You can test this out on a small number of holes (4 minimum). If you don't find it on the first pass (0-99), that means that it didn't start on an even hole. It must then have started on an odd hole, So stagger the search by 1 (repeat the check at 98 instead of checking 99) and head the other direction, and you will now find it on the second pass (99-0) Sep 5, 2022 at 16:10