日報:「会」をやる

今日の風景

最近の、ごくごく一部のエンジニア界隈では、言葉を短縮する傾向にあり、例えば「気持ち」だとか、あるいは「やっていく」とか、そういった雑な言葉が日々誕生している。その理由を察するに、基本的には曖昧さとか雰囲気とか、あるは日本語の乱れとかそういうことなのだろうと思う。そういう言葉使いが好きな人は小林銅蟲先生の「めしにしましょう」という料理漫画が近日発売されるので、予約購入するといいのではないか、と思う。

めしにしましょう(1): イブニング

で、その文脈を補強した上で、さらに曖昧な形で、知人達がやっている「サウ」という場所で、「JSの会」、通称「会」というのをプライベートでやったりした。「サウ」とは下のような場所である。

「サウ」というのは「サマーウォーズ」の略で、長広い和室に机が並んでいるのが「サマーウォーズ」っぽいところから派生して、それを略した形となる。「サマーウォーズ」になると「サマーウォーズ」になってしまうので、それを略して「サウ」になったんだと思うけれども、そのあたりの歴史的経緯は知らない。ちなみに「サウ」自体は禁煙である。

そういう歴史的な経緯はともかくとして、「JSの会」をやることになった。「JSの会」というのは、自分がひさしぶりにフロントエントをやろうとしたときに、どうせだったら「ECMAScript 2015」の仕様を知りたかったので、じゃあ集まって勉強しましょうということで、改めて勉強したのがこの会になる。成果としては下のスライドに詳しい。

• 老害と言われないためのES6勉強会報告・イントロダクション編
• 老害と言われないためのES6勉強会: class編

あとは人のスライドをダシにしながら、Vue.jsについてのお話しと、ReactやRuduxの話をしたりしていた。知人はチュートリアルを作っていて、コミットを見ていくとわかる作りになっているということで、今後これを使ってハンズオンする予定もある。ちなみに、「人の知らないスライドをつまみにしながら、好き勝手にマサカリを投げる」という形式は非常に効果的であるので、是非薦めたい。ちなみに、もうVue.jsは2.0がリリースされるのにも関わらず、このスライドを使って解説していた。

Vue.jsに関しては、知人がかなり苦労した部分もあったので、結構厳しめの意見が出てきて、個人的には「Vue.jsというのは、PHPに似ている」という話をした。もちろん生PHPではないけれど、Viewに対して、反復であったり、分岐であったりするような、若干ロジックが漏れだすような仕組みにはなっていて、それはテンプレートエンジンの宿命なのかもしれないけれど、「PHPっぽい」という気持ちにはなる。また、下手に画面フォームをモデルとして結びつけて、そのフラグをさらにその画面の中で利用してフラグとして活用するみたいなことができるので、そこらへんのフォーム部分制御に関して意識しないと、混沌としたものになるのではないか、という話をした。

あと、フレームワークついでに言うと、Vue.jsはPHPでいうところのCodeignitorや、RubyでいうところのSinatraみたいな、わりと薄いフレームワームなので、簡単な画面を作るときは、設計を気にする必要はないけれど、大規模になると、フレームワークの制約が無いせいで、途端に泥団子みたいにどんどんくっつけていくことになり、日にあてて乾かすとヒビがわれて破滅することになるが難しいという話もした。

このあたりについては、テンプレートであったり、コンポーネントの概念が出てくるわけで、もちろんVue.jsが意識していないわけではないのだけれども、最初の学習コストの安さと、どこでそのあたりをちゃんと学習してペイしていくか、という意識を分けるのは重要であるよなあという気がしている。次はRiot.js最強説が出ているので、そこらへんもおさえていきたいところであったりもする。

とにかく、「会」という概念は便利なので、どんどん雑な「会」を開いていって、知見を広げていきたいとおもった次第でした。

ちなみにこういう格好でやっていたので説得力は殆どなかった。(違うスペースなので煙草をすっている)

参考資料

改訂新版JavaScript本格入門 ~モダンスタイルによる基礎から現場での応用まで

開眼! JavaScript ―言語仕様から学ぶJavaScriptの本質

Rubyのグラフライブラリ(gnuplot)で砲台ゲームを実装しよう

今日の風景

寿司の電子工作

はじめに

今は廃刊してしまった、昔懐しい『ベーシックマガジン』という雑誌には、大抵簡単なゲームのコードが載っていた。俺を含めたパソコン少年は、そのコードを見ながらパチパチとコードを打っていたわけだが、そういったサンプルコードリストの一つに、大抵は「砲台ゲーム」というものが存在していた。

