"Mathe-Puzzle, um das Programmhirn mehr zu trainieren" _Q40 (Code: Ruby) -> Rost unvollendet

Ich dachte, dass das Umschreiben von "Mathe-Rätseln, die das Gehirn des Programmierers mehr trainieren" mit Rust genau richtig sein könnte, um Unschärfe zu verhindern.

F40: Ein Schiff, das Sie auf einer sinkenden Insel treffen

Ruby

Code für Buch S.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)

Der Ruby-Code ist persönlich leicht zu verstehen, wie man mit "Produkt" umgeht. JavaScript wird durch eine for-Anweisung gedreht. Es ist nicht so einfach, also den Code, um alle Muster zu durchsuchen.

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

Fast solide Transplantation. Wenn jedoch n = 16 war, war Ruby 32 und Rust 34. Wenn Sie sich nicht beruhigen und die Grenzwerte des Algorithmus überprüfen, wissen Sie nicht, was anders ist. Oder eher, Ruby scheint über die Größe des Arrays hinaus zu suchen? Vorerst habe ich etwas über Besitz und Casting gelernt und es einmal aufgenommen. Rusts typbezogene Punkte sind interessant, wie ein Puzzlespiel.

2020/10/04 Hinzugefügt, weil ich einen Verbesserungspunkt erhalten habe. Vielen Dank. Nach und nach macht Rusts Redewendung den Code kompakter.

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

In Ruby und Rust weicht der numerische Wert also von N = 16 ab. Ab N = 16 dauert die Beantwortung von Ruby außerdem viel länger. Es scheint etwas zu geben.