Rabbit Searching Problem in Rust

Question

This is my Rust implementation of the rabbit searching algorithm I found yesterday in this video. The problem statement is as follows.

There are 100 holes in a line. A rabbit is in one of the holes. You need to catch the rabbit. However, you can only look at one hole at a time. If the rabbit is in the hole that you looked, you catch the rabbit. If the rabbit is not in the hole, the rabbit will move to an adjacent hole.

The algorithm works as intended. You need to search two times. First, do a whole pass, and then do another pass but starting at index 1. However, I'm not familiar with Rust yet, so there are some awkward code snippets in my implementation. How can I improve the code according to Rust's best practices? Thanks.

use rand::Rng;

const N: i32 = 100;

fn main() {
    let mut rabbit_pos: i32 = rand::thread_rng().gen_range(0..N);
    println!("Rabbit is at {}", rabbit_pos);

    let searched = search(&mut rabbit_pos);
    println!("Rabbit is at {}", rabbit_pos);
}

fn search(rabbit_pos: &mut i32) -> i32 {
    let mut found = false;
    let mut found_pos = 0;
    for i in 0..N {
        if lookup(i, rabbit_pos) {
            println!("Found {}", i);
            found = true;
            found_pos = i;
            break;
        }
    }

    if found {
        return found_pos;
    }

    for i in 1..N {
        if lookup(i, rabbit_pos) {
            println!("Found {}", i);
            found = true;
            found_pos = i;
            break;
        }
    }

    found_pos
}

fn lookup(n: i32, rabbit_pos: &mut i32) -> bool {
    println!("Searching for {}", n);
    if *rabbit_pos == n {
        return true;
    } else {
        move_rabbit(rabbit_pos);
        return false;
    }
}

fn move_rabbit(prev: &mut i32) {
    let new_pos = match *prev {
        0 => 1,
        i if i == (N-1) => N-2,
        _ => *prev + (rand::thread_rng().gen_range(0..2) * 2 - 1),
    };
    println!("Rabbit moved from {} to {}", *prev, new_pos);
    *prev = new_pos;
}

Answer 1

In the search function, I suggest eliminating the variables found and foundpos.

If lookup succeeds, simply return i.

Otherwise it looks fine to me, although I have only scanned the code briefly.

Maybe you could put in a call panic!("Rabbit not found"); in if the algorithm unexpectedly fails ( rabbit not found after the two search loops ). Simply returning found_pos when the algorithm failed would be a little mis-leading!

Answer 2

Possible bug:

Your code only works for even length lines of holes. If you set N to be 99, and the rabbit starts off in an odd hole, you won't find it.

N = 3 example, rabbit starts in hole #1, and alternates between #1 & #0:

[_] r  _
 r [_] _
 _  r [_]
 r [_] _
 _  r [_]
"Rabbit not found" 

You may or may not consider this to be a bug. The question asked for 100, and it works for 100. But you've parameterized it by setting N at the top, so it works for any even value. However, nothing requires N to be even. Either you should add a check, or at the very least a comment, or add a tiny modification to the algorithm so that it works with odd lengths too.

---

The value searched is never used:

    let searched = search(&mut rabbit_pos);
    println!("Rabbit is at {}", rabbit_pos);