読者です 読者をやめる 読者になる 読者になる

初代Masteries

きっとモヒカンにもなれないお前たちに告げる!!!

2代目オイラー王の座を奪取? しました

弊社プログラミング部でオイラー王決定戦が開催されたので, 参加してきました.「オイラー王決定戦」とは, Project Eulerの問題をみんなで解き, その解答速度や実行速度を争う... という, 部活内でのプチ競技プログラミング, と思って頂ければと思います. 第1回…

オイラー王になれませんでした!

弊社(GaiaX)にはプログラミング部と呼ばれる部活動があります. 始業前に「朝練」と呼んでいる自主勉強会を開催したり, Project Eulerの問題を解く会を開いたりして, お互いの技能を高め合ったりしています*1.この部活動ですが, 今年度に入ってから, 「Peroject …

2013年5月のProject Euler [最終更新: 5月27日(月)]

アルゴリズムを考える能力を付ける, というよりは, 「定期的にコツコツ作業する」事に慣れるのと, コードを書く力を伸ばす*1為に挑戦を続けているProject Eulerですが, 先日お伝えしました通り, 解答を月ごとに, 1つの記事にまとめることにしました.というわけ…

Project Euler - Problem 33

Problem 33 '49/98'のような, 分子と分母に共通する数字(この場合, 9)を取り除いた時に, 取り除く前の数字と取り除いた後の数字が一致する(49/48 = 4/8)分数を探す問題です. ただし, 分数は1より小さい. 分子・分母ともに2桁の数. '30/50'のような, 明白なも…

Project Euler - Problem 32

Problem 32 ...今気づいたのですが, 日記の一覧を見ていると, オイラーの日記で投稿数を水増し(?)しているように見えます...よね. Project Euler解答系以外の記事を日記の一覧から探すときにちょっと不便なので, 来月からは月初めの投稿を「5月のProject Eule…

Project Euler - Problem 31

