名古屋で数学するプログラマ(仮)

@antimon2 が趣味兼一部本職の数学で何かするときのブログ。

CodeIQ の「今週のアルゴリズム：ピタゴラス数」について

CodeIQ 整数 ピタゴラス数

この記事は、結城浩（@hyuki）氏著の「数学ガール フェルマーの最終定理」↓を読んでいれば既知の内容ばかりなので、興味の無い方は読み飛ばしていただいて構いません。

数学ガール フェルマーの最終定理 (数学ガールシリーズ 2)

数学ガール フェルマーの最終定理 (数学ガールシリーズ 2)

CodeIQ のアルゴリズム問題「今週のアルゴリズム：ピタゴラス数（先日締切）」を解いたのですが、その解説記事（「第1回「今週のアルゴリズム：ピタゴラス数」解説 #ruby #javascript｜CodeIQ MAGAZINE」）の一部に、なんか「極めてないな感」を覚えてしまったのでカッとなって記事を書きます。
ポイントは、「互いに素の判定」。

最後に、私の提出した解答コードも掲載ます。

続きを読む

平方三角数コードゴルフ その後

整数 コードゴルフ 平方三角数

2ヶ月ほどほったらかしにしててゴメンナサイ(>_<)

平方三角数のコードゴルフ問題解答募集。
Twitter で解答をいただいていたので、それを紹介します。

あと、私の見付けている、最短解ではないけれど結構短い解も紹介します。

【2013/11/17 10:56 追記あり】

続きを読む

CodeIQ の「カードゲームの役判定」問題 by @Nabetani

CodeIQ ゲーム TDD

