名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

CodeIQ のアルゴリズム問題「交差点をすばやく数えよう！」by @hyuki に解答しました

CodeIQ アルゴリズム 転倒数

【2013/09/04 23:00 解答フィードバックを受けて、続編書きました。⇒ もっと「クロッシング問題」（＝転倒数計算問題）】

CodeIQ のアルゴリズム問題（出題者：結城 浩 氏 @）にまた挑戦してきました。

挑戦者求む！【アルゴリズム】交差点をすばやく数えよう！ by The Essence of Programming 結城 浩│CodeIQ

通称「クロッシング問題」（出題者本人公認）。
約半年前の「チョコ問題」から、結城浩氏の問題にはほぼすべて*1解答しているのですが、今回は個人的にちょっと思い入れがあるので、久々に自分の解答コードを公開してみます。

解答の前に…

転倒数

この問題は、数学的に一言で説明すると「与えられた順列の転倒数を算出する問題」です。
たぶん、そのあたりの詳しい説明は解答のフィードバックで結城氏から与えられると思うので、細かいことは省略します。
一応、転倒数というのを簡単に説明しておくと、以下のような感じです。

a1, … , an を、相異なる n 個の数値 1, … , n からなる順序づけられた数列（＝順列）とするとき、以下で表される順序対の個数を『転倒数』という：

#\{(i, j)|1\le i \lt j \le n; a_i \gt a_j\}

すなわち、「i < j であって、ai > aj であるような (i, j) の組の総数」のことである。

より厳密な定義とかは例えば wikipedia:転倒_(数学) とかを参照してください。

で。
これをそのまま計算しようとすると、すぐに思いつく方法は、
「配列の左から順に、その数より左にその数より大きい数がいくつあるかを数えて、それを全部足す」
ということなのですが、これは容易に想像がつくように、バブルソートと同じアルゴリズムであり、計算量は O(n2) となります。情報量が多かったらとてもじゃないけど現実的な時間内に解くことは出来ません。
そこで、「転倒数算出の高速化（アルゴリズムの選定）」が必要になる、というわけですね。というのが、この問題。

転倒数を算出するアルゴリズム

私が試したのは、以下の 3 つです。

  • 二分探索（binary search）を利用したもの
  • マージソートを利用したもの
  • Binary Indexed Tree (Fenwick Tree) を利用したもの

最終的に採用し提出した回答コードは、最後の「Binary Indexed Tree を利用したもの」になりますが、それ以外の 2 つも順に説明していくことにします。

*1:所謂「ウチに来ない？」問題は解答提出していない or 解いていないのですがそれ以外の結城氏の問題はすべて解答しています

続きを読む

日付型のユニットテスト（『CodeIQの問題・パズルを考えよう！』提案その4）

CodeIQ TDD ユニットテスト

『CodeIQの問題・パズルを考えよう！（by CodeIQ×はてな）』に #{"また"*3} 応募してみます。

今回は、提案と言うより相談です。TDD ネタです。

日付型のテスト…

ユニットテストで…

  • 実行環境のシステム日時に依存して結果が変わるメソッドをテストするには、どうすれば良いのでしょうか？
  • 実行環境のロケール（正確にはローカルタイムゾーン）に依存して結果が変わるメソッドをテストするには、どうすれば良いのでしょうか？
続きを読む

センサーデータ解析（『CodeIQの問題・パズルを考えよう！』提案その3）

CodeIQ 解析 機械学習

『CodeIQの問題・パズルを考えよう！（by CodeIQ×はてな）』にまたまた応募してみます。

前 2 回は「ほぼ完全な問題」（そのまま出題できそうな問題）の投稿でしたが、今回は（お題本来の意図に沿った？）「問題のアイデア」応募。

モーションセンサー

iPhone や Android 搭載スマホには各種センサーが搭載されていますよね。
傾きを検知するジャイロセンサー（ジャイロスコープ）、移動・落下・重力を検知する加速度センサー、近接センサーなんてのもありますね。
特に「加速度センサー」や「ジャイロスコープ」は、動きを検知する所謂「モーションセンサー」の部類に入り、スマホアプリでよく利用されると思います。
「モーションセンサーを利用して、スマホの画面上で傾きに応じてボールが転がるアプリを作りましょう」
とかってのはアプリ開発ネタとして Web マガジンの記事とかセミナーとか勉強会とかでよく出るお題だと思います。
それを CodeIQ で出題するのも、それはそれでアリとして。

