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
while not found:
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)