仕様としては、ある範囲が的になっており、角度と強さを指定し、投射線を描写する。的の範囲に入っていたら的中となり、的の外になっていたら外れということになる。

大抵、このゲームに関しては、30代から40代にBASICを触っていたおじさんであるならば、何処かで見たことがあると思うのだけれども、舞台がWebになった現代には、このような「砲台ゲーム」を作るといったようなサンプルを見ることは殆どなくなった。

で、前回にRubyからgnuplotを触るエントリを書いたわけだけれど、「あれ、グラフを使えば砲台ゲームが作れるんじゃないか」と思って、実装してみることにした。実行環境はJupyter Notebookを参考にしているので、上のリンクからインストールして欲しい。

投射線を描写する

ここからは殆ど『Pythonからはじめる数学入門』のパクリとなるので、正確な説明が欲しい場合には、実際に買ってみて試して欲しい。

投射線というのは「ある物体を投げたときに描く軌道のこと」と説明することができる。さて、このとき「ものを投げる」ということを考えた場合、「その物体を投げる力」と、「その物体をどの方向に投げるのか」という二つの物差しで考えることができる。

さて、このように考えたとき、我々の世界には「時間」という概念が存在している。つまり、「ある物体を、任意の力と角度で投げた場合の、ある時間の一点」というのが存在している。この詳しい原理について気になる人は、別途物理の教科書を参照して頂くとして、これを算出する式は、コードであるならば次のように書ける。

  def parabora(u, t)
    t = t / 180.0 * Math::PI
    g = 9.8
    t_flight = 2 * u * Math.sin(t) / g
    intervals = (0.0..t_flight).step(0.001)
    return [
      intervals.map {|x| u * Math.cos(t) * x}, 
      intervals.map {|y| u * Math.sin(t) * y - 0.5*g*y*y }
      ] 
  end

一から順番に追っていく。まず、最初の「t」はラジアン変換している部分だ。ラジアンは、2πを360度とするので、角度をまず最初に180度で割る。そうすると、nπのnの部分が出てくるので、それを使う。

次のgは単なる重力なので、特に気にしなくてもよい。

次に気になるのは、t_flightだが、これはボールの軌道をいつ止めるかの式になる。これは、ちょうどy軸が0になる範囲を示している。

あとは、u * Math.cos(t) * xの部分だけれども、これは要するにパワーと角度、そして時間をかけて、cosで求めている。一方、yのほうに関しては、重力補正がかかるので、ちゃんと- 0.5 * g * y * yといったように、時間軸にあわせて重力の値が補正できるようにしておかないと、どこまでも飛んでいってしまう。ちなみに、ここの解説が雑なのは、自分もよく理解していないせいもあるので、実際に知りたい人は物理の本を読むといいと思う。

class GameField
 #...

  def parabora_only(u, t) 
    Gnuplot.open do |gp|
      Gnuplot::Plot.new( gp ) do |plot|
        ball = Gnuplot::DataSet.new(parabora(u, t)) do |ds|
          ds.with = "lines lt rgb\"blue\""
          ds.linewidth = 1
        end
        plot.data << ball
        IRuby.display(plot)
      end
    end
  end

 #...
end

と書くことによって、下のような図を作画することができる。

ゲーム作るぞー

投射線の考え方はわかった。ポイントは的を描写することである。gnuplotにグラフを流しこむことは簡単で、一次元の配列の場合、要素数が xとなる。これを利用し、途中までの外れの部分の配列は「当たり」の部分の配列よりも短くするようにする。これを重ねることによって、ズレが発生し、当たりの部分がはみだして見えるわけですね。要するにズルです。

# ...

  def initialize
    @first = Random.rand(100...400)
    @last = @first + Random.rand(50..100)
  end

  def show
    Gnuplot.open do |gp|
      Gnuplot::Plot.new( gp ) do |plot|
        plot.title  'Game'
        # gnuplotの場合、配列の要素がxになるので、挟まないといけない
        fix = Gnuplot::DataSet.new([600]) { |ds| ds.with = "lines lt rgb \"#ffffff\"" }
        
        field = Gnuplot::DataSet.new([*0..@first].map {|x| 0 }) do |ds|
          ds.with = "lines lt rgb\"green\""
          ds.linewidth = 10
        end

        hole = Gnuplot::DataSet.new([*0..@last].map {|x| 0 }) do |ds|
          ds.with = "lines lt rgb\"red\""
          ds.linewidth = 5
        end

        plot.data << fix
        plot.data << hole
        plot.data << field
        IRuby.display(plot)
      end
    end    
  end

# ...

