ファイルのハッシュ値をBCHのブロックチェーン上に記録するスクリプト

# 概要

僕は今研究室に配属されているのですが，少し新しいことをしようと思い実験系の研究室に配属しています．その際に，わりと厳しく言われるのが実験ノートです．
実験ノートは研究者の不正防止のためのもので，書き換えが行えないようにボールペンで書き，きちんとページごとに日付と保存したファイルの名前などを書くことが要請されています．
しかし書き換え防止とかハッシュ値とブロックチェーンの出番という感じですし，僕は手書きよりテキストデータのほうを好むので，試しに適当なファイルのハッシュ値をBitcoin Cashのブロックチェーン上に記録するスクリプトを書いてみました(ここ)．

# デモンストレーション

## 仕組み

BitcoinやBitcoin Cashなどはご存知の通り暗号通貨と呼ばれるタイプの新しい通貨で，他の人へお金を送ったり，また逆に受け取ったりすることができます．
そういった送金の際に，送金の理由などを記載することができるようになっており，そこに実験ノートなど改ざんされたら困るファイルのハッシュ値などを記載しておけば，Bitcoin Cashが使われなくなるまではハッシュ値や，ハッシュ値が保存された時間などが残り続けます．
今回は.vimrcのハッシュ値をBitcoin Cashのブロックチェーン上に記録する例を見せます．

## bitcashのインストール

bitcashはBitcoin Cashを扱うためのPythonライブラリです．pipでもインストールできるのですが，pipに登録されているバージョンは少し古く，書き込める文字列が40 byteまでしか出力できません．
なのでGitHubリポジトリからインストールする必要があります．

git clone https://github.com/sporestack/bitcash.git
cd bitcash
sudo python3 setup.py install

## スクリプトのダウンロード

僕の書いたスクリプトをGitHubからcloneします．

git clone https://github.com/TonyMooori/save_file_hash.git

## ウォレットの作成とお金の送信

main.pyは入力された文字列をブロックチェーン上に記録し，そのトランザクションidを表示するプログラムですが，最初の起動の際にウォレットの作成を行います(ウォレットの暗号鍵はprivate.secretというファイルに記録してあります．)．

python3 main.py
>Making and saving new wallet...
>Send some money to bitcoincash:qzuagk4vvp8hmfzrwcgd9fmnuwvce6p6kv704adgav

この表示されたアドレスに持っているBitcoin Cashを送信してください．持ってない人は買うか，あるいはBitcoin.comのアプリを入れると5円分ぐらいもらえるのでもらってみてください．
ブロックチェーンに記録するのに必要な手数料は2018/10現在では0.2円ぐらいですので，5円もあればデモとしては十分でしょう．

## autosave.shの編集

autosave.shという名前のシェルスクリプトにハッシュ値を取得し，ブロックチェーン上に記録するまでのコマンドが書かれています．
sha256sum ~/.vimrcの部分を変えればハッシュ値を保存したいファイルを変えられます．

rm hash.txt
rm tx.txt
sha256sum ~/.vimrc | cut -d " " -f 1 >> hash.txt
cat hash.txt | python3 main.py >> tx.txt
echo "https://explorer.bitcoin.com/bch/tx/$(cat tx.txt))"

## autosave.shの実行

あとはautosave.shを実行するだけです．

>bash ./autosave.sh
https://explorer.bitcoin.com/bch/tx/ed1787e799e5fcb20eaeb891d060ec63e01a117a98f41e0c19d5776e9ee5c046

URLにアクセスすれば保存されたハッシュ値を見ることができます(下図のOP_RETURNを発見しましたの部分)．

定期的に保存したい場合はcrontabとかで設定したら良いと思います．

# 所感

一応今は実験結果などをMarkdownでメモして，週一でそのファイルのハッシュ値を保存するスクリプトを走らせています．
xonshスクリプトが何故かcrontabで動かなかったり，bitcashのバージョンが古いことに気づかなかったりと割と苦戦しましたが形になってよかったです．

アルゴリズムパズル 49-60 僕の解答・感想

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の29-48番目の問題の僕の解答・感想です．

2. 各問題の解答・感想

2.1. 49 宣教師と人食い人種

全幅探索だよなぁっておもって答え見て，状態空間グラフとか解答には書いてあるけど結局のところ禁止操作を除いた全幅探索では？と思ってる．

2.2. 50 最後の球

気づくのに時間がかかった．僕は(黒の球の数)x2+(白の球の数)がどちらの操作でも不変だということに気づいて回答したが，白の球の数のみに注目すれば良いことに答えを見てから気づいた．

2.3. 51 存在しない数字

まぁ100を法とした和が計算できれば行けるが……それはジルにできるのか？と半ば不安ながら答えを見た．できるらしい．
この手の問題は何言ってもヒントになってしまうので問題出題側に厳しいところがある．

2.4. 52 三角形の数え上げ

適当に数字を並べば法則性は見える，なんかややこしいだけな気がしたので証明は特にしなかった

2.5. 53 バネ秤を使った偽造硬貨の検出

にぶたん．\(W(n)=W(\lceil n/2 \rceil)+1\)の解が\(W(n)=\lceil \log_2 n \rceil \)になることはどうやって示されるんだろうか．
そのへんが気になりだしたら普通にアルゴリズム系の本を読んだ本がいい気もする．

2.6. 54 長方形の切断

No.30といたあとなら即答

2.7. 55 走行距離パズル

高校数学でみた気がする．

2.8. 56 新兵の整列

今の所暫定一番で問題文の意図が汲み取れなかった問題．
とりあえず昇順に並べれば良いのはわかるがヒントを見て何を言ってるんだ？となって答えを見て何を言ってるんだ？となった．
ここでいう差は二通りの読み方ができるよね？みたいなのは言葉の定義の話であってそこをどういう言うのは良い問題とは思えない．正直本質的でないところで悩むのは不毛すぎる．
答えを見たあとに問題文を見ると「なんで読み違えたんだろう」となってしまうので，レビューを頼まれたひとが指摘しないといけないのだと思う．
とりあえず僕の意見としては，この問題は「シュヴェイクは上司の命令を勘違いをしているが，どんな勘違いをしているだろうか」と一文入れたりするか，もしくは「～差の絶対値の平均が～の場合と，(ある兵士の身長)-(その兵士の前にいる兵士の身長)の平均が～の場合で解がことなる．どのように配置すればよいか」といういうふうに書き換えたほうが良いと思う．

