スキップしてメイン コンテンツに移動

Project Euler - Problem 4

ラベル:

問題

  • 原文

    Find the largest palindrome made from the product of two 3-digit numbers.

  • 日本語訳

    3桁の数の積で表される回文数のうち最大のものはいくらになるか。

解答

3桁の数値なので、考えられる項は100 .. 999です。つまりナイーブな実装では、900 * 900 = 810,000回の乗算を行う必要があります。これは不可能な大きさではありません。というより私がまともな解法を思いつかないので、今回はこれで。

まず回文数かどうか判定する述語を作ります。palindromic-number?という関数がそれです。やっていることは単純で、数値を文字列に変換した上で反転したものと比較しているだけです。文字列の反転はSRFI-13のstring-reverseで可能です。 実際には文字列の前半と、反転させた後半のみを比較すれば良いのですが、文字列を切り出すコストの方が高いのでそのまま比較しています。

実際の探索を行っているsolveは単純で、すべての積を計算した上で、その中から回文数をSRFI-1のfilterで抽出してリストpalinsとし、そこからmaxで最大値を選び出します。 簡単な最適化として、例えば100 * 101と101 * 100は同じなので、無駄な計算を省くために100 <= i <= j <= 999が常に成り立つように内側のmapに渡すリストを工夫しています。これによって乗算の回数をおよそ半分にできます。

これまでの問題がミリ秒単位で計算できたのに比べると今回のプログラムは時間がかかりますが、数秒で計算できると思います。

(use srfi-1)
(use srfi-13)
(define (palindromic-number? n)
  (define n-str (number->string n))
  (string=? n-str (string-reverse n-str)))
(define (solve)
  (define palins
    (filter palindromic-number?
            (apply append
                   (map (lambda (i)
                          (map (lambda (j) (* i j)) (iota (- 1000 i) i)))
                        (iota 900 100)))))
  (apply max palins))
(define (main argv)
  (display (solve))
  (newline))

コメント

コメントを投稿

このブログの人気の投稿

Perl 5.42 が出たので perldelta を読んだ

去る2025年7月2日に Perl 5.42 がリリースされた。ので例によって perldelta を一通り眺めた。 このバージョンは実験的機能である組込みのクラス構文の実装が進展した。 他にもパフォーマンスの改良、組み込み関数・演算子・C レベル API の追加、多数のバグ修正があるが劇的な変化ではなく、発見・修正された脆弱性もかなり限定的な問題なので刺さる機能がなければ急いで移行する必要はあまりないように思われる。 以下主だった新機能の抜粋。 source::encoding プラグマ ソースコードが特定の文字エンコーディングで記述されていることを宣言するプラグマ。サポートされているエンコーディングは ASCII と UTF-8 のみである。 use source::encoding 'ascii' が宣言された字句的スコープにおいて非 ASCII 文字を記述するとコンパイル時エラーが発生するようになる。 use source::encoding 'utf8' は単に use utf8 のシノニムである。 Perl 5 は 2000 年にリリースされたバージョン 5.6 から UTF-8 によるソースコード記述をサポートしているが、後方互換性のため既定では ASCII を前提としており、 utf8 プラグマを使わない限り文字列リテラルや RegExp リテラルはバイト列として解釈されるし、識別子にも英数字および '_' しか使うことができない。 識別子はともかく「リテラルは既定でバイト列である」という意味論は極めて誤用しやすい。Unicode 文字列のつもりで渡した値が意図せずバイト列であったために実行時警告・エラーを得た経験は非英語圏のプログラマなら一度ならずあるだろう。 このプラグマはそのような初歩的なバグをコンパイル時に検出することで、Perl プログラムの最も頻出するエラーの一つを実質的に解消しようとしている。 ちなみに use v5.42 すると自動で use source::encoding 'ascii' も有効になるので、今まさに警告を吐いているようなアプリケーションをアップグレードする際は注意が必要である。 any / all 演算子 実験的...
コメントを投稿
続きを読む

Perl の新 class 構文を使ってみる