諸事情によりDRY、つまり重複コードばっかりなのは御愛嬌として、こうすることによって、下のようなグラフができる:

右上に点を付けているのは、グラフが最大の値に合うようになるので、こうすることによって、よりゲームらしい広がりのある表現を作りたかったためである。

さて、これを描写すると次のようになる

おっ、砲台ゲームっぽいですね。

発射メソッドを作る

というわけで弾を発射します。こんな感じでいいのではないかと。

    Gnuplot.open do |gp|
      Gnuplot::Plot.new( gp ) do |plot|
        # gnuplotの場合、配列の要素がxになるので、挟まないといけない
        fix = Gnuplot::DataSet.new([600]) { |ds| ds.with = "lines lt rgb \"#ffffff\"" }
        
        field = Gnuplot::DataSet.new([*0..@first].map {|x| 0 }) do |ds|
          ds.with = "lines lt rgb\"green\""
          ds.linewidth = 10
        end

        hole = Gnuplot::DataSet.new([*0..@last].map {|x| 0 }) do |ds|
          ds.with = "lines lt rgb\"red\""
          ds.linewidth = 5
        end

        ball = Gnuplot::DataSet.new(parabora(u, t)) do |ds|
          ds.with = "lines lt rgb\"blue\""
          ds.linewidth = 1
        end

        plot.data << fix
        plot.data << hole
        plot.data << field
        plot.data << ball
        t2 = t / 180.0 * Math::PI
        last =  u * Math.cos(t2) * (2 * u * Math.sin(t2) / 9.8)
        if last.abs.between?(@first, @last)
          plot.title  '成功'
        else
          plot.title  '残念'
        end
        
        IRuby.display(plot)
      end
    end
  end

結果として、何処に落ちたかどうかは計算しなければいけなかったので、別途u * Math.cos(t2) * (2 * u * Math.sin(t2) / 9.8)みたいなかたちで、最後のx軸の部分を計算している。ただし、マイナスになることもあるので、absでちゃんと判定できるようにすると吉。

これは残念なパターンです。

やりましたね。

ちなみに、全体のソースはこちらになります。

まとめ

数学だと思ったらいきなり物理の話が出てきて、とまどったし、実際なんでこういう方程式になるのかというのかを説明できない馬鹿なので、今回はポコー(心が凹んだときの音)した。しかし、グラフが書けると、このように砲台ゲームを作ることができる。今だとR言語がグラフを作るのに丁度いいので、こういう砲台ゲームを作ってみると楽しいのではないか、と思ったりした。だれか書いてくれませんかね(お前が書け)

Pythonからはじめる数学入門

Jupyter Notebookを使い、Rubyでgnuplotを使ってグラフを書いてみた感想

今日の風景

抽象的に言えば寿司です。

Jupyter Notebookについて

過去のエントリにも紹介したけれども、データサイエンティストにとって、もはや必須道具と呼ばれているツールにJupyter Notebookがある。基本的にはPythonから派生したツールなので、Pythonで良く使われている。基本的には画像をグラフィカルに表示できる、ブラウザ上で使えるREPLだと思ってくれれば良い。

Pythonが派生であるとはいえ、現時点では、そういったグラフィカルなREPLとして、多くの言語をサポートするようになっている。現時点で使える言語はここにまとまっているので参考にして欲しい。

唐突になぜJupyter Notebookのことを話題に出したかというと、Asakusa.rbが丁度やられていて、どうせ近くだから、一時間くらい遊びにいこうかなと思ったのがきっかけだった。ちなみに、途中に秋葉原で、ダンボールに円を描いて物乞いをしているおじいさんがいて、自分も本当にどうしようもなくなったときは参考にしようと思ったりした。

それはともかくとして、誕生日プレゼントとして頂いた『Pythonからはじめる数学入門』という本があるのだけれど、せっかくなので、Rubyでできる環境を構築しようかな、というのが今回のエントリの趣旨となるわけである。

Jupyter Notebookからgnuplotを動かす

とはいえ、まず開発環境が無いとはじまらないので、適当にJupyter Notebook + Rubyを入れてください。このあたりに関しては、検索すればいくらでも出てくると思う。

もし、Jupyter NotebookにうまくRubyの環境が入ったならば、「New」というメニューのところに下のように出てくるはず。

もし、選択を間違えても「Chenge Kernel」が使えるので気にしなくていい。

さて、さっそくRubyでグラフを描こうということになるのだが、gemの候補としては二つある。一つ目は、gnuplotをそのままラップした、そのものズバリのgnuplotというのがある。ただし、メンテナンスを見ればわかるように、2013年の段階で開発は停滞しているのだが、いい感じでグラフが描ければいいので、こちらを利用するのはあり。