2.9. 57 フィボナッチのウサギ問題

まぁ数列はすぐ出るでしょう．高校数学．

2.10. 58 ソートして、もう1回ソート

これは面白かった．トランプを実際に引っ張り出してきてあれこれやって「アレ？これひょっとして常に0なの？」と気づいたときは狐につままれたようだった．
証明は考えたがちゃんとまとまってないが納得できる状態まで持っていけた．

2.11. 59 2色の帽子

まぁよかった．少し考えたらわかると思う．
ただ「午後12:05から始めて午後12:55まで5分おきに囚人を整列させる」は12:05を含まないと思って「10回だからムリ！」と答えを見たら違ったので「合計11回整列させる」と書いてほしかった(中途半端な時間だから少し考えたらわかる気がするし若干ア.ス*ペ味がある)．

でも流石にこれは考えすぎかもしれないが，囚人の考え方しだいでうまくいかない場合があるのでは？と思った．というのも，解答では
・「自分の帽子の色がわからない，もしくは自分の帽子の色が白である」→「とどまる」
・「自分の帽子の色が黒である」→「前に出る」
という「黒だったときのみ前に出る」で行動をしていたが，
・「自分の帽子の色が白である」→「とどまる」
・「自分の帽子の色がわからない，もしくは自分の帽子の色が黒である」→「前に出る」
という「白だったときのみとどまる」で行動する可能性も否定出来ないなぁと思った．

2.12. 60 硬貨の三角形から正方形を作る

とりあえず「正方形」って何？となった．
外枠だけで良くて複数の正方形を作らせたいのか，中身が詰まってる1つの正方形を作らせたいのか，中身を詰めるとしたら詰め方はどんなものを許容するのか．
あと「何種類の」とは「向き・場所が異なる正方形」を区別するの話なのか，あるいは「大きさの異なる正方形」を区別する話なのかわからないなぁとなってた．
いちゃもんみたいに聞こえるかもしれないけれど変に深読みしてしまって混乱したので，とりあえず目標となる正方形の図を入れてほしかったのはある．
正直何言ってもヒントになるタイプの問題なので辛いところではあるので致し方なし．

3. 感想とか

問題文がよくわからなくて本質的じゃないところで悩むのが本当に不毛である．
訳者は悪くなくて(むしろ訳注を入れてくれたりして助かっている)，多分これは著者というかレビューしたひとがちゃんとレビューしてくれなかったのがいけないのではと思ってる．

アルゴリズムパズル 29-48 僕の解答・感想

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の29-48番目の問題「の僕の解答・感想です．

2. 各問題の解答・感想

2.1. 29 魔法陣再び

足して15になる組み合わせは(1,5,9), (1,6,8), (2,4,9), (2,5,8), (2,6,7), (3,4,8), (3,5,7), (4,5,6)で，そうすると中央の数字は5以外ありえないことがわかる(中央は縦横斜めで4種類の和が15にならないといけないので)．そこから(1,5,9)をどう配置するかとか理詰めで考えていけば解は出て，回転対称とかやれば8通りある事がわかる．

2.2. 30 棒の切断

まぁなんかわかる．どんだけ頑張ってもn回の切断では2^n個の分割しかできないので100<2^7より最低でも7回だし7回でできるので7回でできる！！！！みたいな．
一般の場合は帰納的に証明できそうという感じだった(n=1明らか，n>1，n>=a_1をみたすもので最大のa_1=2^kとa_2=n-a_1にまず切断するとa_1>a_2より～みたいな)．

2.3. 31 3つの山のトリック

3分探索

2.4. 32 シングル・エリミネーション方式のトーナメント

シングル・エリミネーション方式？僕らの知ってるトーナメント戦であってるのか……？という不安があったので図を入れるか訳注入れるかしてほしかった．
有名な問題なので(a) (b)は明らかだけれど(c)は何が言いたいのかさっぱりわからなかったし，解答を見て問題文ちゃんと書けやとなった．

2.5. 33 魔法陣と擬似魔法陣

29を解いたあとなら割とすぐわかると思う．

2.6. 34 星の上の硬貨

ちょろい．

2.7. 35 3つの水入れ

初期状態の記述を読み漏らしてたけれどこれは試行錯誤してればいつか最適解みつかるでしょ感(本の解答も全幅探索紹介してるし)．

2.8. 36 限られた多様性

nが適当な数字のときについて考えたら普通にいけるやん！となって答え見たら不覚にも奇数のこと考えてなかった．

2.9. 37 2n枚の硬貨の問題

苦戦した．最初の僕の解は，重ねた状態でNクイーン問題解けば良いなとなったがNクイーン問題が任意のn>4で解を持つことが怪しかったし答えちら見したら貪欲っぽいことやってたのでもう少し考えて同じ構成法に至った．

2.10. 38 テトロミノによる敷き詰め

まぁ考えればわかる．ここまでちゃんと解いていれば不変条件とか市松模様の色とか散々やったのでそのタイプやろなぁとなる．

2.11. 39 盤面上の一筆書き

ルネジムだ！！！！！！！！！！！！ってなった．
エメラルドでいきなり出てきたルネジムのおっさん，ほんと影が薄いですよね．
とりあえずbは良いとして，aの理由付けがうまく行かなかった．
上下左右にある3x3の領域を埋める方法は，3x3の外から入ってきて全部埋めて出る方法は限られていること，最終的な位置が決まってることには気づいたので多分無理だよな……みたいな理由付けで答えを見たらなるほどーとなりましたね……

2.12. 40 交互に並ぶ4つのナイト

