picoCTF2018 WriteUp 100点以下編

こんちか! たくみんです。2018.09.28(金)から2018.10.12(金)まで行われたpicoCTFに挑戦してみました。競技に参加したのが10.08(月)から、10.09(火)だったので、実質５日間で競技に取り組みました。 最終結果が以下のようになります。この内、General Skillsの400点問題１問と、Web Exploitationの300点問題1問、400点問題1問は大会終了後に解いているので実際は6735点が最終結果となります。

ぼくもCTFのWriteUpをやってみたかったので、記事にしてみます。picoCTFは問題の数が多かったので、複数回にわけて行いたいと思います。 今回は、100点以下の問題全14問のWriteUpを行います。

Forensics Warmup 1 - Points: 50

問題文

Can you unzip this file for me and retreive the flag?

ヒント

Make sure to submit the flag as picoCTF{XXXXX}

解答

ファイルがDLできるようになっているので、DLしてみます。するとflag.zipというファイルがDLできるので、素直にunzipコマンドを実行してみましょう。

$ unzip flag.zip

すると、flag.jpgという画像ファイルが出現します。開いてみるとフラグ獲得!

flag

Forensics Warmup 2 - Points: 50

問題文

Hmm for some reason I can't open this PNG? Any ideas?

ヒント

How do operating systems know what kind of file it is? (It's not just the ending! Make sure to submit the flag as picoCTF{XXXXX}

解答

pngファイルが何故か開けないようです。Warmupなので、そこまで難しくはないはず。というわけでとりあえずfileコマンドを実行してみましょう。

$ file flag.png
flag.png: JPEG image data, JFIF standard 1.01, resolution (DPI), density 75x75, segment length 16, baseline, precision 8, 909x190, frames 3

いや、めっちゃJPEGやん!!PNGちゃうやん!!
というわけで、flag.pngをflag.jpgになおしてフラグ獲得!!

flag

General Warmup 1 - Points: 50

問題文

If I told you your grade was 0x41 in hexadecimal, what would it be in ASCII?

ヒント

Submit your answer in our competition's flag format. For example, if you answer was 'hello', you would submit 'picoCTF{hello}' as the flag.

解答

ASCIIコード上で、0x41は何だろう?という問題です。こんな時は、ASCll表の出番ですね。

はい、ASCll表をみると0x41はAになっていますね。なので、picoCTF{A}がフラグになります。

flag

picoCTF{A}

General Warmup 2 - Points: 50

問題文

Can you convert the number 27 (base 10) to binary (base 2)?

ヒント

Submit your answer in our competition's flag format. For example, if you answer was '11111', you would submit 'picoCTF{11111}' as the flag.

解答

10進数の27は2進数だとどうなりますか?という問題です。27は10進数に直すと61ですね。なので、picoCTF{61}がフラグになります。

flag

picoCTF{61}

General Warmup 3 - Points: 50

問題文

What is 0x3D (base 16) in decimal (base 10).

ヒント

Submit your answer in our competition's flag format. For example, if you answer was '22', you would submit 'picoCTF{22}' as the flag.

解答

16進数の3Dは10進数だとどうなりますか?という問題です。16進数の3Dは10進数に直すと61ですね。なので、picoCTF{61}がフラグになります。

flag

picoCTF{61}

Resources - Points: 50

問題文

We put together a bunch of resources to help you out on our website! If you go over there, you might even find a flag! https://picoctf.com/resources (link)

ヒント

なし

解答

リンク先のページからフラグを見つけろという問題です。おそらくHTMLのなかにあるのではないかと推測しました。 HTML内で、picoCTFと検索するとフラグ発見!!

flag

picoCTF{xiexie_ni_lai_zheli}

Reversing Warmup 1 - Points: 50

問題文

Throughout your journey you will have to run many programs. Can you navigate to /problems/reversing-warmup-1_1_b416a2d0694c871d8728d8268d84ac5c on the shell server and run this program to retreive the flag?

ヒント

If you are searching online, it might be worth finding how to exeucte a program in command line.

解答

ファイルをDLすると、runというファイルがDLできます。拡張子が書かれていないのでなんのファイルかわかりません。こういう時は、fileコマンドですね。fileコマンドを実行してみましょう。

$ file run
run: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=3f4cbb89ad8989bad12dfa913e40072f3d21c96d, not stripped

実行結果から、ELFファイルだとわかりました。 実行ファイルから文字列を見つけるときは、とりあえずstringsコマンドを叩いてみましょう。

$ strings run | grep pico
picoCTF{welc0m3_t0_r3VeRs1nG}

ビンゴ!!!

flag

picoCTF{welc0m3_t0_r3VeRs1nG}

Reversing Warmup 2 - Points: 50

問題文

Can you decode the following string dGg0dF93NHNfczFtcEwz from base64 format to ASCII?

ヒント

Submit your answer in our competition's flag format. For example, if you answer was 'hello', you would submit 'picoCTF{hello}' as the flag.

解答

base64のdGg0dF93NHNfczFtcEwzという文字列をデコードしろという問題ですね。ググってみると、ブラウザ上でデコードしてくれるサイトがあるようなので、ぶち込みます。

www.convertstring.com すると、dGg0dF93NHNfczFtcEwz　→　th4t_w4s_s1mpL3
となるので、picoCTF{th4t_w4s_s1mpL3}がフラグですね。

flag

picoCTF{th4t_w4s_s1mpL3}

Crypto Warmup 1 - Points: 75

問題文

Crpyto can often be done by hand, here's a message you got from a friend, llkjmlmpadkkc with the key of thisisalilkey. Can you use this table to solve it?.

ヒント

Submit your answer in our competition's flag format. For example, if you answer was 'hello', you would submit 'picoCTF{HELLO}' as the flag. Please use all caps for the message.

解答

table.txtというファイルがDLできます。中身は以下のとおりです。

    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 
   +----------------------------------------------------
A | A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
B | B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
C | C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D | D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E | E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
F | F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
G | G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
H | H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
I | I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
J | J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
K | K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
L | L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
M | M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
N | N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
O | O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
P | P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
Q | Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
R | R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
S | S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
T | T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
U | U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
V | V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
W | W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
X | X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
Y | Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Z | Z A B C D E F G H I J K L M N O P Q R S T U V W X Y

はい、これはシーザー暗号の上位互換である、ヴィジュネル暗号ですね。鍵の文字によって、ずらす回数が変化するやつです。 Rubyでヴィジュネル暗号を復号するスクリプトを作成しました。(ネットに復号するサイトがあることに後で気づきました…)

strs = "llkjmlmpadkkc"
keys = "thisisalilkey"


strs.each_char.with_index do |str,index| 

  str_ord = str.ord - "a".ord
  key_ord = keys[index].ord - "a".ord
  
  print((((((str_ord + 26) - key_ord) % 26) + "a".ord).chr).upcase)
  
  
end

実行した結果がこちらになります。

$ ruby answer.rb 
SECRETMESSAGE

SECRETMESSAGEなんて完全にフラグっぽいですね。よってフラグはpicoCTF{SECRETMESSAGE}になります。

これは余談ですが、渡された文を平文と鍵の2つだと勘違いしていて、50分位まちがったスクリプトを作り続けていました…

flag

picoCTF{SECRETMESSAGE}

Crypto Warmup 2 - Points: 75

問題文

Cryptography doesn't have to be complicated, have you ever heard of something called rot13? cvpbPGS{guvf_vf_pelcgb!}

ヒント

This can be solved online if you don't want to do it by hand!

解答

で、でた~ROT13奴~。はい、シーザー暗号ですね。ROT13は13文字ずつずらせということです。以下のサイトに暗号をぶち込みました。

ango.satoru.net するとcvpbPGS{guvf_vf_pelcgb!}　→　picoCTF{this_is_crypto!}になりました。 シーザー暗号の前に、ヴィジュネル暗号が来るのは何故なんでしょう。

flag

picoCTF{this_is_crypto!}

grep 1 - Points: 75

問題文

Can you find the flag in file? This would be really obnoxious to look through by hand, see if you can find a faster way. You can also find the file in /problems/grep-1_2_ee2b29d2f2b29c65db957609a3543418 on the shell server.

ヒント

grep tutorial

解答

問題名からして、grepを使ってみよー的な問題だと思われます。 ファイルをDLします。また拡張子がないのでfileコマンド実行

$ file file
file: ASCII text, with very long lines

ASCllということはstringsコマンドでフラグが見つかるかもしれません。やってみます。

$ strings file | grep pico
picoCTF{grep_and_you_will_find_42783683}

フラグ獲得!!
ちなみにcatコマンドでも獲得できます。

flag

picoCTF{grep_and_you_will_find_42783683}

net cat - Points: 75

問題文

Using netcat (nc) will be a necessity throughout your adventure. Can you connect to 2018shell3.picoctf.com at port 36356 to get the flag?

ヒント

nc tutorial

解答

これも問題名からして、ncを使ってみよー的な問題だと思われます。 2018shell3.picoctf.comの36356番ポートに接続しろとのこと。

$ nc 2018shell3.picoctf.com 36356
That wasn't so hard was it?
picoCTF{NEtcat_iS_a_NEcESSiTy_9454f3e0}

フラグ獲得!!

flag

picoCTF{NEtcat_iS_a_NEcESSiTy_9454f3e0}

HEEEEEEERE'S Johnny! - Points: 100

問題文

Okay, so we found some important looking files on a linux computer. Maybe they can be used to get a password to the process. Connect with nc 2018shell3.picoctf.com 35225. Files can be found here: passwd shadow.

ヒント

If at first you don't succeed, try, try again. And again. And again. If you're not careful these kind of problems can really "rockyou".

解答

passwdとshadowの2つのファイルをDLできます。 psswdとshadowの内容は以下の通りです。

passwd

root:x:0:0:root:/root:/bin/bash

shadow

root:$6$L0grUkkk$H8JS0BBMMpGj8qqVpdvkOoBumhqhP5l2RYyOb/0aNhhgjtoEN4pJW3LVXIl93qieXao/G14AsjstVjJYxBmaz0:17770:0:99999:7:::

passwdを見ると、rootユーザが存在しており、パスワードは、shadowの方にハッシュ化して保存されているようですね。 ググってみると、ハッシュ化されたパスワードを推測するツールにJohn the Ripperがあるようです。 John the Ripperを用いて、ハッシュ化されたパスワードを推測します。

https://www.openwall.com/john/

$ john --show shadow    
root:superman:17770:0:99999:7:::

1 password hash cracked, 0 left

これにより、rootユーザのパスワードはsupermanだと判明しました。この情報を用いて、フラグを獲得しましょう。

$ nc 2018shell3.picoctf.com 35225
Username: root
Password: superman
picoCTF{J0hn_1$_R1pp3d_99c35524}

フラグもjohnとなっているので、John the Ripperを使うことが想定されているようです。

flag

picoCTF{J0hn_1$_R1pp3d_99c35524}

strings - Points: 100

問題文

Can you find the flag in this file without actually running it? You can also find the file in /problems/strings_4_40d221755b4a0b134c2a7a2e825ef95f on the shell server.

ヒント

stringsコマンドのドキュメントページヘのリンク

解答

これもstringsコマンド使ってみよー問題です。今までの問題ですでに使ってしまっていますが、やってみましょう。 stringsというファイルがDLできます。またまた拡張子がないので、とりあえずfileコマンド実行。

$ file strings 
strings: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 2.6.32, BuildID[sha1]=e5ca61b750713b9161da547bc8ba99efc6e976be, not stripped

はい、ELFファイルですね。stringsコマンドを使う問題なので、stringsコマンドを実行してみます。grepでpicoで絞り込むとおそらくフラグにヒットすると思います。

$ strings strings| grep pico
picoCTF{sTrIngS_sAVeS_Time_d3ffa29c}

やったね。

flag

picoCTF{sTrIngS_sAVeS_Time_d3ffa29c}

おわりに

picoCTFはかなり初心者向けだと感じました。100点以下の問題であれば、linux触りたての人でも解けるのではないでしょうか。 次は、問題数的に、101~199点の問題のWriteUpになると思います。 ではでは。

悪魔の数字判定ツールが完成したってこと。

皆さんこんにちは。関タクミゼイアンです。 もうね、来ちゃったよね。もうやりすぎのカメラがここまで来ちゃってるんだよね。 皆さんはこの記事を覚えているでしょうか?私は入力した数字を悪魔の数字かどうかを判定するツールを作っちゃったんだよね。

takuminv.hatenablog.jp

とうとうこのツールが完成したんだよね。完全にパンドラの箱開けちゃってるよね。以下のリンクで利用できるんだよね。

数字の真実

今回の記事では、変更点や追加した点を取り上げていくんだよね。

1. トップページの追加

前回の記事では、悪魔の数字判定ページしかなかったんだけど、それじゃ味気ないよね。 だから、トップページを作っちゃったんだよね。赤文字の部分が悪魔の数字判定ページへのリンクになってるんだよね。

ちなみに、赤文字にマウスが乗ると次のように炎が表示されるギミックがあるんだよね。 この炎はgif画像だから、すこしホラーチックなんだよね。

このギミックは、mouseoverイベントとmouseoutイベントを利用しているんだよね。 以下がそのコードなんだよね。赤文字のリンクには、link-akumaというidを振っていて、炎にはfireというクラス名を割り振っているんだよね。 link-akuma(赤文字のリンク)にマウスが乗ったときに、fireクラスのdisplayをinline(表示)にして、マウスが離れたときに、displayをnone(非表示)にしているんだよね。簡単なんだよね。

$("#link-akuma").mouseover(function() {
    $(".fire").css("display","inline");
}).mouseout(function() {
    $(".fire").css("display","none");
});

2. フォントの変更

悪魔の数字を扱っているのに、普通のフォントじゃ味気ないんだよね。 だから、ホラーチックなフォントに変更したんだよね。 変更前と変更後を比べてみるね。 フォントを変えるだけでここまで印象が変わっちゃうんだよね。

使用したフォントは怨霊フォントなんだよね。 暗黒工房 日本語フリーホラーフォント怨霊

ひらがな、カタカナ、数字、漢字に対応していて理想的なフォントだったんだよね。 CSSに以下のようなコードを追加することで、font-familyで怨霊フォントをしようできるようになるんだよね。

@font-face {
    font-family: "Onryou";           /* フォント名 */
    src: url("../font/Onryou.ttf");  /* フォントファイルへのパス */
}

3.色の変更

もっとホラーチックにするために、背景色やグラフの色を変更したんだよね。 背景は白から黒に変更したんだよね。この方がホラーチックだってこと。 グラフの色も黄色と紫に変更したんだよね。選択基準は特にないんだよね。直感ってこと。

4. GitHub Pagesの利用

GitHubには、GitHub Pagesという機能があるんだよね。 これは、GitHubが提供している、Webページを公開することができる機能なんだよね。 使い方は以下のサイトを参考にしたんだよね。

https://www.tam-tam.co.jp/tipsnote/html_css/post11245.html

それで、公開してみたんだよね。すると、ページの表示にめちゃくちゃ時間がかかっているんだよね。 だから、Chromeの開発者用ツールを利用して、原因を調べてみたんだよね。それが次の画像になるんだよね。 これを見ると、フォントファイルの読み込みに11秒もかかっているんだよね。原因は13Mとかいう容量の大きさだよね。

4-1. フォントファイルの圧縮

フォントファイルの読み込みを速くするために、ファイルの圧縮を行うんだよね。 これには、サブセット化という手法を用いるんだよね。 フォントファイルの容量が大きい理由は、膨大な文字に対応しているからなんだよね。 つまり、ページで使用しない無駄な文字にも対応しちゃってるってこと。サブセット化というのは、無駄な文字を省くことでファイルを圧縮する手法なんだよね。 サブセット化には、サブセットフォントメーカーというフリーソフトを使用したんだよね。 ダウンロードと使い方は以下のサイトを参照したらいいんだよね。

サブセットフォントメーカー

フォントファイルをサブセット化したファイルに変更して、もう一度GitHubPagesで公開してみたんだよね。すると次のようになったんだよね。 読み込み時間は、0.6秒、ファイルサイズは54kまで減少したんだよね。圧縮のおかげでスムーズに表示されるようになったんだよね。

4-2. gif画像の圧縮

よく見ると、gif画像も874kBとちょっと容量が大きいんだよね。こいつも圧縮しちゃうんだよね。圧縮には以下のサイトを使ったんだよね。 これは、ブラウザ上でgif画像を無料で圧縮できるんだよね。画像の見た目もほとんど変わらないから便利なんだよね。

www.iloveimg.com

gif画像を圧縮して、もう一度公開した結果が以下の通りなんだよね。圧縮した結果、読み込み時間が1.2秒から0.9秒に短縮できているんだよね。 容量も、531kBと40%くらい圧縮できているんだよね。 これで、皆さんも安心、快適に悪魔の数字ツールを使うことができるんだよね。人類の選別はもう始まってるんだよね。

5. おわりに

もう完全にやりすぎのカメラがここまで来ちゃってるんだよね。 数字に、こんなことが隠されてるの。それにじゃあ何故皆さんは気づかなかったのって話。 もしかしたら、世界はもうやばいところまできてるかもしれない。 信じるか信じないかはあなた次第です。

github.com

悪魔の数字はごく普通の数字に潜んでるってこと

皆さんこんばんは。関タクミゼイアンです。

悪魔の数字は普通の数字に潜んでるんだよね。みんなはそれを理解しているのかって話。

僕はそれを確かめるためのツールを作っちゃったんだよね。
もうパンドラの箱は開いちゃってるんだよね。

ツールの概要

このツールは、数字を入力することで、その数字が悪魔の数字に変換できるかどうかをを知ることができるんだよね。 悪魔の数字に変換する処理は、以下の二つなんだよね。

1. 1桁ずつ数値を分解し、すべて加算する。

2. 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

ラブライブエンジニアとして、有名になりたいなぁ