"Mathematical puzzle to train the program brain more" _Q40 (code: Ruby)-> Rust unfinished

I thought that rewriting "Mathematical puzzles to train the programmer's brain" with Rust might be just right for preventing blurring.

Q40: A ship you meet on a sinking island

Ruby

Code of book p.193.

q30.rb

N = 16

def check(island)
    pos = [0, N]
    q = [pos]
    log = {pos => 0}
    while q.size > 0 do
        left, right = q.shift
        [-1,1].product([-1,1]) do |dl, dr|
            l,r = left + dl, right + dr
            return log[[left, right]] + 2 if l == r
            if (l >= 0) && (r <= N) && (island[l] == island[r])
                q.push([l, r])
                log[[l,r]] = log[[left, right]] + 2
            end
        end
    end
end

def search(island, left, level)
    island[left] = level
    return check(island) if left == N

    max = -1
    if level > 0
        max = [max, search(island, left + 1, level - 1)].max
    end
    if left + level < N
        max = [max, search(island, left + 1, level + 1)].max
    end
    max
end

puts search([-1] * (N + 1),0 ,0)

The handling of product in Ruby code is easy to understand personally. JavaScript is turned by a for statement. The code is to search all patterns because it is not a very easy problem.

Rust

main.rs

use std::collections::HashMap;

fn main() {
    let size_of_island = 16;
    let mut island:Vec<u64> = (0..size_of_island).map(|_x| 0).collect();
    println!("{}", search(&mut island, 0, 0, size_of_island));
}

pub fn check(island: &Vec<u64>, size_of_island: usize) -> i64 {
    let pos = (0, size_of_island);
    let mut q = vec![pos];
    let mut log = HashMap::new();
    log.insert(pos, 0);
    while q.len() > 0 {
        let p = q.pop().unwrap();
        let left = p.0;
        let right = p.1;
        for d in vec![(-1, 1), (-1, -1), (1, -1), (1, 1)] {
            let dl = left as i64 + d.0;
            let dr = right as i64 + d.1;
            if dl == dr {
                return log.get(&(left, right)).unwrap() + 2;
            }
            if (dl >= 0)
                && (dr < size_of_island as i64)
                && (island[dl as usize] == island[dr as usize])
            {
                if (dl < dr) && !log.contains_key(&(dl as usize, dr as usize)) {
                    q.push((dl as usize, dr as usize));
                    log.insert(
                        (dl as usize, dr as usize),
                        log.get(&(left, right)).unwrap() + 2,
                    );
                }
            }
        }
    }
    return -1;
}

pub fn search(island: &mut Vec<u64>, left: usize, level: u64, size_of_island: usize) -> i64 {
    island[left] = level;
    if left == size_of_island -1 {
        return check(island, size_of_island);
    }

    let mut max: i64 = -1;

    if level > 0 {
        max = *vec![max, search(island, left + 1, level - 1, size_of_island)]
            .iter()
            .max()
            .unwrap();
    }
    if left + (level as usize) < size_of_island {
        max = *vec![max, search(island, left + 1, level + 1, size_of_island)]
            .iter()
            .max()
            .unwrap();
    }
    return max;
}

Almost solid transplant. However, when n = 16, Ruby was 32 and Rust was 34. Unless you calm down and review the boundary values of the algorithm, you will not know what is different. Or rather, Ruby seems to be searching beyond the size of the array? For the time being, I learned about ownership and casting, so I recorded it once. Rust's type-related points are interesting, like a puzzle game.

2020/10/04 Added because I received an improvement point. Thank you very much. Little by little, Rust's idioms make the code more compact.

main.rs

use std::collections::HashMap;

fn main() {
    let size_of_island = 16;
    let mut island:Vec<u64> = (0..size_of_island).map(|_x| 0).collect();
    println!("{}", search(&mut island, 0, 0, size_of_island));
}

pub fn check(island: &Vec<u64>, size_of_island: usize) -> i64 {
    let pos = (0, size_of_island);
    let mut q = vec![pos];
    let mut log = HashMap::new();
    log.insert(pos, 0);
    while q.len() > 0 {
        let (left, right) = q.pop().unwrap();
        for d in vec![(-1, 1), (-1, -1), (1, -1), (1, 1)] {
            let dl = left as i64 + d.0;
            let dr = right as i64 + d.1;
            if dl == dr {
                return log.get(&(left, right)).unwrap() + 2;
            }
            if (dl >= 0)
                && (dr < size_of_island as i64)
                && (island[dl as usize] == island[dr as usize])
            {
                if (dl < dr) && !log.contains_key(&(dl as usize, dr as usize)) {
                    q.push((dl as usize, dr as usize));
                    log.insert(
                        (dl as usize, dr as usize),
                        log.get(&(left, right)).unwrap() + 2,
                    );
                }
            }
        }
    }
    return -1;
}

pub fn search(island: &mut Vec<u64>, left: usize, level: u64, size_of_island: usize) -> i64 {
    island[left] = level;
    if left == size_of_island -1 {
        return check(island, size_of_island);
    }

    let mut max: i64 = -1;

    if level > 0 {
        max = std::cmp::max(max, search(island, left + 1, level - 1, size_of_island));
    }
    if left + (level as usize) < size_of_island {
        max = std::cmp::max(max, search(island, left + 1, level + 1, size_of_island));
    }
    return max;
}

So, after all, in Ruby and Rust, the numerical value deviates from N = 16. Furthermore, from N = 16, Ruby takes much longer to answer. There seems to be something.