"Math puzzles that train your program brain more" _Q41 (code: Ruby)-> Rust

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

Q41: Start menu tiles

What kind of idea do you think of such a problem? The problem of targeting shapes is fun.

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)

I feel that it is compressed too much. Since there is no illustration of the algorithm in the book, it is difficult to understand due to the appropriateness of variable names and the exposed data structure. The image of recursive search cannot be obtained without illustrating what kind of judgment will lead to the next state. Maybe I'm the only one.

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

Since there is a "method directly connected to space" that embeds tiles, that method is organized on the Space structure side. This alone may have made the processing patterns () of the main body easier to understand. When it comes to this scale, it is just right for studying design.