チュートリアルを見てればわかる．

2.13. 41 電灯の輪

とりあえず全部つければ全部つくことには幾つかのケースで試せばわかるし，3の倍数のときはうまくやれることにも気づくでしょう．

2.14. 42 もう1つの狼と山羊とキャベツのパズル

n>1ではできないと思って答えを見たら違った．
WCHGとGHCWはわかったが，n=2の場合はその2つをくっつけることしか考えてなくて，WCHGWCHGはダメじゃん！とおもいこんで完全に間違えた．
とりあえずn=2をちゃんと理詰めでやればよかった．

2.15. 43 数の配置

上手いこと思いついたと思って喜々として証明を書いてたら違ってることに気づいた．
一応とりあえず1からnの数字を並べて，左から見てって不等号が成り立ってないところは入れ替えるというのを入れ替えがなくなるまで繰り返せば行けそうだけれどうまくいくという証明はできなくてうーん．答えみたいな方法正直思いつかんよ．

2.16. 44 より軽いか？より重いか？

解答とは少し違ってた．

n=3mのとき，|A|=ｍ, |B|=m, |C|=mとなるようにA,B,Cに分割する．
・AとBを比較して同じ重さ→Cに偽物があるのでAとCを比較
・AとBを比較して違う重さ→Cはすべて本物なのでAとCを比較
n=3m+x(x∈{1,2})のとき，|A|=ｍ, |B|=m, |C|=m+xとなるようにA,B,Cに分割する．
・AとBを比較して同じ重さ→Cに偽物があるので，AとBから|D|=m+xなるように硬貨を集めてCとDを比較
・AとBを比較して違う重さ→Cは本物なのでCからx枚を除いたものをDとしてAとDを比較

これでも行けるはず．

2.17. 45 ナイトの最短経路

チェスを上が来たとなるように東西南北に向けて考えると，ナイトが南南東に進むと(dx,dy)=(1,2)，東南東に進むと(dx,dy)=(2,1)なので南南東に進んだ回数をn，東南東に進んだ回数をmとして右下に到着できるn,mを求めた．

2.18. 46 3色配置

適当にやればいけるやろぐらいの解答しか思いつかなかった．答え見てすげーなーってなった．

2.19. 47 展示計画

(a)自明だったので適当にやったら1多く答えてしまった．(b)ルネジムの問題(No. 39)を見た後なのでまぁわかる．

2.20. 48 マックナゲット数

適当に足したりしてたら気づくでしょ．

3. 感想

競技プログラミングに似ている問題があるので競技プログラミングの向上が期待できそうだけれどほんと貪欲思いつかないのでアレ．
「それ貪欲で解けるよ」ってほんと何もヒントになってないからな～💢💢💢💢💢💢

アルゴリズムパズル 8-28 僕の解答・感想

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の8-28番目の問題の僕の解答・感想です．

2. 各問題の解答・感想

2.1. 8 ジグソーパズルの組み立て

1ピースの場合，2ピースの場合，3ピースの場合……と考えていけばあぁそういうことねみたいな感じになるので解けた．

2.2. 9 暗算

ガウスっぽい求め方もやったけれど，先に思いついたのは行列を分割する方法．

A = [ [1 2 3 ... 10] [1 2 3 ... 10] ... [1 2 3 ... 10] ]

B = [ [0 0 0 ...  0] [1 1 1 ... 1] ... [9 9 9 ... 9] ]

という行列を考えると問題の行列はA+BになるのでAの合計とBの合計を求めた．

こういう問題は僕は好きで，昔小学生のころの実験的な授業で，「九九の百ます計算の表の中から，性質をたくさん見つけましょう」というのがあって，あの授業は良かったなぁと今でも思い出す．

2.3. 10 8枚の硬貨に含まれる1枚の偽造硬貨

引っかかりました．8だから2^3やし3!!! と思って答えを見たら2と書いてあって，2手だよと書いてあるのをみてすぐに手法はわかったので先入観がネックだなぁと強く感じた問題．

2.4. 11 偽造硬貨の山

思いついたのですごく気分が良かった．やり方は本の解答と同じだった．

2.5. 12 注文付きのタイルの敷き詰め

本の解答同様に理詰めでやったところ，解答にある形とはちょっと違うけど条件を満たせない形に至った．

2.6. 13 通行止めの経路

大学受験でやった．

なにげにこういうテクニックって授業ではあまりやらなくて，どちらかといえば塾とかでしか教えてもらえないイメージ(友人から聞いた気がする)．

2.7. 14 チェス盤の再構成

同じ色が隣り合わせになってはダメなので，そうならないように切断する必要がある．

その場所を全部切れば答えに行き着く．

2.8. 15 トロミノによる敷き詰め

n=1について考えればチョロい．

2.9. 16 パンケーキの作り方

問題文読んで「よくわからない，普通に2枚ずつ焼いていって奇数だったら最後の1枚を2分かけて焼けばよいのでは？」みたいに思ったが当たり前に違っていて悲しい．

ヒントをちゃんと読んで考えるべきだった．

2.10. 17 キングの到達範囲

紙にかけばわかる．

2.11. 18 角から角への旅

小学生の頃「レイトン教授と悪魔の箱」をやっていて，ナイトツアーがめちゃくちゃ好きだったのだけれど問題見た瞬間「おっ！8x8のナイトツアーやな！久々だけれどできるかな～？」とやってたら問題を読み間違えていることに解答を見て気づいた．

2.12. 19 ページの番号付け

計算するだけ，高校数学感がすごい．

2.13. 20 山下りの最大和

本では上からだが僕は下から計算した(一番下に0があるものとして，下から順番にその数字の下のある数字で最も大きいものをその数字に加える，という処理を上までやると最大和が出て，その経路を見れば下り方もわかる)．

プロジェクトオイラーっぽい問題だなぁと思ってたらプロジェクトオイラーの問題だった．

なんとなく既視感があるしどこかで解いたのかもしれない．

2.14. 21 正方形の分割

