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

[「もっとプログラマ脳を鍛える数学パズル」](https://www.shoeisha.co.jp/book/detail/9784798153612)をRustで書き直すのは、ボケ防止にちょうど良いかもしれない、と思った。

# Q62:壊れたピンチハンガー

こういうのを見るといつも思うのが「条件を満たす最小数はnです」よりも、「条件を満たすパターンはこれです」を出したいのだ。そうでないと検証ができない。

## Rust

```rust:main.rs
use std::collections::BTreeSet;

pub fn main() {
    let width = 5;
    let height = 4;
    let pairs = all_pairs(width, height);

    for i in 0..(width * height) / 2 {
        let states = initial_patterns(i, &pairs);
        for s in &states {
            let patterns = find_filling_pattern(s, &pairs, width, height);
            if patterns.len() == 1 {
                for i in &patterns {
                    println!("the state {} has exact one filling pattern {}.", to_string(s), to_string(i));
                    return;
                }
            } else {
                println!("{} has {} patterns!", to_string(s), patterns.len());
            }
        }
    }
}

pub fn initial_patterns(
    iteration: u64,
    pairs: &BTreeSet<(u64, u64)>,
) -> BTreeSet<BTreeSet<(u64, u64)>> {
    let state: BTreeSet<(u64, u64)> = BTreeSet::new();
    let mut all_states: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
    all_states.insert(state);
    for i in 0..=iteration {
        let mut next_state: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
        for s in &all_states {
            let temp = all_patterns(s, pairs);
            for t in &temp {
                next_state.insert(t.clone());
            }
        }
        all_states = next_state;
    }
    return all_states;
}

pub fn to_string(state: &BTreeSet<(u64, u64)>) -> String {
    let mut result = String::new();
    for (p0, p1) in state {
        result.push_str(&format!("({},{}),", p0, p1));
    }
    result
}

pub fn find_filling_pattern(
    initial_state: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
    width: u64,
    height: u64,
) -> BTreeSet<BTreeSet<(u64, u64)>> {
    if is_filled(initial_state, width, height) {
        let mut result: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
        result.insert(initial_state.clone());
        return result;
    }
    if can_not_be_filled(initial_state, pairs, width, height) {
        return BTreeSet::new();
    }
    let mut all_states: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
    all_states.insert(initial_state.clone());
    for i in initial_state.len() as u64..(width * height) / 2 {
        println!("state {}, loop {}", to_string(initial_state), i);
        let mut next_states: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
        for s in &all_states {
            let nps = all_patterns(s, pairs);
            for np in &nps {
                next_states.insert(np.clone());
            }
        }
        all_states = next_states;
    }
    return all_states;
}
// 与えられた空間内の、全てのペアの集合を返す。
pub fn all_pairs(width: u64, height: u64) -> BTreeSet<(u64, u64)> {
    let mut pairs = BTreeSet::new();

    // for all horizontal pairs. (1,2), (2,3)...
    for x in 1..width {
        for y in 0..height {
            let first = (width * y) + x;
            let second = first + 1;
            pairs.insert((first, second));
        }
    }
    // for all vertical pairs.
    for x in 1..=width {
        for y in 0..height - 1 {
            let first = (width * y) + x;
            let second = first + width;
            pairs.insert((first, second));
        }
    }
    return pairs;
}

pub fn clone(set: &BTreeSet<(u64, u64)>) -> BTreeSet<(u64, u64)> {
    let mut new_set: BTreeSet<(u64, u64)> = BTreeSet::new();
    for e in set {
        new_set.insert(*e);
    }
    new_set
}

// pairsとpairが衝突しない。
pub fn can_be_inserted(pairs: &BTreeSet<(u64, u64)>, pair: (u64, u64)) -> bool {
    for (p0, p1) in pairs {
        if *p0 == pair.0 || *p0 == pair.1 || *p1 == pair.0 || *p1 == pair.1 {
            return false;
        }
    }
    true
}

// 全てのマスが埋まっている。
pub fn is_filled(state: &BTreeSet<(u64, u64)>, width: u64, height: u64) -> bool {
    state.len() as u64 == (width * height) / 2
}

// stateの次の1手の全パターンを出力する。
pub fn all_patterns(
    state: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
) -> BTreeSet<BTreeSet<(u64, u64)>> {
    let mut patterns: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
    for p in pairs {
        if can_be_inserted(&state, *p) {
            let mut new_pattern = clone(&state);
            new_pattern.insert(*p);
            patterns.insert(new_pattern);
        }
    }
    patterns
}

// 全部埋まっておらず、かつ、次に配置できるペアもない。
pub fn can_not_be_filled(
    state: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
    width: u64,
    height: u64,
) -> bool {
    !is_filled(state, width, height) && all_patterns(state, pairs).len() == 0
}

```

愚直に全てのパターンを計算する。
例えば5*4の空間では、

```console
the state (1,2),(7,8), has exact one filling pattern (1,2),(3,4),(5,10),(6,11),(7,8),(9,14),(12,13),(15,20),(16,17),(18,19),.
```

と出る。これは

|   |  |  |  |  |
|--:|--:|--:|--:|--:|
|  1| 2| 3| 4| 5|
|  6| 7| 8| 9|10|
| 11|12|13|14|15|
| 16|17|18|19|20|

のうち、(1,2),(7,8)を固定すると、あとは1種類しか埋め方がないことを示す。

ただ、今は全部埋まる判定にメモ化をしていないので、ものすごく遅い・・・10*7の実行は現実的でない。
おそらく、最初に埋め方の全パターンを作成しておいて、「この前提状態では、全埋めパターンのうち、いくつにヒットする」という判定をすれば高速化できるはず。

## Rust(高速化)

```rust:main.rs
use std::collections::{BTreeSet,HashMap};

pub fn main() {
    let width = 10;
    let height = 7;
    let pairs = all_pairs(width, height);

    for i in 0..(width * height) / 2 {
        let states = initial_patterns(i, &pairs,width,height);
        for s in &states {
            println!("{}",to_string(s));
            match search(s, &pairs, width, height) {
                None => {
                    println!("{} can not be filled or multiple results.",to_string(s));
                }
                Some(result) => {
                    println!("{} has uniq result {}",to_string(s), to_string(&result));
                    return;
                }
            }
        }
    }
}

pub fn search(
    initial_state: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
    width: u64,
    height: u64,
) -> Option<BTreeSet<(u64, u64)>> {
    let prev_fill = BTreeSet::new();

    let first = search_sub(&initial_state, &pairs, &prev_fill, width, height);
    match first {
        None => {
            return None; /* 一度も埋まらない。解なし */
        }
        Some(result) => {
            /* まず1回見つかった */
            /* 同じinitial_stateでもう一つ探す。 */
            let second = search_sub(&initial_state, &pairs, &result, width, height);
            match second {
                None => {
                    return Some(result); /* 解が一つに定まった。Goal!*/
                }
                Some(_) => {
                    return None; /* 解が複数あった。Fail. */
                }
            }
        }
    }
}

pub fn initial_patterns(
    iteration: u64,
    pairs: &BTreeSet<(u64, u64)>,
    width:u64,
    height:u64,
) -> BTreeSet<BTreeSet<(u64, u64)>> {
    let state: BTreeSet<(u64, u64)> = BTreeSet::new();
    let mut all_states: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
    all_states.insert(state);
    let mut n = iteration;
    if iteration >= pairs.len() as u64 {
        n = pairs.len() as u64;
    }
    for i in 0..=n {
        let mut next_state: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
        for s in &all_states {
            let temp = all_patterns(s, pairs);
            for t in &temp {
                if !has_singlehole(t,width,height) {
                    let lr_sym = left_right_symmetrcal_set(t,width,height);
                    let ud_sym = up_down_symmetrical_set(t,width,height);
                    let r_sym = rotational_symmetrical_set(t,width,height);
                    if !next_state.contains(&lr_sym) && !next_state.contains(&ud_sym) && !next_state.contains(&r_sym) {
                        next_state.insert(t.clone());
                    }
                }
            }
        }
        all_states = next_state;
    }
    return all_states;
}

pub fn has_singlehole(state:&BTreeSet<(u64,u64)>,width:u64,height:u64) -> bool {
    let mut map:BTreeSet<u64> = BTreeSet::new();
    for (p,q) in state {
        map.insert(*p);
        map.insert(*q);
    }
    for i in 1..=width*height {
        if !map.contains(&i) {
            let mut up_fill = false;
            if (i -1) / width > 0 {
                if map.contains(&(i-width)) {
                    /* 自分が空で、上が埋まっている */
                    up_fill = true;
                }
            } else {
                /* 最上段なのでtrue */
                up_fill = true;
            }
            let mut down_fill = false;
            if (i-1)/width + 1 < height {
                if map.contains(&(i+width)) {
                    down_fill = true;
                }
            } else {
                down_fill = true;
            }
            let mut right_fill = false;
            if i % width != 0 {
                if map.contains(&(i+1)) {
                    right_fill = true;
                }
            } else {
                right_fill = true;
            }
            let mut left_fill = false;
            if i % width != 1 {
                if map.contains(&(i-1)) {
                    left_fill = true;
                }
            } else {
                left_fill = true;
            }
            if up_fill && down_fill && right_fill && left_fill {
                return true;
            }
        }
    }
    return false;
} 

pub fn left_right_symmetrcal_set(state:&BTreeSet<(u64,u64)>,width:u64,height:u64) -> BTreeSet<(u64,u64)> {
    let mut map:HashMap<u64,u64> = HashMap::new();
    for x in 1..=width {
        for y in 0..height {
            map.insert((y*width)+x,y*width+(width+1-x));
        }
    }
    let mut new_state:BTreeSet<(u64,u64)> = BTreeSet::new();
    for (p,q) in state {
        let np:u64 = *map.get(p).unwrap();
        let nq:u64 = *map.get(q).unwrap();
        new_state.insert((np,nq));
    }
    new_state
}

pub fn up_down_symmetrical_set(state: &BTreeSet<(u64,u64)>,width:u64,height:u64) -> BTreeSet<(u64,u64)> {
    let mut map:HashMap<u64,u64> = HashMap::new();
    for x in 1..=width {
        for y in 0..height {
            map.insert((y*width)+x,((height-1-y)*width)+x);
        }
    }
    let mut new_state:BTreeSet<(u64,u64)> = BTreeSet::new();
    for (p,q) in state {
        let np:u64 = *map.get(p).unwrap();
        let nq:u64 = *map.get(q).unwrap();
        new_state.insert((np,nq));
    }
    new_state
}

pub fn rotational_symmetrical_set(state: &BTreeSet<(u64,u64)>,width:u64,height:u64) -> BTreeSet<(u64,u64)> {
    let mut map:HashMap<u64,u64> = HashMap::new();
    for x in 1..=width {
        for y in 0..height {
            map.insert((y*width)+x,((height-1-y)*width)+(width+1-x));
        }
    }
    let mut new_state:BTreeSet<(u64,u64)> = BTreeSet::new();
    for (p,q) in state {
        let np:u64 = *map.get(p).unwrap();
        let nq:u64 = *map.get(q).unwrap();
        new_state.insert((np,nq));
    }
    new_state
}

pub fn to_string(state: &BTreeSet<(u64, u64)>) -> String {
    let mut result = String::new();
    for (p0, p1) in state {
        result.push_str(&format!("({},{}),", p0, p1));
    }
    result
}

pub fn search_sub(
    initial_state: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
    prev_fill: &BTreeSet<(u64, u64)>,
    width: u64,
    height: u64,
) -> Option<BTreeSet<(u64, u64)>> {
    if has_singlehole(initial_state,width,height) {
        return None;
    }
    if can_not_be_filled(initial_state, pairs, width, height) {
        return None;
    }
    if is_filled(initial_state, width, height) && initial_state != prev_fill {
        println!("{}",to_string(initial_state));
        let cloned = initial_state.clone();
        return Some(cloned);
    }
    let search_pairs: BTreeSet<(u64, u64)> = available_pairs(initial_state, pairs);
    for next_pair in search_pairs {
        let mut next_state = initial_state.clone();
        next_state.insert(next_pair);
        let result = search_sub(&next_state, pairs, prev_fill, width, height);
        match result {
            Some(state) => return Some(state),
            _ => {}
        }
    }
    return None;
}

pub fn available_pairs(
    orig: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
) -> BTreeSet<(u64, u64)> {
    let mut avails = BTreeSet::new();
    for p in pairs {
        if can_be_inserted(orig, *p) {
            avails.insert(*p);
        }
    }
    return avails;
}

/* 幅優先探索。規模が大きくなると、極端に時間がかかる。 */
pub fn find_filling_pattern(
    initial_state: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
    width: u64,
    height: u64,
) -> BTreeSet<BTreeSet<(u64, u64)>> {
    if is_filled(initial_state, width, height) {
        let mut result: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
        result.insert(initial_state.clone());
        return result;
    }
    if can_not_be_filled(initial_state, pairs, width, height) {
        return BTreeSet::new();
    }
    let mut all_states: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
    all_states.insert(initial_state.clone());
    for i in initial_state.len() as u64..(width * height) / 2 {
        println!("state {}, loop {}", to_string(initial_state), i);
        let mut next_states: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
        for s in &all_states {
            let nps = all_patterns(s, pairs);
            for np in &nps {
                next_states.insert(np.clone());
            }
        }
        all_states = next_states;
        println!("loop {} {} ", i, all_states.len());
    }

    return all_states;
}

// 与えられた空間内の、全てのペアの集合を返す。
pub fn all_pairs(width: u64, height: u64) -> BTreeSet<(u64, u64)> {
    let mut pairs = BTreeSet::new();

    // for all horizontal pairs. (1,2), (2,3)...
    for x in 1..width {
        for y in 0..height {
            let first = (width * y) + x;
            let second = first + 1;
            pairs.insert((first, second));
        }
    }
    // for all vertical pairs.
    for x in 1..=width {
        for y in 0..height - 1 {
            let first = (width * y) + x;
            let second = first + width;
            pairs.insert((first, second));
        }
    }
    return pairs;
}

pub fn clone(set: &BTreeSet<(u64, u64)>) -> BTreeSet<(u64, u64)> {
    let mut new_set: BTreeSet<(u64, u64)> = BTreeSet::new();
    for e in set {
        new_set.insert(*e);
    }
    new_set
}

// pairsとpairが衝突しない。
pub fn can_be_inserted(pairs: &BTreeSet<(u64, u64)>, pair: (u64, u64)) -> bool {
    for (p0, p1) in pairs {
        if *p0 == pair.0 || *p0 == pair.1 || *p1 == pair.0 || *p1 == pair.1 {
            return false;
        }
    }
    true
}

// 全てのマスが埋まっている。
pub fn is_filled(state: &BTreeSet<(u64, u64)>, width: u64, height: u64) -> bool {
    state.len() as u64 == (width * height) / 2
}

// stateの次の1手の全パターンを出力する。
pub fn all_patterns(
    state: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
) -> BTreeSet<BTreeSet<(u64, u64)>> {
    let mut patterns: BTreeSet<BTreeSet<(u64, u64)>> = BTreeSet::new();
    for p in pairs {
        if can_be_inserted(&state, *p) {
            let mut new_pattern = clone(&state);
            new_pattern.insert(*p);
            patterns.insert(new_pattern);
        }
    }
    patterns
}

// 全部埋まっておらず、かつ、次に配置できるペアもない。
pub fn can_not_be_filled(
    state: &BTreeSet<(u64, u64)>,
    pairs: &BTreeSet<(u64, u64)>,
    width: u64,
    height: u64,
) -> bool {
    !is_filled(state, width, height) && all_patterns(state, pairs).len() == 0
}

```

この設問では「解が一つに定まるのは、いくつのペアを選択したときか」なので、複数解を全て求める必要がない。

1. 深さ優先探索により、解が2つ見つかったら探索を打ち切る。
2. 一つだけ穴があく箇所ができたら探索を打ち切る。
3. 左右、上下、回転対象は探索しない。

まだ甘いけど、初期から比べればだいぶ高速化できたので、一旦打ち切る。

1. 探索を同方向に2回やっている。逆方向から探索すれば無駄がない。
2. それ以上絶対埋まらない、というパターンを大量に探索している。空白が奇数個繋がっているところは埋まらないので、もう少し枝刈りできる。