あともう一つの候補としては、確かにgnuplotはいいんだけど、モダンなインターフェイスが欲しいよね、ということになると思う。そういう場合はnyaplotを使えばいいと思う。nyaplotはメンテナンスが進んでいるので、利用する側も安心であると思う。

とはいえ、人間はモダンであればいいというわけではなく、「いや、そこはgnuplotを使いたいんだ」という人もいると思われるので、Jupyter notebookからgnuplotを使う方法を書いておく。ちなみに、Rubyでgnuplotを使う方法については、ここを見れば書いてある。

直線のグラフを書いてみよう

というわけで、さっそくJupyter notebookでgnuplotを使っていくことになるわけなんだけど、使うだけなら、前のエンドリにあるように:

require 'gnuplot'
Gnuplot.open do |gp|
  Gnuplot::Plot.new( gp ) do |plot|
    plot.title  'test'
    plot.ylabel 'ylabel'
    plot.xlabel 'xlabel'
 
    x = (-100..100).collect {|v| v.to_f}
    y = x
    
    plot.data << Gnuplot::DataSet.new( [x, y] ) do |ds|
      ds.with = "lines"
      ds.notitle
    end
  end
end

と描けば良い。しかし、これには問題があって、このままだと、別ウィンドウに描写されてしまうことになる。

今回の趣旨としては、Jupyter Notebookにグラフを描きたいわけだから、この要件にはあわないことになる。

そこで、おそらくJupyter Notebookにある、何かしらのAPIを使えば画面に表示できる筈である。そのものズバリIRuby.displayである。さっそく、それをコードに追加してみる。

require 'gnuplot'
Gnuplot.open do |gp|
  Gnuplot::Plot.new( gp ) do |plot|
    plot.title  'test'
    plot.ylabel 'ylabel'
    plot.xlabel 'xlabel'
    plot.size "0.5, 0.5"
    plot.origin "0.5, 0.5"
    plot.bmargin "0"
    
    x = (-100..100).collect {|v| v.to_f}
    y = x
    
    plot.data << Gnuplot::DataSet.new( [x, y] ) do |ds|
      ds.with = "lines"
      ds.notitle
    end  
  IRuby.display(plot)
  end
end

やりましたね。

ちなみに、実際のgnuplotを使ったRubyの描き方はここが詳しいので、参考にするといいと思う。

まとめ

基本的には、この手のグラフに関しては、matlabなどや数学系ライブラリが充実してあるPythonを使うほうが望ましい可能性はあるのだけれども、簡単なグラフであったり、どうしてもRubyで書きたい、あるいはgnuplotが慣れているので……という人は、こういう方法があるので、やっていってみてはどうでしょうか。因みに、 個人的にはnyaplotのほうが良さそうな気がしているんだけれど、こればっかりは触ってみないとわからないですね。

Pythonからはじめる数学入門

日報: 「0点を50点にする人」と「50点を100点に近づけていく人」

今日の風景

プロトタイプとプロダクトの違いを視覚化したものです

雑談

今現在、プログラミングのリハビリもかねて、自分のできる範囲で知人のプロダクトを手伝っている。進捗的にはそこそこ理想的な進捗になっている。これはVue.jsのおかげであるのが殆どで、たぶん、普通にjQueryでスクラッチで書いたら、今の工数の5倍はかかっていたと思う。それだけ、UI周りの挙動をライブラリに丸投げできることは、とてもいいことである。そのあたりについては、過去のエントリに書いたので参考にしてもらえれば、と思う。

「日報」という題名が付いているときは、大抵は証拠の無いことを、自分が思ったままに書くエントリということになるんだけど、今回もそういったエントリになる。最近ちょっと思ったのは、いわゆるWeb系エンジニアと呼ばれる人達には、プロトタイプを作るのが得意な人と、プロダクトとしてリリースするのに品質を上げていくのに向いている人がいるのではないか、ということだった。

この話をするのは何故かというと、ここで自慢したいのだけれど、だいたい自分が書くコードは、いわゆる「こういう機能を実装したい」という場合には、一般的なプログラマよりも早く書けている、と褒められることが多々ある。もしかしたら社交辞令かもしれないけれど、そう言ってくれるのはありがたい。ただ、自分がコードを早く書けているのは、最初に「それを使って何ができればいいのか」だけを考えていて、「それが想定以外の使われ方をした場合はどうするのか」をあんまり考えないせいもある。

