メニエスの名のもとに

プログラミング関係を中心としたぐだぐだブログ

macports + scons でハマる。

AutoTools が難しすぎて使えないので scons にしたのであった。

ただし、make くらいならなんとか easy mode で使えるので、ふだんは make を使い、環境依存が大きくmake の easy mode ではどうにもならないような場合は scons を使うというように使い分けていた。
もちろん、scons だってよく分かっている訳ではない。「酢昆布と語呂が似ている」ということくらいしか知らないのである。それだって実は怪しくて、スコンスではなくエスコンスかも知れないし、o は古代ケルト語のなんとかいう発音が本来とか言われかねない怖ろしい世界なので、日本人には発音不可能なコズミックホラーと思っておいた方がいい。
で、よく知らないままsconsを使い始めてすぐに scons でbuildするとそのままではC_INCLUDE_PATHなどの環境変数を参照してくれないということを知ったのであった。まあ、それは build script である SConstruct に追加すればいいわけだ。
で、昔のプログラムに手を入れようと思って、少し修正してsconsしたらコンパイルエラーになる。まあ、そこまでは良くあることだが、自分のエラーを修正してもコンパイルエラーがなくならない。macports を使っているので、gcc を切り替えてみた。apple版から4.9.2 にしてもコンパイルエラー。どうやってもエラーがなくならないので、scons をやめてmakeにしたら通った。正確には make を使い、gcc 4.9.2 ならコンパイルエラーがでない。
どうもscons はコンパイラを探すときにパスを見てくれないらしい。じゃあ、apple版のgccは何故エラーになるのか。それは、私がYosemiteにしていないからだろうか。それとも何か環境が壊れたのか。どちらにしてもYosemiteにすれば直るような気はする。

気になることは自分で調べよう。

「上目遣い」というのは「魔法使い」とか「妖術使い」とかの一種に違いない。

氷菓

氷菓

ナンプレ問題生成のGitHubのWikiを書きました


Home · MSaito/NumPl Wiki · GitHub

いやあ、MarkDownって便利ですなぁ。こうやって、テキストで書いてそれがhtmlに編集されるなんて便利すぎますよ。私もRD(Ruby Document Format)や、このはてな記法や、doxygenの記法や、PukiWiki の記法やらいろいろ似ているようで違うものを使ってきましたが、滅茶苦茶便利なので今後も大量に少しずつ違う記法が山のように出現するんでしょうな。なに、MarkDownで最後ですって? いやいや、現にGitHubのMarkDownはMarkDownの方言ですよ。MarkDownが最後だったとしても方言は数限りなく出てくるのではないでしょうか。いやあ、めっちゃ便利だわぁ。

ナンプレ(数独)問題作成プログラム 生成法解説2

phase3 再帰しながら指定された解法を含むまで全部調べる。

phase3 は再帰アルゴリズム。入力は盤面配列(実は入出力)と検索開始位置と解法指定、出力はあまり言いたくないけど難易度、ただし、マイナスは矛盾があって解けない。ゼロは知っている解法では解けない。
最初に解いてみて、指定された解法で解ければ適当に計算した難易度を返す。解けなければ0またはマイナスを返す。指定された解法では解けない場合、関数本体の処理を行う。
開始位置から配列の半分までのすべての固定マスについて、そこを固定でなくしてみて再帰する。その中で再帰の返却値が最も大きい時の盤面を返す。
なんだ簡単だった。

phase4 もう一度固定を外す。

phase3では指定の解法を含んだ時点で固定マスを外すのを止めていたので、まだ固定マスを減らせる可能性がある。そこで対称性を保ちながら、固定マスを外しても解けるか調べる。

phase5 対称性を考えずに固定を外す。

最後に対称性を考えずに固定を外して解けるかを調べる。

単純ですね。

プログラムを日本語でそのまま説明して、ドキュメントにするなんていうのは、職業プログラマならいくらでも経験しているはず。図を描けばいいんだけど、それは面倒だからね。まあ、本当に関心のあるひとはプログラムを読むでしょう。明らかにphase3が遅い。その結果、難しい解法だけを指定するとプログラムの実行がすごく遅くなる。まあ、1問につき1行の出力なのでTuple以上あたりの指定(-tfy)で大量に出力させ、その中から良いものを選ぶのがいいんじゃないかな。

mosaic.wav の新作が出ている

だが、ナンプレアプリが売れていないのでがまん、我慢。

ナンプレ(数独)問題作成プログラム ドキュメント

ドキュメントは重要、超重要

といいながら、プログラムが出来てからドキュメントを書いているようではいけないわけだが。doxygen ドキュメントを頑張っていれましたよ。まだまだ不足していますが、一気にやる気力はない。ボチボチやるが、ドキュメントなので、このブログでは修正報告はしません。
それ以前に、昨日のgit push 時には重大なミスがあってコンパイルできない状態でした。ダメじゃん。
MSaito/NumPl · GitHub