Problem 31 イギリスの硬貨, ポンドとペンス(1p, 2p, 5p, 10p, 20p, 50p, £1 = 100p, £2 = 200p)から, £2(2ポンド)を作る組み合わせがいくつかあるかを求める問題. use strict; use warnings; my $pattern = 0; my $target = 200; for (my $A = $target; $A …

Project Euler - Problem 30

Problem 30 なんだかんだで30問目まで到達ですね. もうちょっと頑張ってみましょう!さて, 今回の問題は, 各桁を5乗した数の和がもとの数と同じになるような数の和を求める問題. my $i = 1; while (1) { my $sum; $i++; $sum += 9 ** 5 for 1..$i; print "$i:…

Project Euler - Problem 29

Problem 29 2 答えを配列にpushしていくと, 「同じ項」を除去するのが面倒なので, 連想配列に格納していく形にしました. use strict; use warnings; use bigint; my %term; my $max = 100; for my $A (2..$max) { for my $B (2..$max) { $term{$A ** $B} = 1; …

Project Euler - Problem 28

Problem 28 どういう問題かを簡潔に説明するのがちょっと難しいので, 上記ページをご覧ください. use strict; use warnings; use bigint; my $answer = sum_diagonal(2) + sum_diagonal(4) + sum_diagonal(6) + sum_diagonal(8) + 1; print "$answer\n"; sub…

Project Euler - Problem 27

Problem 27 プログラミングのセンスもさることながら, 数学的センスも全っ然ないなあ... とヘコむ今日このごろです.問題としては, 「連続するnの値から素数を生成したとき最長の長さとなる二次式を求めよ」という感じ. 簡単に言えば, n^2+an+bについて, nを0か…

Project Euler - Problem 26

Problem 26 d use strict; use warnings; use Math::BigInt; for (reverse 1..1000) { my $n = Math::BigInt->new('1'.'0'x(2*$_))->bdiv($_)->bstr; if ($n =~ /(\d{2,}?)\1/ && length $1 == $_ - 1) { print "$_\n"; last; } } 1/dにおける循環節の長さは…

Project Euler - Problem 25

Problem 25 フィボナッチ数が1000桁を越える最初の項は何項目かを調べる問題. use strict; use warnings; use bigint; use Memoize; memoize('fibonacci'); my $length = 1000; my $n = 1; while (length fibonacci($n) < $length) { $n++; } print "$n\n"; …

Project Euler - Problem 24

Problem 24 30までは頑張りたいです(震え声).今回の問題は, 0..9からなる順列をソートして並べたときの100万番目を求める問題です. forループを延々と回してもよいのですが, 時間がかかりそうですしシンプルではないので, こういう風に考えてみました.9! = 3…

Project Euler - Problem 23

Problem 23 問題を解くのが結構キツくなってきました. ...もうちょっと頑張ります.この問題は, 2つの過剰数の和で書き表すことができない整数の総和を求める問題. 過剰数とは, ある数の約数の和がその数よりも多いものを指すようです. で, 数学的な解析によ…

Project Euler - Problem 22

Problem 22 テキスト処理系の問題. Perlの得意分野ですね!テキストには5000個以上の名前が書いてあって, リスト中の出現順と名前の各アルファベットのスコア(Aは1, Bは2...)をスコアとした時の全名前のスコアの和を求める, という問題です. 但しリスト中の出…

Project Euler - Problem 21

旅行中はお休みを頂いておりましたが, そろそろ復帰します. 4月1日より, 毎週月・水・金曜日に1問ずつProject Eulerの問題に取り組んでいきます.今後の予定ですが, ひとまず自分のスキル的に問題が解けなくなるか, 50問あたりに達した時点で, リファクタリング…

Project Euler - Problem 20

Problem 20 100!の答えの各位の和を求める問題. use strict; use warnings; use bigint; my $factorial = 1; for (1..100) { $factorial *= $_; } my $sum = 0; $sum += $_ for split //, $factorial; print $sum; 手堅く実装. 余談: 後置forについて 後置fo…

Project Euler - Problem 19

Problem 19 20世紀中に, 月の始めが月曜日日曜日である日は何回あるか求める問題. とりあえず素直に実装してみた. use strict; use warnings; my @days = qw/ 31 28 31 30 31 30 31 31 30 31 30 31 /; my ($y, $m, $d) = (1900, 1, 1); my ($now, $sum) = (0…

Project Euler - Problem 18

Problem 18 根本から総当たりで解くのではなく, 葉から値が大きくなるように値を求めていくと, 楽に求められますね. use strict; use warnings; use Data::Section::Simple qw/ get_data_section /; my @rows = reverse map { [split/\s+/, $_] } split /\n/…

Project Euler - Problem 17

※先週は就活で忙しかった為, 1週間お休みさせて頂きました. ご了承下さい. Problem 17 1から1000までの数字を英単語で書いた時, 全部で何文字になるかを求める問題. とりあえず答えは出たけれど, もっとスマートに書けそう... use strict; use warnings; my …

Project Euler - Problem 16

Problem 16 2 ^ 1000の各桁の和を求める問題. use strict; use warnings; use bigint; my $n = 2 ** 1000; my $sum = 0; $sum += $_ for (split //, $n); print "$sum\n"; とりあえず, シンプルに実装. ふと思ったけど, 2の1000乗はどっちで書くのがいいんだ…

続・Memoizeの話

簡単にメモ化を実現するMemoizeについては以前紹介しました. 今回はその話の続編... っぽい話です.Project EulerのProblem 14で, Memoizeを使って実装していたんですが, @bool_foolの兄から「Perlの実行速度遅すぎね?」とツッコミが入りました. # C 0.05s user…

Project Euler - Problem 15

Problem 15 20 x 20のマス目の左上から右上までを, 引き返しなしで行くルートは何通り存在するか, という問題. use strict; use warnings; use Memoize; memoize('check_route'); my @route; print check_route(20, 20) . "\n"; sub check_route { my ($x, $…

Project Euler - Problem 14

Problem 14 最長のコラッツ数列を求める問題. いい方針が浮かばなかったので, @bool_foolの兄にヘルプを求めました. use strict; use warnings; use Memoize; memoize('sequence'); sub sequence { my $n = shift; if ($n == 1) { return 1; } elsif ($n % 2…

Project Euler - Problem 13

Problem 13 50桁の数値100個を足して, その上位10桁を導く問題. bigint先生のおかげで簡単にできました. use strict; use warnings; use bigint; my $number = <

Project Euler - Problem 12

Problem 12 500個以上の約数を持つ最初の三角数を探す問題. use strict; use warnings; my $n = 1; my $triangular = 1; while (divisor_count($triangular) < 500) { $n++; $triangular += $n; } print "$triangular\n"; sub divisor_count { my $n = shift…

Project Euler - Problem 11

Problem 11 以下の格子から, 縦・横・斜めに連続する4つの数字の積から, 最大のものを見つける問題. use strict; use warnings; my $grid = <

Project Euler - Problem 10

Problem 10 200万以下の素数の和を求める問題. use strict; use warnings; use bigint; my $sum; my @primes = (2); for (1..2_000_000) { $sum += $_ if is_prime($_); } print "$sum\n"; sub is_prime { my $n = shift; if($n < 2) { return 0; } elsif($n…

Project Euler - Problem 9

Problem 9 a + b + c = 1000 かつ a^2 + b^2 = c^2 を満たすa, b, cを求めてから, それらの積 abc を求める問題. use strict; use warnings; for my $a (1..1000) { for my $b (1..(1000 - $a)) { my $c = 1000 - $a - $b; if($a ** 2 + $b ** 2 == $c ** 2)…

Project Euler - Problem 6〜8

いっぱい解いちゃったのでいっぱい載せちゃいます. Problem 6 1から100の二乗の和と, 1から100の和の二乗の差を求める問題. use strict; use warnings; my $sum_square; my $square_sum; for (1..100) { $square_sum += $_ ** 2; $sum_square += $_; } $sum_…

Project Euler - Problem 5

Problem 5 最初は総当たりで解こうと思ったのですが, かなり時間がかかってしまうので方針変更. 最終的にはこちらのページを参考に(参考というか, 書いてあったJavaのコードをPerlに書き直して...)実装しました. use strict; use warnings; use bigint; my $…

Project Euler - Problem 4

Problem 4 3桁×3桁の積で表される最大の回文積を求める問題. 「工夫がない」と言われればそれまでですが, 2重のforループでひたすら積を計算して, その答えと答えをreverseしたものと等しいなら回文積と判定しています. あとはその中で一番大きいものを保有し…

Project Euler - Problem 3

Problem 3 素因数分解. いろいろ悩んだ結果, 王道というか, 素直に実装してみた感じです. use strict; use warnings; use Math::BigInt; my $n = Math::BigInt->new('600851475143'); print "$n:"; for (2..int($n->copy->bsqrt)) { while ($n->copy->bmod($…

Project Euler - Problem 2

Problem 2 フィボナッチ数列を使う問題. いい感じに先日のプロダクト(Memoizeを使ったフィボナッチ数の計算)を流用できそうですね! use strict; use warnings; use Memoize; memoize('fib'); my $sum = 0; my $n = 0; while (1) { my $fib = fib($n); last i…

Project Euler - Problem 1

...就職活動が始まって以来, 「コードを書く日」と「書かない日」の差がありすぎてヤバイ*1ので, 「どんなに忙しくても2日に1回くらいは, どんなコードでもいいので20分〜30分くらいコーディングをしよう!」と決意しました. もちろん, 毎日毎日「なんか書こう!」とい…