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

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];

コメント

このブログの人気の投稿

C の時間操作関数は tm 構造体の BSD 拡張を無視するという話

久しぶりに C++ (as better C) で真面目なプログラムを書いていて引っかかったので備忘録。 「拡張なんだから標準関数の挙動に影響するわけねえだろ」という常識人は読む必要はない。 要旨 time_t の表現は環境依存 サポートしている時刻は UTC とプロセスグローバルなシステム時刻 (local time) のみで、任意のタイムゾーン間の時刻変換を行う標準的な方法はない BSD / GNU libc は tm 構造体にタイムゾーン情報を含むが、tm -> time_t の変換 ( timegm / mktime ) においてその情報は無視される 事前知識 C 標準ライブラリにおいて時刻の操作に関係するものは time.h (C++ では ctime) ヘッダに定義されている。ここで時刻を表現するデータ型は2つある: time_t と tm である。time_t が第一義的な型であり、それを人間が扱い易いように分解した副次的な構造体が tm という関係になっている。なので標準ライブラリには現在時刻を time_t として取得する関数 ( time_t time(time_t *) ) が先ずあり、そこから time_t と tm を相互に変換する関数が定義されている。 ここで time_t の定義は処理系依存である。C / C++ 標準はそれが算術型であることを求めているのみで (C11 からは実数型に厳格化された)、その実体は任意である。POSIX においては UNIX epoch (1970-01-01T00:00:00Z) からのうるう秒を除いた経過秒数であることが保証されており Linux や BSD の子孫も同様だが、この事実に依存するのは移植性のある方法ではない。 一方で tm は構造体であり、最低限必要なデータメンバが規定されている: int tm_year : 1900 年からの年数 int tm_mon : 月 (0-based; 即ち [0, 11]) int tm_mday : 月初からの日数 (1-based) int tm_hour : 時 (Military clock; 即ち [0, 23]) int tm_min : 分 int tm_sec : 秒 (うるう秒を含み得るので [0

BuckleScript が ReScript に改称し独自言語を導入した

Via: BuckleScript Good and Bad News - Psellos OCaml / ReasonML 文法と標準ライブラリを採用した JavaScript トランスパイラである BuckleScript が ReScript に改称した。 公式サイトによると改称の理由は、 Unifying the tools in one coherent platform and core team allows us to build features that wouldn’t be possible in the original BuckleScript + Reason setup. (単一のプラットフォームとコアチームにツールを統合することで従来の BuckleScript + Reason 体制では不可能であった機能開発が可能になる) とのこと。要は Facebook が主導する外部プロジェクトである ReasonML に依存せずに開発を進めていくためにフォークするという話で、Chromium のレンダリングエンジンが Apple の WebKit から Google 主導の Blink に切り替わったのと似た動機である (プログラミング言語の分野でも Object Pascal が Pascal を逸脱して Delphi Language になったとか PLT Scheme (の第一言語) が RnRS とは別路線に舵を切って Racket になったとか、割とよくある話である。) 公式ブログの Q&A によると OCaml / ReasonML 文法のサポートは継続され、既存の BuckleScript プロジェクトは問題なくビルドできるとのこと。ただし現時点で公式ドキュメントは ReScript 文法のみに言及しているなど、サポート水準のティアを分けて ReScript 文法を優遇することで移行を推進していく方針である。 上流である OCaml の更新は取り込み、AST の互換性も維持される。将来 ReScript から言語機能が削除されることは有り得るが、OCaml / ReasonML からは今日の BuckleScript が提供する機能すべてにアクセスできる。 現時点における ReScript の

救急外来にかかったときの記録

子どもの頃にかかった記憶はあるが自分で行ったことはなかったのでメモしておく。 先日怪我をした。より具体的に云うとランニング中に転倒し顎を地面に叩きつけた。深夜の12時ごろの話である。 その時点ては両手の擦傷が痛いとか下顎の間接が痛いとか奥歯のセラミックが割れなくて幸いだったといった程度だが、マスクを外して見るとなにやら下部に血がついている。 顎にも擦傷があるのかとうんざりしながら歩いて帰り、血の滲んだマスクを捨てて傷口を洗おうとしたところで皮膚が割けて肉が見えているのに気付いた。 一瞬顔が青くなったが単身なので倒れるわけにはいかない。幸い血は固まっていてそれほど出血していないし、先程まで運動していたからかあまり痛みもない。 この時点で明白な選択肢は3つあった。即ち: 救急車を呼ぶ 自力で病院へ行き救急外来を受診する 応急処置して朝になったら近場の医院を受診する である。まず 3 は精神的に無理だと悟った。血も完全には止まっていないし、痛みだしたら冷静に行動できなくなるだろう。 1 はいつでも可能だったが、意識明瞭で移動にも支障がない状態では憚られた。救急車が受け入れ先病院を探すのにも時間がかかると聞く。 結局とりあえず 1 をバックアップ案とし、2 の自分で連絡して病院へ向かうことにした。まずは病院探しである。このときだいたい 00:30 AM。 最初に連絡したのは最寄りの都立病院の ER だった。ここならタクシーで10分もかからない、のだが、なんと ER が現在休止しているとの回答だった。そんなことがあるのかと驚愕したがどうしようもない。 近場に形成外科の救急外来の開いている病院はないか尋ねたところ 消防庁の相談センター の電話番号を案内された。 ここで4つの病院を紹介された。余談だが相談の対応は人間だが番号の案内は自動音声に切り替わるので録音の用意をした方が良い (一応2回くり返してくれる。) いずれも若干遠くタクシーで2、30分かかるが仕方がない。最初に連絡した最寄りの病院はその日形成外科の当直医師がいなかった。二件目でトリアージの質問をされ、受け入れ可能とのことだったので受診先が決定。このとき 00:45 AM。 診察時に脱ぎ易い服に着替え (このときまでランニングウェアだった)、健康保険証を持って病院へ向かう。ガーゼがないのでマス

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

開発環境の構築に asdf が便利なので anyenv から移行した

プロジェクト毎に異なるバージョンの言語処理系やツールを管理するために、pyenv や nodenv など *env の利用はほとんど必須となっている。 これらはほとんど一貫したコマンド体系を提供しており、同じ要領で様々な環境構築ができる非常に便利なソフトウェアだが、それを使うことで別の問題が出てくる: *env 自身の管理である。 無数の *env をインストールし、シェルを設定し、場合によりプラグインを導入し、アップデートに追従するのは非常に面倒な作業だ。 幸いなことにこれをワンストップで解決してくれるソリューションとして anyenv がある。これは各種 *env のパッケージマネージャというべきもので、一度 anyenv をインストールすれば複数の *env を簡単にインストールして利用できる。さらに anyenv-update プラグインを導入すればアップデートまでコマンド一発で完了する。素晴らしい。 そういうわけでもう長いこと anyenv を使ってきた。それで十分だった。 ——のだが、 ここにもう一つ、対抗馬となるツールがある。 asdf である。anyenv に対する asdf の優位性は大きく2つある: 一貫性と多様性だ。 一貫性 “Manage multiple runtime versions with a single CLI tool” という触れ込み通り、asdf は様々な言語やツールの管理について一貫したインタフェースを提供している。対して anyenv は *env をインストールするのみで、各 *env はそれぞれ個別のインタフェースを持っている。 基本的なコマンド体系は元祖である rbenv から大きく外れないにしても、例えば jenv のように単体で処理系を導入する機能を持たないものもある。それらの差異はユーザが把握し対応する必要がある。 多様性 asdf はプラグインシステムを持っている。というより asdf 本体はインタフェースを規定するだけで、環境構築の実務はすべてプラグイン任せである。 そのプラグインの数は本稿を書いている時点でおよそ 300 を数える。これは言語処理系ばかりでなく jq などのユーティリティや MySQL のようなミドルウェアも含むが、いずれにしても膨大なツールが asdf を使えば