さて、ここでなんでプロトタイプとプロダクトを分けて考えるかというのを説明しないといけない。クライアントにとって、まず「こういうものが欲しいんですけど」という漠然としたアイデアがある。それを形にしてお金を貰うというのが、いわばプログラマの仕事の一部であるのだけれども、そのような漠然としたアイデアというのは漠然としているが故に、まだ形となっていない。

現代的な開発だと、ペーパープロトタイピングとか、ワイヤーフレームとかあるけれど、それは良しとしよう。まず必要なのは、クライアントにとって、「その漠然としたアイデア」というものを具体的な形に落しこむ作業だ。もうちょっと言えば、「これこれ、こういうのが欲しかったんだよ」という風にしていくというものである。

だいぶプログラマ界隈では一般的になってきたけれど、見積はプロジェクトが進むに従って誤差が少なくなっていく。つまり、見積が完成するのはプロジェクトが終わってからということになるので、だからこそ見積は頻繁に修正していく必要があったりするのだけれど、詳しい話は、下の本を読んだほうが早いと思う。

アジャイルな見積りと計画づくり ~価値あるソフトウェアを育てる概念と技法~

で、もしかしたら同様のことというのはプロトタイプにも言えるかもしれない。「漠然と、このようなアプリが欲しい」とした場合、まず最低限動くプロトタイプを作って提出する。それを元にして「こういう機能があったほうが便利」「最初に要求していた、こういう機能はこの場合だといらないね」といったような議論ができるようになるのではないかと思う。つまり、プロトタイプができあがっているときには既に完成している!!……とは言わないか。

もちろん、プロトタイプの工数は別途かかるわけだけれども、しかしお互いの認識がズレていたり、本当は必要無いのに作るみたいなことが無くなるので、中期的にはコストの削減になる気がするとは思うのだがわからない。あと、ガワのエコシステムが整えば、そのようなプロトタイプ的なコストの削減もだんだん減っていくはずなので、あったほうがいいよなあとは漠然と思っている。

で、そういうプロトタイプの話をしたいわけではなくて、俺自身はそういうプロトタイプを雑に作って「こういうの良さそう」というのはできるのだけれども、何しろ飽きっぽく、また一つの問題にずっと付きあっているとイライラしはじめて、ディスプレイを破壊したくなるという衝動が抑えきれなくなる。

当然ながら、プロトタイプはプロトタイプであって、例えていうならば「50点」の段階で、クライアントとクリエイト側が「このあたりを妥協点に作っていきましょう」という同意を結ぶものであって、とすると当然ながら「50点から100点に限りなく近づかせていく作業」が必要になってくる。

たぶん、このあたりのプロダクトにする部分については、自分はそれほど得意なのではないのではないか、という気がしている。いわゆる白紙のプロジェクトが段々要素とか増えていって形になっていくのはいいのだけれど、それが細かい修正に入りはじめると、持ち前の飽きっぽさが出てきて、段々と苦痛になっていったりするのであった。苦痛であるけれども、それが仕事であるからには仕方ない。

しかし、同様にプロトタイプは苦手だけれども、プロダクトに詰めていくのは得意な人はいるんじゃないんだろうか、というのは同様に思ったりした。つまり、仕様書だったり、あるいはあるていど固まったものを作るのは向いているのだけれども、「形のもやっとしたもの」を「こういうものはどうかな、ああいうのはどうかな」みたいな形で提案していくのは苦手なタイプ。

もちろん、どっちが凄いとかそういうのはない。プロトタイプができたとしても、プロダクトでリリースできなければ意味がないわけだし、プロトタイプですりあわせることのなかったプロダクトの開発でしっちゃかめっちゃかになったりする場合もあると思う。

現在無職で適当に暮している人間が、こういうことを言うのもアレですが、自分が「0点から50点にするのに向いている人間」か、あるいは「50点から限りなく100点に近づけていくのに向いている人間か」を意識することで、大分、仕事への向きあいかたというか、あるいは仕事のミスマッチみたいなものを避けられるよなあ、というお話でした。

今回の乞食アフィリエイト

SF映画で学ぶインタフェースデザイン アイデアと想像力を鍛え上げるための141のレッスン

デザイニング・インターフェース 第2版 ―パターンによる実践的インタラクションデザイン

Lean UX ―リーン思考によるユーザエクスペリエンス・デザイン (THE LEAN SERIES)

アナグラムを素数の積で求めると簡単(ではないけど)判定できるよって話

今日の風景

つくりおきはじめました。

はじめに

元々は 永和システムマネジメントの技術面接で出された問題らしい。こく難しく言えば「ある文字列」(この文字の集合をAとすると)と「ある文字列」(この文字の集合をBとする)とした場合、このAとBの文字の集合が一緒であるかどうかをどのように判定するか、という問題らしい。もうすこし簡単に言えば、Bの文字列はAの文字列かどうかをどのように判定するかということである。

