2013-07-01から1ヶ月間の記事一覧

RでProject Euler 11〜15

R

Problem 11 文字列のベクトルを作っておいて、各文字列をsplitしたかったんですが、うまくいかず。しかたなくファイルにしてそれを読み込みました。それだと簡単に行列になるんですよね。そうすれば、あとは始点と方向を列挙するだけ。これはデータフレーム…

Project Euler 202

Problem 202考え方は簡単ですが、コードがなかなか書けなくて。

Project Euler 434(3)

http://projecteuler.net/index.php?section=problems&id=43471着。 実装がきついので手抜きしたら、O(n^6)になってPyPyで2時間36分かかった。でもたぶんO(n^4.6)くらいにはなるんじゃないかと思う。

Project Euler 434(2)

http://projecteuler.net/index.php?section=problems&id=434今朝考えたら、たぶんだいたいわかった。O(N^5+)だと思う。ごり押しできるはず。しかし、なかなかコードが書けない。この週末にはなんとかしたい。

Project Euler 434(1)

http://projecteuler.net/index.php?section=problems&id=434もう出題から半月以上経つが、ここで進捗報告を。 何日かで思いついた方法をずっと考えてきたが、うまくいかず。先週の木曜日くらいから違う方向がぽんやり思いうかんできて、土曜日に頭の中で形…

RでProject Euler Problem 1再考

R

Problem 1ではfilterを使いたいですよね。Rでfilterにあたるものはないようです。その代わりにwhichを使います。whichは条件を満たす要素の添え字のベクトルを作ります。 N <- 10 v <- 1:(N-1) print(which(v %% 3 == 0 | v %%5 == 0)) [1] 3 5 6 9そしてそ…

RでProject Euler 6〜10

R

Problem 6 N <- 100 v <- 1:N s1 <- sum(v) s2 <- sum(v * v) print(s1 * s1 - s2) v * vとすると各項の自乗のベクトルになります。 Problem 7 make_primes <- function(N) { a <- rep(TRUE, N) # TRUEに初期化 最終的にTRUEなら素数 for(p in 2:N) { if(p *…

RでProject Euler 1〜5

R

Rを勉強しなくてはならなくなったので練習のためにProject Eulerの問題を解いてみます。 Problem 1 ふつうに手続き型で書くこともできます。 N <- 1000 s <- 0 for(n in 1:N-1) { if(n %% 3 == 0 || n %% 5 == 0) { s <- s + n } } print(s) 1:3で(1, 2, 3)…

C#でProject Euler(8) Dictionary

C#

Pythonの辞書の代替になるコンテナはDictionaryです。Problem 27を考えてみましょう。Pythonならこんな感じです。 from itertools import * import time memo = { } def IsPrime(n): if n < 2: return False elif n in memo: return memo[n] b = all(n % p !…

C#でProject Euler(8) Set

C#

Pythonのsetの代替になるコンテナはHashSetとSortedSetがあります。Problem 29の小規模超ナイーブ版で考えてみましょう。Pythonならこんな感じです。 N = 10 s = set(a ** b for a in xrange(2, N + 1) for b in xrange(2, N + 1)) print len(s) HashSetを使…

C#でProject Euler(7) List

C#

ListはPythonのリストにあたるものです。C++のvectorにあたるといったほうがわかりやすいかもしれません。 using System; using System.Collections.Generic; // おまじない using System.Linq; class list_test { static void Main(string[] args) { var sw…

C#でProject Euler(6) 反復子ブロック

C#

タイトルは、英語ではiterator block、日本語公式サイトでは反復子ブロックと呼んでいるようです(方法 : 整数リストの反復子ブロックを作成する (C#))。反復子ブロックはPythonでいうジェネレータのようなものです。例としてProblem 2を考えてみましょう。…

C#でProject Euler(5) 速度

C#

ここで時間計測をしてみましょう。 using System; using System.Linq; class e001 { static void Main(string[] args) { var sw = new System.Diagnostics.Stopwatch(); sw.Start(); const int N = (int)1e9; var s = Enumerable.Range(1, N - 1). Where(n =…

C#でProject Euler(4) クエリ式

C#

前回はPythonの N = 1000 print sum(ifilter(lambda n: n % 3 == 0 or n % 5 == 0, xrange(1, N))) をC#で書くと、 const int N = 1000; var s = Enumerable.Range(1, N - 1). Where(n => n % 3 == 0 || n % 5 == 0).Sum(); Console.WriteLine(s); となるの…

C#でProject Euler(3) LINQ

C#

Problem 1をPythonでふつうに書くとこうなるのでした。 N = 1000 print sum(n for n in xrange(1, N) if n % 3 == 0 or n % 5 == 0) ジェネレータ式ではなく関数で書いてみると、 print sum(ifilter(lambda n: n % 3 == 0 or n % 5 == 0, xrange(1, N))) こ…

C#でProject Euler(2) ラムダ式

C#

次のコードを見てください。 using System; class lambda_test { static void Main(string[] args) { Func<int,int> f = (x) => x + 1; // ラムダ式 Console.WriteLine(f(1)); // 2 } } このfの定義がラムダ式です。型はFuncとなっています。引数がint一つで返り値がi</int,int>…

C#でProject Euler(1) はじめの一歩

C#

例えば、Problem 1ですが、Pythonでふつうに書くとこうでしょう。 N = 1000 print sum(n for n in xrange(1, N) if n % 3 == 0 or n % 5 == 0) 実質1行で書けます。しかし、Pythonは書きやすいけど遅いんですよね。C++の200倍くらい遅いことがあります。PyPy…