algx 0.2.0

Implementation of Knuth's Algorithm X
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109

use std::collections::{BTreeSet, VecDeque};

#[global_allocator]
static ALLOC: wee_alloc::WeeAlloc = wee_alloc::WeeAlloc::INIT;

use js_sys::Array;
use wasm_bindgen::prelude::*;

#[wasm_bindgen]
#[derive(Default)]
pub struct SolverBuilder {
    rows: Vec<Vec<usize>>,
    initial_columns: Vec<usize>,
}

#[wasm_bindgen]
impl SolverBuilder {
    #[wasm_bindgen(constructor)]
    pub fn new() -> Self {
        Self::default()
    }

    pub fn add_row(&mut self, row: Vec<usize>) {
        self.rows.push(row);
    }

    pub fn set_initial_columns(&mut self, initial_columns: Vec<usize>) {
        self.initial_columns = initial_columns;
    }

    pub fn build(self) -> Solver {
        Solver {
            solver: crate::Solver::new(self.rows, self.initial_columns),
        }
    }
}

#[wasm_bindgen]
pub struct Solver {
    solver: crate::Solver,
}

#[wasm_bindgen]
impl Solver {
    pub fn next_solution(&mut self) -> Array {
        let next_solution = self.solver.next();
        into_js_array(next_solution.unwrap_or_default())
    }

    pub async fn all_solutions(self) -> Array {
        self.solver.map(into_js_array).collect()
    }
}

fn into_js_array<T>(vec: Vec<T>) -> Array
where
    JsValue: From<T>,
{
    vec.into_iter().map(JsValue::from).collect()
}

#[wasm_bindgen]
#[derive(Copy, Clone, Hash, Eq, PartialEq, Ord, PartialOrd)]
pub struct Pos {
    pub x: i32,
    pub y: i32,
}

impl Pos {
    pub fn new(x: i32, y: i32) -> Self {
        Self { x, y }
    }
}

#[wasm_bindgen]
pub fn generate_polyamino_rows(square_count: usize) -> Array {
    let mut shapes = BTreeSet::new();

    let mut stack: VecDeque<Vec<(i32, i32)>> = VecDeque::new();
    stack.push_back(vec![(0, 0)]);

    while let Some(shape) = stack.pop_front() {
        if shape.len() == square_count {
            let mut ret = vec![];
            let min_x = shape.iter().map(|(x, _)| x).min().copied().unwrap();
            let min_y = shape.iter().map(|(_, y)| y).min().copied().unwrap();

            for (x, y) in shape {
                ret.push(Pos::new(x - min_x, y - min_y));
            }

            shapes.insert(ret);
        } else {
            for (i, j) in [(1, 0), (0, 1), (0, -1), (-1, 0)] {
                let mut shape = shape.clone();
                let mut pos = shape.last().copied().unwrap();
                pos.0 += i;
                pos.1 += j;

                if !shape.contains(&pos) {
                    shape.push(pos);
                    stack.push_back(shape);
                }
            }
        }
    }

    into_js_array(shapes.into_iter().map(into_js_array).collect())
}