肉5パック,魚4パック,野菜3パック,豆2パックから1日2パックずつ選び一週間(7日間)の献立を作成する。条件は以下の通り。
肉をM，魚をF，野菜をV，豆をBとして考える。
肉は5パックあるので，少なくとも肉は以下のように使わなければならない。
組合せは(M,M)，(M,F)，(M,V)，(M,B)の4種類。
残りの組合せは(F,F)，(F,V)，(V,B)の3種類。
全部の組合せは以下の通り。
このうち(F,V)の組合せに注目すると，隣に来れるのは(M,M)，(M,B)に限る。
このうち(M,B)の隣に来るのは(F,F)または(F,V)であるから，以下のように拡張できる。
(F,F)の隣は(M,F)，(M,V)，(V,B)の３通りが来ることが出来るが，Mは１つおきに置かなければならないので，(V,B)の可能性は無い。
(M,F)はFが隣り合うことになるので，(M,V)しか残っていない。よって以下のように拡張できる。
ここまで来ると後は一直線。
うーん，プログラムを書かずに簡単に解けちゃったなー。
プログラムを作るとしたら数字の割り当て問題を改良し7種類を虱潰すコードになる。
メニューに使われる食材の種類をval[ ]で表現する。M,F,V,Bにビット1,2,4,8を割り当てると，食材の組合せは以下のように定義できる。
int val[7] = {1,3,5,9,12,6,2};
最後に結果を表示するため以下のように文字列を定義する。
cstring s[7] = { "(M,M)", "(M,F)", "(M,V)", "(M,B)", "(V,B)", "(F,V)", "(F,F)"};
ループの途中で前日と同じ種類が使われているかどうか判定するのは面倒なので，ループの一番中で全て判定する。コードは以下のようになる。
if( !((val[a] & val[b]) ||
(val[b] & val[c]) ||
(val[c] & val[d]) ||
(val[d] & val[e]) ||
(val[e] & val[f]) ||
(val[f] & val[g]))) {
ps( "%s, %s, %s, %s, %s, %s, %s\n", s[a], s[b], s[c], s[d], s[e], s[f], s[g]);
}
答えは2件出力されるが，逆向きにしたものなので実質1件。