EXCELで1次元セルオートマトンを作る

　こないだに続いてEXCELネタです。
　特に目新しくもないですが、1次元セルオートマトンも関数で簡単に実現できますのでメモしておきます。

　まずは遷移ルールの入力/表示部分です。

　セルD2は次のようにします。これはルール入力欄（E4:L4）に基づきルール番号を計算して表示します（ただの表示ですので、この式はなくても動きます）。

="ルール"&SUMPRODUCT(E4:L4,{1,2,4,8,16,32,64,128})

　E3:L3には「="000"」から「="111"」までを入力します。これらは単なるラベルではなく後に参照されますので、このとおり入力する必要があります。

　これとルール入力欄（E4:L4）によって遷移ルールが定まります。
　この例では「011」の下が「1」となっていますので、1世代前の左側・中央・右側のセルがそれぞれ「0」「1」「1」であるとき、セルの値は「1」となります。

　続いてセルオートマトン部分です。
　左端の列（A列）の値はいずれも「0」としておきます。同じく右端の列の値も同じく「0」としておきます（列数が多すぎるとかなり重くなりますので、どの列を右端にするかは適宜決定してください。）。

　こうしないとエラーが発生してどんどん伝播してしまうからですが、遷移ルールによってはやはり端の列付近で不自然な結果になりますので、これを避けたい場合は十分な列数を確保して初期状態の設定にも注意する必要があります。

　最後にセルオートマトン内部です。

　7行目は初期状態入力欄ですのでさしあたりすべて「0」としておきます。
　そしてB8セルに次のように入力し、全体（右下方）にコピーします。

=HLOOKUP(A7&B7&C7,$E$3:$L$4,2)

　あとは見やすいように、値が「1」であるセルを塗りつぶすように条件付き書式を設定すれば設定完了です。

　実行の様子です（冒頭の画像の再掲）。ルール入力欄（E4:L4）と初期状態入力欄（7行目）の値を書き換えればセルオートマトン全体がリアルタイムで更新されます。
　ただし条件付き書式のせいか、再計算には結構時間がかかり、値の変更が直ちに反映されない場合がありますので注意してください。
　画像はルール90を示しています。ルール入力欄（E4:L4）の値を「0,1,0,1,1,0,1,0」とし、初期状態としてセルAI7の値を「1」としています。

　次にルール30です。ルール入力欄（E4:L4）の値を「0,1,1,1,1,0,0,0」としています。

　最後にルール110です。ルール入力欄（E4:L4）の値は「0,1,1,1,0,1,1,0」です。

ナップサック問題をEXCELワークシート関数で解く

　[※2022年11月追記]　新関数を使った総当たり法の例を別ブログに記載していますのでそちらもどうぞ。

　松の内も明けたところで今年初の記事です。今年もよろしくお願いします。
　さて、いきなりですが今日のテーマはナップサック問題の動的計画法による解決です。普通はVBAかソルバーでやるところですが、方法的にワークシート関数で実現できそうなのでやってみます。

問題の概要

　ここで扱うのは「0-1ナップサック問題」で、詳細は次のとおりです。

• 価値、重量がそれぞれ異なるアイテムがいくつかあり、定められた上限重量以内で価値が最大になるようにアイテムを選択する
  
• 1つのアイテムを分割したり2回以上選択することはできない
  
• 重量は整数とする

　動的計画法の適用については以下のサイトなどが参考になるかと思います。

mathwords.net

正直難しいですが、各アイテムに順次着目しながら漸化式の要領で解いていくことができ、総当たり式と比べて計算量を大幅に削減できるのが特長です。

手順

シート構成

　画像が小さくてスミマセンがEXCELシートです。

　まずは次のような各欄を設けます。

入力部
　上限重量入力欄……B4
　アイテム価値/重量入力欄……B8:C17
出力部
　価値総和表示欄……E4
　個々のアイテムの要否判定表示欄……E8:E17
作業部
　参照列欄……G8:G17
　重量総和メモ（DP）欄……H8:W17

