3
\$\begingroup\$

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)

\$\endgroup\$
2
  • \$\begingroup\$ This algorithm is not guaranteed to find the rabbit. What if it always moves to the hole that you just checked? \$\endgroup\$
    – iuvbio
    Commented Sep 4, 2022 at 15:08
  • \$\begingroup\$ @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) \$\endgroup\$ Commented Sep 5, 2022 at 16:10

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.