提案する問題アイデア

以下の 2 つのアイデアを提出します。

アイデア (1)
  • まず、スマホで取得したモーションセンサーのデータを用意する。
    • 例えば、加速度センサーのデータを 20ms ごとに取得して数分間、合計数千〜数万行のデータ。
    • データ形式は、CSV とか TDV とか一般的なもの。どの列がどのデータかの説明はもちろん必要。
      例えば加速度センサーなら、「タイムスタンプ(ms), x方向(G または m/s^2), y方向(G または m/s^2), z方向(G または m/s^2)」
  • 問題は以下のような感じ：

このセンサーデータを解析して、この人がどういう行動をしていたのかを推測してください！

  • 実際に何らかの、できる限り単純な行動（歩く、走る、階段の上り下り、等）をしたときのデータを用意すること。
  • ヒントは最小限に（車や電車などの移動物には乗っていません、とか）。
  • データを後出しで追加するのもありかも（最初は加速度センサーだけ、そこに後でジャイロスコープのデータや、GPS データを追加するとか）。
アイデア (2)
  • まず、スマホで取得したモーションセンサーのデータを数種類用意する。
    • データの形式等は「アイデア (1)」と同様。
    • 違いは、数種類用意して「このデータは普通に歩いたときのデータ、これは走ったときのデータ、これはエレベータに乗ったときのデータ…」等の説明を付ける
  • それを受けて、もう 1 種類別のセンサーデータ（形式は同じ）を出して以下のような出題：

ではこのデータは、この人がどういう行動をしたときのデータでしょう？推測してください！

続きを読む

平方三角数（『CodeIQの問題・パズルを考えよう！』提案その2）

整数 CodeIQ

『CodeIQの問題・パズルを考えよう！（by CodeIQ×はてな）』にまた応募してみます。
今回はコードゴルフ問題案。

提案する問題

【コードゴルフ】平方三角数


■平方三角数とは？
三角数とは、n×(n+1)/2 で表すことの出来る整数（>0）のこと。
1 から n までの整数の総和（\sum_{k=1}^n k）のことですね。
下図のように、綺麗な三角形の形に並べることが出来るので「三角数」と呼ばれます。

　　　　　　　　　　　　　　　　　　　●
　　　　　　　　　　　　　●　　　　●●
　　　　　　　　●　　　●●　　　●●●
　　　　●　　●●　　●●●　　●●●●
　●　●●　●●●　●●●●　●●●●● …
　 1　　 3　　　 6　　　　10　　　　　15 …

平方数（別名：四角数）は、n2 で表すことの出来る整数（>0）のこと。
三角数と同様、綺麗な四角形（正方形）の形に並べることが出来ます。

　　　　　　　　　　　　　　　●●●●●
　　　　　　　　　　●●●●　●●●●●
　　　　　　●●●　●●●●　●●●●●
　　　●●　●●●　●●●●　●●●●●
　●　●●　●●●　●●●●　●●●●● …
　 1　　 4　　　 9　　　　16　　　　　25 …

そして平方三角数とは、平方数でありかつ三角数でもある数のことです。
一番小さい平方三角数は 1 、2 番目は 36（= 8×(8+1)/2 = 62）、3 番目は 1225、… となります。


■問題
標準入力から整数 N（>0）を与えて、N 番目の平方三角数を標準出力に出力するプログラムを書いてください。


■注意事項
　・N の最大値は 99 としておきます。1 から 99 までの整数を与えて正しい平方三角数が出力されれば OK です。
　・言語は Ruby 2.0.0 とします（※1）。


■解答方法
完成したコードをテキストファイル（.txt）に変換し、ファイルアップロードにより提出してください。
複数回ご提出いただいた場合は、正しく出力されるコードの中で、コードサイズが最小のものを記録とします。

この問題の問題点・要考察点