　入力行が10行ですので設定できるアイテムは10個までです。
　重量総和メモ（DP）欄が16列ですので指定できる上限重量の限界は15までです。
　なお、H6:W6に記入されている0~15の値は計算に用いられますので必須です。
　また、G7:W7（緑色）はこの解法に特有のダミー行（0番アイテム）です。

関数の入力

　では関数を入力していきます。
　まずは重量総和メモ（DP）欄からです。

　W8セルに次のように入力し、それからH8:W17の範囲でコピーします。
　H8セルで始めるのが普通かと思いますがこっちの方が解法の考え方が見えやすいかと思いました;-o-)

=MAX(W7,IF($C8>W$6,0,OFFSET(W7,0,-$C8)+$B8))

　この式により、1つ上のアイテムまでの選択結果に基づき、当該アイテムを追加するのとしないのとどちらが価値が高いのかを判定しています。
　当該アイテムの重量に応じて参照先が変わるようにOFFSET関数を用いていますが、参照先が表外に飛び出さないようにIF関数を用いています。

　
　次に参照列欄です。

　G8セルに次のように入力し、G17セルまでコピーします。

=IF(G9="",B$4,IF(OFFSET(H8,0,G9)=OFFSET(H9,0,G9),G9,G9-C9))

　この欄の目的は、上記の選択の過程（最終結果につながるもの）を記録することです。結果を直接記録しているわけではありませんが、この値を1つ上の行と比較することにより判定することができます。

　次に要否判定表示欄です。

　E8セルに次のように入力し、E17セルまでコピーします。

=IF(OR(OFFSET(H8,0,G8)=0,G7=G8),"","○")

　基本的に参照列欄の値が1つ上と同じであれば当該アイテムは選択されておらず、異なっていれば選択されているものと判定します。
　複数の解（アイテム選択の組み合わせ）がある場合でも表示される組み合わせは1つのみです。

　最後に価値総和表示欄です。

　E4セルに次のように入力します。

=OFFSET(H7,COUNTIFS(B8:B17,"<>" & "",C8:C17,"<>" & ""),B4)

　価値総和はSUMIFで求める方が簡単ですけども、あえて重量総和メモ（DP）欄からの表引きにしました。アイテムが記録されている行のうち最も下の行で、重量上限の値に対応する列の値が表示されます。

実行の様子

　入力部に各アイテムの価値、重量を記入すれば解はリアルタイムに更新されます。　

　実際に値を入力した様子です。8つのアイテムデータと上限重量を入力したときの解が出力部に表示されています。

備考

　上限アイテム数と指定できる上限重量の限界は、表をコピペで拡張することで容易に拡大できます。念のため上限アイテム数100（実際に100個設定）、上限重量の限界300でやってみましたところ、結果は上記の例と同様に一瞬で出ました（2018年春モデルのミドルレンジノートPC使用）。
　方法的にアイテム数を増やすのは容易であるものの、個々のアイテム重量が4桁とか5桁とかになった場合に扱うのが難しい（列数不足、計算量増大に直結する）のが難点です。
　結びになりますが、考え方は大きく間違っていないハズですけども酒漬けの年末年始に考えたものなのでなんか穴があるかもしれません。あしからず;-o-)

AOJで100問ほど解いてみました

　こないだ登録したAOJについてです。プログラミング入門者ですので簡単なやつばかりですけども100問ほど解いてみました。
　Pythonのリストや辞書の操作は面白いですが何回やっても理解が怪しく、毎回ググってしまいます;-o-)一度自分でまとめてみるのもいいかもしれません。

　というわけで印象に残った問題をいくつか紹介してみます。解法も記していますがコードは恥ずかしくて出せません_ _)

ALDS1_1_D: Maximum Profit

　問題はこちら。

最大の利益 | アルゴリズムとデータ構造 | Aizu Online Judge