この問題の解き方は簡単で、先に言ってしまえば次のようになる:

def anagram(s1, s2)
  s1.chars.sort == s2.chars.sort
end

これは、順序を考慮しない集合の場合、同じ要素が一対一になっていればいいということなわけだから、とてもシンプルでわかりやすい解答である。ただ、元のエントリが「Scheme」で書かれているので、Redditの日本語Lispコミュニティにも言及された(r/lisp_jaで見つけることができる)。その中のコメントで、とても秀逸なコメントをみつけたので紹介したい。

もし ASCII コードの範囲内だけとかいった、文字数が限定的であるような条件が付いていた場合には文字コードを素数に対応つけて掛け算するという方法がありますね。 文字の並び順にかかわらず同じ文字を同じ回数使っていれば同じ値になります。 Unicode 全体とかいった巨大な文字セットだと単純にソートした方が速いと思いますが……。

どういうことかというと、スレッドにも書いてあるとおり、「素因数で生成された積」は一緒にならない。このような理論は、例えば暗号技術に使われているし、またゲーデルの不完全性定理でも、このようにある文字列を素数の積として表現し、メタ的に判定に使われることがある。

このアルゴリズムは面白いので、さっそく自前で実装してみることにした。(本当はLispでの話題なのでLispのほうがいいかもしれませんが、Rubyでやります)

実装

require 'prime'

class String
  def to_prime_s
    t = prime_table
    return self.split('').map { |c| t[c] }.inject(:+)
  end

  private
  def prime_table
    alpha = ([*'a'..'z'] + [*'A'..'Z'] + [" "])
    Hash[alpha.zip(Prime.each.take(alpha.size).to_a)]
  end
end

def prime_calc(origin, anag)
  puts origin
  puts anag
  origin.to_prime_s == anag.to_prime_s
end

def string_shuffle(s)
  s.split('').shuffle.join('')
end


p prime_calc('Esehara Shigeo', string_shuffle('Eseraha Shigeo'))
p prime_calc('Esehara Shigeo', string_shuffle('Eseraha Shideo'))

特に特殊なことはしていない。あるとするならば、アルファベットと素数のHashを作っているくらいだろう。ただ、これだけだと、メソッドが呼びだされるたびにHashが作られるので、本来であるならばキャッシュするのがいいだろう。今回は二回のみだけなので、このような実装をしている。実行してみると、下のようになる:

Esehara Shigeo
hrSeieah goasE
true

Esehara Shigeo
ioahEseSa ehrd
false

雑感

このアルゴリズムの問題点は元のスレッドでも議論されているように、まず文字種が多い場合、それに対応した素数を増やさなければならないので、例えばUnicode全体を網羅しようとすると地獄になる。

また、長い文章に対応させるとなると、その分だけ素数の積を計算しなければいけなくなるので、計算量も膨大になるというデメリットがある。ただ、そのかわり複数の単語からなる文章のアナグラムも探しやすくなるということのようだ。

まとめ

というわけで、今回はネットから拾ってきたものをネタにしてみた。自分も、「なんかソートして、その文字列を比較するのはずるいなー、なんか方法ないかしら」と考えていたものだから、今回の方法は目から鱗だった。こういう風に何気ない一言で開眼できるのが、インターネットのいいところだと思う。

3の累乗の差と和であらゆる自然数を表現してみる(ついでに、その測り方を考える)

今日の風景

すたみな太郎にて誕生日会でした

はじめに

『算数の文化史』を読んでいたら、「あらゆる自然数は2の累乗の和としてあらわすことができる」ということが紹介されていた。証明はともかくとして、これは直感的にわかるものだ。だが、もう一つ「あらゆる自然数は3の累乗の和と差であらわすことができる」というのがある。これは直感的にはちょっとよくわからない。

例えば、5であるならば、3の累乗のリストは「9、3、1」となる。この場合、「9」から「3」と「1」を引くことで、5の数を表現できる。このように、全ての自然数は3の累乗の和と差で表現できるという。当然、このことは数学的帰納法かなにかで証明するのが正しいのかもしれないけれど、その証明はとりあえず追いておくとして、そのような3の累乗の和と差で、あらゆる自然数を表現するようなプログラムを書いてみるのが、今回の記事の目的となる。

仕様決め

まず、仕様を決めることにする。まず、基本的に3進法の考えかたを持ちいる。要するにどういうことかというと、例えば「12」を現わすときには、3進法では「110」と表現できる。しかし、3進法の場合、「13」の場合、「120」というように表現できる。