Ruby 2.0.0（※1） ？

コードゴルフ問題なので言語を指定すべきですが、Ruby2.0 としたのは、私が一番得意でこの問題も解きやすそうだから。
なのでこれは別にこの言語・バージョンにこだわる必要は全くないですね。
むしろ あっという間に 64bit の壁を超えることを承知の上で 多倍長整数型を標準で持たない言語を指定する、というのもありかも。

平方三角数？

少しだけネタばらししてしまうと、Wikipedia（日本語版）で wikipedia:平方三角数 を調べれば、一般項を求める式も漸化式も載っています。
だからこの問題、そんなに難しくないんですよね。
フィボナッチ数列を列挙する有名なコードゴルフ問題に触れたことがあれば、あっという間に《上級の壁》は突破できると思います。

ということで、そもそも『平方三角数』ではなく、Wikipedia には載っていないような（でも法則性は数学的に掴みやすそうな）別の数列で問題を考えた方が良いかも。

平成変換チェッカースクリプト組んでみた

整数 平成変換

一昨日の続き。

平成変換チェック

平成変換の結果をチェックするスクリプトを Ruby で書いてみました。
スクリプト本体は gist に上げてあります。最後に埋め込みます。

使い方

prompt$ ./heisei_henkan_check.rb [year] < textfile

または

prompt$ ./heisei_henkan_check.rb [year] textfile

  • 平成変換の結果を表す 1 行のテキストファイルを、標準入力（リダイレクト）または引数で指定してください。
    正しい変換になっているかチェックします。
  • 引数 [year]（整数 ＞ 0）を指定すると、指定した年の西暦年から平成年への平成変換としてチェックします。年は西暦でも平成年でもOK。
    省略可能、省略すると年のチェックを行いません（西暦年から対応する平成年への平成変換でなくてもチェックエラーに成りません）。

例：

prompt$ cat 3to7.txt
[3]->[9]->[8]1->6(4)1->6[21]->(64)41->(841)->[2]9->(49)->7


prompt$ ./heisei_henkan_check.rb < 3to7.txt
OK: 9 step(s).


prompt$ cat 1991.txt
19(9)1->19[31]->[19](9)61->(36)1(36)1->6(16)1->(64)1->(81)->(9)->3


prompt$ ./heisei_henkan_check.rb 1991 1991.txt
OK: 8 step(s).


prompt$ ./heisei_henkan_check.rb 1991 1991.txt
OK: 8 step(s).

チェック内容

以下をチェックします。

  • 文字種チェック。
    数字、「[」「]」「(」「)」「-」「>」以外の文字が含まれていたらエラーとなります。
  • ネストチェック。
    「[ ]」や「( )」のネスト（入れ子）があるとエラーとなります。
    • 例：[9(9)]←×
  • 平方根チェック。
    「( )」で括られた中身が平方数出ない場合エラーとなります。
    • 例：7(18)8←×
  • [0x], [1], (0x), (1) チェック。
    これらの禁止事項に該当する場合もエラーとなります。
  • 書式チェック。
    各ステップが正しい平成変換の書式になっていない（カッコの対応、「>」の単独混入等）場合にエラーとなります。
    特に一番最後の項は数字以外の文字が含まれていたらエラーとなります。
  • ステップチェック。
    前の数と後の数が正しい変換になっていない場合にエラーとなります。
    • 例：[12]->1444←×
  • 指定年チェック。
    引数 year を指定した場合、最初の数が指定した西暦年、最後の数が対応する平成年になっていないとエラーとなります。
    • 例：[13]->(16)9->(49)->7 ← year 引数を指定した場合は×
    • ※ 逆に year 引数を指定しなければ、年の対応とは無関係な変換の途中経過の確認ができます。
  • ステップ数チェック。
    エラーがなければ、ステップ数を結果として出力します。
続きを読む

平成変換（『CodeIQの問題・パズルを考えよう！』提案その1）

整数 パズル CodeIQ 平成変換

『CodeIQの問題・パズルを考えよう！（by CodeIQ×はてな）』に応募してみます。

平成変換

平成変換とは？