　刻々と変動する価格のデータRt (t=0,1,2,,,n−1)が示されます。その中で1回だけ買って必ずその後に売るということを（事後評価として）考えた場合に、最大利益はどう求められるかという問題です。
　Ri<Rjという条件で2重ループして差の最大値を求めれば答えは簡単に求まるのですがそこが罠でして、題意どおり時間切れになります;-o-)
　そこでループは1回とし、「現在の価格（ループで取得した価格）」と「そこまでの最低価格」を比較して最大利益を更新していくことにより最終的に正解が得られます。
　要点が理解できれば10行も必要ないのですが、わからないうちは「価格が下がる一方で終わる場合の処理」（実は対応不要）などいろいろ考えてしまいますし、値の更新順序なども間違いやすく一苦労。

1173: The Balance of the World

　文中の2種類のカッコ ( ) と [ ] の使い方が正しいかどうかチェックするという問題です。

The Balance of the World | Aizu Online Judge

　ついついカッコの数を数えて差し引きして…とやりたくなりますが2種のカッコの咬み合いをチェックするのが難しく、わけがわからなくなります。
　答えとしては ( と [ をスタックに加え ) や ] が現れたら除いていくというのが簡単です。) に対応するのが [ だったり ] に対応するのが ( だったらその場でOUT、スタックが余ったり不足してもOUT、それらがなければOKとなります。
　スタックの有用な例としてとてもわかりやすいです。

ALDS1_3_D: Areas on the Cross-Section Diagram

　地形の断面図から、そこにたまる水の断面積の最大値を求めるという問題です。

模式断面図の面積 | アルゴリズムとデータ構造 | Aizu Online Judge

　いくら考えてもわかりません;-o-)
　そこでググりましたところ、つまり＼のX座標をスタックに加えていき、その後／が見つかったらスタック末尾のX座標との差を求める（＼のX座標はスタックから除く）、ということを続けていけば断面積は求まるということが判明。／に対してスタックが空であればその／は水たまりになり得ないことを意味しており、＿の存在や「高さ」を考慮する必要も全くない…なるほどわかれば驚異的に簡単ですが、やはり知らなければ一生思いつかない気がします。
　なお問題としては全体の断面積だけでなく個々の水たまりの面積を回答する必要があり、そっちの方が厄介です（自分は各水たまりの左端の座標と面積を記録するリストを作り管理しました）。

0067: The Number of Island

　マップ上に島（上下左右につながっている点の集まり）がいくつあるかという問題です。

島の数 | Aizu Online Judge

　素人目でライフゲーム的な解法があるのではないかと思ってしまったのですが、環礁のような場合を考えると無理っぽいことが判明。そもそもそんなやり方では明らかに時間が足りません。
　結局ググりましたところ、これはどうやら探索と呼ばれる分野に属していて、深さ優先探索というのをやればよいとのこと。そんなん思いつくわけありませんね;-o-)
　というわけで再帰処理というものから調べなければなりませんでしたが、これがどうも苦手で目が回ります。階乗の例で一応納得して、あとは細かいことを考えず探索の関数を作成。配列上に記録したマップを2重ループでチェックして島（点）を発見したらそこから探索開始するとともに見つかった点は消していくものとし、最終的に関数の呼び出し回数を数えればそれが答えになります。先達の皆様のコードを参考にしながら自分が理解できる形でなんとか正解できました。
　ところで探索というのはロマンがありますね。応用が広そうですし、何と申しましょうか俺のナノマシンが世界を覆いつくすぜ的な厨気分に浸れるのがいいです。

ここまでとこれから

　まずPythonというものに慣れる必要がありますので無勉で解けるような問題を優先して解いている段階です。
　もう少し慣れたらより本格的なアルゴリズムの学習を…と言いたいところですが、地味なソートとか木とか、覚えるべき基本がゴロゴロありますので当面はその辺りに注力したいと思います。