読者です 読者をやめる 読者になる 読者になる

きままにブログ

プログラミングを主とした私のメモ帳です。寂しいのでコメントください笑

Project Euler Problem 1

C++ Project Euler

10未満の自然数のうち, 3 もしくは 5 の倍数になっているものは 3, 5, 6, 9 の4つがあり, これらの合計は 23 になる.

同じようにして, 1000 未満の 3 か 5 の倍数になっている数字の合計を求めよ.

auto list = std::vector<int>(999);
std::iota(list.begin(), list.end(), 1);
auto new_iterator = std::remove_if(list.begin(), list.end(),
	[](int n) { return !(n % 3 == 0 || n % 5 == 0); });
auto result = std::accumulate(list.begin(), new_iterator, 0);
printf("%d", result);

でも、「なっているもの」っていっているのに、「なっていないものを削除する」という問題を性格に表現していないこのコードはなんか気持ち悪い。

追記

リスト〔vector〕を用意しちゃうところが最高にダサいよね……。できれば、こんなふうに書きたい :

auto result = Range(1, 999)
.filter([](int n) { return n % 3 == 0 || n % 5 == 0; })
.reduce([](int m, int n) { return m + n; });

そしてこうやって動いて欲しい :

int sum = 0;
for(int i = 1; i <= 999; ++i) {
	if(i % 3 == 0 || i % 5 == 0) {
		sum += i;
	}
}

できました

Rangeクラスは、reduceインターフェース及びfilterトレイトを実装します。filterトレイトは、フィルターをセットするだけです。reduceインターフェースは、2つの値をある関数を用いて計算し、その結果を返します。

テストケース

Range<int> range(1, 9);
auto ret = range
	.filter([](const int& it) { return it % 3 == 0 || it % 5 == 0; })
	.reduce(std::plus<int>());
printf("%d", ret); // 23

実装

using std::function;

template <typename T>
struct Reduce_i {
	virtual T reduce(function<T(const T&, const T&)> func) const = 0;
};

template <typename SELF, typename T>
struct Filter_t {
	Filter_t() : filter_function([](const T&) { return true; }) { }
	SELF& filter(function<bool(const T&)> filter_function) {
		this->filter_function = filter_function;
		return *static_cast<SELF*>(this);
	}
	bool operator()(const T& it) const { return filter_function(it); }
protected:
	function<bool(const T&)> filter_function;
};

template <typename T>
class Range : Reduce_i<T>, public Filter_t<Range<T>, T> {
public:
	Range(T m, T n) : m(m), n(n) { }
	
	T reduce(function<T(const T&, const T&)> func) const {
		T ret;
		T value;
		for(value = m; value <= n; ++value) {
			if(filter_function(value)) {
				ret = value;
				break;
			}
		}
		for(++value; value <= n; ++value) {
			if(filter_function(value)) {
				ret = func(ret, value);
			}
		}
		return ret;
	}
private:
	T m;
	T n;
};