平成変換とは、田村三郎著の「数学パズルランド—身近な素材でパズる」（isbn:4061329049、講談社ブルーバックス、絶版）で紹介されている数字パズルです。
著者の田村氏が京都府の上山秀幸氏から平成 3 年の年賀状でもらった問題として、以下のような文章が紹介されています：

　下のような規則で自然数Mから別の自然数Nを生成する操作を《平成変換》と呼ぶことにする。
『自然数Mの連続した各位の数が、自然数Nの連続した各位の数の平方に成るか、または、平方根に成る。』
（例）[5]63→(256)3→(16)[3]→(49)→7 (4 step)
［問題］
　（西暦）1991（年）を（平成）3（年）に《平成変換》せよ！

（Webで紹介するにあたって傍点や傍線を別の表現に置き換えました）

この問題の解答は、田村氏によって同著書内に載っています。と言っても 3→→1991 の逆向きの変換手順が載っているのですが、すぐに分かるように平成変換は可逆変換なので、どちらでも同じことです。一応、1991→→3 に向きを直した解答例を以下に示します。

19(9)1→19[31]→[19](9)61→(36)1(36)1→6(16)1→(64)1→(81)→(9)→3 (8 step)

平成変換できる年、できない年

同著書には、田村氏による「どのような数が 3 に平成変換できるのか、あらゆる自然数は 1 桁の自然数に平成変換されるだろうか」といった数学的考察も加えられています。
その全てを載せるのにここはスペースが限られているので、その結果として分かりやすい以下の事実だけ述べておきます。

  • 西暦年、平成年のいずれかが 5 の倍数の年は、平成変換できない。
    • 例：（西暦）2000（年）は（平成）12（年）に平成変換できない。
  • （西暦）1989（年）は 1（平成元年）に平成変換できない。

つまり、今年（西暦2013年、平成25年）も、平成変換できない、というわけです。ちょっと残念。

提案する問題

これを踏まえて、こんな問題を考えてみました。

【パズル】平成変換


■平成変換とは？
西暦年を平成年に変換する数字パズルです。
以下の規則に従って、整数（＞0）を別の整数（＞0）に変換していきます。
『前の数の連続した各位の数が、次の数の連続した各位の数の平方に成るか、または、平方根に成る。』
（例：（西暦）1991（年）→→（平成）3（年）の場合）

19(9)1->19[31]->[19](9)61->(36)1(36)1->6(16)1->(64)1->(81)->(9)->3

※このように、「平方に成る」変換部分を「[ ]」で括り、「平方根に成る」変換部分を「( )」で括ることにします。前の数と次の数は「->」でつなぎます。「->」の個数がステップ数となります。またこの例のように 1 ステップ内に 2 つ以上の変換が混在してもOKです。


■問題
今年（2013→→25）…は、残念ながら平成変換不可能（ヒント：5 は何乗しても下 1 桁が 5 のまま）なので、来年でいきましょう。
（西暦）2014（年）を（平成）26（年）に《平成変換》してください！
できる限りステップ数の短い解答を高評価とします！


