TIM Labs

2018年8月アーカイブ

ナンプレブームが今も続いていて、今年もMATH POWER 2018 に巨大合体ナンプレ世界一(?)を提供することになった。
去年は国政選挙に邪魔されて、六本木のニコファーレが使えず、会場が青山になったが、今年はニコファーレの予定である。
巨大合体ナンプレは現在鋭意制作中であり、世界一になるかどうかはまだ分からない。
さて今回は、合体ナンプレの話ではなく、サイズが9x9の単体のナンプレ問題の話をしよう。
NPSame1.png NPSame2.png
さて、この2つの問題、何が違うだろうか?

文字列が格納されている変数 str から、末尾の連続する改行文字を削除しようとして次のようなコードを書いた(言語:Ruby)。

str.sub(/(\r\n|\r|\n)+\z/, "")

本コードには問題がある。

  1. 問題点を指摘せよ。
  2. 改善案を提案せよ。

とだけ書いて、答えられる人はどのくらいいるだろうか。これは別に筆記試験というわけではない。手元に Ruby 実行環境があるなら様々な入力で試してみて欲しい。もちろん Web を検索してみても良い。

一見なんの変哲もない一行のコードだが、これはシステムをダウンさせかねない大きな問題を抱えている。読み進める前に、今、コードレビューやテストをしている段階だと考えて、ぜひそれを指摘してみてほしい。

数学の祭典 MATH POWER が今年も開催される。
時期は、10月最初にある連休の最初の2日間に行われる。
今年の場合、10月6日昼から7日夜まで、31時間連続で夜を徹して数学を愛でるイベントだ。
場所は、六本木のニコファーレだ。

既に MATH POWER 2018 のサイトが公開されていて、参加申し込みも受け付けている。


MathPower2018SiteHeadImage.png

サイトは、まだまだ情報不足だが、どんなことが行われるかは、去年のサイト MATH POWER 2017 を見ると良いだろう。
去年は、イベントの最初から最後まで、多人数でやっと解ける程度の合体ナンプレを作って欲しいというので、247合体ナンプレを作った。
フィナーレまでには終わらなかったが、若干の延長で解き終えると思われたので、イベントをちょっと延長し、完成したのであった。
その問題がこれだ。

MP247Q.png
MATH POWER 2017 のサイトを見れば、ExcelとPDFで問題があるので、興味のある場合は解いてみよう。

さて、今年のMATH POWERでは、もうちょっとグレードアップした問題を提供することになっていて、現在鋭意製作中である。

去年は「世界最大級」というふうに級をつけていたが、今年はそんなに遠慮せずに、「世界最大」とすることにした。
そのために、去年よりもさらに大きくなってしまった。

去年のデザインは、美しいけれども単純な繰り返しなので、解き筋もモノトーンになってしまう。もっと色々な手筋が現れるように、もうちょっとデザインを頑張ってみた。
その他にも、色々なことにチャレンジしている。

しかし、そんなことをすると、どうやっても問題ができなくなることがある。

それに、いきなり巨大なものを作るのは危険だ。何時間、いや何日も連続でコンピュータを走らせても、何の結果も得られないことが多くなる。
そのため、小さい問題、といっても148合体とかなのだが、その程度の小ぶりな問題(?)で試作をしてみる。
この程度のサイズですんなり出来ない場合には、今年の問題サイズでは絶対に無理なのだ。

コンピュータ、ネットワークなど何でも同じなのだが、小さい場合にうまくいっても、そのまま拡大したら破綻することが多い。
サイズが2倍になったら、計算時間は10倍、100倍どころか永久に終わらなくなる。

ということで、色々な小さな問題を作っては問題生成の調子をみて、スケールアウトできそうだったら本番サイズで試すというのを繰り返している。
使っているアルゴリズムは、進化計算の一種である。
デタラメに問題をつくっては解き、どのくらい酷いかを判定し、ちょっと問題をいじっては酷さを判定している。
どんどんひどくない方向にヒントの数字をいじるのを繰り返しているだけである。
要するに、仕組みは簡単至極である。

問題の難易度はポイントで示される。
これを元に解くのにかかる時間が予想できる。
しかし、それだけでは十分ではない。
極端に易しい場所や、極端に難しい場所がないか、コンピュータに計算させている。
その結果を見て、ざっと判定し、良さそうな問題ができたら、実際に解いてみて、解き心地を調べる。

