Help us understand the problem. What is going on with this article?

逆FizzBuzzを解いてみる

More than 1 year has passed since last update.

はじめに

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

感想

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした