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

Project Euler - Problem 33

問題

  • 原文

    The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

    We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

    There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

    If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

  • 日本語訳

    49/98は面白い分数である. 「分子・分母の9をキャンセルしたので 49/98 = 4/8 が得られた」と経験を積んでいない数学者が誤って思い込んでしまうかもしれないからである.

    我々は 30/50 = 3/5 のようなタイプは自明な例だとする.

    1より小さく分子・分母がともに2桁の数になるような自明でない分数は 4個ある.

    その4個の分数の積が約分された形で与えられたとき, 分母の値を答えよ.

解答

どうも「自明でない分数」の基準がよく分かりませんが、「分子・分母に共通する数字を取り除いたとき、元の分数と同じ値になるような分数(ただし分子・分母が10の倍数である場合を除く)」みたいです。

分数を(numerator, denominator)というリストの形で扱うことにして、「共通する数字を取り除いた1桁/1桁の分数で、通分した結果が元の分数のそれと等しい」という長ったらしい述語is_non_trivialを作りました。

#!/usr/bin/env perl

use strict;
use warnings;
use feature qw/say/;
use List::Util qw/reduce/;
use List::MoreUtils qw/none/;

sub gcd {
  my ($m, $n) = @_;
  ($m, $n) = ($n, $m) if $m < $n;
  my $r = $m % $n;
  $r == 0 ? $n : gcd($n, $r);
}

sub reduce_fraction {
  my ($num, $den) = @_;
  my $gcd = gcd($num, $den);
  map { $_ / $gcd } ($num, $den);
}

sub is_non_trivial {
  my ($num, $den) = @_;
  return 0 if $num % 10 == 0 or $den % 10 == 0;

  my @ns = split //, $num;
  my @ds = split //, $den;
  my @uns = grep { my $n = $_; none { $_ == $n } @ds } @ns;
  my @uds = grep { my $d = $_; none { $_ == $d } @ns } @ds;
  return 0 unless @uns == 1 and @uds == 1;

  my ($rn, $rd) = reduce_fraction($num, $den);
  my ($urn, $urd) = reduce_fraction(@uns, @uds);
  $rn == $urn and $rd == $urd;
}

my @product = @{
  reduce {
    [ $a->[0] * $b->[0], $a->[1] * $b->[1] ]
  } map {
    my $den = $_;
    map { [$_, $den] } grep { is_non_trivial($_, $den) } 10 .. $den - 1;
  } 11 .. 99
};
say +(reduce_fraction(@product))[1];

コメント

このブログの人気の投稿

Perl 7 より先に Perl 5.34 が出るぞという話

