何気なく調べ物をしていると、全然関係なかったのだが「ソフトウェアエンジニアなら1時間以内に解けなければいけない5つの問題」なる記事が目に入った。流行ったのは去年の夏前頃のようだが、遅ればせながら参戦してみた。一番よく使っている言語、C++で。結論から言うとクリアできたのでソフトウェアエンジニアの必要条件は満たしているようだ。
問題1
forループ、whileループ、および再帰を使用して、リスト内の数字の合計を計算する3つの関数を記述せよ。
問題の要件がわかりにくい。C++にコア言語機能としての「リスト」は存在しない。std::listでいいのだろうか。しかし通常C++で配列様の何かというと、std::vectorを使うだろう。片方よりは両方がいいだろうと考え、この両方に対応することにした。
数字の型が指定されていないので、当然templateを用いる。複数のコンテナに対応するためには、数値型をtemplate引数にする他に、vectorもしくはlistを取れるようなtemplate引数を追加すればいいと考え、そのまま書いたところ以下のようになった。
template<typename numT, typename alloc, template<typename T, typename A> class containerT> numT sum_for(containerT<numT, alloc> const& cont) { numT sum = 0; for(auto iter = std::begin(cont); iter != std::end(cont); ++iter) sum += *iter; return sum; } template<typename numT, typename alloc, template<typename T, typename A> class containerT> numT sum_while(containerT<numT, alloc> const& cont) { numT sum = 0; auto iter = std::begin(cont); while(iter != std::end(cont)) { sum += *iter; ++iter; } return sum; } template<typename numT, typename alloc, template<typename T, typename A> class containerT> numT sum_rec(containerT<numT, alloc> const& cont, numT s = 0) { return (cont.size() == 0) ? s : sum_rec( containerT<numT, alloc>( [](typename containerT<numT, alloc>::const_iterator i){return ++i;}(cont.cbegin()), cont.cend()), s + *(cont.cbegin())); }
書いている時にsum_rec内で++(cont.cbegin())をするとやばいかもな、と思ったのでその場でlambdaを書いて回避することにした。さて、書き上げて見直してみると、templateがごちゃごちゃしている印象だ。それでいてあまり汎用性がない。汎用性のためでも速度のためでもなくて、ただ複雑で読みにくいのは、つまり良くないコードだ。
最初に数値型をtemplate引数にしようと考えたために引っ張られてそのまま素直に書いてしまったが、コンテナ型そのものをtemplate引数にした方が良いのでは、と感じた。ここまでまだ5分も経っていなかったのと、正直これらの問題をナメていたので、私は勢いのまま少し書き直すことにした。
template<typename T> typename T::value_type sum_for(T const& cont) { typename T::value_type sum = 0; for(auto iter = std::begin(cont); iter != std::end(cont); ++iter) sum += *iter; return sum; } template<typename T> typename T::value_type sum_while(T const& cont) { typename T::value_type sum = 0; auto iter = std::begin(cont); while(iter != std::end(cont)) { sum += *iter; ++iter; } return sum; } template<typename T> typename T::value_type sum_rec(T const& cont, typename T::value_type s = 0) { return (cont.size() == 0) ? s : sum_rec(T([](typename T::const_iterator i){return ++i;}(cont.cbegin()), cont.cend()), s + *(cont.cbegin())); }
value_typeを直接書いてしまっているのがちょっと気になるが、そんなに時間がないので挑戦中はこれでよしとした。value_typeは直接書くのでなく、STL以外のコンテナのことを考えるとtype generater的なものでラップするべきだろう。例えば配列の場合はvalue_typeなんてものはないので、
template<typename T> struct value_type_of {typedef typename T::value_type type;}; template<typename T, std::size_t N> struct value_type_of<T[N]> {typedef T type;};
のようにするべきだ。まあこんなことをしても、再帰版のコードでcontainerT::size()とかイテレータを取るコンストラクタとかを当然のように使っているので、配列の場合はそこも解決しなければならないのだが。
実際、問題文の内容に従って素直に書くと先のコードのようになるだろうが、iteratorを受け取るようにした方がSTLっぽい。ので今そのように書き直してみた。
template<typename Iterator> typename std::iterator_traits<Iterator>::value_type sum_for(Iterator iter, Iterator end) { typename std::iterator_traits<Iterator>::value_type sum = 0; for(; iter != end; ++iter) sum += *iter; return sum; } template<typename Iterator> typename std::iterator_traits<Iterator>::value_type sum_while(Iterator iter, Iterator end) { typename std::iterator_traits<Iterator>::value_type sum = 0; while(iter != end) { sum += *iter; ++iter; } return sum; } template<typename Iterator> typename std::iterator_traits<Iterator>::value_type sum_rec(Iterator iter, Iterator end, typename std::iterator_traits<Iterator>::value_type s = 0) { return (iter == end) ? s : sum_rec(std::next(iter), end, s + *iter); }
この方がすっきりするし、当然だがIteratorがT*に解決されるだけで生配列にもそのまま適用可能である。題意からコンテナを引数にとる関数を作らなければならないが、それが内部的にこちらを呼び出す方がよい選択だろう。
ついでに再帰版で使っていたlambdaを何とかできないかと思って少し調べたのだが、std::advanceは引数をインクリメントしてvoidを返すので、この用途では使えなかった。もう少し調べるとstd::nextなるものがあり、これがちょうど良さそうだったので、これを使うことにした。
問題2
交互に要素を取ることで、2つのリストを結合する関数を記述せよ。例えば [a, b, c]と[1, 2, 3]という2つのリストを与えると、関数は [a, 1, b, 2, c, 3]を返す。
ある意味この問題が一番難しい。なんせ解答例が「異なる型の値を要素に持つリストを結合する」ということをしているからだ。これは非常にヤバい。
同じ型の要素を持つstd::listまたはstd::vectorを結合するのは非常に簡単だ。何も頭を使わずとも書ける。
template<typename T> T join(const T& lhs, const T& rhs) { if(lhs.size() != rhs.size()) throw std::logic_error("join: different size"); auto l = std::begin(lhs); auto r = std::begin(rhs); T retval; while(l != std::end(lhs)) { retval.push_back(*l); retval.push_back(*r); ++l; ++r; } return retval; }
しかしこれでは問題の要件を満たしたことにならないだろう。同じ型の要素を持つリストしか統合できないからだ。とはいえ、C++という言語の特性上、[a, b, c]と[1, 2, 3]を[a, 1, b, 2, c, 3]にするのは一筋縄ではいかない。
パッと思いついた策は、
pairのlistを作る- イテレータをラップしてあたかも
[a, 1, b, 2, c, 3]のリストのイテレータであるかのように振舞わせる std::tupleによって実際にstd::tuple<char, int, char, int, char, int>なる構造体を作る- a, b, cは
char型で、つまりintegral型なので、intにcastしてしまう boost::anyを使うか、そのようなクラスを実装してそのリストを返す
といったところだった。1.は題意を満たしていないように思う。2.を最初にトライしたが、operator*によって返す型を分岐するのは非常に難しく、operator++で新規な型の値を作って返したりもできる気がしなかったので、少し試して諦めた。ここで結構時間を浪費してしまった。3.は考えただけで実行に移していない。variadic template地獄になることが見えていて、時間オーバーの可能性があるからだ。4.はこれは策ではなく、イチャモンである。というわけで5.を実行に移した。
#include <iostream> #include <stdexcept> #include <vector> #include <boost/any.hpp> template<typename T1, typename T2> std::vector<boost::any> join(T1 const& lhs, T2 const& rhs) { if(lhs.size() != rhs.size()) throw std::logic_error("join: different size"); std::vector<boost::any> retval; retval.reserve(lhs.size() * 2); auto liter = std::begin(lhs); auto riter = std::begin(rhs); while(liter != std::end(lhs)) { retval.push_back(*liter); retval.push_back(*riter); ++liter; ++riter; } return retval; } int main() { std::vector<int> v1{1, 2, 3}; std::vector<char> v2{'a', 'b', 'c'}; auto s = join(v1, v2); for(auto item : s) { const std::type_info& t = item.type(); if(t == typeid(int)) std::cout << boost::any_cast<int>(item) << std::endl; else if(t == typeid(char)) std::cout << boost::any_cast<char>(item) << std::endl; else throw std::logic_error("unknown type"); } return 0; }
実は、存在は知っていたもののboost::anyを自分で実際に使ったのはこれが初めてであった。
問題3
最初の100個のフィボナッチ数のリストを計算する関数を記述せよ。定義では、フィボナッチ数列の最初の2つの数字は0と1で、次の数は前の2つの合計となる。例えば最初の10個のフィボナッチ数列は、0, 1, 1, 2, 3, 5, 8, 13, 21, 34となる。
これは上二つほど長くはならない。イテレータのように見える構造体を作って、数値型をテンプレート引数に取るということを真っ先に思いついた(というか昔そうすれば無限リストを扱えると考えて無限リストライブラリ的なものを作ろうとしたことがあった)。
あとは100回インクリメントして終了、楽勝! と思って走らせたところ、後ろの方でオーバーフローしていた。確かによく考えてみると、フィボナッチ数列は一回で約1.618倍になるが、これはよりも大きい。なので100番目は250よりも大きくなる。これならオーバーフローは起きなさそうだが、もう少し真面目に評価すると、log_2(1.6) = log_2(24/10) = 4 - log_2(10)で、まあ大体0.66とかそんなもんなので(log(2) ~ 0.3010だ)、100番目の要素は266とかになる。符号なし64bit整数を使っても、最後の数個はオーバーフローするというわけだ。
たぶんオーバーフローに気づいて任意倍長整数を使えますか、という問題なのだろう。最初にtemplate化してあったので、boost::multiprecision::int128_tでインスタンス化して終了。修正は10秒で終わった（コンパイル時間含まず）。templateは偉大だ。
#include <boost/multiprecision/cpp_int.hpp> template<typename intT> struct Fibonacci { intT current; intT next; Fibonacci(){} Fibonacci(intT i, intT j) : current(i), next(j){} Fibonacci& operator++(); Fibonacci& operator++(int); intT operator*(){return current;}; }; template<typename intT> Fibonacci<intT>& Fibonacci<intT>::operator++() { const intT tmp = current + next; this->current = this->next; this->next = tmp; return *this; } template<typename intT> Fibonacci<intT>& Fibonacci<intT>::operator++(int) { const intT tmp = current + next; this->current = this->next; this->next = tmp; return *this; } int main() { Fibonacci<boost::multiprecision::int128_t> fib(0, 1); for(std::size_t i=0; i<100; ++i) { std::cout << *fib << std::endl; ++fib; } return 0; }
問題4
正の整数のリストを与えられたとき、数を並び替えて可能な最大数を返す関数を記述せよ。例えば、[50, 2, 1, 9]が与えられた時、95021が答えとなる
C++でやるなら一番簡単だ。比較用のlambdaを書いて、std::sortに投げて終了。3分もいらない。
#include <string> #include <vector> #include <algorithm> #include <iostream> int main() { std::vector<int> v{50, 2, 1, 9}; std::sort(v.begin(), v.end(), [](int i, int j){ return std::stoi(std::to_string(i) + std::to_string(j)) > std::stoi(std::to_string(j) + std::to_string(i)); } ); for(auto item : v) std::cout << item; std::cout << std::endl; return 0; }
問題5
1,2,…,9の数をこの順序で、”+”、”-“、またはななにもせず結果が100となるあらゆる組合せを出力するプログラムを記述せよ。例えば、1 + 2 + 34 – 5 + 67 – 8 + 9 = 100となる
これは結構ハマった。最初、operator_baseクラスを作って、そこから派生する+, -, joinの三つの演算子に相当するファンクタを定義して、shared_ptr<operator_base>の列を渡すと演算する関数を作ろうとしたのだが、結合順序などをきちんとするのが面倒で途中で別の方法がないか考え始めた。
しばらく考えて(考えているうちに焦りが生じて中々きつかった)、数字と'+'と'-'を結合して文字列にし、それをistringstreamで読み出して計算するということを思いついた。これを思いついてからは、ちゃんと全通り試せるようにするところで少し時間を使ったが、概ねスムーズに書けた。
#include <iostream> #include <sstream> #include <vector> #include <stdexcept> #include <cmath> int run(const std::string& expr) { std::istringstream iss(expr); int retval; iss >> retval; while(not iss.eof()) { const char op = iss.get(); switch(op) { case '+': { int i; iss >> i; retval += i; break; } case '-': { int i; iss >> i; retval -= i; break; } default: throw std::logic_error("invalid expression: " + expr); } iss.peek(); } return retval; } int main() { for(std::size_t i=0; i<std::pow(3, 8); ++i) { std::size_t mod = i; std::string expression; for(std::size_t j=0; j<8; ++j) { expression += std::to_string(j+1); switch(mod%3) { case 0: expression += '+'; break; case 1: expression += '-'; break; case 2: break; } mod /= 3; } expression += '9'; if(run(expression) == 100) std::cout << expression << " = 100" << std::endl; } return 0; }
最初、std::pow(3,9)回ループを回してしまい、大量の解答を出してしまったのに気づかずに終えそうになったのは内緒だ。
総括
普段はexplicitな時間制限ありの問題を解こうとはしないタチなのだが、こういうのもやってみると面白いと感じた。趣味でやっているものだと時間的制約がほぼないので妥協点を見誤ることが多いのだが、こういう時間制限ありの問題はその辺のバランスを取るのに役立ちそうだ。もし時間的制約がなければ、勉強になるからとboost::anyの実装を調べて劣化コピーを再実装していただろうし、問題5も色々調べて木構造を作ったりしていただろう。他のことが暇かどうかにもよるが、1時間以内で出来るはずのことに数日かけていたかもしれない。
実際、趣味や学習目的ならともかく仕事的には同じコードなら素早く書けたほうがいいに決まっているので、妥協点を探る練習というのもいずれしていかねばならないよなあという気持ちを新たにした。あと問題5のやり方をすぐに思いつくような瞬発力か。まあこれも書くしか道はあるまい。
