逆FizzBuzzを解いてみる

#はじめに

『[逆FizzBuzz問題 (Inverse FizzBuzz) - 猫とC#について書くmatarilloの雑記](http://d.hatena.ne.jp/matarillo/20120515/p1)』という記事を読んで、挑戦してみた。

#FizzBuzz問題

##一般的なFizzBuzz

FizzBuzz問題とは、ある範囲の連続した自然数列に対し、 3 で割り切れるなら `Fizz` 、 5 で割り切れるなら `Buzz` 、 3 と 5 で割り切れるなら `FizzBuzz` 、それ以外はその整数を出力するという問題である。


```rust:FizzBuzz解答例
///自然数`start`から自然数`end`までの数列に対し、FizzBuzzを行う。
///1 ~ 100 について解く場合は、fizzbuzz(1, 100) とする。
fn fizzbuzz(start: usize, end: usize) {
    (start..(end + 1)).for_each(|n| {
        if n % 15 == 0 {
            //3と5で割り切れる場合
            println!("FizzBuzz");
        } else if n % 3 == 0 {
            //3で割り切れる場合
            println!("Fizz");
        } else if n % 5 == 0 {
            //5で割り切れる場合
            println!("Buzz");
        } else {
            //3でも5でも割り切れない場合
            println!("{}", n);
        }
    });
}
```

##FizzBuzzリストを取得する

逆FizzBuzz問題に移る前に、FizzBuzz問題から整数の出力を除いた、 `Fizz`, `Buzz`, `FizzBuzz` の 3 要素のみで構成されるリストを取得する問題を考えたい。なお、このリストのことを FizzBuzz リストと呼ぶこととする。

```rust:FizzBuzzリストの取得
///FizzBuzzリストを符号化する。
enum FizzBuzz {
    Fizz,
    Buzz,
    FizzBuzz,
    Number(usize)
}

///自然数`start`から自然数`end`までの数列に対し、FizzBuzzリストを取得する。
///1 ~ 100 について取得するには、get_fizzbuzz_list(1, 100) とする。
fn get_fizzbuzz_list(start: usize, end: usize) -> Vec<FizzBuzz> {
    (start..(end + 1)).map(|n| {
        if n % 15 == 0 {
            FizzBuzz::FizzBuzz
        } else if n % 3 == 0 {
            FizzBuzz::Fizz
        } else if n % 5 == 0 {
            FizzBuzz::Buzz
        } else {
            FizzBuzz::Number(n)
        }
    }).filter(|item| {
        match *item {
            FizzBuzz::Number(_) => false,
            _ => true
        }
    }).collect()
}
```

内容はFizzBuzz解答例とほとんど変わらず、出力を `FizzBuzz` 列挙型にして、整数部分を除いた配列を返すようにしただけである。

#逆FizzBuzz問題

逆FizzBuzz問題とは、`Fizz`, `Buzz`, `FizzBuzz` の 3 つの要素から構成されるリストが与えられたとき、 FizzBuzz を実行するとその FizzBuzz リストを出力するような最短の連続数列を求める問題である。

##解答例
```rust:逆FizzBuzz
///FizzBuzzリストを符号化する。
#[derive(PartialEq, Eq)]
enum FizzBuzz {
    Fizz,
    Buzz,
    FizzBuzz,
    Number(usize)
}

///受け取った FizzBuzz リスト `input` から、その FizzBuzz リストを出力するような最短の連続数列を返す。
fn inverse_fizzbuzz(input: &[FizzBuzz]) -> Option<Vec<usize>> {
    let (fizzbuzz_arry, number_arry) = {
        let mut fizzbuzz_arry = vec!();
        let mut number_arry = vec!();
        for n in 1..(15 + 1) {
            match check_fizzbuzz(n) {
                FizzBuzz::Fizz => {
                    fizzbuzz_arry.push(FizzBuzz::Fizz);
                    number_arry.push(n);
                },
                FizzBuzz::Buzz => {
                    fizzbuzz_arry.push(FizzBuzz::Buzz);
                    number_arry.push(n);
                },
                FizzBuzz::FizzBuzz => {
                    fizzbuzz_arry.push(FizzBuzz::FizzBuzz);
                    number_arry.push(n);
                },
                _ => {}
            }
        }
        (fizzbuzz_arry, number_arry)
    };

    let idx = match_fizzbuzz(input, &fizzbuzz_arry)?;
    let end_idx = idx + (input.len() - 1);
    let end = number_arry[end_idx % number_arry.len()] + (end_idx / number_arry.len()) * 15;
    Some((number_arry[idx]..(end + 1)).collect())
}

///与えられたリストがFizzBuzzリストかチェックする。
fn match_fizzbuzz(input: &[FizzBuzz], fizzbuzz_arry: &[FizzBuzz]) -> Option<usize> {
    for i in 0..fizzbuzz_arry.len() {
        let mut fizzbuzz_cycle = {
            let mut fizzbuzz_cycle = fizzbuzz_arry.iter().cycle();
            (0..i).for_each(|_| { fizzbuzz_cycle.next(); });
            fizzbuzz_cycle
        };
        if input.iter().find(|&item| { Some(item) != fizzbuzz_cycle.next() }).is_none() {
            return Some(i);
        }
    }
    None
}

///与えられた自然数`n`に対し、FizzBuzzする。
fn check_fizzbuzz(n: usize) -> FizzBuzz {
    if n % 15 == 0 {
        FizzBuzz::FizzBuzz
    } else if n % 3 == 0 {
        FizzBuzz::Fizz
    } else if n % 5 == 0 {
        FizzBuzz::Buzz
    } else {
        FizzBuzz::Number(n)
    }
}
```

##逆FizzBuzzのテスト
```rust:逆FizzBuzzテスト
#[test]
fn test_fizz() {
    let fizzbuzz_array = [
        FizzBuzz::Fizz
    ];
    let (start, end) = (3, 3);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_buzz() {
    let fizzbuzz_array = [
        FizzBuzz::Buzz
    ];
    let (start, end) = (5, 5);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_fizzbuzz() {
    let fizzbuzz_array = [
        FizzBuzz::FizzBuzz
    ];
    let (start, end) = (15, 15);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_fizz_buzz() {
    let fizzbuzz_array = [
        FizzBuzz::Fizz,
        FizzBuzz::Buzz
    ];
    let (start, end) = (3, 5);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_buzz_fizz() {
    let fizzbuzz_array = [
        FizzBuzz::Buzz,
        FizzBuzz::Fizz
    ];
    let (start, end) = (5, 6);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_fizz_fizz() {
    let fizzbuzz_array = [
        FizzBuzz::Fizz,
        FizzBuzz::Fizz
    ];
    let (start, end) = (6, 9);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_buzz_buzz() {
    let fizzbuzz_array = [
        FizzBuzz::Buzz,
        FizzBuzz::Buzz
    ];
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), None);
}
#[test]
fn test_fizz_fizzbuzz() {
    let fizzbuzz_array = [
        FizzBuzz::Fizz,
        FizzBuzz::FizzBuzz
    ];
    let (start, end) = (12, 15);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_buzz_fizzbuzz() {
    let fizzbuzz_array = [
        FizzBuzz::Buzz,
        FizzBuzz::FizzBuzz
    ];
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), None);
}
#[test]
fn test_fizzbuzz_fizzbuzz() {
    let fizzbuzz_array = [
        FizzBuzz::FizzBuzz,
        FizzBuzz::FizzBuzz
    ];
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), None);
}
#[test]
fn test_fizz_fizz_fizz() {
    let fizzbuzz_array = [
        FizzBuzz::Fizz,
        FizzBuzz::Fizz,
        FizzBuzz::Fizz
    ];
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), None);
}
#[test]
fn test_buzz_buzz_buzz() {
    let fizzbuzz_array = [
        FizzBuzz::Buzz,
        FizzBuzz::Buzz,
        FizzBuzz::Buzz
    ];
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), None);
}
#[test]
fn test_fizz_buzz_fizz() {
    let fizzbuzz_array = [
        FizzBuzz::Fizz,
        FizzBuzz::Buzz,
        FizzBuzz::Fizz
    ];
    let (start, end) = (3, 6);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_fizzbuzz_fizz() {
    let fizzbuzz_array = [
        FizzBuzz::FizzBuzz,
        FizzBuzz::Fizz
    ];
    let (start, end) = (15, 18);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_fizzbuzz_buzz() {
    let fizzbuzz_array = [
        FizzBuzz::FizzBuzz,
        FizzBuzz::Buzz
    ];
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), None);
}
#[test]
fn test_3_to_15() {
    let fizzbuzz_array = [
        FizzBuzz::Fizz,
        FizzBuzz::Buzz,
        FizzBuzz::Fizz,
        FizzBuzz::Fizz,
        FizzBuzz::Buzz,
        FizzBuzz::Fizz,
        FizzBuzz::FizzBuzz
    ];
    let (start, end) = (3, 15);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
#[test]
fn test_3_cycle() {
    let fizzbuzz_array = [
        FizzBuzz::FizzBuzz,
        FizzBuzz::Fizz,
        FizzBuzz::Buzz,
        FizzBuzz::Fizz,
        FizzBuzz::Fizz,
        FizzBuzz::Buzz,
        FizzBuzz::Fizz,
        FizzBuzz::FizzBuzz,
        FizzBuzz::Fizz,
        FizzBuzz::Buzz,
        FizzBuzz::Fizz,
        FizzBuzz::Fizz,
        FizzBuzz::Buzz,
        FizzBuzz::Fizz,
        FizzBuzz::FizzBuzz
    ];
    let (start, end) = (15, 45);
    assert_eq!(inverse_fizzbuzz(&fizzbuzz_array), Some(
        (start..(end + 1)).collect()
    ));
}
```

##アルゴリズム

FizzBuzzリストは、以下に示すリストを繰り返す特性を持つ。

```:FizzBuzz基本リスト
Fizz
Buzz
Fizz
Fizz
Buzz
Fizz
FizzBuzz
```

本プログラムでは、与えられたリストが、無限に繰り返されるFizzBuzz基本リストに部分一致するかどうかを調べ、一致するなら、与えられたリストの最初の要素が対応する自然数と、最後の要素が対応する自然数を元に連続数列を作成している。

#感想
それほど複雑なアルゴリズムではない気がするのに、プログラムが大変ごちゃっとした感じになってしまった。気が向いたらもう少しスマートにできないか試してみようと思う。