Finds a moving target within a given space

Question

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)

• iuvbio: This algorithm is not guaranteed to find the rabbit. What if it always moves to the hole that you just checked?
• Stephen Williams: @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)

Answer 1

Simpler

This line:

self.start = random.choice([i for i in range(space)])

is simpler if you use the randrange function instead of choice:

self.start = random.randrange(space)

Similarly for style:

self.style = random.randrange(3)

Documentation

The documentation is excellent.

I appreciate that you keep the documentation lines relatively short, but I think the style variable description should use this more natural line breaking, where all 4 values are on the same line:

style : int
 A number representing one of the 4 possible movement behaviors of the rabbit 
 {1: 'random', 2: 'range', 3: 'up', 4: 'down'}

Since the code restricts style values between 0 and 3, I think the documentation should match that range:

 {0: 'random', 1: 'range', 2: 'up', 3: 'down'}

DRY

In this line:

if check_pos == space_size - 1 or check_pos == 0:

check_pos appears twice, but it could only appear once:

if check_pos in (space_size - 1, 0):

This expression is repeated twice:

int(self.space * .1)

You could set it to a variable in the __init__ method:

self.delta = int(self.space * .1)

• Kelly Bundy: I'd prefer randrange(space) over randint(0, (space - 1)). Especially since they were already thinking in terms of range.
• Kelly Bundy: Do you see why they even check or check_pos == 0 at all? Can that ever happen?
• toolic: @KellyBundy: Regarding randrange, I agree. I updated the answer with attribution to you in the edit comments. Thanks.
• Kelly Bundy: style needs randrange(4) instead of 3. Or maybe randint(1, 4) after all, since that's what their docstring says? Though that doesn't match their list. And really I think they should just use self.style = random.choice([self.move_random, self.move_range, self.move_up, self.move_down]).

Answer 2

business terms

In the Review Context we see:

Random - Randomly choose left or right ...

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

For internal consistency, please stick to Ben Awad's original phrasing of the problem. He seemed to be using a "left" / "right" world setup, so I find names like self.move_up() gratuitously confusing. In general, if a stakeholder uses certain terms in the Problem Specification, try hard to keep using those terms in the code and its documentation.

Also, I wouldn't have minded seeing just a little more context.

There are a set of 100 holes ... rabbit jumps to an adjacent

Upon first reading I visualized a 10 ×ばつ 10 grid like a chessboard, with rabbit able to visit its 4-neighborhood. The fact that the "set" is a 1-D vector is crucial to the problem statement.

docstring

The class has a lovely one-sentence docstring, thank you.

And then it goes on to describe attributes and methods. Which can be nice. But I worry about DRY, especially as the codebase evolves.

The trouble with comments is that they lie. Not at first. But refactors happen, bit rot sets in, and the comments lag behind the code, telling yesterday's news.

We strive to keep comments and docstrings as close to the relevant code as possible, so when things change it's more likely a maintainer will notice that two things are out of sync and immediately set them right.

We also strive to write documentation which both man and machine can read. This explains the popularity of the mypy and pyright type checkers, which keep looking over your shoulder, checking your work, and immediately point out inconsistencies when they arise. Telling a human we have start : int is nice enough, but it was much nicer when you told humans and linters that we have ... , space: int):, since maintainers can keep doing automated checks of that property.

method docs

Similarly with that block of "move" descriptions. Maybe it makes for lovely documentation? But I'd be more comfortable with five short docstrings instead, each attached to its own method.

help()

Recall that help(Rabbit) is informative, and so is examining an instance with help(r). It will go grovelling through all those methods to consolidate their documentation in a single screenful.

If you're dedicated to producing high quality documentation, which is terrific, remember that ecosystem tools such as Sphinx are here to help you.

enum

 self.style = random.choice([0, 1, 2, 3])

This is an OK design choice, but not the best one available. Consider defining an Enum so you can define four helpful names. It could take over the "dispatch" task performed by self.style_list.

Also, it feels like {min_pos, max_pos, range_set} belong in another object, since they're specific to one of the four movement styles.

range

Rather than having a pair of {min_pos, max_pos} variables, consider storing a single range() object. This has the advantage of being immediately self documenting, plus it offers conveniences like an in operator.

 if self.pos == self.max_pos:
 ...
 if self.pos == self.min_pos:

That 2nd test is entirely natural, but the 1st test is a bit weird in python land. Usually we talk about half open intervals in python code. They play well with loop bound tests, and they compose nicely.

The OP code is asking each maintainer to learn that max_pos is a valid bunny position. Don't be surprised if some maintainer assumes the usual conventions apply, and the bunny can only go to max_pos - 1. This is how off-by-one bugs get introduced.

small world

The original problem sets the spaces parameter at 100. But it's a flexible setup which lets us imagine both larger and smaller worlds. This is convenient when writing unit tests, and we also see spaces = 4 show up in the interview video. There are some (unstated) constraints on how small spaces could plausibly be, and that's fine, I'm willing to assume people will only pose plausible problems.

But the \10ドル\%\$ parameter in int(self.space * .1) seems worrying. I don't notice any checks which verify we still have a "big enough" range for the rabbit to move to.

guard

main(100)

Conventionally we protect that with a guard clause:

if __name__ == "__main__":
 main(100)

Why? So other modules, such as a unit test, can safely import this module without unfortunate side effects.

GoF

Consider calling "style" by the more usual term of "strategy".