答えはあってるし，構成法も解答と同様だったがn=5の場合にできない理由にあまり自信がなかった．

なお答えを見たらその理由が簡単に説明されていて少し考えたらなるほどとなった．

(n=5の場合に仮に分割できたとすると，分割されてできた小正方形の四隅は，大正方形の四隅にくっついていないといけないが，そうすると真ん中に「十」みたいな空間ができてしまい，その空有間を埋めるとn=4になるしどう頑張っても構成できない)

2.15. 22 チームの並べ方

結構苦戦した．問題文もすこし読み取りづらかった．でも面白い問題だった．

「推移律はないが大小比較ができる集合」って意識的に考えたことがなかったので普通におもしろいし，そういった集合でもソートみたいなことはできるのは面白いし，普通のソートのアルゴリズムが使えなさそうなのでどうやるんだろうとか妄想が捗る．

2.16. 23 ポーランド国旗の問題

問題文だけだとよくわからないので図と例が欲しいところではあった．

(正直一番左から～とか一番右から～というような情報を得ることはOKなのか？と若干不安になりながら答えを見た)

2.17. 24 チェス盤の塗り分け

問題文だけだとよくわからない問題だった．多分こういうことだろうと考えて答えを作った．

(a) 2なのは明らか(チェス盤でナイトが行ける場所は今いる場所とは色が異なる場所なので9

(b) とりあえず角においてみて，効きのある場所の色をすべて異なるようにしてゴニョゴニョしたら[[1 2 3 ... n] ... [1 2 3 ... n]]とすれば条件を満たすことがわかったのでn.

(c) ビショップ同様とりあえず置いて……とやって本の答えと同じになった．

2.18. 25 最高の時代

競プロかな？？？みたいになった．

計算のオーダーが指定されてないし頭も良くはないので以下のようにやればいけそうだなぁと思って答えを見た．

1. 没年で昇順にソートして，i番目の科学者の生年と没年を(a_1 b_1) ... (a_n b_n)とする．

2. 各iについて，j番目(j<i)の科学者は死亡しているので，i番目～n番目の科学者でb_i-1年に生まれている科学者の集合をA_iとする(A_i = {a_k | a_k < b_i, k ∈ {i...n}})

3. A_iの要素の数をn_i，A_iの要素で最も大きい数字をc_iとする

4. iをn_iが最大となるiとすると，c_i年～b_i-1年が最高の時代

という方針でO(n^2)やなと思って見たらO(n log n)の方法が紹介されていてしょぼりーぬであった．

2.19. 26 何番目か求めよ

高校数学だった．

2.20. 27 世界周遊ゲーム

適当にやったら見つけられた．解はたくさんありそうではある．

2.21. 28. 一筆書き

ちょろい．

小学生の頃一筆書きをしよう！みたいな算数の授業があったのだけれどそれが全然できなくて軽く泣いた思い出がある．その時書けなかった図形は今でも覚えている．

まぁそういう経験があったので奇数のnodeがあったらそこから出発し，奇数のnodeで終わる必要があるのも熟知している．

3. 感想

今回得られた反省としては，

1: 問題文をよく読むこと

問題文をよく読んで，よくわからなかったらヒントを読むこと．

2: 先入観にとらわれるな

簡単すぎる場合はもう少し考えて本当にその解であってるか考えたほうが良い．

また最適だろうと思ってももう少し考えて改良できないか考えたほうが良い．

といったところだろうか．後加えるなら

3: オライリー本がプログラム書くための本だとは限らない

ですね．正直読むスタンスを間違えていた．

プログラムが書ける人向けのパズル集なので，数独の問題をとくのと同じように紙とペンで解いてるのが適切だった．とても楽しい．

アルゴリズムパズル 6-7 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の6, 7番目の問題「行と列の入れ替え」の実装例です．

2. 解

この本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本なので，ブログにパズルの内容について書くのは引用に収まるのか？という疑問があるので問題文は書かないです．

2.1. 問題6 指数え

本の解説のとおりなのでまぁ実装する必要はない

2.2. 問題7 真夜中の橋渡り

1分の男を何回も酷使すればいけるのではと思ったら駄目だったので少し考えることになった問題．良問だと思うが一般的に解く方法は全探索しか思いつかない．
解説にあるが「橋とトーチ問題」という有名な問題でそこそこ研究されてるらしいが特に調べてないのでわからない．
なお今回のような「歩くのが遅いやつ二人をどこかで一緒に連れてく」という方法では最適解を得られない場合もある(例：5分 6分 6分 7分のひとがいる条件では一番渡るのが早いやつが懐中電灯を持ってひたすら往復するのが一番早い)

3. 所感

難易度はまだ低いがまぁよい．
プログラミングの能力というのはぶっちゃけアルゴリズムを考える能力や数学力によって上限が決まってしまうので，それをどう上げるかが大事だと思ってるのだけれど，それが上がってないのはよく感じる．
そう考えるといちいち実装する必要はないので，頭で解けば良い問題は頭で解いて，実装が楽しそうな問題だけ実装することにした．
ただし今後も1日～2日に1回はブログを更新するつもり．

アルゴリズムパズル 5 行と列の入れ替え 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の5番目の問題「行と列の入れ替え」の実装例です．
この本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本なので，ブログにパズルの内容について書くのは引用に収まるのか？という疑問があるので問題文は書かないです．

2. 解説など

まぁ少し考えれば答えが「いいえ」であることはあきらかで，理由は解説に書いてあるとおりである(15と13といった同じ行にある数字を，相異なる行に移動させるという操作は行の入れ替え・列の入れ替えではできない)．
また一つの行を揃えれば全部の行の並びは揃うし，一つの列を揃えれば全部の列の並びは揃うという性質がある．
なお，パネルの並びを行列としてみたときに行の入れ替え・列の入れ替えは行列の積で表せる．
また行・列を入れ替えるような行列は行列式が-1であるから，初期状態と最終状態の行列式の絶対値が異なってるかどうかでもこの問題では判定できる(初期状態では行列式は0だが最終状態では行列式が0でない)．
ただし「行列式の絶対値が異なる→解はNo」は真だが「行列式の絶対値が等しい→解はYes」は必ずしも真ではない(行列によっては成り立たない).

3. ソースコード

一致させられるか判定するプログラムをCommon Lispで書こうとして詰まってしまって，ひょっとして単に僕のプログラミング力が低いからではと思いRustで実装した．
単に僕のプログラミング力が低いからだった．
判定方法は実際に揃えてみて一致するか確認してるだけ．

4. 感想

線形代数の勉強をしているので少し面白かった．

アルゴリズムパズル 2-4 実装例

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』という本の問題を解いてる．
初級編なので無限に簡単すぎてあまり面白みを感じられてない．
プログラムも短いのでまとめて問題2-4の実装例を貼っておく．

2. 実装例

この本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本なので，ブログにパズルの内容について書くのは引用に収まるのか？という疑問があるので問題文は書かないです．

2.1. 手袋選び

最悪のケースだけ考えれば良いということに気づかなかったのは痛いが，手袋が左右違うというのは問題文に書いておくべきではと思った．
ヒントにあるとおり(a)はたまたま同じ側の手袋が出まくるケースを，(b)はたまたまたくさんある色が出まくってて，しかも片方の方の手袋が出まくるケースを考えれば良いですね．
そうするともうただ計算式を書くだけという感じなのでプログラムを書く必要ないな……という感じです．

2.2. 長方形の分割

数字やテキストの処理で済まないのではみたいな問題だったが再帰的に直角三角形を分割するプログラムをProcessingで書いた．
まぁ無限に分割の仕方はあるので本とは異なる実装にはなった(長方形をまず直角三角形に分割して，それぞれの三角形をint(n/2)個とn-int(n/2)個の直角三角形に分割するのを繰り返してる)．
見た目は本よりも良さそうではあるが初級編なので著者は再帰関数を使わない手法にしたんだろうなぁと思うなどした．

実装のための計算で，ベクトルを幾何のベクトルとして触ったの何年ぶりだよという感じだった(そしてふつうに計算ミスしたりしてた)．

2.3. 兵士の輸送

1人のケースについて考えればあとはそれをn人に適用するだけなのでプログラムを書くほどでもない……

3. 所感

こうやってブログに書くことで継続的にやるモチベーションを作ってるのだけど問題が簡単すぎるとモチベダウンがすごい．上級者向けは多分僕が逆立ちしても解けないんだろうけど．

アルゴリズムパズル 1.狼と山羊とキャベツ 実装例[Rust]

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』という本を見つけたので，今勉強しているCommon Lispの練習として使ってみようと思ったが，思ったより苦戦してしまって癪だったのでRustで実装した．
有名な問題なのでググれば出てくるがこの本はパズルの問題文・ヒント・解法が羅列されているという少し特殊な本で，ブログにパズルの内容について書くのは引用に収まるのか？という疑問がある．
そのためパズルの名前と僕の解答(ソースコードとかんたんな解法)についてのみ書いておく．

2. 解答

Rustで幅優先探索で解いた．

3.感想

思ったより書きにくかった．コードもあまりきれいじゃない．

気になったこととしてはRustについてで，get_all_statesの引数の変数名を，あとで使う変数名と違うものにしないとうまく動作しなかった．
同じ変数名は後で定義された変数で前に定義された変数が隠蔽されるようになっていたはずだけれど，思ったとおりの挙動をしなかった．

はじめてのLispインタプリタをRustで実装して失敗した話

# 概要

プログラミング言語を作りたいがいまいち何から初めていいのかわからない，という場合に有名？なものにmal - Make a Lispというプロジェクトがある．
これはmalというClojureライクなLispを実装してみよう！というもので，73種類のプログラミング言語による実装がリポジトリにある．
malによるmalの実装もあるため，セルフホスティングするのを目指したが，うまく行かなかった(実装はここ)．
今日は一ヶ月かかったその実装の過程を簡単にメモする．

# 失敗談

## 構文解析

GitHubのinitial commitは6月2日だった．
malは実装ガイドというものがあって，Step1-9，StepAという順番に実装するべきものが紹介されている．
最初の方は構文解析で割と辛いところではあるが，ネットに転がっていたものを参考にしつつ，お手製パーサーを実装した．
ただ適当に実装したため-1が読み込めないという悲しいバグを含んでいる(おととい気づいた)
あとよくわからないことに，字句解析器はidentifierと記号と数字という三種類に分解していて，なんで数字だけ独立してるんだ……という感じになっていた．

その後順調に進めるのだが，ちゃんと英語を読んでないために結構悲しいことが起きていた．
というのも，リポジトリの./process/下に擬似コードがあったり，./tests/下にテストケースがあるのを完全に見逃していた．

## 擬似コードを見なかったことによる失敗

特に擬似コードを見逃していたのが実はかなり痛くて，何が痛いかというと評価のタイミングを見誤るということが結構あった．
例えばapplyだと，(def! a 3)とすると，(apply func '(a 2))を実行すると(func a 2)というものに仕様では変換され，第一引数はシンボルのままとなる．
ところが僕の最初の実装では引数を2回評価してしまっていて，(func 3 2)となってしまうバグが有った．
あわてて評価をしないようにすると今度は(def! r '(1 2 3))として(apply func r)とすると，rを評価しないからapplyの第二引数がリストでなくシンボルのままとなるというバグが……．
多分こういった評価のバランス感覚？というものは何回もプログラミング言語を実装しないと生まれないものだと思うので，ちゃんと擬似コードを読みながらやるべきだったと反省．

## テストケースによる失敗

あとテストケースを見逃していたことは，細々としたところが違っているということがセルフホスティングの段階で顕著に現れた．
たとえば(first '())を僕の実装でやるとエラーを吐くのだが，Clojureとかはnilを返すんですよね……
そういった細かい違いが顕著化して残念な結果になってセルフホスティングを諦めるということとなった．

## Lisp力不足

なにげにLispをあまり本格的に使ったことがないという事実はわりと問題ではあった．
例えば上記のようなテストケースの問題は，そもそもLispに慣れていれば起きなかった問題かもしれない．
あと逐一Clojureを立ち上げて動作を比較するとかしていたので割と効率が悪かった．

## オリジナリティを求めたことによる失敗

きちんとしたエラーハンドリングのない言語とかやってられないというお気持ちはあったのでランタイムエラーをいい感じに表示させようといろいろコードを追加したが，一切使わなかった(しかも取り除くことなく未だにそのムダなコードは残っている)．

## Rust力，プログラミング力不足による失敗

Rustで1000行ぐらいのプログラムを書いた経験，なし．
プログラムで2000行以上のプログラムを書いた経験，心当たりなし．
こういう状態で挑んだがためにムダにプログラムが肥大化した上に，コードが僕のコントロール外に行ってしまった．

正直Rustのマクロを使えばこの辺1/10のコード量になるよね？みたいなところが無限にあったが，マクロを知らないので実装できてない．
もう一度Rustドキュメントを読み直すべきである．

# 成功談

もちろん失敗談だけではない．

遅いし仕様は違うが，大抵のプログラムなら実行できるので，プログラミング言語を作ったという実感はある．

あとRust力が上がったのは感じるし，Rustの良さを実感することもできた．
これだけ長いコードを曲がりなりにも書けたという実感は自信になった(多分)．

# 今後の予定

とりあえずLispをちゃんと知りたくなったので『Land of Lisp』を読むつもり．
あとRust力の向上は感じるので，パズルゲームをRustで実装したりしたいなぁと思っている．

Raspberry Piを緊急地震速報機もどきにした際のメモ

1. 概要

今日の朝大阪で震度6弱の地震があったのですが，僕の下宿先(愛知)も揺れました．
地震発生時僕はまだ寝ていたのですが，とうとう東南海地震来たかと思って慌てて飛び起きました(n回目)．
先日も桜島が噴火したり長野や群馬で震度5ぐらいの地震がちょくちょく起きていたりしていて，緊急地震速報が家で聞けるようにしておきたいなと思ったので少しいじってみたのでメモします．

2. 準備

使用するものはRaspberry Piとスピーカーです．
僕はRaspberry Pi 2 Model Bを目覚まし代わりに使っていてスピーカーが常時接続されているのでそれを使いました．

3. セットアップ

3.1. 方針(とメモ)

CSV形式でTwitterに情報を垂れ流しているbotとかjson形式でデータを公開しているサイトとかありましたが，前者はTwitter API叩けばよいのですがAccess Tokenを得るためにTwitterにいろいろ情報送らないといけないので面倒だし，後者はデバッグがしづらそうなのでとりあえず保留にしました．

調べていたところ意識が低いですが緊急地震速報 by ExtensionというChrome拡張機能があったのでそれを使うことにしました．

3.2. 拡張機能のインストール

まぁインストールするだけです．
Chromiumにログインする必要ないんですね，初めて知りました．

3.3. 音声ファイルの変更

拡張機能のデフォルトの音声ファイルは3秒ぐらいしか音がならないし，パッとしない音だったので変更しました．
拡張機能には音声ファイルの変更というオプションがないので拡張機能のデータ類が入っているフォルダを直接いじりました(なにか問題が起きそうな気はする)．

• Where does Chrome store extensions? - Stack Overflow

Linux(Raspbian)でのChrome拡張機能の保存場所は，上記サイトにも書かれているように ~/.config/chromium/Default/Extensions/ にファイルがあったのでその中の音声ファイルをニコニ・コモンズから引っ張ってきた音声ファイルに変更しました．
(拡張子の変更は ffmpeg -i nc99687.mp3 nc99687.wav )

3.4. 動作確認

多分数日中にできるんじゃないですかね……(震え)
地震，来ないでほしいですねぇ．

4. 所感

上記拡張機能の仕様上，「愛知県で震度X以上」みたいなことはできてないです．
細かいことをやりたくなるとやはり自分でプログラムを書く他なさそうです．とりあえず愛知県専用の緊急地震速報のTwitter botとかあったのでそこから引っ張ってくれば良さそうな気はしますが，もうちょいまともな方法で実装したいですね．
とりあえずこれで少し安心ですが，どちらかといえば部屋の掃除・耐震のほうが大事かもしれません．

というか雑な感想ですが今日のニュース見てて土木屋さんは塀の安全率はどのぐらい考えてるのだろうというお気持ちになりました．
土木屋さんは地震に気を遣ってるのか機械系よりもずっと安全率に気にしてるイメージなのですが，家の安全率を気にしすぎて塀の安全率をすこし疎かにしている気がしました(今は違うかもしれないですし観測バイアス的なものだったりするかもしれないですが)．
地中に杭を打って杭にブロックを挿す感じでやるだけで改善できそうな気はします(コストの問題もあるでしょうが)．
先日トヨタの車リコールの話を少し耳にしたのですが，その原因は燃費に関係ある部品はすごく精巧に作っていたが，燃費と関係ない部品が少し疎かになっていたためにリコールすることになったという話だったのでそれと似たようなものを感じました．

ほんともっと住みやすい国になってほしいですねぇ……．

操車場アルゴリズムの実装例[Python]

1. 概要

コンパイラを書いてみたいと思いつつも，構文解析すらわからない．
その手の本を開くと操車場アルゴリズムというものが書いてあったのでWikipediaをもとに実装してみた．
ついでに逆ポーランド記法の処理系と変数及び代入を実装し，対話形式で計算ができるようにした．

• 操車場アルゴリズム - Wikipedia
• 逆ポーランド記法 - Wikipedia

一応確認した限りではちゃんと動作しているのが，クリティカルなミスはない(と信じたい).

2. ソースコード

200行ちょいと，ブログに貼るのは少し長くなったのでGitHub Gistにあげた．

• Pythonによる操車場アルゴリズムの実装例

3. 感想とか

動作したところはこんなかんじ．

操車場アルゴリズムのWikipediaが割と詳しく書いてあったので良かった．実装時にそれ以外のリファレンスは特に見ていない．
昔このサイトにあるコードを写経したときはこんなに面倒なのかと思ったけど，これなら僕にも実装できそうだ(というかできた)のでよかった．

そういえば今年に入ってPython3に移行した．
WindowsでのPython2の開発環境の構築が無限に面倒だったので，またインストールするの嫌だなぁと渋っていたのですが，やってみたらすぐ終わってしまった．
とくにpipでnumpyとかが入るのはすごい．Python2だとまだ入らないのでは．
mapの返り値がイテレータなのはビビったけどなんとか使えそう．

パズル「美術館」を解くプログラムを書いたお話[Rust]

新しい言語としてRustを始めたのですが，まだ使い慣れていない状態です．
練習がてらなにかプログラムを書きたいと思っていたところ，友人が，プログラミングの課題で「美術館」というパズルを解くプログラムを書かされたという話を聞いた．
面白そうなので書いてみたところ，思ったよりも辛い問題で，躓いた点があったのでメモします．

1.概要

「美術館」というパズルゲームはニコリという出版社が生み出したパズルゲームで，Nクイーン問題みたいなパズル．
ルールやサンプル問題などは以下を参照．

• 美術館 (パズル) - Wikipedia
• パズル > 美術館のおためし問題 [nikoli.com]
• 美術館の遊び方、ルール、解き方 | WEBニコリ
• 美術館 | ニコリパズル道場！

公式サイトはFlashのバージョンの問題からか，ChromeやFirefoxからはスッと試すことができなかったので，一度手でやってみたいという方は4番目のニコリパズル道場！という趣味で自作のパズルをあげてるサイトを見ると良いと思います．

2.解法

単純に深さ優先探索とかで書くと，探索空間が2^(WH)で増えていくので解くことはできない．

ただ，一度自分の手で解いてみるとわかりますが，とりあえず置いてみておかしいところが無いか確認する探索よりも，よく知られている経験則によって置く場所が決まることが多いです．

そういった人間でいう「解くためのコツ」を如何に高速に実装できるかがキモでした．

ただ問題によってはある経験則を消したほうが早くなる場合もあってこうしたら絶対に良くなると言い切るのは難しいです．

私の実装では置ける場所・明るくなった場所をbool型の2次元配列でもっておき，以下の制約を実装しました(1-2はルールの言い換え)．

1. 数字マスの周りに置かれた照明の数が，数字マスの数字と一致した場合，その数字マスの周囲にはもう照明は置けない．
2. 明るくなったマスには照明は置けない．
3. 数字マスの数字が，置ける空白マスの数と一致している場合は，全ての置ける空白マスに照明をおける．(e.g. 数字4のマスの周りは全て置ける)
4. 数字マスの周囲に，数字マスに書かれた数だけ照明を置く事ができない場合は条件を満たすことができないので探索を終える．
5. 置くことができる暗いマスで，その縦列・横列に置ける場所がない場合はそのマスに照明を置ける．
6. 置くことができない暗いマスで，その縦列・横列に置ける場所がない場合は条件を満たすことができないので探索を終える．

上記のルールに基づいていけば結構なマスを埋めることができます．

ただ，5はない方が早いこともあるしあったほうが早くなることもあるが，6番目の条件は，これがないとマトモに解けない問題もあります．

この条件でマスを埋めることができなくなった場合は

1. 照明を置ける場所にとりあえず置いてみて条件が満たせないか確認し，もとに戻す．条件を満たせなかったらそのマスは置けないマスとなる．(e.g.数字3のマスの斜め方向には置けないなどの制約になる→Wikipediaの解法を参照)
2. 数字の周りから先に探索する

という方針で探索領域を狭めながら探索を進めたところ，当方の環境でニコリのお試し問題すべてを4秒以内に解けるようになりました．

ただ公開するにあたって修正したのですが，修正する前のコードは半分ぐらいの時間で計算しているので実装の仕方次第でもう少し早くなるはずです．

3.ソースコード

サンプル入力・出力とともにGithub Gistにあげました．

サンプル入力はニコリのお試し問題からの引用です．

見た目を良くしたつもりなのですが500行を超えてます．

しかも整形しただけで計算時間が2倍になった理由がわからない……．

4.追記

書いた後に調べたところ，もっと良い経験則があるとのこと．

• YSR研究所 |ペンシルパズル『美術館』のプログラミング part2
• YSR研究所 |ペンシルパズル『美術館』のプログラミング part3

爆速になるらしいので機会があったら実装したいです(多分しない)

2018年最初の投稿

また年が変わりましたね．あけましておめでとうございます．

昨年は全然ブログ更新とかしてなかったのですが，毎年ブログで目標を立てて生きているので，今年も昨年を振り返りつつ目標をたてて1年頑張りたいと思います(去年の投稿はここ)．

1.昨年を振り返って

今思うと激動の1年だったと思います．
ざっくりいうとCPUと動物に興味を広げたという一年だった．

1月……
ペットボトルロケット飛ばしてた(この記事とかこの記事)．
何かと雑だったけどそれなりの開傘アルゴリズムだと自負してる．この手法でハイブリッドロケットも回収できたのでよかった．

2月……
ハフマン符号化の実装をしてたみたい．このツイートが数回RTされたところで既出ネタだったことが発覚．まぁみんな考えるよね．

圧縮した文章を画像の中にうまいこと埋め込むことで『吾輩は猫である』などの文章，合計約850万文字の共有に成功した！！！！！！！
140字の6万倍！！！！！ pic.twitter.com/KDjQYAFmYw

— もりとにー (@TonyMooori) 2017年2月18日

3月……
後述するが昨年の目標として本を読むことをあげていたので春休み中は何かと本を読んでいた．
『数値計算の常識』とか読んでいたのでLU分解の実装をしてたらしい．あとはim920とか使って遊んでた．

4月……
基本情報技術者試験を受けた．11月に受けた応用情報技術社試験も含めて合格したけど，これ読解力の試験だなぁという感想が強い．ストラテジ・マネジメントの問題は全然覚えてなかったけど日本語読めばこれは違うだろうというのが明らかだったので消去法で言ったら結果的にそっちの方が点数が良かった気がする．午後問も同様に答えが文章中にあるタイプの問題でこれはちょっと……ってなった．
その勉強をしている際にアセンブラとかに興味が湧いたので『Hacking: 美しき策謀』を少し読んでう～～～ん？？？と唸ることになった．

5月……
『CPUの創りかた』を読んだ．目からうろこだったのでLogisimでTD4作ったりして遊んだ．今見るとひどい回路だけどこれは大きな知見が得られた．
同時期に春休みぐらいからちまちま写経してた離散数学の教科書に目を通しきった．
更には『コンピュータの構成と設計 第2版 上』も5月中によんでたらしい．

6月……
BrainfuckCPUを作ったりしながら結構本を読んでいたらしい．
友人が仮想通貨で一儲けしたらしく，少し興味を持ったので『暗号が通貨になる「ビットコイン」のからくり』『ブロックチェーン入門』を読んだ．ここでBTCを買っとけば……．
他に『自然言語処理 (放送大学教材)』を読んだりしたが，この月に読んだ本で一番大きな衝撃を与えたのはP.J.B. スレーター 著『動物行動学入門』だった．けものフレンズを見てすこし読んでみるかーと手に取った，私にとっては異色の本だったがこれがドハマリした．この本を最初に読んだのは正解だったと今おもうと感じる．動物行動学という動物の行動に着目する学問があるということを初めて知った．この学問が血縁淘汰説を支持することになることを知るのはしばらく後である．
さらに『世界哺乳類図鑑 (ネイチャー・ハンドブック)』を読んで哺乳類がウマ目・ウシ目・ネコ目などという幾つかの大きなくくりが存在することを知った．大学には学研の図鑑のようなとっつきやすい本が無いのが非常に残念だったが僕の興味を広げるにはこの本は十分だった．

7月～12月……
この後はずっと月に1度ほどの頻度で動物園に行きつつ，動物関係の本を読み漁ることしかしていない．
『利己的な遺伝子』を読んだのは非常に印象に残っている．これは非常に良書だった．長い本だったがその分充実感は大きかった．血縁淘汰説をとても面白く感じたのを覚えている．
カール・ジンマー 著の『進化の教科書』は僕が知りたかったことを抽出して書いてくれて非常に良かった．利己的な遺伝子では少々回りくどく，浅い理解だったところを程よくおさらいできた．

技術的な方だと『ゼロから作るDeep Learning』を読んで実装した．結構いろんな知見が得られた．後は現代制御の勉強の結果を使って倒立振子のシミュレーション・制御をしたりRustを初めたりした．Rustは結構良い．

2.去年できるようになったこと

昨年の投稿に倣って書いてみると

• 基礎的なRustのコードが書けるようになった
• logisimでCPUを作れるようになった
• 現代制御で初歩的な制御対象を制御できるようになった
• CAD(授業にて)

結構少ない……．動物関係にリソースを割きすぎてしまった気はする．

3.去年の目標達成率

・数学の能力を上げる……25点
離散数学の本は読んだけど結局記号に慣れただけという印象が強い．もう少し頑張りたかった．

・関数型言語の勉強……50点
Rustは関数型言語……というのは誤りであることがわかったので50点ですかね(そういう書き方もできるだろうが)．そもそも関数型言語ってなんやねんという感じが強い．再帰つかったりfoldとかmapとか使うのはまぁできるけどうーん．純粋な関数型言語は触れなかったなぁ……．

・大会やニコ動にアウトプットしてく……0点
だめですね(だめなのです)．去年も駄目だったんですよね．うーん性ではない気はする．

・本を読む……80点
これは意識的に行った．100冊ぐらい読みたかったが児童書含めて60冊だった．友人で3年で1000冊の本を読んだ男が居るが到底かなわない．
ただあまりにもインプットに徹しすぎたというか，冊数を稼ぐゲームになっていたのでこれは良くないと感じた．趣向を変えるべきだと思う．

4.今年の目標

入学直後に先生が言った「学部時代に勉強しなかった科目は一生学ぶことがない」という発言が頭をよぎる．
昨年は動物の本にリソースを割きすぎた．動物は具体的で，読みやすい本が多いが深くまで切り込んだ本が少ないと感じた．
今年はもう少しうまくリソースを配分し，より深く，抽象的な理論を学ぶことをしたい．

・英語の多読をする……
　TOEICに対してプログラムのドキュメンテーションを読むだけではダメだというのがわかったので．院試が終わったらやめる．

・数学の勉強をする……
　院試用の試験勉強＋論理を追う力をつけたい．論理学を良書の情報を聞きつけたのでそれを読む予定．

・Lispの勉強をする……
　『Land of Lisp』を入手したので読む．関数型言語のキモはここで学ぶ．

・CPUのより詳細な内容(割り込みとか)/コンパイラ/OSについて学ぶ……
　「学部時代に勉強しなかった科目は一生学ぶことがない」という発言が頭をよぎる．

・本を読む……
　冊数にこだわるのではなく内容を重視していきたい．新書よりも専門書，なるべく手を動かしていきたい．ただ月に1度ぐらいのペースで軽めの本も読むつもり．

・ブログを更新する……
　アウトプットはここで．ハードルも低い．なんかコンペみたいなのに出したりするのはハードル高いし性に合わないことがわかった．ただ人に見せられるようなプロダクトの形をした物を作ってみたいなとは思う．

・新しいことに挑戦する……
　雑な目標だが僕は保守的な人間であるということを感じて非常に時代遅れになっているのを感じるのでなれないことになるべく手を出していきたい．


研究室に配属し，さらには院試もあるが頑張っていきたい．