Y箱

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

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


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






この問題からClojure 1.3に移行しました。
contribの使いかたが変ってしまったり、これまでデフォルトで読みこまれていた機能が読み込まれなくなっていたりして、慣れない感じです。

1.3.0で速度はどうかなと思って、今回のコードで、1.2.1と比べてみました。
5回の平均です。

【1.3.0】
2120 msec

【1.2.1】
2748 msec

ちょっと速いですね。23%くらい。


さて、問題の方は...





直角三角形の各辺x,y,zの長の関係は、




















ということになります。
さて、ここから、

Lは偶数になる。
mはL/2の約数

ということがわかるので、その性質を使って解こうと思ったのですがだめ。候補が多すぎる。
で、他の性質を調べてみると、

mかnの一方が偶数
m>n
mの最大値は√(L/2)

また、mとnが互いに素=最大公倍数が1である場合のx,y,zを原始ピタゴラス数といい、それの整数倍もまたピタゴラス数であるそうな。
それで、これらの条件に合うmとnの組を作って求めることにした。

ただ、この方法だと、整数倍のところで重複するものが出てきてしまうので、重複していないかチェックする必要があります。素数生成で使った、配列をマーカーにする方法を使ってこれを検出しています。
今回は、配列にマークして、最後に重複していないものを数える方法を採りましたが、マークするときに数えることにすれば、ちょっと速くなりそうですが、面倒だったのでやめ。





- perimeter-list
条件に合うmとnを求めて、Lのリストを返します。
1から√(L/2)までのすべてのmについて、m以下で、mが偶数だったら奇数・奇数だったら偶数の、mと素であるようなnをすべて求めて、そのときのLのリストを作ります。

- pe-75
初期値0のマーク用の配列を用意して、perimeter-listで作ったリストにある数とその倍数がインデックスの場所を+1します。全部やると、1回だけ使われたものは値が1になっていますので、最後にそれを数えます。

arrをmutableなのにmutableっぽく使っていないところが気に入らない。atomにするのが正しいのかな？
あと、dorunを2回使わなくちゃならないところが気に入らないけど、これは回避できるのかな？



他のは作ったけど使わなかった関数と、ゴテゴテになってしまったpe-75。