LoginSignup
5
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@mhgp

逆FizzBuzzを解いてみる

Posted at

はじめに

『逆FizzBuzz問題 (Inverse FizzBuzz) - 猫とC#について書くmatarilloの雑記』という記事を読んで、挑戦してみた。

FizzBuzz問題

一般的なFizzBuzz

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

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 リストと呼ぶこととする。

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 リストを出力するような最短の連続数列を求める問題である。

解答例

逆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のテスト

逆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基本リストに部分一致するかどうかを調べ、一致するなら、与えられたリストの最初の要素が対応する自然数と、最後の要素が対応する自然数を元に連続数列を作成している。

感想

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

5
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
5
4

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?