Y箱

針金を曲げて直角三角形を作るとき、1種類しか作れないものを見つける問題です。

ピタゴラス数の問題ですね。


75個解いたので、Level 3になったよ。年内に100を目標にしてたんだけど、届かなかったな。

この記事は、Clojure Advent Calendar 2011の20日目の記事です。



[[2012/1/6 23:00 再修正]]
最新のswank-clojure (1,3.4)では、windowsのパス名の扱いの問題が解決していました。1.3.4以降のものを使えば、特に何もしないで使えます。



[[2011/12/26 23:00 修正]]

最初の投稿では、結局うまくいかなかったのですが、いろいろ調べたり方法を変えたりしてうまく行きました。


これまで、Project EulerとかCode Jamとかやるときには、ClojureBoxを使ってました。ClojureBoxは、立ちあげるとすぐにREPLが使えて便利なのですが、だいぶ前にメンテナンスが終了していて、1.3になる可能性がありません。
自分で1.3に入れ替えるのもそれほど難しくなさそうですけど、1.2ベースで作っちゃったものもあるし、ソースの管理という意味でも、leiningenを使った環境にするのがいいかなと思ったので、やってみました。

数を構成する数字を階乗したものの和で作る数列の長さを求める問題です。

3 -(3!)> 6 -(6!)> 720 -(7!+2!+0!)> 50402 -...

これをそのままやっては終らないので、別の方法を考えたのですけど、思いつかないし、改善方法は思いついたので、それで実装。
2分ちょいかかります。

これもファレイ数列の問題です。

数えるだけなので、他にいい方法もありそうですが、70の方法で正面から解いてます。

ところが、初めに作ったものは再帰で実装して作ったデータを全部持っていたため。OutOfMemoryになってしまった
で、今ちょうど読んでいる、Joy of Clojureで、遅延評価のクイックソートのことが出ていたので、それを使ったらできた。
ついでにJoCに出ていた、名前付き引数を使ってデータ定義をしなくてもいいようにしてみたけれど、あまりよくないかな。

これもファレイ数列の問題です。

なんか、もうちょっといい方法が見つかりそうだんだけれども断念。
まあ、1分弱で解けたからいいということにしよう。




ファレイ数列の個数は、






※wikipediaの画像を勝手に拝借してみた。

と表わせるとのとのこと。 ここにでてくるφ(m)は前に出てきた、オイラーのトーシェント関数。

このまま計算すると、1から1000000までの数を全部素因数分解する必要があって、ちょっと大変なんで、最初は20分近くかかってしまった。
でも、素因数分解の関数(factors)を前のやつからちょっと工夫してやったら、1分を切った。
factorsはもうちょっと高速化できるかもしれない。

百万までの素数を作るのに、5秒くらいかるので、それを入れたら1分を切れないねぇ。





- phi-n
 φ(n)を求める関数。