Perl 5 の次期バージョンとして一部後方互換でない変更 (主に間接オブジェクト記法の削除とベストプラクティスのデフォルトでの有効化) を含んだメジャーバージョンアップである Perl 7 がアナウンスされたのは昨年の 6 月 のことだったが、その前に Perl 5 の次期周期リリースである Perl 5.34 が 5 月にリリース予定 である。 現在開発版は Perl 5.33.8 がリリースされておりユーザから見える変更は凍結、4 月下旬の 5.33.9 で全コードが凍結され 5 月下旬に 5.34.0 としてリリース予定とのこと。 そういうわけで事前に新機能の予習をしておく。 8進数数値リテラルの新構文 見た瞬間「マジかよ」と口に出た。これまで Perl はプレフィクス 0 がついた数値リテラルを8進数と見做してきたが、プレフィクスに 0o (zero, small o) も使えるようになる。 もちろんこれは2進数リテラルの 0b や 16進数リテラルの 0x との一貫性のためである。リテラルと同じ解釈で文字列を数値に変換する組み込み関数 oct も` 新構文を解するようになる。 昨今無数の言語に取り入れられているリテラル記法ではあるが、この記法の問題は o (small o) と 0 (zero) の区別が難しいことで、より悪いことに大文字も合法である: 0O755 Try / Catch 構文 Perl 5 のリリース以来 30 年ほど待たれた実験的「新機能」である。 Perl 5 における例外処理が特別な構文でなかったのは予約語を増やさない配慮だったはずだが、TryCatch とか Try::Tiny のようなモジュールが氾濫して当初の意図が無意味になったというのもあるかも知れない。 use feature qw/ try / ; no warnings qw/ experimental::try / ; try { failable_operation(); } catch ( $e ) { recover_from_error( $e ); } Raku (former Perl 6) だと CATCH (大文字なことに注意) ブロックが自分の宣言されたスコープ内で投げられた例外を捕らえる...

(multi-)term-mode に dirtrack させる zsh の設定

TL;DR .zshrc に以下を書けば良い: # Enable dirtrack on (multi-)term-mode. if [[ " $TERM " = eterm * ]]; then chpwd() { printf '\032/%s\n' " $PWD " } fi 追記 (May 14, 2025): oh-my-zsh を使っていれば emacs プラグインが勝手にやってくれる: plugins = ( emacs ) 仔細 term-mode は Emacs 本体に付属する端末エミュレータである。基本的には Emacs 内でシェルを起動するために使うもので、古い shell-mode よりも端末に近い動きをするので便利なのだが、一つ問題がある。シェル内でディレクトリを移動しても Emacs バッファの PWD がそのままでは追従しない点だ。 こういう追従を Emacs では Directory Tracking (dirtrack) と呼んだりするが、 shell-mode や eshell ではデフォルトで提供しているのに term-mode だけそうではない。 要するにシェル内で cd してもバッファの PWD は開いた時点のもの (基本的には直前にアクティヴだったバッファの PWD を継承する) のままなので、移動したつもりで C-x C-f などをするとパスが違ってアレっとなることになる。 実は term-mode にも dirtrack 機能自体は存在しているのだが、これは シェルがディレクトリ移動を伴うコマンドを実行したときに特定のエスケープシーケンスを含んだ行を印字することで Emacs 側に通知するという仕組み になっている。 Emacs と同じく GNU プロジェクトの成果物である bash は Emacs 内での動作を検出すると自動的にこのような挙動を取るが、zsh は Emacs の事情なんか知ったことではないので手動で設定する必要がある。 まずもって「ディレクトリ移動のコマンドをフックする」必要がある訳だが、zsh の場合これは簡単で cd / pushd / popd のようなディレクトリ...

Project Euler - Problem 35

問題 原文 How many circular primes are there below one million? 日本語訳 100万未満の巡回素数は何個か? 解答 回転させた数値がすべて素数ということは、すべての桁が奇数でなければいけません(ただし2を除く)。 追記 匿名氏にコメントでご指摘頂いたのでコードを一部修正しました。 いずれかの桁に5がある場合も、回転させると必ず5の倍数が現れるので除外できます。 もっと追記 前の修正に間違いが入っているのをご指摘頂いたので修正しました。 5自体は素数なので、巻き添えで除外してはいけません。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::MoreUtils qw/all none/; sub is_prime($) { state %memos; my $n = shift; return 0 if $n < 2; return 1 if $n == 2; return 1 if $n == 3; return $memos{$n} if exists $memos{$n}; $memos{$n} = none { $n % $_ == 0 } 2 .. sqrt $n; } sub rotate($) { my $n = shift; substr($n, 1) . substr($n, 0, 1); } sub rotations($) { my $n = shift; my %seen = ($n => 1); $seen{$n} = 1 until exists $seen{$n = rotate $n}; keys %seen; } sub is_circular_prime($) { state %memos; my $n = shift; return 0 if $n =~ /[024568]/ and $n != 2 and $n != 5; return $memos{$n} if exists $memos{$n}; my ...

macOS で GUI 版 Emacs を使う設定

macOS であっても端末エミュレータ上で CLI 版 Emacs を使っているプログラマは多いと思うが、端末側に修飾キーを取られたり東アジア文字の文字幅判定が狂ってウィンドウ描画が崩れたりなどしてあまり良いことがない。 それなら GUI 版の Emacs.app を使った方がマウスも使える上に treemacs などはアイコンも表示されてリッチな UI になる。 しかし何事も完璧とはいかないもので、CLI だと問題なかったものが GUI だと面倒になることがある。その最大の原因はシェルの子プロセスではないという点である。つまり macOS の GUI アプリケーションは launchd が起動しその環境変数やワーキングディレクトリを引き継ぐので、ファイルを開こうとしたらホームディレクトリ ( ~/ ) でなくルートディレクトリ ( / ) を見に行くし、ホームディレクトリなり /opt/local なりに好き勝手にインストールしたツールを run-* 関数やら shell やら flycheck やらで実行しようとしてもパスが通っていない。 ワーキングディレクトリに関しては簡単な解決策があり、 default-directory という変数をホームディレクトリに設定すれば良い。ただし起動時にスプラッシュスクリーンを表示する設定の場合、このバッファのワーキングディレクトリは command-line-default-directory で設定されており、デフォルト値が解決される前に適用されてしまうので併せて明示的に初期化する必要がある: (setq default-directory "~/") (setq command-line-default-directory "~/") 次にパスの問題だが、まさにこの問題を解決するために exec-path-from-shell というパッケージがある。これを使うとユーザのシェル設定を推定し、ログインシェルとして起動した場合の環境変数 PATH と MANPATH を取得して Emacs 上で同じ値を setenv する、という処理をやってくれる。MELPA にあるので package-install するだけで使えるようになる。 このパッケージは GUI ...

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

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