そこで、今回は「2」の使用を禁止し、差を表現できるようにする。そのような表現は、寡聞にして見たことがないので、暫定的に、ある位の差を~というように表現しよう。例えば、「11」の場合、「11~1」という表現をするようにする。例えば、10進法の場合、95を表現するなら「10~5」と書けるようにしよう、という表記である。

このような表記をどうして導入するのか、というと、元の問題が文銅を使って重さを測る問題であることと関係している。どういうことかというと、例えば2gの塩か何かを測りたい場合、手元には3gと1gの分銅しかない。その場合、天秤であるならば、2gの塩のほうに、1gの分銅をおいてあげて、もう片方のほうに、3gの分銅をおけば、無事つりあうというわけだ。

さて、このような表記を導入したのちに、位には二つの方式が出てくることになる。つまり、位と位との足し算、位と位との引き算である。通常、位というのは次のような式で表すことができる。

この式を見ればわかるように、足し算しか出てこないわけなのだが、これに引き算を付加するという記法が先ほどの記法になるわけだ。

というわけで、式を生成する

基本的には、ツリー形式で総当たりにしてある。もちろん、本来なら、自然数という定義に拘るならば、途中で数がマイナスになるならば、それ以降はプラスにならないと考えてそれ以上探索しないとか、あるいは途中のノートで似たようなノードが出る可能性を考えて、テーブルにキャッシュをしこむなどの方法があるのだけれども、そのあたりの面倒なところを考えるとロジックの部分が追いかけにくい部分が出てくると思うので、単純な総当たりにしてある:

class Scale < Struct.new(:even, :weight)
end

class Op < Struct.new(:n, :type)
end

class Spindle
  def initialize g
    @g = g
  end

  def three_table
    result = [1]
    point = 3
    while @g * 3 > point
      result.push(point)
      point = point * 3
    end
    result.reverse
  end

  def calc
    calcp(@g, 0, three_table, [])
  end

  def calcp(origin, prev_g, table, types)
    if table.empty?
      Scale.new(prev_g == origin, types)
    else
      next_table = table.clone
      next_g = next_table.shift
      return [calcp(origin, prev_g, next_table, types.clone.push(Op.new(next_g, 0))),
       calcp(origin, prev_g + next_g, next_table, types.clone.push(Op.new(next_g, 1))),
       calcp(origin, prev_g - next_g, next_table, types.clone.push(Op.new(next_g, 2)))]
              .flatten
              .select { |s| s.even }
    end
  end

  def to_s
    s = calc[0].weight.map do |s|
      if s.type == 0
        "0"
      elsif s.type == 1
        "1"
      elsif s.type == 2
        '~1'
      end
    end
    s.shift if s[0] == "0"
    s.join('')
  end

  def self.decode(s)
    result = 0
    a = s.split('').select{ |x| x != "~" }
    table = [*1..a.size].map { |x| x == 1 ? 1 : 3 ** (x - 1) }
    a = s.split('')

    until a.empty?
      check_minus = a[0..1]
      if check_minus[0] == "~"
        result -= table.pop
        a.shift(2)
      else
        next_num = table.pop
        result += next_num if check_minus[0] == "1"
        a.shift
      end
    end
    result
  end
end

2.upto(20) do |i|
  puts "#{i} => #{Spindle.new(i).to_s}"
end

calcpの再帰部分が正直綺麗ではないことをのぞけば、これで動く筈だ。ちなみにログは次のようになる:

2 => 1~1
3 => 10
4 => 11
5 => 1~1~1
6 => 1~10
7 => 1~11
8 => 10~1
9 => 100
10 => 101
11 => 11~1
12 => 110
13 => 111
14 => 1~1~1~1
15 => 1~1~10
16 => 1~1~11
17 => 1~10~1
18 => 1~100
19 => 1~101
20 => 1~11~1

ちなみに、最後の部分を:

2.upto(100) do |i|
  puts Spindle.decode(Spindle.new(i).to_s)
end

とすれば、元の数に戻せるはずである。これによって、コンピューターによって、3の累乗の和と差によって、あらゆる自然数が表現できることが確かめられたと思う。

この再帰部分てやっていることと言うのは、つまり:

• 9
  • 0
    • 1
    • -1
    • 0
  • -3
    • 1
    • -1
    • 0
  • 3
    • 1
    • -1
    • 0

