"Puzzle mathématique pour entraîner le cerveau du programme plus" _Q40 (code: Ruby) -> Rust inachevé

Je pensais que la réécriture "puzzles mathématiques qui entraînent davantage le cerveau du programmeur" avec Rust pourrait être juste pour éviter le flou.

Q40: Un navire que vous rencontrez sur une île qui coule

Ruby

Code du livre 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)

Le code Ruby est facile à comprendre personnellement à propos de la gestion du «produit». JavaScript est activé par une instruction for. Ce n'est pas si simple, donc le code pour rechercher tous les modèles.

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;
}

Greffe presque solide. Cependant, lorsque n = 16, Ruby avait 32 ans et Rust 34. À moins de vous calmer et de revoir les valeurs limites de l'algorithme, vous ne saurez pas ce qui est différent. Ou plutôt, Ruby semble chercher au-delà de la taille du tableau? Pour le moment, j'ai appris la propriété et le casting, donc je l'ai enregistré une fois. Les points liés au type de Rust sont intéressants, comme un jeu de puzzle.

2020/10/04 Ajouté car j'ai reçu un point d'amélioration. Merci beaucoup. Petit à petit, l'idiome de Rust rend le code plus 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;
}

Donc, après tout, dans Ruby et Rust, la valeur numérique s'écarte de N = 16. De plus, à partir de N = 16, Ruby met beaucoup plus de temps à répondre. Il semble y avoir quelque chose.