「もっとプログラム脳を鍛える数学パズル」_Q40 (code:Ruby) -> Rust 未完成

「もっとプログラマ脳を鍛える数学パズル」をRustで書き直すのは、ボケ防止にちょうど良いかもしれない、と思った。

Q40:沈みゆく島で出会う船

Ruby

書籍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)

Rubyのコードはproductの扱い辺りが個人的には分かりやすい。JavaScriptはfor文で回してる。
そんなに簡単ではない問題、ということで、全パターンを探索するというコード。

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

ほぼベタ移植。なのだが、n=16にしたら、Rubyは32、Rustは34と出た。落ち着いてアルゴリズムの境界値を見直さないと、どこが違うのか分からない。というかRubyの方は配列のサイズを超えて探索してるような?
とりあえず、所有権とキャストの勉強にはなったので一旦記録。Rustの型関連の指摘はパズルゲームみたいで面白い。

2020/10/04改善指摘をいただいたので追記。ありがとうございます。少しづつ、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 (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;
}

で、やっぱり、RubyとRustではN=16から数値がずれる。さらに、N=16からRubyは格段に回答までに時間がかかる。何かありそう。