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

Project Euler - Problem 18

問題

  • 原文

    Find the maximum total from top to bottom of the triangle

  • 日本語訳

    三角形を頂点から下まで移動するとき、その最大の合計値を求めよ。

解答

動的計画法を使ってボトムアップで簡単に解くことができる問題です。

簡単のため、小さい三角形で考えることにします:

0:    j
1:   h i
2:  e f g
3: a b c d

2行目の各点を頂点として、2行の小さい三角形が作れることが分かります。 上の例で言えば、(e, a, b)と(f, b, c)、(g, c, d)の3つです。 (e, a, b)の頂点eから末端(a、b、c、dのいずれか)に移動したとき、その数値の合計は最大でe + max(a, b)となります(maxは最大値を選ぶ関数)。同様に他の2つもf + max(b, c)、g + max(c, d)と表せます。 これらをE、F、Gとおくことにして、例を次のように書き換えます:

0:   j
1:  h i
2: E F G

(h, E, F)からなる三角形の最大値はH = h + max(E, F)、(i, F, G)からなる三角形のそれはI = i + max(F, G)です。 Eは「頂点eから末端に至る経路の最大値」で、FやGも同様ですから、HとIは「頂点h(やi)から末端に至る経路の最大値」となります。

これを先ほどと同様に置き換えて:

0:  j
1: H I

頂点jから末端に至る経路の最大値はJ = j + max(H, I)となり、これが解です。

#!/usr/bin/perl

use strict;
use warnings;
use feature qw/say/;
use List::Util qw/max/;

my @rows = map { [ split /\s+/ ] } <DATA>;
until (@rows == 1) {
  my $curr_row = $rows[-2];
  my $bigger_branch;
  for (my $i = 0; $i < @$curr_row; $i++) {
    $bigger_branch = max $rows[-1][$i], $rows[-1][$i + 1];
    $curr_row->[$i] += $bigger_branch;
  }
  $#rows--;
}

say $rows[0][0];

__END__
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23

コメント

  1. エントリを拝読しました。
    大変参考になりました。
    感謝です。

    返信削除
  2. 見落としていました。コメント承認が遅くなりましてすいません。
    ありがとうございます。稚拙なエントリですが、何かの役に立ちましたなら幸いです。

    返信削除
  3. とんでもない、とても役に立ちました。
    年をとって頭が固くなっていますから、
    Webでこうしていろんな方のコードを見せてもらうことがとてもいい刺激になっているんです。

    感謝です。

    返信削除

コメントを投稿

このブログの人気の投稿

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...

js_of_ocaml の使い方

js_of_ocaml (jsoo) は Ocsigen が提供しているコンパイラである。その名の通り OCaml バイトコードから JavaScript コードを生成する。 これを使うことで OCaml で書いたプログラムを Web ブラウザや node.js で実行することができる。 インストール 単に OPAM を使えば良い: $ opam install js_of_ocaml js_of_ocaml-ocamlbuild js_of_ocaml-ppx バージョン 3.0 から OPAM パッケージが分割されたので、必要なライブラリやプリプロセッサは個別にインストールする必要がある。 とりあえず使うだけなら js_of_ocaml と js_of_ocaml-ppx の二つで十分。後述するように OCamlBuild でアプリケーションをビルドするなら js_of_ocaml-ocamlbuild も入れると良い。 これで js_of_ocaml コマンドがインストールされ、OCamlFind に js_of_ocaml 及びサブパッケージが登録される。 コンパイルの仕方 以下ソースファイル名は app.ml とし、ワーキングディレクトリにあるものとする。 手動でやる場合 一番安直な方法は、直接 js_of_ocaml コマンドを実行することである: $ # バイトコードにコンパイルする。js_of_ocaml.ppx は JavaScript オブジェクトの作成や操作の構文糖衣を使う場合に必要 $ ocamlfind ocamlc -package js_of_ocaml,js_of_ocaml.ppx -linkpkg -o app.byte app.ml $ # 得られたバイトコードを JavaScript にコンパイルする $ js_of_ocaml -o app.js app.byte OCamlBuild を使う場合 OCamlBuild を使う場合、.js 用のビルドルールを定義したディスパッチャが付属しているので myocamlbuild.ml でこれを使う: let () = Ocamlbuild_plugin . dispatch Ocamlbuild_js_of_ocaml . dispatcher $ # app.ml -...

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 の ...

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

Schemeでカリー化

Haskellの有名な特徴として、関数が勝手に カリー化 されるという点があります。 要するにHaskellの関数は常に部分適用可能になっていて、 f foo bar baz という関数適用は (((f foo) bar) baz) と解釈されています。これは非常に強力な機能で、汎用的な関数を目的に合わせて簡単に特殊化することができます。 Schemeやその他のLispでは、引数は必ず同時に与えないといけないので、カリー化したものを作ろうとするとクロージャを使って (define f (lambda (x) (lambda (y) (lambda (z) ...)))) とでもしなければなりません。しかも呼び出すときには (((f foo) bar) baz) と、1つずつ順番に適用する必要があります。 私が欲しいのは、"(Haskellが透過的にやっているように)与えられた引数を先頭から順に束縛し、足りない分を引数とするクロージャを返す"ような関数です。 ((f foo) bar baz) だろうが (f foo bar baz) だろうが (((f foo) bar) baz) だろうが同じ結果を返す関数を作りたいわけです。そこで、カリー化関数を作成するマクロを書きました。 (define-syntax curry (syntax-rules () ((_ (arg0) body ...) (lambda (arg0) body ...)) ((_ (arg0 arg1 ...) body ...) (lambda (arg0 . rest) (define applied (curry (arg1 ...) body ...)) (if (null? rest) applied (apply applied rest)))))) このマクロを使って作成した関数は、引数を先頭から束縛していき、すべての引数が揃ったときに値を返します。 (define greet (curry (when who) (display (string-append "...