こういうのを繰り返して、イベントで解いてもらう問題を1問選定するのだ。
とても時間のかかる作業だ。

去年うまくいったので、さらにレベルアップして、来場者が驚くような、印象的なイベントにしようとしているのだ。
どんなサプライズがあるかは、イベントに参加して体感してみよう。

コピーの基礎的なことから書くので、話が無駄に長くなるのを最初に断っておく。 最後に、a[...] のような記述について書くので、そこだけ読みたい場合は最後から読もう。
まず、Pythonでの浅いコピーを示す。
>>> a = [[1,2,3],[4,5,6]]
>>> b = a
>>> a[0][0],a[1][1] = 100,200
>>> a
[[100, 2, 3], [4, 200, 6]]
>>> b
[[100, 2, 3], [4, 200, 6]]
aの要素だけを変更しようとしても、 b = a の代入により浅いコピーが行われているので、bの対応する要素も変わってしまう。

これを避けるためには、b=aの代わりに、copyのdeepcopy()を使う。
>>> import copy
>>> a = [[1,2,3],[4,5,6]]
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
[[100, 2, 3], [4, 200, 6]]
>>> b
[[1, 2, 3], [4, 5, 6]]
さて、Pythonで色々計算しようとすると、Pythonではやってられなくて、NumPyを使うのが普通だ。 そもそも、Pythonには配列がなく、Deep Learningで必須の行列計算に困る。
では、numpyの配列で同じことをやってみよう。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b = a
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[100,   2,   3],
       [  4, 200,   6]])
単に代入ではコピーにならないようだ。
次に、numpyで用意されているcopy()を使ってみよう。


深いコピーができたようだが、念の為、サイズが歪なarrayでやってみよう。
>>> a = np.array([[1,2,3],[4,5]])
>>> b = np.array([[2,4,6],[3,6]])
>>> b = np.copy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([list([100, 2, 3]), list([4, 200])], dtype=object)
>>> b
array([list([100, 2, 3]), list([4, 200])], dtype=object)
歪んだarrayでやったら、元のaがリストの配列になってしまい、失敗したようだ。
numpyには、copy()はあるようだが、deepcopy()が存在しない。 それで、ここはやむなく、copy.deepcopy()でやるとどうなるか試してみよう。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[1, 2, 3],
       [4, 5, 6]])
>>> a = np.array([[1,2,3],[4,5]])
>>> b = np.array([[2,4,6],[3,6]])
>>> b = copy.deepcopy(a)
>>> a[0][0],a[1][1] = 100,200
>>> a
array([list([100, 2, 3]), list([4, 200])], dtype=object)
>>> b
array([list([1, 2, 3]), list([4, 5])], dtype=object)
これで深いコピーができたわけだが、元の配列aは2次元配列ではなくて、リストの配列になっているので深いコピーができなかったようだ。
さて、配列の深いコピーをするのに、copy.deepcopy()を使えば問題ない。 しかし、普通のnumpyの配列なら、numpyのcopy()で深いコピーができる。


ごちゃごちゃ書いてきたが、最後に ...(3点)の使い方について書いておく。
>>> a = np.array([[1,2,3],[4,5,6]])
>>> a
array([[1, 2, 3],
       [4, 5, 6]])
>>> a[...]
array([[1, 2, 3],
       [4, 5, 6]])
配列aを表示するのに、単にaと書けば済むのだが、a[...]と書くこともできる。
ならば、a[...]に代入するとどうなるだろうか?
>>> a = np.array([[1,2,3],[4,5,6]])
>>> b = np.array([[2,4,6],[3,6,9]])
>>> b[...]=a
>>> a[0][0],a[1][1] = 100,200
>>> a
array([[100,   2,   3],
       [  4, 200,   6]])
>>> b
array([[1, 2, 3],
       [4, 5, 6]])
同じサイズの配列の場合、これで配列の深いコピーができている。 copy.deepcopy()やnumpy.copy()を使わなくてもできるのだが、事前に同じサイズの配列が存在していないといけない。

最後に、...が何者か示しておく。
>>> ...
Ellipsis
>>> type(...)

...はオブジェクトなので、引数として渡すなどもできる。

このアーカイブについて

このページには、2018年8月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2018年7月です。

次のアーカイブは2018年9月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。

月別 アーカイブ