generate プログラムの解説

generate.c は主に5つのphaseに別れています。このうち、phase5だけが非対称にする操作なので、-S オプションで対称生成を指定した場合は、phase5をスキップしています。

phase1 数字を決め打ち

phase1とphase2はAとBという二種類あります。主にAで説明します。phase1Aが呼ばれる時点で、ナンプレの盤面にはすべてのマスにすべての数字が候補として入っています。この時、まだ固定された数字はありません。
9つのブロック三行三列でありますが、それを四隅の4ブロックと中央十字の5ブロックに分けます。この扱いがAとBの違いになります。Aでは中央十字ブロックのそれぞれのブロックに数字を置いてそこを固定マスとします。固定マスとは出題時に数字が入っているマスです。
十字の上のマス内のランダムな位置に数字の1を置きます。それと点対称な位置(十字の下のブロック)に数字の2を置きます。ブロック内の位置はランダムですが数字は決め打ちです。あとで convert コマンドによってランダム化する必要があります。
同じく十字の上のマス内のランダムな位置に数字の3を、点対称な位置に4を置きます。十字の右側のブロック内のランダムな位置に5,7を、点対称な位置に6,8を置きます。
8まで使ってしまったので、十字の中央のブロックにはランダムな位置とその点対称な位置にランダムな数字を置きます。ここではランダムな数字を置くので、解けない可能性があります。解いてみて解けなければ、やり直します。
それから、中央以外のブロックにランダムな数字を一個ずつ対称性を保ちながら入れます。ここも解いてみて解けなければやり直し。
というのがphase1Aです。phase1Bは中央の代わりに四隅に数字を入れる点が違います。

random_solve ユニークでない解を適当に選ぶ。

ここまででは、固定マスの数が14なので、矛盾して解けない場合を除けば高い確率で複数の解をもつナンプレ問題になっています。用意してある解法をつかうと、ほとんどのマスに複数の候補が入った状態になります。この複数の候補からランダムに一つ選んで解くということを再帰的に実行して解きます。選び方が悪いと矛盾して解けないこともありますので、その場合はやり直します。
結果的にはすべてのマスに一つの数が入った完成形のナンプレが得られます。

copy

完成形のナンプレから、phase1Aの盤面に四隅のブロックだけコピーします。コピーした部分は固定マスに設定します。phase1Bの後なら中央の十字ブロックをコピーします。
この後、phase2以降で固定マスを減らすということを繰り返していきます。

phase2A

全部固定マスになっている四隅のブロックからランダムなマスを選んで固定を解除しすべての数字を候補として入れます。各ブロックに4個ずつ固定を解除します。解いてみて解けなければあきらめる、つまり最初からやり直し。
十字の上のブロックに固定で入っている数字をその左右のブロックから取り除いてそこをすべての数字を候補とするマスに変えます。

phase3

ちょっと説明が面倒なので、明日にしよう。phase1, phase2が特に勘と経験と失敗に基づくヒューリスティックな部分。phase3以降は比較的工夫のないオーソドックスなアルゴリズム

グレンラガン

バンダイチャンネルで見放題に入ったのでグレンラガンを見た。これ、螺旋がテーマなのは話が宇宙までスケールアップするという設定が先にあって、そこから螺旋とドリルが出て来たのではないかと思う。こういうスケールアップはガイナックスならではですね。

ナンプレ(数独)問題作成プログラム その23 generate

generate の実行形式がmake できるソースをGitHubに上げました。

まあ、例によってバグがあるという可能性は否定できない。というかむしろ高い。
ドキュメントが出来ていない。doxygen を想定してコメントは入れていたけど、実際にはdoxygenをかけていないのでdoxygenのエラーが出ると思われる。これから直さないと。
MSaito/NumPl · GitHub

使用法

9x9のナンプレの問題を作成する

./generate
generate start seed = 4226 number = 1
"90,4,7,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,28,1":"  1 2    32 4 1      563     4  51  61  4  75  83  9     954      1 8 64      7  "

何も引数を指定しないと、一個だけ問題を作成する。出力の最初の行は疑似乱数のseed を表示している。number = 1 は出力を1個だけ出すということを表している。
次の行のコロンの前は、使用する解法の情報を示しているが、最後の二つは固定数字の数と解けるかどうかを示している。上の例では固定数字が28個、そして解ける。これはユニークな解があるという意味である(バグがなければ)。
後半は最初の9個が1行目、次の9個が2行目というように問題を表している。

 ./generate -v
