悪魔の数字はごく普通の数字に潜んでるってこと
皆さんこんばんは。関タクミゼイアンです。
悪魔の数字は普通の数字に潜んでるんだよね。みんなはそれを理解しているのかって話。
僕はそれを確かめるためのツールを作っちゃったんだよね。 もうパンドラの箱は開いちゃってるんだよね。
ツールの概要
このツールは、数字を入力することで、その数字が悪魔の数字に変換できるかどうかをを知ることができるんだよね。 悪魔の数字に変換する処理は、以下の二つなんだよね。
1桁ずつ数値を分解し、すべて加算する。
1桁ずつ数値を分解し、すべて乗算する。
この2つの処理を繰り返して、悪魔の数字にするってこと。 図にすると、以下のような感じだよね。こんな感じで、悪魔の数字にできる処理を探索していくんだよね。
ツールの見た目
このツールは、ブラウザ上で動かすことができるんだよね。見た目は、以下の画像の通りなんだよね。
textboxに数字を入力し、変換ボタンを押すか、Enterキーを押すことで、変換が始まるんだよね。
試しに、123を入力してみるね。結果は、以下の画像の通りなんだよね。123というごく普通の数字も悪魔の数字の6になり得るってこと。
次は、12345676543を入力してみるね。こんな複雑な数字も悪魔の数字になり得るんだよね。
こんな感じで、このツールを使えばいつも使っている数字が悪魔の数字になり得るかどうかわかるってこと。
ソースコード
じゃあ次は、ソースコードを見ていくね。このツールは、JavaScriptで作ったんだよね。ライブラリとしてjQueryを使ったんだよね。 CSSはかけないから、Bootstrapを使ったんだよね。htmlは大したことないから、省略するね。
main的な
以下のコードは、main的なやつだよね。変換ボタンをクリックすることでクリックイベントが発火するんだよね。 textboxがフォーカスされているときに、Enterキーを押すことでも、イベントが発火するようにしているよ。
ボタンが押されると、まずは、textboxの値を取得して、数値かどうかを確認するんだよね。 数値じゃなければ、警告を表示するってこと。数値であれば、悪魔の数字への変換が始まるんだよね。
//==================================================================== // window.load //==================================================================== $(function() { //---------------------------------------------------------------- // textboxでEnterキーを押すことで、クリックイベント発火 //---------------------------------------------------------------- $('#number').on('keydown', function(e) { if (e.which == 13) { $('#button').trigger('click'); } }); //---------------------------------------------------------------- // 変換ボタンを押すことで、悪魔の数字変換開始 //---------------------------------------------------------------- $("#button").click( function () { result_text = []; akuma_view_init(); // 結果表示要素を初期化 number = $("#number").val(); // textboxの値を取得 if(isNaN(number)){ // 値が数値がどうか not_number(); // 数値でないなら警告を表示 return ; } if (number < 0) { // 数値が負数かどうか var chart_data = akuma_number_frequency(number*-1); // 0からnumberまでの悪魔の数字の頻度を求める chart_view(chart_data[0], chart_data[1], chart_data[2]); // 円グラフとして表示 } else { var viewcode = akuma_number(number, result_text); // 悪魔の数字に変換 view_check_img(viewcode, result_text); // 結果を表示 } }); });
悪魔の数字に変換するakuma_number()
次は、悪魔の数字に変換するfunctionのakuma_numberを見ていくね。まず初めに、悪魔の数字かどうかチェックするんだよね。 これにより、入力された数値が悪魔の数字ならすぐに結果を表示できるってこと。 悪魔の数字じゃなければ、変換処理が始まるんだよね。 すべて加算する処理1を最初に行って、それでも変換できなければ処理2を行うってこと。
//-------------------------------------------------------------------- // 入力された数字をなんとか悪魔の数字にする //-------------------------------------------------------------------- function akuma_number(number, result_text) { var check = check_akumanumber(number, result_text); // 悪魔の数字かどうかチェック if ( check != 0 ) {return check;} var result = add_1(number, result_text,0); // 処理1 すべて加算 if ( result != 0 ) {return result;} var result = mult_1(number, result_text,0); // 処理2 すべて乗算 if ( result != 0 ) {return result;} return 0; }
処理1のadd_1()と処理2のmult_1()
じゃあ、処理1のadd_1と処理2のmult_1を個別にみていくね。 このadd_1とmult_1は相互再帰を行ってるんだよね。 計算して、悪魔の数字なら終了、それ以外なら、再帰を使ってさらに探索するんだよね。 add_1とmult_1の違いは、計算が加算か、乗算かだけなんだよね。 すごい冗長のにおいがするけど気にしちゃだめなんだよね。
//-------------------------------------------------------------------- // 数字を1桁ずつ分解し、すべて足す (mult_1と相互再帰) //-------------------------------------------------------------------- function add_1(number, result_text,c) { var num = []; if (parseInt(number/10) == 0 && (number != 6 || number != 9)) {return 0;} // 1桁になって悪魔の数字じゃなければ失敗 num = numarray_split(number); // 数値を1桁ずつ分解 sum = num.reduce((s, n) => s + n, 0); // すべて加算 result_text[c] = array_value_text(num, sum,"+"); // 計算過程の文字列を作成 var check = check_akumanumber(sum, result_text); // 悪魔の数字かどうかチェック if ( check != 0 ) {return check;} // 悪魔の数字なら終了 var result = add_1(sum, result_text,c+1); // さらに、処理1を実行(再帰) if ( result != 0 ) {return result;} else {result_text.splice(c, 1);} var result = mult_1(sum, result_text,c+1); // 処理2を実行(相互再帰) if ( result != 0 ) {return result;} else {result_text.splice(c, 1);} return 0; }
//-------------------------------------------------------------------- // 数字を1桁ずつ分解し、すべてかける (add_1と相互再帰) //-------------------------------------------------------------------- function mult_1(number, result_text,c) { var num = []; if (parseInt(number/10) == 0 && (number != 6 || number != 9)) {return 0;} // 1桁になって悪魔の数字じゃなければ失敗 num = numarray_split(number); // 数値を1桁ずつ分解 sum = num.reduce((s, n) => s * n, 1); // すべて乗算 result_text[c] = array_value_text(num, sum,"×"); // 計算過程の文字列を作成 var check = check_akumanumber(sum, result_text); // 悪魔の数字かどうかチェック if ( check != 0 ) {return check;} // 悪魔の数字なら終了 var result = add_1(sum, result_text,c+1); // 処理1を実行(相互再帰) if ( result != 0 ) {return result;} else {result_text.splice(c, 1);} var result = mult_1(sum, result_text,c+1); // 処理2を実行(再帰) if ( result != 0 ) {return result;} else {result_text.splice(c, 1);} return 0; }
悪魔の数字かどうかチェックするcheck_akumanumber()
最後に、悪魔の数字かどうかチェックするfunctionを見ていくね。 悪魔の数字かどうか判定する前に、18を666、27を999に変換、9を6、999を666に変換しているよ。 18は6+6+6、27は9+9+9だから悪魔の数字と同じ扱いなんだよね。9や999は反転させることで、6や666になるから、これも悪魔の数字になり得るってこと。 悪魔の数字6、666、それ以外の3パターンで、返却値を変えているんだよね。この返却値によってどの画像を表示するのか決定するってこと。
//-------------------------------------------------------------------- // 悪魔の数字になっているかチェック //-------------------------------------------------------------------- function check_akumanumber(number, result_text) { number = check_extra_akumanumber(number, result_text); // 18を666、27を999に変換 number = check_reverse_akumanumber(number,result_text); // 9を6、999を666に変換 if (number == 6) { // 悪魔の数字かどうか return 1; } else if (number == 666) { return 2; } else { return 0; } }
それ以外のfunction
これ以外の、functionはほとんど結果を表示するためのものなんだよね。 htmlに要素を追加しているだけだから省略するってこと。
隠された機能
実は、このツールには隠された機能があるんだよね。 textboxに負数を入れることでその機能を使えるんだよね。 その機能とは、0から任意の数値(入力した負数の絶対値)の範囲でどれだけの数値が悪魔の数字になれるかを円グラフで表示する機能なんだよね。 試しに、-10000と入力してみるね。この場合だと、0から10000の範囲で、円グラフを表示するんだよね、小さいからちょっと見にくいけど、半分以上の数値が悪魔の数字になってるんだよね。 もうこれ完全に来ちゃってるよね。これはもうすごいことだよね。ヤバタクスゼイアンだよね。パンドラの箱は開いちゃったってこと。
おわりに
数字に隠された真実、私は点を置いただけ。それをつなげるのは皆さんですからね。信じるか信じないかはあなた次第です。
C言語で競プロは苦行だった話
こんちか、たくみんです。 今日は、2018年09月08日に行われたAtCoder Beginner Contest 109に挑戦してみました。 時間が取れなかったので、競技時間外に行いました。 A問題とB問題は解くことができましたが、C問題とD問題は解けませんでした。 C言語で解いたのですが、かなり苦行だったので、WriteUpを兼ねてお話しします。
AtCoder Beginner Contest 109 - AtCoder
以下が結果となります。
A問題 ABC333
問題文 1以上3以下の整数A,Bが与えられます。 A×B×Cが奇数となるような1以上3以下の整数が存在するか判定してください。
制約 入力はすべて整数である 1≦A, B≦3
入力
A B
出力
存在するならYes、存在しないならNo
解法
では、解いていきましょう。問題文ではごちゃごちゃ言っていますが、ようするにAとBを入力して、A×B×C=奇数になるようなCが存在するかどうかを判定しろということです。
掛け算の性質として、偶数×偶数の答えは必ず偶数、偶数×奇数の答えは、偶数、奇数×奇数の答えは奇数となります。つまり、2つの値のうち、片方が偶数だと、絶対に奇数にはならないということです。
ではここで、A×B×CのA×BをDとおき、D×Cとします。
掛け算の性質から、この式の答えが奇数になるかどうかは、Dが偶数か奇数かどうかで判定することができます。
このプログラムをCで書くと以下のようになります。 A×Bの答えが偶数か奇数かによって出力をわけているだけですね。このくらいならCでも問題なく書けます。
#include<stdio.h> int main(void) { int a,b; scanf("%d %d", &a, &b); if (((a*b) % 2) == 0 ) { printf("No"); } else { printf("Yes"); } return 0; }
B問題 Shiritori
問題文
高橋くんは今日も1人でしりとりの練習をしています。 しりとりとは以下のルールで遊ばれるゲームです。
はじめ、好きな単語を発言する
以降、次の条件を満たす単語を発言することを繰り返す
その単語はまだ発言していない単語である
その単語の先頭の文字は直前に発言した単語の末尾の文字と一致する
高橋くんは、10秒間にできるだけ多くの単語を発言する練習をしています。 高橋くんが発言した単語の個数 Nと i番目に発言した単語 Wiが与えられるので、どの発言もしりとりのルールを守っていたかを判定してください。
制約 Nは2≦N≦100を満たす整数である Wiは英小文字からなる長さ1以上10≦の文字列である
入力
N W1 W2 : Wn
出力
しりとりのルールを守っているならYes、守っていないならNo
解法 では、解いていきましょう。これは、文字列検索の問題ですね。チェックしなければならないのは、同じ文字列が出現していないかという点と、文字列の先頭が、一つ前の文字列の末尾と同じかどうかという点です。 前者はCでも簡単に書けます。チェックする関数は以下のようになります。 愚直に、2重for文を用いました。入力する文字列は2次元配列のchar型変数wordsとして定義しています。stecmp関数ですべての組み合わせをチェックし、同じ文字列があれば0(No)を返しています。
int check_shiritori1(int n) { int k1,k2; for (k1 = 0; k1 < n; k1++) { for (k2 = 0; k2 < n; k2++) { if (k1 == k2) { continue; } if (strcmp(words[k1], words[k2]) == 0) { return 0; } } } return 1; }
では、後者の点をチェックしてみます。このチェックに必要なのは、文字列の先頭と末尾です。先頭は[0]で表せますが、末尾をCで表そうとするとかなりめんどくさいです。(RubyとかPythonだと[-1]でいけるらしい。いいなぁ) 悩んだ結果、strlenで文字列の長さを取得し、-1することで末尾を表しました。 以下のような関数になりました。いまみてもif文の条件がひどいですね… for文を回し、文字列の先頭と一つ前の文字列の末尾が違う文字の場合0(No)を返しています。
int check_shiritori2(int n) { int k; for (k = 1; k < n; k++) { if (words[k][0] != words[k-1][strlen(words[k-1])-1]) { return 0; } } return 1; }
最後にmain文です。set_words関数は、入力した文字列を変数wordsに格納する関数です。
check_shiritori1関数と、check_shiritori2関数の両方が1を返したときにYesと表示します。
一応、正解することはできましたが、Cで競プロは厳しいと思った問題でした。
#include<stdio.h> #include<string.h> #define MAX_N 100 #define MAX_L 10 void set_words(int n); int check_shiritori1(int n); int check_shiritori2(int n); char words[MAX_N][MAX_L+1]; int main(void) { int n; int result1, result2; scanf("%d", &n); set_words(n); result1 = check_shiritori1(n); result2 = check_shiritori2(n); if ( (result1 * result2) == 0) { printf("No"); } else { printf("Yes"); } return 0; }
おわりに
Cで競プロをしようとする場合、文字列検索や、ソートなどを自分で実装しないといけないため、かなり厳しいと感じました。次は、Rubyとかでやってみようかと思います。ではでは。
P.S.
ブログって日本語力が試される
Pythonのmatplotlibを使ってみた
こんちか、たくみんです。 今日は、Pythonのグラフ描画ライブラリであるmatplotlibを使ってみます。 Wikipediaによると、numpyと呼ばれるライブラリのためのグラフ描画ライブラリらしいです。 このmatplotlibを使うことで、巡回セールスマン問題の可視化ができそうですね。
ウィンドウを出してみる
初めに、グラフを描画するためのウィンドウを表示してみましょう。実は、初めてのPythonだったりします。 なので、Python2とかPython3とかまだよくわかってませんが、今回はPython3を使います。 test.pyを作成し、以下のようなコードを記述します。
import numpy as np import matplotlib.pyplot as plt def plot_start(): plt.figure() # ウィンドウを作成 plt.show() # ウィンドウを描画 if __name__ == '__main__': print("plot start") plot_start()
そして、test.pyを実行すると次のような何もないウィンドウが表示されます。 たった２行の処理を書くだけでウィンドウを表示することができました。
グラフを表示してみる
では、次にグラフを表示してみましょう。 test.pyを以下のように書き換えます。グラフに使用する値をnumpyライブラリを用いて設定し、反映させました。
import numpy as np import matplotlib.pyplot as plt def plot_start(): plt.figure() # ウィンドウを作成 #---- グラフに使用する値を設定 x = np.asarray([1,2,3]) y = np.asarray([1,2,3]) plt.plot(x,y) # 値をグラフに反映 plt.show() # ウィンドウを描画 if __name__ == '__main__': print("plot start") plot_start()
実行すると以下にような、グラフが表示されました。なんとかグラフを表示するところまでたどり着くことができました。
おわりに
matplotlibはオブジェクト指向を意識してグラフを描画することができ、更に細かい設定もできるようです。 まだまだ先は長そうなので、ゆっくり進んでいこうかと思います。ではでは。
P.S.
こんなしょぼい内容でいいのかと思ってみたり。
巡回セールスマン問題に興味を持つ
継続してブログを書くといいつつ、２回めの記事が２ヶ月後となってしまいました。論文とかもあったので許してください。
巡回セールスマン問題
巡回セールスマン問題とは、複数の点とその距離が与えられたとき、すべての点を通りつつ、最初の点に戻ってくる総移動距離を最小にする最適化問題のことです。(巡回セールスマン問題 - Wikipedia) ようするに、以下の図のような６点が与えられた時に、移動距離が最小となるような経路を探せという問題ですね。この例だとこの経路が一番移動距離が短いようです。
この問題は、点の数が多くなるほど、総当りで解くのが困難になります。なぜならば、nの点に対する経路の組み合わせはn!通りとなるからです。以下の表にnとn!の関係を表してみたところ、点の数が１５の時点で１兆パターンを超えてしまっています。 このことを考えると５０個や１００個の点の経路を総当りで解くのは不可能ですね。そのせいかはわからないですが、この巡回セールスマン問題はNP困難とかいうとてもむずかしい問題のひとつとなっています。
| n | n! |
|---|---|
| 1 | 1 |
| 5 | 120 |
| 10 | 3628800 |
| 15 | 1307674368000 |
| 20 | 2432902008176640000 |
巡回セールスマン問題に興味を持ったきっかけ
私が、巡回セールスマン問題に興味を持ったきっかけは、「理系が恋をしたので証明してみた」という漫画を読んだからです。漫画では、遊園地のアトラクションを効率よく回るルートを調べる方法として、巡回セールスマン問題が登場していました。
巡回セールスマン問題を応用したアプリの構想
これを見た時に、自分の周りでも巡回セールスマン問題を応用できるのではないかと考えたところ、あるひとつの解を思いつきました。 そう、聖地巡りです。 というわけで、アニメ聖地の緯度経度情報から、最適な聖地巡りのルートを算出するアプリケーションを作っていきたいなと思います。
おわりに
まだ概要しかきまっていないため、いつになるかはわかりませんが、開発が進めば記事として紹介していきます。 おそらく、まだまだ進まないので、当分の記事は、今まで作ってきたアプリの紹介や、いま興味を持っているものなどになりそうです。 ではでは
はてなブログデビュー
初めてのブログに挑戦
大学4年生にして、ブログを書くことにしました。
私自身、忘れやすい性格で、自分が実装したコードが理解できないということよくがあります。
なので、自分がやったことを文章化し、後々ドキュメントとして役立てたいという思いでブログを書くことにしました。
しかし、ここで一つ問題があります。
それは、開発の記事しか書かないという縛りを行った場合、記事数が少なくなってしまうということです。開発すればいいじゃんというツッコミは受け付けていませんよ。なので、開発に関すること以外の記事、例えば趣味の話なども記事にしていきたいと思います。
ラブライブと私
アイコンを見てもわかる通り、ラブライブにはまっています。開発しているアプリケーションもラブライブに関係するものが多く、これからもラブライブ関連のアプリを作っていきたいと思っています。
抱負
とりあえず、継続してブログを書くということを心がけていきたいと思います。また、自分の開発したアプリや、学んだ技術もなるべく記事として残し、アウトプットしていきます。
PS
ラブライブエンジニアとして、有名になりたいなぁ