■注意事項
　・「[ ]」や「( )」のネスト（入れ子）は禁止です。
　　例：[9(9)]←×
　・「[」や「(」の直後に「0」が来るのも禁止とします。
　　例：2(01)4←×
　・「[0]」「[1]」「(0)」「(1)」は、変換前後で結果が変わらないのでこれも禁止にしておきます。


■解答方法
answer.txt
サンプル解答用ファイルにならって、1 行目に平成変換の解答を書き、アップロードしてください。

answer.txt：

19(9)1->19[31]->[19](9)61->(36)1(36)1->6(16)1->(64)1->(81)->(9)->3


■注意事項
　・1 行目に、2014 を 26 に変換する平成変換の解答を書いてください。
　　ただし、「[ ]」は括った部分を平方（2 乗）する変換、「( )」は平方根を取る変換を表し、
　　「->」は前の数と次の数の区切りを表します。
　・1 行目に、数字と「[」「]」「(」「)」「-」「>」と改行以外の文字を書いた解答は評価 1（最低点）になります。
　・1 行目は、「2014」に「[」「]」「(」「)」のいずれかを組み合わせた文字列から始まり、必ず「26」で
　　終わるようにしてください。これに従っていないものは評価 1（最低点）になります。
　・変換結果が正しくない場合も評価 1（最低点）になります。
　・以下の禁止事項に該当するものも評価 1（最低点）になります。
　　・「[ ]」や「( )」のネスト（入れ子）は禁止です。
　　　例：[9(9)]←×
　　・平方数でない数を「()」で平方根変換するのも禁止です。
　　　例：7(18)8←×
　　・「[」や「(」の直後に「0」が来るのも禁止とします。
　　　例：2(01)4←×
　　・「[0]」「[1]」「(0)」「(1)」は、変換前後で結果が変わらないのでこれも禁止にしておきます。
　・採点対象は answer.txt の 1 行目だけです。2 行目以降には自由にお書きください。
　　例えば、自分が解答に至るまでに考えたことや作ったプログラム（言語不問）などを書いてくださってもかまいません。
　　もちろん、2 行目以降には何も書かなくても構いません。

こんなんでどうでしょう？

因みに私も、解答例は 1 つ見付けてはいますが、それが最短解かどうかは未確認です。てかきっともう少し短い解があるような気がしてます。


【2013/08/08 12:45 Twitterでの指摘その他を反映して微修正】

【2013/08/09 23:17 平成変換チェックスクリプトを組んでみました。今日のブログ記事参照】

CodeIQ のアルゴリズム問題「チョコの量を減らせ！」by @hyuki に解答しました

素数 整数 アルゴリズム CodeIQ

CodeIQ のアルゴリズム問題（出題者：結城 浩 氏 @）に先日挑戦してきました。

挑戦者求む！【アルゴリズム】チョコの量を減らせ！ by The Essence of Programming 結城 浩│CodeIQ

昨日締切だったので、もう大丈夫ですよね？
私が解答に使ったプログラムを公開します。

解答（言語：Ruby）

Point

Point は言うまでもなく、78桁という文字通りの天文学的数字*1の素因数分解。
Ruby 標準の prime ライブラリの素因数分解に頼ってちゃ、たぶん一生かかっても終わりません。

私の解答は、見て分かるとおり、素因数分解を独自実装しています。
実装には、2つの乱択アルゴリズムを組み合わせて使用。

ま、独自実装と言っても Wikipedia に載っているアルゴリズムをほぼそのまま流用しただけなんですけどね。ミラー-ラビン法（以下「MR法」と略記）に関しては同じ Ruby なんでまるぱくりなのがばればれですね(^-^;
ただポラード・ロー法（以下「ρ法」と略記）に載っているアルゴリズムは、（素）因数を見つけ出すものだけなので、それを繰り返し利用してきちんと素因数分解を実装しています。
あとρ法の方は、Wikipedia にも記載があるとおり、素数だと検出に失敗するのですが、それがある程度大きな素数だと失敗という結果が出るまでに非常に時間がかかります*2。また素因数分解法と記述があるのですが、実際にはこれは「約数」を見付けるアルゴリズムであって、必ずしも「素因数」が検出されるわけではないんですよね*3。そちらに関しては Wikipedia には記載がないですけど。
だから、MR法を組み合わせたわけです。まずMR法で素数じゃないか判定する、素数じゃないと出たらρ法で約数を見つける、見付かった約数を再帰呼出で素因数分解する、また元の数を見付けた約数で割った数も再帰呼出で素因数分解する。基本的な流れはそんな感じです。

ということで、

404 Blog Not Found:Math - おまいら素因数分解どうしてますか?

みなさんは素因数分解の必要にせまられたとき、どうしてますか?

ないものは自分で作る！
これ基本！

*1:「全宇宙の元素の0.0028倍」だそうです。 http://blog.livedoor.jp/dankogai/archives/51854062.html 参照

*2:日本語版の Wikpedia には、ループを高速検出する改良アルゴリズムも載っていましたが、それよりもMR法での素数判定を組み合わせた方がお手軽だったのでそちらは利用していません。

*3:もっとも充分大きな数に対しては高い確率で素数の約数（＝素因数）が見付かるのですけれど。