generate start seed = 3593 number = 1
number = 0
kill_single:86
kill_hidden:10
kill_locked:3
kill_tuple :2
swordfish  :0
naked_tuple[2] = 0
naked_tuple[3] = 0
naked_tuple[4] = 0
naked_tuple[5] = 0
naked_tuple[6] = 0
hidden_tuple[2] = 2
hidden_tuple[3] = 0
hidden_tuple[4] = 0
hidden_tuple[5] = 0
hidden_tuple[6] = 0
fish[2] = 0
fish[3] = 0
fish[4] = 0
fish[5] = 0
fish[6] = 0
fish[7] = 0
fish[8] = 0
xywing     :0
fx_count   :29
solved     :1

            [1][2][3][4][5]


         [3]      [1]


               [5]   [6]


      [7][5]   [4][8]   [2]


   [9]               [3]


[5]   [8][2]   [3][4]


   [5]   [6]


      [6]      [7]


[7][8][2]   [5]
  • v オプションを指定すると、もう少し見やすい形式で作成した問題の情報を表示する。-v オプションを指定しないときの出力は、この出力と対応している。最初がkill_singleの数、次がhidden_single の数というように。naked_tuple[2]はnaked pair の数を表している。hidden_tuple[6]とか絶対に出現しないが気にしてはいけない。fish[2]はx-wing, fish[3]はswordfishの数である。
  • h を指定すると hidden_singl を解法として含むような問題だけを出力する。-l はlocked_candidate, -t はnaked tuple, hidden tuple, -f はx-wing, swordfish,...,
  • y はxywing を解法として含むような問題を出力する。この指定を複数すると or で結合される。つまり、どれかを含めば出力される。この部分に何も指定しないと、-tfy が指定されたものと解釈する。
  • S オプションを指定すると、点対称な問題だけを出力する(はずである)

出力された問題は正規化(いいかげんな正規化)されているので、sort -u なりなんなりして、同一の問題を取り除くとよい。その後、convert を使ってランダム化するとよい。

./convert "1        2 3 4      5167    89    41 3 281 6 51    83    4157      3 9 6        4"
84,11,3,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,29,1"  5      6 2 4    8  395   14    39  2 917 4  59    16   829  3    5 7 4      9  "

ああ、convertの出力がおかしい。あとで直さなければ。(今直せって)(いやでももう今日は達成感があるのでやりたくない。)
おっと、重要なオプションを書くのを忘れていた。-c 数値で出力する問題数を指定する。-c 1000 とか指定するとそこそこ時間がかかるので、-c 10 で時間を計って見当を付けてから大きな数字を指定するとよい。数万から数十万問題を作成してその中からよいものを選ぶ必要があると思う。

アルゴリズムなど

これぞ、ヒューリスティックというようないい加減なアルゴリズムなので、うまく説明できないが、まあうまく動いているみたいだからいいじゃないか。あとで説明するかも。で、既に問題生成プログラムがあったのに時間がかかったのは、潜在バグがあったからです。あと高速化しようとして逆に低速化したりしていたので。

あさひなぐ小学館漫画賞受賞おめでとうございます

1巻から買ってるよ。大工原さんもいいキャラです。

あさひなぐ 14 (ビッグコミックス)

あさひなぐ 14 (ビッグコミックス)

Application Not Responding 対策

処理が遅くてANRが発生しているのだと思っていたが、実際にはバグだった。

自分のバグじゃないと思ったときは、たいてい自分のバグなんだよね。解いている途中のデータを保存するときに、不正な保存形式になっていて、次回起動時にその不正なデータを読み込もうとすると、あろうことか無限ループに陥ってしまうという怖ろしいバグであった。
その原因は、空のマスに数字を確定として入力したときに、この数字は大きい文字で表示というフラグを立てるのだが、undo するとそのフラグだけ残るというものであった。数字がないのに大きく表示するというフラグのあるデータは、フラグを無視して読み込むように修正し、動作を確認したのちに、フラグだけ残るバグを取って不正なデータが出来ないように修正。
処理が重いのだと思ってかなり改変してしまったので、メモリ消費量とか減っているといいな。

Application Not Responding 対策

ANR が発生していました。

ANR 対策のためアプリを全面的に書き換えています。その間、ナンプレアプリの公開を停止しています。デバッグ後、再度公開する予定です。

基準がないのが問題ではないか。

重い処理をするときは別タスクと言っても、どこから重いかは誰にも分からないのです。仕方がないので、画面表示処理以外は可能な限り別タスクにすることにしました。ということはつまり、全面書き換えに近いわけです。それにも拘わらず、ここは重くないよねとかつい思ってしまうが、それが罠という気もする。

インテントによる画面遷移もしていない

まあ、重いと言えばインテントによる画面遷移が重いのですが、これは開発初期に止めていました。重いからというより、遷移先の画面でhomeボタンが押されたら、次に再開するときはその遷移先の画面であるという仕様と、ボタンが足りないので前画面に戻るのはBackボタンにするという決定から、インテントではほとんど無理だったので。

デバッグも不足していた

デバッグでANRを発見できなかったのは、デバッグ不足もあるので、今後はもっとデバッグに時間を掛ける必要がある。というわけで、再公開はすぐにはできません。