Perl 5 のオブジェクト指向機能は基本的には Python の影響を受けたものだが、データを名前空間 (package) に bless する機構だけで Perl 4 以来の名前空間とサブルーチンをそのままクラスとメソッドに転換し第一級のオブジェクト指向システムとした言語設計は驚嘆に価する。 実際この言語のオブジェクトシステムは動的型付言語のオブジェクト指向プログラミングに要求されるおよそあらゆる機能を暗にサポートしており、CPAN には Moose を筆頭とした屋下屋オブジェクトシステムが複数存在しているがその多くは Pure Perl ライブラリである。つまり「やろうと思えば全部手書きで実現できる」わけである。 そういうわけで Perl のオブジェクト指向プログラミングサポートは機能面では (静的型検査の不在という現代的には極めて重大な欠如を除けば) 申し分ないのだが、しかし Moose その他の存在が示しているように一つ明らかな欠点がある。記述の冗長さだ。 コンストラクタを含むあらゆるメソッドは第一引数としてレシーバを受ける単なるサブルーチンとして明示的に書く必要があるし、オブジェクトのインスタンス変数 (a.k.a. プロパティ / データメンバ) は bless されたデータに直接的ないし間接的に プログラマ定義の方法 で格納されるためアクセス手段は実装依存である。これはカプセル化の観点からは望ましい性質だが、他者の書いたクラスを継承するときに問題となる。ある日データ表現を変更した親クラスがリリースされると突然自分の書いた子クラスが実行時エラーを起こすようになるわけだ。 そうならないためにはインスタンス変数へのアクセスに (protected な) アクセサを使う必要があるのだが、そのためには親クラスが明示的にそれらを提供している必要があるし、そもそも Perl にはメソッドのアクセス修飾子というものがないので完全な制御を与えるならばオブジェクトの内部状態がすべて public になってしまう。 そのような事情もあり、特にパフォーマンスが問題にならないようなアプリケーションコードでは Moose のようなリッチな語彙を提供するオブジェクトシステムを使うことが 公式のチュートリアルでも推奨 されてきた。Perl コアのオブジェクトシステムの改良は...
コメントを投稿
続きを読む

Project Euler - Problem 25

問題 原文 What is the first term in the Fibonacci sequence to contain 1000 digits? 日本語訳 1000桁になる最初の項の番号を答えよ. 解答 Gaucheのストリームライブラリを使ってみました。 (use util.stream) (define fibonacci-sequence (iterator->stream (lambda (yield end) (let loop ((a 1) (b 1)) (yield a) (loop b (+ a b)))))) (define (digits n) (define (digits-1 m acc) (if (< n m) acc (digits-1 (* m 10) (+ acc 1)))) (digits-1 1 0)) (define (solve) (+ 1 (stream-index (lambda (n) (= 1000 (digits n))) fibonacci-sequence))) (define (main argv) (display (solve)) (newline))
コメントを投稿
続きを読む

Project Euler - Problem 17

問題 原文 If all the numbers from 1 to 1000 (one thousand) inclusive were written out in words, how many letters would be used? 日本語訳 1 から 1000 (one thousand) までの数字をすべて英単語で書けば、全部で何文字になるか。 解答 どう考えても数値計算じゃなくて文字列処理の問題です。つまりPerlの出番です。 数値を英語表現に変換する必要がありますが、 Lingua::EN::Numbers というCPANモジュールがまさにその機能を持っています。 以前のバージョンではイギリス/アメリカ英語の切り替え機能を持っていたようですが、現在は削除されています。生成される英語表現はイギリス英語が元になっているようなので、当座の用は満たせます。 コードの本質的な箇所ではありませんが、Perl 5.10から関数プロトタイプに _ を指定できるようになりました。 これを使うと、引数が省略されたとき $_ の値を使うという組み込み関数と同様の挙動を簡単に実現できます。 #!/usr/bin/perl use strict; use warnings; use feature qw/say/; use Lingua::EN::Numbers qw/num2en/; use List::Util qw/sum/; sub num_of_chars_in_english(_) { my $english_expr = num2en shift; $english_expr =~ tr/a-z//; } say sum map { num_of_chars_in_english } 1 .. 1000;
コメントを投稿
続きを読む

Project Euler - Problem 42

問題 原文 By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t 10 . If the word value is a triangle number then we shall call the word a triangle word. Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words? 日本語訳 単語中のアルファベットを数値に変換した後に和をとる. この和を「単語の値」と呼ぶことにする. 例えば SKY は 19 + 11 + 25 = 55 = t 10 である. 単語の値が三角数であるとき, その単語を三角語と呼ぶ. 16Kのテキストファイル word.txt 中に約2000語の英単語が記されている. 三角語はいくつあるか? 解答 42問目! ちょっと拍子抜けするほど簡単です。三角数を片っ端から計算して連想配列に入れておき、文字列の値を計算して照合するだけです。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say/; use List::Util qw/sum/; sub word_value($) { my $offset = ord('A') - 1; sum map { ord($_) - $offset } split //, uc shift; } sub tri_num($) { my $n = shift; $n * ($n + 1) / 2...
コメントを投稿
続きを読む