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

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

Q41:スタートメニューのタイル

こういう問題、どういう発想で考えてるんだろう。図形を対象とする問題は楽しい。

Ruby

q41_2.rb

W, H = 10, 10

@memo = {}
def search(tile)
    return @memo[tile] if @memo[tile]
    return 1 if tile.min == H

    pos = tile.index(tile.min)
    cnt = 0
    [[1,1],[2,2],[4,2], [4,4]].each do |px,py|
        check = true
        px.times do |x|
            if (pos + x >= W) || (tile[pos + x] + py > H)
                check = false
            elsif tile[pos + x] != tile[pos]
                check = false
            end
        end
        next if !check

        px.times do |x|
            tile[pos + x] += py
        end
        cnt += search(tile)
        px.times do |x|
            tile[pos + x] -= py
        end
    end
    @memo[tile.clone] = cnt
end

puts search([0] * W)

いやさすがに圧縮しすぎな気がする。アルゴリズムの図解が書籍中には無いので、変数名の適当さとデータ構造がむき出しであることが相まって理解が難しい。どういう判断によって、次の状態がどうなっていくのか、を図解しないと、再帰的探索のイメージがつかない。私だけかもしれないが。

Rust

main.rs

use std::collections::HashMap;

fn main() {
    let space_width = 10;
    let space_height = 10;
    let mut q41 = Q41 {
        memo: HashMap::new(),
    };
    let space = Space::new(space_width,space_height);
    println!(
        "{}",
        q41.patterns(&space, &vec![(1, 1), (2, 2), (4, 2), (4, 4)])
    );
}

struct Q41 {
    memo: HashMap<Space, u64>,
}

impl Q41 {
    pub fn patterns(&mut self, space: &Space, tiles: &Vec<(u64, u64)>) -> u64 {
        match self.memo.get(space) {
            Some(v) => *v,
            _ => {
                if space.is_filled() {
                    return 1;
                }
                let mut count = 0;
                for t in tiles {
                    if space.can_be_placed(t) {
                        let new_space = space.place(t);
                        count += self.patterns(&new_space.unwrap(), tiles);
                    }
                }
                self.memo.insert(space.clone(), count);
                return count;
            }
        }
    }
}

#[derive(Eq, Hash)]
struct Space {
    rows: Vec<u64>,
    width: usize,
}

impl PartialEq for Space {
    fn eq(&self, other: &Self) -> bool {
        self.rows == other.rows
    }
}

impl Space {

    pub fn new(width:u64, height:u64) -> Space {
        Space {
            rows: vec![0u64; height as usize],
            width: width as usize,
        }
    }

    pub fn height(&self) -> usize {
        self.rows.len()
    }

    pub fn min_value(&self) -> u64 {
        let mut min = std::u64::MAX;
        for i in 0..self.height() {
            if self.rows[i] < min {
                min = self.rows[i];
            }
        }
        min
    }

    pub fn index_of_min_value(&self) -> usize {
        let min_value: u64 = self.min_value();
        self.rows.iter().position(|&v| v == min_value).unwrap()
    }

    pub fn is_filled(&self) -> bool {
        for i in 0..self.height() {
            if self.rows[i] != self.width as u64 {
                return false;
            }
        }
        true
    }

    pub fn place(&self, tile: &(u64, u64)) -> Option<Space> {
        if !self.can_be_placed(tile) {
            return None;
        }

        let mut new_space: Space = self.clone();

        let py = self.index_of_min_value();
        for y in py..py + tile.1 as usize {
            new_space.rows[y] += tile.0;
        }

        return Some(new_space);
    }

    pub fn can_be_placed(&self, tile: &(u64, u64)) -> bool {
        let index_of_min = self.index_of_min_value();
        let (tw, th) = tile;
        if index_of_min + *th as usize > self.height() {
            // height over!
            return false;
        }
        for dh in 0..*th {
            let ih = index_of_min + dh as usize;
            if self.rows[ih] + tw > self.width as u64 || self.rows[ih] != self.rows[index_of_min] {
                return false;
            }
        }
        return true;
    }

    pub fn clone(&self) -> Space {
        Space {
            rows: self.rows.clone(),
            width: self.width,
        }
    }

    #[warn(dead_code)]
    pub fn to_string(&self) -> String {
        let mut str = String::new();
        for i in 0..self.height() {
            str.push_str(&self.rows[i].to_string());
            str.push_str(", ");
        }
        format!("rows=[{}],width={}",str, self.width)
    }
}

タイルを埋め込む「空間に直結したメソッド」があるので、そのメソッドをSpace構造体側に整理した。これだけでも、本体の処理patterns()は分かりやすくなったのではないか。このくらいの規模になってくると、設計の勉強としてちょうど良い。