このとおり。
こういうふうに書けるところがClojure(ｌｉｓｐ）が好きな理由だね。


- pe-72
  ファレイ数列の式の通りの計算。
  でも、公式の場合、0と1を含んだ個数で、PEの問題は両端を含まないので、
  公式の結果から2を引いたものが答え。  ここちょっとはまった。

ファレイ数列の問題です。

Wikipediaの解説を見たら、解きかたは一瞬でわかります。





この数列でa/bとc/dが隣りあっている場合、その間に新しい分数が加わるとすると、それは2数の中間数 (a+c)/(b+d) であるとのこと。

ということは、問題の場合、2/5と3/8 について、
 - 中間数Mを求める。
 - 中間数Mの分母が1000000を超えたら、1つまえのものが答
 - そうでなければ、Mと3/8について同様のことを続ける。

この通りの実装でございます。

これもトーシェント関数の問題です。

普通に考えたら解けないのが分っているので、ちょっと考えます。





今回は、n/φ(n)を小さくするので、問題69で考えたことからすると、素因数の種類は少ないほうがいいということになります。
素因数を1つにするには、nは素数でなくてはならないのですが、nが素数のときのφ(n)は、n-1なので、これがpermutationになることはないでしょう。

ということで、素因数を2つとしてみます。少なくとも問題にある87109の素因数は2つなので、最悪、これが答になります。

さて、素因数が2つということは、

n=p1*p2

ということになります。 また、そのときのトーシェント関数の値は、

φ(n) = φ(p1)*φ(p2) = (p1-1)*(p2-1)

なので、掛けたときに10^7未満になる素数の組を作って、φ(n)とnがpermutationになるかどうか確認します。

20秒弱で解けましたけど、終了条件が分ればもっと速く解けるんじゃないかと思うんだけど、思いつかない。

オイラーのトーシェント関数φ(n)の問題です。


まずは、普通に解いてみましがやっぱり15分もかかります。大きな数の素因数分解そのものに時間がかかるのが問題です。
答が出たので、まあこれでもいいかな...と思っていたのですが、帰りの電車で考えていたら、ひらめきまして、やり直しました。


nの素因数分解が







のようにあらわせるとき、φ(n)は、








で得られます。問題の答は、n/φ(n)を求めます。
最初のやりかたは、ここで、nを素因数分解して、この式をそのまま計算するものでした。

このあと、この式を眺めていて別の方法を思いつきました。

n/φ(n)の値はこういう値です。









nが消えるところがポイントです。
この式の値を大きくするということは、分母を小さくするということです。それには、掛け合わされているかっこの中を小さくすればすればよくて、かっこの中を小さくするには、pを小さくすればいいということがわかります。さらにその数が沢山あればなおいいですね。
ということで、求めるnは、小さな素因数を沢山持つものであることになります。
とはいっても、同じ素因数をいくら持っていても、pは増えませんので、これは、小さい素数から順に素因数として持つものということになります。

ようするに、2、3、5...と、小さいほうから順に1000000を超えないように素数を掛けていくと答が出るということです。
ただ、このやりかただと、重複している素因数がみつからないので、実際にもとめる数はこの数の倍数ということになります。



前半はだめな実装。

- get-n-slash-phi-n
  n/φ(n) を計算する関数
  素因数分解をして、式のとおりに計算しています。

- pe-69
  2からnまでの数について、上の関数を使って、n/φ(n)が最大のものを求める。

下の二つができたやつ。
- product-list
  与えられたコレクションを順に掛けてできる数のリストを返す。
  2 2 2 2 2... なら 2 4 8 16 32... が返ります。

- pe-69
  説明の通りの動作をする関数。
  上の関数で素数を順に掛けた数のリストを作って、引数以下の最大数を求めます。さらに、
  それの倍数で引数以下のものをすべて求めます。

この記事は、Clojure Advent Calendar 2011の5日目の記事です。

Clojure界隈では、というより他でもWeb系のいろいろが沢山なわけですが、仕事がそっち系でないのでそういう指向があまりないのです。
Clojureは今のところ趣味で、主にProject Eulerとか解くのに使っているわけですが、以前、デスクトップアプリ作ってみたのでその時のことを。



環境
---------------------------------------
- マシン
自宅ではLinux機メインでやってますけど、仕事ではWin機です。

- エディタ
いつもはエディタとしてxyzzyを使っているのですが、Clojureを使うには環境があまり整備されていないし(自分でなんとかしろ？ですよねぇ。)、ClojureBoxってのがあるようなので、入れちゃうことにしました。

でも、もうメンテされていないので、1.3.0にしたければ自分でやることになります。 あまり手間もかからないとは思いますけど、そろそろ自分で一から環境作ってもいいかなと思ってます。

- shell
Leiningen使うにはコマンドラインを使うのですが、Winのcommand.comはとても使えたものじゃありません。cygwinとかmsysとか入れたらいいんでしょうけど、それはちょっとだったので、PowerShell使うことにしました。PowerShellが入っていなかったので入れました。

emacsからPowerShellを使いたいので、PowerShell-modeをここを読んで入れました。
設定して起動したらと、"unrecognized shell program" って怒られます。特に問題無く動くんのでしばらく無視してたんですが、やっぱり気になって調べてみたら、ClojureBox/emacs/emacs/lisp/shell.el で出しているメッセージで、コーディングシステムを設定しているところでした。
command.comと同じ設定でいいだろうということで、PowerShell用の設定を追加して黙らせました。


587行目あたり

(cond ((w32-shell-dos-semantics) (set-process-coding-system proc cp-out-dos cp-in-unix)) ((string-match "/msys/" fullprog) (message "think it is MSYS...") (set-process-coding-system proc cp-locale-dos cp-locale-unix)) ((string-match "/cygwin/" fullprog) (message "think it is Cygwin...") (set-process-coding-system proc cp-locale-dos cp-locale-unix)) ;; 以下3行追加。 ((string-match "powershell.exe" fullprog) (message "think it is Powershell...") (set-process-coding-system proc cp-out-dos cp-in-unix)) (t (message "unrecognized shell program yosi: %s" fullprog)))))))