といったような、木構造を作り、手当たり次第に検索している。これが、元の数と一緒の計算になるならば、それを残し、結果を出力する。結果のタイプは、「使わない、足す、引く」の三種類となる。今回の仕様の場合、「0, 1, ~1」となるわけだから、Opというオブジェクトのタイプを見ながら、文字列を組みたてる、というのがプログラムの概要となる。当然、手当たり次第なので、数が大きければ大きいほど、計算量が大きくなっていく。6の場合であるならば、3の3乗、つまり27通りで済むが、それ以上になると、3乗ずつ増えていくので、正直非効率である。

さいごに

とはいえ、証明が無いので、例えば101のときに、3の乗数で組み立てられない可能性があることも間違いない。本来ならば証明でやる必要であるけれども、証明については、詳しい人にまかせようと思う。

算数の文化史

今気がついたけど、もう売ってないのか……

明日は誕生日なので本当の乞食というものをお見せしますよ

今日の風景

今年も生き伸びてしまった。

誕生日 in 山谷

とうとう33歳となった。33歳といったところで特別に何かが変わるわけではない。変ったことと言えば、山谷のドヤ街でゴロゴロし、隙間から這い出る虫(具体的な名前は付せる)の姿を見るにつけて、侘しい気持ちになったりするくらいのものである。そんな暮しとはいえ、パソコンさえあれば、プログラミングができるので、それで時間を潰し、その知見というものをブログに書くという日常を送っている。

時折、酒で酔っぱらった老人の唸り声が、薄い壁越しに聞こえてはくるが、文明の力であるところの耳栓があれば解決する。耳栓は下のものを使っている。しかし、半日ほどつけているため、耳の垢が貯まるのが唯一の弱点である。

MOLDEX 使い捨て耳栓 コード無し 6620 Goin'Green 10ペアパック

ちなみに愛用品である。

山谷は周囲(この場合の周囲は空間的なものを指す)に酒呑みが多く、コンビニの隣で座って酒とつまみを広げている老人を尻目に、山谷特有の、コンビニだろうが、スーパーだろうが、酒が詰まれたワンカップを買うほどの余裕は無く、ただ今まで積ん読していた本と、あるいは図書館で借りられる本を読むのが精一杯だ。

俺がギークハウスからドヤ街に返ってくると、路上でダンボールも敷かずに寝ている人に二日に一度は出あう。ライオンだってサバンナの中で寝ているわけだから、コンクリートジャングルの中で寝るということは、自然としてはあり得なくはない。

何処かに行き先があるのか、と問われれば、それは知らぬ。

元々流されるようにしていきてきた中で、なんとか自分の欠陥を誤魔化したつけが溜ってきただけである。具体的に言えば説得力も増すだろうが、ここでは述べない。

ただ、ジョブホッパーしたり、あるいは身の丈の合わないことばかりに挑戦してきたというとだけ述べれば十分だろう。そのツケが溜ってきただけで、いま自分ができることと言えば、プログラミングくらいしかない。なので、ただ俺はプログラミングをやるというだけである。サイゼリヤすら潰れてしまう山谷という街では、プログラミングをほそぼそとやっているのが、自分としては一番いごこちがいいのである。

欲しいもの

一時期から、欲しいものリストを公開することに関して、まあ当然のことながら「乞食だろ」という反応が増えてきた。だが、俺の現状は他でもなく乞食である。一番欲しいのは現金であるが、しかし本さえあれば何とか生きていける。当然それだけでは無理なのだが、一番コストパフォーマンスの高い娯楽というのは読書だからだ。時間はある。

なので、欲しいものリストを公開する。とはいえ、欲しいものリストをただ公開しただけだと能が無いので、欲しいものに関しては全てにメモを付けるようにして、「どうして欲しいのか」を明確にしたつもりであるが、いかんせん文才の無い人間であり、人徳というかカルマも使いはたした関係上、購入してくれる人がいるとは思えない。とはいえ、買ってくれた人には感謝する。既に別件で頂いた『アンダースタンディング コンピュテーション』は不可解なまでにボロボロになっているので、それくらいは読み込むつもりだ(写真がないのが残念だが)。

• 誕生日の欲しいものリスト

なお、おすすめの書籍に関しては、ブクマなどで推奨してくれれば、所持してない限り追加すると思う。

今後

良くわからないが、プログラミングでそこそこに復帰できるくらいには筋力を蓄えておきたいというところがある。無を集めれば有くらいにはなろう。また、復帰できるそのときまで、暫くは休養しているつもりだ。まだ、死ぬ予定は無い。

俺はかろうじて、プログラミングという部分でなんとか社会なるものと繋っている。Ustreamで自殺した彼も、もしかしたら、プログラミングを覚えれば、かろうじて社会と繋っていたのかもしれないが、それは結果論でしかない。