"Mathe-Rätsel, die das Programmhirn mehr trainieren" _Q41 (Code: Ruby) -> Rust

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.

F41: Startmenükachel

Was für eine Idee halten Sie von einem solchen Problem? Das Problem der Ausrichtung auf Zahlen macht Spaß.

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)

Ich fühle, dass es zu komprimiert ist. Da der Algorithmus in diesem Buch nicht dargestellt ist, ist er aufgrund der Angemessenheit des Variablennamens und der exponierten Datenstruktur schwer zu verstehen. Wenn Sie nicht veranschaulichen, welche Art von Beurteilung zum nächsten Zustand führt, können Sie kein Bild der rekursiven Suche erhalten. Vielleicht bin ich der einzige.

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

Da es eine "direkt mit dem Raum verbundene Methode" gibt, die Kacheln einbettet, ist diese Methode auf der Seite der "Raum" -Struktur organisiert. Dies allein könnte das Verständnis der "Muster ()" des Hauptkörpers verständlicher gemacht haben. Wenn es um diese Skala geht, ist es ein guter Ort, um Design zu studieren.