準備
---------------------------------------
- GUIツール
これまでJavaとか華麗にスルーして生きてきて、つい最近androidのアプリが作りたくて初めて触ったような人なので、awtとかswingとかちんぷんかんぷん。とてもそのままでは作れる気がしません。で、ちょっと調べてみたらよさそうなのがあるではないですか。

seesaw
Seesaw is a library/DSL for constructing user interfaces in Clojure. It happens to be built on Swing, but please don't hold that against it.
SeesawはUIを作るためのライブラリー/DSLで、Swingの上に構築されていますが、Swingがだめだというわけではありません。

メイン
https://github.com/daveray/seesaw

使いかた
https://github.com/daveray/seesaw/wiki


-プロジェクトの作成
1. Leiningenで新しいプロジェクトを作ります。
 lein new guitest
 cd guitest

2. project.cljを編集してseesawを追加します。

(defproject guitest "1.0"
  :description "Seesaw test project, and more."
  :dependencies [[org.clojure/clojure "1.2.1"]
[org.clojure/clojure-contrib "1.2.0"]
[seesaw "1.0.7"]]                        ;; 作ったときはこれが最新だった。
  :main guitest.core)                             ;; スタンドアロンにするにはこれが要る。


これで準備は終り。


作成
---------------------------------------
「画像処理おもしろそう」と思って作ったアプリがあるのでこれについて。
GUIが目的ではないので見た目とか適当です(なんのこっちゃ)。

  ★★
  って書いておいて、動かしてみたら動かない。
  処理を早くしようとか、保存できるようにとかしてる途中だったみたいです。
  次の番が回ってくるまでに動くようにしときます。*_*;;;;;;

  動いていたときの画像。




- ソース (github)
https://github.com/ypsilon-takai/clojure-seesaw-test001

苦しまぎれに、解説なんかを。 いや、自分用に...
こうした方がいいんじゃない？ってなことがあれば、ご指摘いただけるとうれしいです。


core.clj
----------------------
 UI部分。画像の読み込みと表示。
 画像処理部分は、別ファイル (imagetool.clj)

14行目
 * 元画像BufferedImage と 表示用画像BufferedImage と 画像処理用long-array など
   書き換えるのでmutableなデータになってます。

23-38行目
 * 入力画像の選択/結果の出力ダイアログ。
   seesawのダイアログを使ってるだけ。

43-78行目
 * 新しい画像を読み込んだときの処理関数たち。
   下の2つが、新しいデータを作る関数と、データを再表示する関数。

81-87行目
 * 画像を保存する関数たち。

91-140行目
 * 画像処理関連
   配列からBufferedImageを作る関数。
   グレースケール化とエッジ検出の処理を呼ぶ関数。

141行目からGUI関連

147-216行目
 * 各ボタンの定義。 actionはそのためのseesawの関数(マクロ？)です。
   押されたときの関数を定義したり、ボタンに表示される文字列を設定したりします。
   Clojure流に設定できるので、気持いいです。

218行目
 * ウィンドウの定義です。
   実行すると、ウィンドウのフレームを返します。
   :content で中を定義します。
   これもClojure流に設定できます。

248行目
 * このクラスのメイン関数です。
   projectファイルでこのファイルをmainとしているので、jarを実行したときに、この-main関数が呼ばれます。
   native! を呼んでおくと、見た目がプラットフォームのものになるそうな。
   上で定義したmain-windowに show!してやると表示されます。




imagetool.clj
----------------------
前半はたいしたことやっていないので割愛。

72行目からがエッジ検出のところです。
いくつかの種類のフィルタを使えるようにしてあります。

create-operationは、フィルタを与えると、どうすればいいかを返します。

transform-to-edge-imgは、画像のデータの入った配列と変換の種類を受け取って、変換後の配列を返します。