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

Project Euler - Problem 14

問題

ある関数を繰り返し適用して得られる数列が最も長くなる初期値n(1,000,000未満)を求める問題です。

解答

nから始まる数列の長さをlen(n)で表すと、次のように定義できます:

  1. len(n) = 1 (n = 1)
  2. len(n) = len(3n + 1) + 1 (nは奇数)
  3. len(n) = len(n / 2) + 1 (nは偶数)

つまり、len(n)の計算は1.の場合を基底ケースとする再帰アルゴリズムとして実装できます。

これをそのまま実装しても答えが得られますが、非常に遅いです。高速化の為に少し検討を加えましょう。

まず56から始まる数列を考えます。56は偶数なので3.の場合に該当し、len(56) = len(56 / 2) + 1 = len(28) + 1です。また、9から始まる数列の場合は2.に該当し、len(9) = len(3 * 9 + 1) + 1 = len(28) + 1となります。 つまりlen(56) = len(9) = len(28) + 1というわけで、len(56)とlen(9)の値は実は同じです。2.と3.の再帰式を見て予想できるように、このような重複は度々起こるので、それぞれの計算でlen(28)の計算をやり直すようなことをしていると大きな無駄となります。

これを解決するには過去に計算したlen(n)の値を覚えておき、次に同じnが与えられた時には覚えていた値を返すようにします。そうすることで2度目以降の関数呼び出しでは計算を省くことができ、時間の節約になります。これは同じ引数に対して常に同じ値を返す(つまり参照透過性がある)関数一般に使えるテクニックで、これをメモ化と呼びます。

そう言うわけで長々と説明しましたが、要はProblem 10で使ったルックアップ・テーブルと同じものです。今回はクロージャ生成時に確保されたベクタの長さより大きいnが与えられる場合(十分大きい奇数が与えられた時)が有り得るので、上限(upper-limit)より大きいnに対してはその都度計算し直しています。

(use srfi-1)
(define (get-sequence-length next-value upper-limit)
  (define lookup-table (make-vector (+ upper-limit 1) 0))
  (define (sequence-length n)
    (let ((len (if (> n upper-limit) 0 (ref lookup-table n))))
      (if (not (zero? len)) len
          (let ((len
                 (+ 1 (sequence-length (next-value n)))))
            (unless (> n upper-limit) (set! (sequence-length n) len))
            len))))
  (set! (setter sequence-length)
        (lambda (n len) (set! (ref lookup-table n) len)))
  (set! (sequence-length 1) 1)
  sequence-length)
(define (solve)
  (define sequence-length
    (get-sequence-length (lambda (n) (if (even? n) (/ n 2) (+ (* 3 n) 1)))
                         999999))
  (car (fold (lambda (a b) (if (> (cdr a) (cdr b)) a b))
             '(0 . 0)
             (map (lambda (n) (cons n (sequence-length n))) (iota 999999 1)))))
(define (main argv)
  (display (solve))
  (newline))

コメント

このブログの人気の投稿

開発環境の構築に 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 を使えば

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 (大文字なことに注意) ブロックが自分の宣言されたスコープ内で投げられた例外を捕らえる

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

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 の

部分継続チュートリアル

この文書について これは Community Scheme Wiki で公開されている composable-continuations-tutorial (2010年09月30日版)の日本語訳です。 誤字脱字・誤訳などがありましたらコメントあるいはメールで御指摘いただけると幸いです。 本訳は原文のライセンスに基づき Creative Commons Attribution-ShareAlike 2.0 Generic の下で公開されます。 Original text: Copyright© 2006-2010 Community Scheme Wiki Japanese translation: Copyright© 2011 SATOH Koichi 本文 部分継続(Composable continuation)は継続区間を具象化することで制御を逆転させるものです。 ウンザリするほど複雑な概念を表す長ったらしいジャーゴンのように聞こえますが、実際はそうではありません。今からそれを説明します。 reset と shift という2つのスペシャルフォームを導入するところから始めましょう [1] 。 (reset expression) は特別な継続を作るなりスタックに目印を付けるなりしてから expression を評価します。簡単に言えば、 expression が評価されるとき、あとから参照できる評価中の情報が存在するということです。 実際には shift がこの情報を参照します。 (shift variable expression) は目印のついた場所、つまり reset を使った場所にジャンプし、その場所から shift を呼び出した場所までのプログラムの断片を保存します; これはプログラムの区間を「部分継続」として知られる組み合わせ可能な手続きに具象化し、この手続きに variable を束縛してから expression を評価します。 組み合わせ可能(Composable)という語はその手続きが呼び出し元に戻ってくるため、他の手続きと組み合わせられることから来ています。 Composable continuationの別名として例えば限定継続(Delimited continuation)や部分継続(Partia