なんか最近 CodeIQ の話ばっか書いているような気がします(^-^;
ここ最近、少し余裕が出来たときにちょこちょこ目についた問題を解いて投稿したりしています。

その中の一つ。カードゲームの役を判定する。
先日フィードバックが来た*1のですが、なんか「antimon2 様の評価は『完璧』」とか「今回のベストアンサーだと思います」とか言われちゃいましたヾ(〃∇〃)ノ

そんなたいそうなものではなく、Ruby のメソッドを駆使して見た目シンプルに（ただし決して効率の良くない）コードを書いただけなのですが。
まぁせっかくなので、公開しちゃいます。

問題のおさらい

すでに締め切られているのでサイトを見ても問題は見えないと思いますので、簡単にどんな問題だったのか、概要を記述しておきます。
使用するのは、通常のトランプのカード52枚です。以下、"S", "H", "D", "C" はそれぞれ「スペード」「ハート」「ダイヤ」「クラブ」を表します。

6枚のカードを使って行うカードゲームがあります。その役を判定するプログラムを書いて下さい。
役は下表のとおりです。

役名 記号 意味 例
アンサー An 同一ランクの4枚組と、同一ランクの2枚組 S2,H2,D2,C2,SA,HA
シンクダブルトリオ sDT 同一ランクの3枚組が、2組。
各3枚組は、スートの組み合わせが同一。		 S10,H10,D10,SQ,HQ,DQ
ダブルトリオ DT 同一ランクの3枚組が、2組。
sDT ではない。		 S10,D10,C10,SQ,HQ,DQ
シンクコントトリプルペア scTP 同一ランクの2枚組が、3組。
各2枚組はスートの組み合わせが同一。
3つのランクが連続している。		 S9,H9,S10,H10,SJ,HJ
コントトリプルペア cTP 同一ランクの2枚組が、3組。
3つのランクが連続している。
scTP ではない。		 S9,C9,S10,H10,HJ,DJ
シンクトリプルペア sTP 同一ランクの2枚組が、3組。
各2枚組はスートの組み合わせが同一。
scTP ではない。		 S9,H9,S10,H10,SA,HA
トリプルペア TP 同一ランクの2枚組が、3組。
scTP, sTP, cTP のいずれでもない。		 S3,H3,H10,D10,SA,CA

data.txt に含まれている手札に各役が何組あるか数えて下さい。

*1:3連休中で旅行中だったので確認遅れました。

続きを読む

続・文字と数値リテラルを使わない Hello World 考 (in Ruby)

Ruby

先日の続き。

解答集サイトを見ていて、他にもこういう解き方があるな、と色々発見があったので、引き続き Ruby で、先日のとは全く違う方向性の別解をまたいくつか。

続きを読む

文字と数値リテラルを使わない Hello World 考 (in Ruby)

Ruby

CodeIQ の大人気問題「Restricted Words」が、ついに解答締切となりました。

この問題は「数値・文字・文字列リテラルを使用せずに、"Hello World" と出力する」というもの。
解答締切と共に、出題者から解答集が公開されました。

色々な言語の解答が載っていて、見ているだけで楽しいですね(^-^)

さて、でもここにのっている解答は、基本、以下のパターンです。

  • キーワードや配列リテラルを利用して、そのサイズ（や length 等）から数値を生成する。
  • 数値から文字を生成する。

でも最低条件は、「数値・文字・文字列リテラルを使用しないこと」。
この基本パターン以外の解答も探せばいくらでも見つかります*1。
ということで、私の提出した解答例と共に、それ以外のものも含めた Ruby での「別解」を探ってみたいと思います。

*1:実際、解答集サイトには、Perl の barewaord を利用した例、Ruby の class オブジェクトからクラス名を取得できることを利用した例、C の 関数名を文字列で取得できることを利用した例、などが挙げられています。

続きを読む

平方三角数コードゴルフ 解答募集！

整数 コードゴルフ 平方三角数

まずは報告。

『CodeIQの問題・パズルを考えよう！』 にて、平成変換（提案その1） と 日付型のユニットテスト（提案その4） の 2 作が採用になりましたo(≧▽≦)o

『日付型のユニットテスト』の方は、審査員のお一方、和田卓人氏（@）の「TDDの理解度を知るには、どんな問題が良いでしょう。」という言葉に「そう言えば私もちゃんと理解してな…」と思ってぴーんときた問題（というより『相談』）。だから選ばれて晴れて問題化されることになって、本当に嬉しいです。
でも正直、『平成変換』の方は、個人的に 20 年近く*1ずっと気になってた問題であり、個人的な思い入れは強いですけれど、それだけであり自分の中で Hot だっただけであり、まさか採用されるとは思ってなかったので、本当に正直にびっくりです。どうせ不採用だから結果発表されたらこのブログで解答募集しちゃおうかなーとか考えて準備し始めてたし。まーでもこれで『平成変換』もついに世に広まるかと思うと胸熱ですけれどね(^-^)

何はともあれ、葉っぱ の到着が待ち遠しいです(^-^)

さて、前置き長くなりました。本題。
不採用となった残り 2 作のうち、『平方三角数』。
平成変換の代わりに、こっちの解答を募集します(^-^)

まずは、問題を加筆修正して再掲します。

【※2013/11/16 追記】
寄せられた解答を別記事で公開しました。→
平方三角数コードゴルフ その後 - 名古屋で数学するプログラマ(仮)

*1:元ネタが『平成 3 年』ですし。

続きを読む

もっと「クロッシング問題」（＝転倒数計算問題）

CodeIQ アルゴリズム 転倒数

一昨日 の続き。

通称「クロッシング問題」（実質「転倒数計算問題」）について、結城 浩 氏からフィードバックが届きました。
（解答投稿した人しか見られないらしいのでURLとか貼れませんのでご了承ください）

その中で、こちらの想定していたアルゴリズム以外のものが紹介されていたので、ちょっと試してみました。

改めて、転倒数計算アルゴリズム

結城氏の紹介していたアルゴリズムは、以下の 3+1 つでした。

  • ナイーブな方法（＝バブルソートと同等の素朴な方法、計算量 O(n2)
  • マージソートを使う方法（計算量 O(n log n)）
  • 転倒表（逆転表）を使う方法（計算量 O(n log n)）
  • （おまけ）BIT を利用する方法

最後の「BIT を利用する方法」を（おまけ）と表記したのは、結城氏は想定しておらず「皆さんの解答でこんなのを利用したものがありました」という紹介をされていたからです（サンプルコードは示されていませんでした）。
私の考えていた「二分探索利用」は端から眼中になかった(笑)模様ですが、そこには私の知らなかったもう一つの方法が与えられていました。

「転倒表（逆転表）*1」というものを利用する方法。

ということで理解のために、自分で改めて書いて動作を試してみました。

*1:「転倒」も「逆転」も英語の inversion の訳語であり、結城氏は「逆転」の方を使用していましたが、私は「転倒」の方がなじみがあるのでこの記事では「転倒表」で通します。

続きを読む