Rustで有限オートマトンを書いてAtcoder Beginner ContestのA問題を解いてみる

有限オートマトン(finite automaton) は計算モデルの一種であり, 一般に以下の要素を持つ．

- Q は状態(state)の集合
- Σ はアルファベット(alphabet)と呼ばれる集合
- δ: Q × Σ -> Q は遷移関数(transition function)
- q_0 ∈Q は開始状態(start state)
- F ⊆Q は受理状態の集合( set of accept states)

// Atcoderで用いることのできる，便利な入出力クレートのインポート
use proconio::input;

fn solve(s: &str) -> &'static str {
    if s == "AAA" || s == "BBB" {
        return "No";
    }

    "Yes"
}

fn main() {
    // 適当に期待する型を列挙しておけば，入力文字列をパースしてくれる
    input! {
        s: String,
    }

    println!("{}", solve(&s));
}

M = (Q, Σ, δ, q_0, F)

Q = {q_0, q_1, q_2, q_3}
Σ = {'A', 'B'}
δは下記に記載
q_0 は開始状態
F = {q_3}

struct State {
    /// 受理状態かどうか
    is_accept: bool,
    /// State間を比較できるように，IDをつけておく
    id: usize,
}

use proconio::input;
use std::collections::HashMap;

/// 状態
#[derive(Hash, Eq, PartialEq, Ord, PartialOrd, Clone, Copy)]
struct State {
    /// 受理状態かどうか
    is_accept: bool,
    /// State間を比較できるように，IDをつけておく
    id: usize,
}

/// 有限オートマトンを表す構造体
struct Automaton {
    /// 状態の有限集合Q
    states: HashMap<String, State>,
    /// 遷移関数群
    transitions: HashMap<State, Box<dyn Fn(char) -> String>>,
    /// Stateにつける通し番号
    id: usize,
}

impl Automaton {
    /// ある状態qと, qからの遷移関数を登録する
    fn add_states(&mut self, name: &str, is_accept: bool, transition: fn(char) -> String) {
        let state = State {
            is_accept,
            id: self.id,
        };
        self.id += 1;
        self.states.insert(name.to_string(), state);
        self.transitions.insert(state, Box::new(transition));
    }

    /// 言語Lで記述された文字列sを受理するか判定
    fn run(&self, s: String) -> bool {
        // 開始状態からスタート
        let mut current_state = *self.states.get("q0").unwrap();

        // 文字列をイテレートして，状態遷移を次々と行う
        for c in s.chars() {
            let transition = self.transitions.get(&current_state).unwrap();
            let next_state_name = transition(c);
            current_state = *self.states.get(&next_state_name).unwrap();
        }
        
        // 入力文字列を処理し終わったあと，最終的な遷移先が集合Fの元であるかチェック
        current_state.is_accept
    }
}

fn transition_q0(c: char) -> String {
    if c == 'A' {
        return "q1".to_string();
    }

    "q2".to_string()
}
fn transition_q1(c: char) -> String {
    if c == 'B' {
        return "q3".to_string();
    }

    "q1".to_string()
}
fn transition_q2(c: char) -> String {
    if c == 'A' {
        return "q3".to_string();
    }

    "q2".to_string()
}
fn transition_q3(_c: char) -> String {
    "q3".to_string()
}

fn main() {
    input! {
        s: String,
    }

    let mut m = Automaton {
        states: HashMap::new(),
        transitions: HashMap::new(),
        id: 0,
    };

    m.add_states("q0", false, transition_q0);
    m.add_states("q1", false, transition_q1);
    m.add_states("q2", false, transition_q2);
    m.add_states("q3", true, transition_q3);

    if m.run(s) {
        println!("Yes");
    } else {
        println!("No");
    }
}

s = set()
for c in input():
  s.add(c)

print('No' if len(s) == 1 else 'Yes')