rust-incoming-git の PKGBUILD
rust の最新の変更の commit 先が master ブランチから incoming ブランチに変更されたため、 master ブランチの動きが少なくなってしまい寂しかったので、 incoming ブランチ用の PKGBUILD を作成しました。ついでに、AUR にアップしておきました。
正確には、この PKGBUILD 自体は半月前くらいに作成したものなのですが、以下のコミットの影響で正しくインストールできなくなってしまったので、それの修正がてら、ついでにAURに投稿したという経緯です。
コンパイルに clang 使うオプション有効にしたまま投稿してしまったので、依存パッケージとか全然足りてない気がするけど、それはそれで、まあ、良いと言うことで。。。気が向いたら、というか指摘されたら直します。。。
rust-git の PKGBUILD
AUR にある rust-git が、makepkg しようとすると毎回 llvm やら libuv のサブモジュールを clone しようとして時間がかかって仕方が無いので、初回だけ clone するように修正してみた。ついでに、コンパイラとして clang を使う設定もいれてみた。
既にある物の改造版を AUR にアップして良い物かわからないので、ここに貼り付けておきます。
# Author: NAKASHIMA, Makoto <makoto.nksm@gmail.com>
pkgname=rust-git
pkgver=20120528
pkgrel=1
pkgdesc="A safe, concurrent, practical language from Mozilla."
arch=(i686 x86_64)
url="http://www.rust-lang.org/"
license=('MIT')
depends=('gcc-libs')
makedepends=('git' 'gcc'
'libffi' 'python2' # for LLVM
)
optdepends=('pandoc: to build rust.pdf'
'llnextgen: for build-time grammar verification'
'naturaldocs: to build library doc')
_gitroot="git://github.com/mozilla/rust.git"
_gitname="rust"
build() {
cd "$srcdir"
msg "Connecting to git server...."
if [ -d $_gitname ] ; then
cd $_gitname && git pull origin
git submodule sync
git submodule update --init --recursive
git submodule foreach --recursive git clean -dxf
git submodule foreach --recursive git checkout .
msg "The local files are updated."
else
git clone --recursive $_gitroot $_gitname
cd $_gitname
fi
msg "git checkout done or server timeout"
rm -rf "$srcdir/$_gitname-build"
cp -r "$srcdir/$_gitname" "$srcdir/$_gitname-build"
cd "$srcdir/$_gitname-build"
./configure --prefix=/usr --enable-clang
msg 's/python$/python2/'
find . \
-type f -executable -exec grep -qe 'env python$' '{}' ';' \
-exec sed -i 's/env python$/env python2/' '{}' ';' -print
msg "Starting make..."
make || return 1
}
package() {
mkdir "$pkgdir/usr"
cd "$srcdir/$_gitname-build"
make install DESTDIR="$pkgdir/usr/"
_docdir=$pkgdir/usr/share/doc/rust
mkdir -p "$_docdir"
for _doc in rust.pdf rust.html tutorial.html rust.css core std rust.md ; do
if ! [ -e "doc/$_doc" ] ; then continue ; fi
cp -r "doc/$_doc" "$_docdir/"
chmod -R 644 "$_docdir/$_doc"
chown -R root:root "$_docdir/$_doc"
done
find "$_docdir" -type d -exec chmod 755 '{}' ';'
}
Rust で ProjectEuler #8 ~ #12
Problem 8
入力された数列に含まれる5つの連続した数の積のうち、最大のものを求める問題。
use std; fn main() { const prod_len: uint = 5u; let input = " 73167176531330624919225119674426574742355349194934 96983520312774506326239578318016984801869478851843 85861560789112949495459501737958331952853208805511 12540698747158523863050715693290963295227443043557 66896648950445244523161731856403098711121722383113 62229893423380308135336276614282806444486645238749 30358907296290491560440772390713810515859307960866 70172427121883998797908792274921901699720888093776 65727333001053367881220235421809751254540594752243 52584907711670556013604839586446706324415722155397 53697817977846174064955149290862569321978468622482 83972241375657056057490261407972968652414535100474 82166370484403199890008895243450658541227588666881 16427171479924442928230863465674813919123162824586 17866458359124566529476545682848912883142607690042 24219022671055626321111109370544217506941658960408 07198403850962455444362981230987879927244284909188 84580156166097919133875499200524063689912560717606 05886116467109405077541002256983155200055935729725 71636269561882670428252483600823257530420752963450 "; let nums = vec::filter_map(str::chars(input)) { |c| uint::from_str(str::from_char(c)) }; if (vec::len(nums) < prod_len) { fail; } let max = 0u; uint::range(0u, vec::len(nums) - prod_len) { |i| let prod = 1u; uint::range(0u, prod_len) { |j| prod *= nums[i + j]; } max = uint::max(prod, max); } std::io::println(#fmt("%u", max)); }
まず、str::charsで文字列をcharの配列にして、それに対してvec::filter_mapを呼び出すことで、uint 型の数値の配列に変換しています。vec::filter_mapは配列の各要素に対して、第2引数の関数を呼び出します。関数の戻り値はoption型で、値がsome(x)を返した要素のみからなる新たな配列を生成します。これで改行文字列等を除去した数値のみの配列が得られます。
その後の積の最大値を求める処理は単純です。(0u, 4u) ~ (vec::len(nums) - 5u, vec::len(nums) - 1u)の範囲についてそれぞれ積を求めて、それらの最大値を求めています。対象とする数が十分少ないので、このような単純な方法で十分高速に解を求められます。
Problem 9
和が1000になるピタゴラス数を求める。
use std; fn isqrt(n: u64) -> u64 { let (min, max) = (0u64, n); while min < max { let mid = (min + max + 1u64) / 2u64; if (mid * mid) == n { ret mid; } else if (mid * mid) >= n { max = mid - 1u64; } else { min = mid; } } ret min; } fn find_pyrhagorean(sum: u64) -> [(u64, u64, u64)] { let answer = []; uint::range(2u64, sum - 2u) { |c| uint::range(1u64, uint::min((sum - c) / 2u, isqrt(c*c / 2u))) { |a| let b = sum - c - a; if a * a + b * b == c * c { answer += [(a, b, c)]; } } } ret answer; } fn main() { for (a, b, c) in find_pyrhagorean(1000u) { std::io::println(#fmt("%u^2 + %u^2 = %u^2", a, b, c)); std::io::println(#fmt("prod: %u", a * b * c)); } }
愚直な作りです。,
なので、まず
とおき、
],
]の範囲で動かして、条件を満たすかどうか確かめています。
Problem 10
200万以下の素数の和を求める
use std; fn gen_prime(&primes: [u64]) { let num = alt vec::last(primes) { none { primes = [2u64]; ret } some(2u64) { primes += [3u64]; ret } some(x) { x + 2u64 } }; while true { for p in primes { if p * p > num { primes += [num]; ret; } if num % p == 0u64 { break; } } num += 2u64; } fail; } fn main() { let sum = 0u; let primes = []; while true { gen_prime(primes); let p = vec::last_total(primes); if p >= 2000000u64 { break; } sum += p; } std::io::println(#fmt("%u", sum)); }
200万以下の素数を作って、足しているだけです。
Problem 11
行列の中から、縦、横、対角方向で連続する4つの数の積のうち最大の物を求める
use std; fn find_max_row(row: [uint], prod_len: uint) -> uint { if vec::len(row) < prod_len { ret 0u; } let max = 0u; uint::range(0u, vec::len(row) - prod_len) { |i| let prod = 1u; uint::range(0u, prod_len) { |j| prod *= row[i + j]; } max = uint::max(max, prod); } ret max; } fn find_max_grid(grid: [[uint]], prod_len: uint) -> uint { vec::foldl(0u, grid) { |max, row| uint::max(max, find_max_row(row, prod_len)) } } fn find_max_v(grid: [[uint]], prod_len: uint) -> uint { if vec::is_empty(grid) { ret 0u; } let max = 0u; uint::range(0u, vec::len(grid[0])) { |i| max = uint::max(max, find_max_row(vec::map(grid) { |row| row[i] }, prod_len)); } ret max; } fn find_max_d(grid: [[uint]], prod_len: uint) -> uint { if vec::is_empty(grid) { ret 0u; } let num_row = vec::len(grid); let num_col = vec::len(grid[0]); let max = 0u; int::range(-(num_row as int) + 1, num_col as int) { |i| let tl_br = vec::filter_map(vec::enum_uints(0u, uint::min(num_row, num_col) - 1u)) { |d| let (x, y) = (i + (d as int), d); if x < 0 || x as uint >= num_col || y >= num_row { ret none; } ret some(grid[y][x]); }; max = uint::max(max, find_max_row(tl_br, prod_len)); let bl_tr = vec::filter_map(vec::enum_uints(0u, uint::min(num_row, num_col) - 1u)) { |d| let (x, y) = (d, (num_col as int - 1 - i) - (d as int)); if x >= num_col || y < 0 || y as uint >= num_row { ret none; } ret some(grid[y][x]); }; max = uint::max(max, find_max_row(bl_tr, prod_len)); } ret max; } fn main() { let input = " 08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48 "; let grid = vec::map(str::lines(str::trim(input))) { |row| vec::map(str::split_char(row, ' ')) { |cell| alt uint::from_str(cell) { some(x) { x } none { fail } } } }; let max = find_max_grid(grid, 4u); max = uint::max(max, find_max_v(grid, 4u)); max = uint::max(max, find_max_d(grid, 4u)); std::io::println(#fmt("%u", max)); }
find_max_row関数で1次元配列中の隣接するn要素のうち、最大の積をもつものを求めています。行方向の配列、列方向の配列、対角方向の配列をそれぞれ作ってやって、find_max_row関数に渡してやることで、これらすべての方向に隣接する数値の積の最大値を求めることができます。
Problem 12
三角数のうち、最初に約数の数が500を越える物を求める。
use std; fn gen_triangles(&trigs: [uint]) { alt vec::len(trigs) { 0u { trigs = [1u]; } x { trigs += [trigs[x - 1u] + x + 1u]; } } } fn gen_prime(&primes: [u64]) { let num = alt vec::last(primes) { none { primes = [2u64]; ret } some(2u64) { primes += [3u64]; ret } some(x) { x + 2u64 } }; while true { for p in primes { if p * p > num { primes += [num]; ret; } if num % p == 0u64 { break; } } num += 2u64; } fail; } fn div_mult(&num: u64, f: u64) -> u64 { let exp = 0u64; while (num % f == 0u64) { exp += 1u64; num /= f; } ret exp; } fn factorize(num: u64, &primes: [u64]) -> [(u64, u64)] { let itr = num; let result = []; for p in primes { let exp = div_mult(itr, p); if exp > 0u64 { result += [(p, exp)]; } } while itr != 1u64 { gen_prime(primes); let p = vec::last_total(primes); let exp = div_mult(itr, p); if exp > 0u64 { result += [(p, exp)]; } } ret result; } fn num_factors(num: u64, &primes: [u64]) -> u64 { let facts = factorize(num, primes); ret vec::foldl(1u, facts) { |prod, tuple| let (_base, exp) = tuple; prod * (exp + 1u) }; } fn main() { let trigs = []; let primes = []; while true { gen_triangles(trigs); let t = vec::last_total(trigs); let num = num_factors(t, primes); if num > 500u { std::io::println(#fmt("%u -> %u", t, num_factors(t, primes))); break; } } }
Rust で ProjectEuler #4 ~ #7
Problem 4
3桁の2つの数の積で表せる最大の palindrome な数。
use std; fn to_palindromic(n: u64, dup_flag: bool) -> u64 { let cs = str::chars(u64::to_str(n, 10u)); let s = str::from_chars( if dup_flag { cs + vec::tail(vec::reversed(cs)) } else { cs + vec::reversed(cs) } ); alt u64::from_str(s, 10u) { none { fail } some(x) { ret x } } } fn dividable_pairs(num: u64, min: u64, max: u64) -> [(u64, u64)] { let div = u64::max(uint::div_ceil(num, max), min); let result = []; while div * div <= num { if num % div == 0u64 { result += [(div, num / div)]; } div += 1u64; } ret result; } fn main() { let dup_flag = false; while true { let seed = 999u64; while (seed >= 100u64) { let num = to_palindromic(seed, dup_flag); let pairs = dividable_pairs(num, 100u64, 999u64); if vec::is_not_empty(pairs) { std::io::print(#fmt("%u", num)); for (d1, d2) in pairs { std::io::print(#fmt(" = %u * %u", d1, d2)); } std::io::print("\n"); } seed -= 1u64; } if (!dup_flag) { dup_flag = true; } else { break } } }
最大の数だけじゃなくて、すべての palindrome な数を列挙します。palindrome な数を大きな方から生成していって、3桁の数で割れるかどうか確かめています。特に凝ったことはしていません。
Problem 5
1~20の最小公倍数を求める
use std; fn gen_prime(primes: [u64]) -> [u64] { let num = alt vec::last(primes) { none { ret [2u64] } some(2u64) { ret primes + [3u64] } some(x) { x + 2u64 } }; while true { for p in primes { if p * p > num { ret primes + [num]; } if num % p == 0u64 { break; } } num += 2u64; } fail; } fn div_mult(&num: u64, f: u64) -> u64 { let exp = 0u64; while (num % f == 0u64) { exp += 1u64; num /= f; } ret exp; } fn factorize(num: u64, &primes: [u64]) -> [(u64, u64)] { let itr = num; let result = []; for p in primes { let exp = div_mult(itr, p); if exp > 0u64 { result += [(p, exp)]; } } while itr != 1u64 { primes = gen_prime(primes); let p = vec::last_total(primes); let exp = div_mult(itr, p); if exp > 0u64 { result += [(p, exp)]; } } ret result; } fn merge_fact(fs1: [(u64, u64)], fs2: [(u64, u64)]) -> [(u64, u64)] { let result = []; let i1 = 0u, i2 = 0u; let len1 = vec::len(fs1), len2 = vec::len(fs2); while (i1 < len1 && i2 < len2) { let (base1, exp1) = fs1[i1]; let (base2, exp2) = fs2[i2]; if (base1 < base2) { result += [(base1, exp1)]; i1 += 1u64; } else if (base1 > base2) { result += [(base2, exp2)]; i2 += 1u64; } else { result += [(base1, uint::max(exp1, exp2))]; i1 += 1u64; i2 += 1u64; } } if i1 < len1 { result += vec::slice(fs1, i1, len1); } if i2 < len2 { result += vec::slice(fs2, i2, len2); } ret result; } fn merge_facti(fss: [[(u64, u64)]]) -> [(u64, u64)] { ret alt vec::len(fss) { 0u64 { [] } 1u64 { fss[0] } l { let pre = merge_facti(vec::slice(fss, 0u64, l / 2u64)); let post = merge_facti(vec::slice(fss, l / 2u64, l)); merge_fact(pre, post) } } } fn pow(base: u64, exp: u64) -> u64 { let result = 1u64; let itr = exp; let pow = base; while itr > 0u64 { if itr & 0x1u64 == 0x1u64 { result *= pow; } itr >>= 1u64; pow *= pow; } ret result; } fn fact_to_uint(fs: [(u64, u64)]) -> u64 { let result = 1u64; for (base, exp) in fs { result *= pow(base, exp); } ret result; } fn main() { let primes = []; let factors = vec::map(vec::enum_uints(1u64, 20u64)) { |num| factorize(num, primes) }; std::io::println(#fmt("%u", fact_to_uint(merge_facti(factors)))); }
1〜20の数を素因数分解して、それらの因数をマージして、最後に掛けています。
Problem 6
1~100の数字の「二乗和」と「和の二乗」の差を求める。
use std; fn sum_of_square(n: u64) -> u64 { ret n * (n + 1u64) * (2u64 * n + 1u64) / 6u64; } fn sum_of_seq(n: u64) -> u64 { ret n * (n + 1u64) / 2u64; } fn square_of_sum(n: u64) -> u64 { let s = sum_of_seq(n); ret s * s; } fn main() { let sq_of_sum = square_of_sum(100u64); let sum_of_sq = sum_of_square(100u64); std::io::println(#fmt("%u - %u = %u", sq_of_sum, sum_of_sq, sq_of_sum - sum_of_sq)); }
二乗和には以下の公式を用いました。高校でやりましたね！
Problem 7
1001番目の素数を求める。
use std; use util; fn gen_prime(&primes: [u64]) { let num = alt vec::last(primes) { none { primes = [2u64]; ret } some(2u64) { primes += [3u64]; ret } some(x) { x + 2u64 } }; while true { for p in primes { if p * p > num { primes += [num]; ret; } if num % p == 0u64 { break; } } num += 2u64; } fail; } fn main() { let idx = 10000u64; let primes = []; uint::range(0u64, idx + 1u64) { |_num| gen_prime(primes); } std::io::println(#fmt("%u", primes[idx])); }
Rust で ProjectEuler のレポジトリを github で公開しました
レポジトリ作った。ソースは適宜修正していく予定ですので、最新版はこちらを参照してください。
Rust で ProjectEuler #1 ~ #3
放置状態になっていたProject Eulerを再開してみることにしました。以前はHaskellでProb. 133まで解いてHaskellに慣れることができたので、今回はRustで書いてみようと思います。Haskellは最後まで使いこなせてる感は出なかったのですが、遅延評価ではないRustなら直感的に計算量とか理解できてやりやすいはず…？
というわけで、解いていきます
Problem 1
1000以下の数字で3か5で割り切れるものの和を求める問題。最初なので素直に書いた。
use std; fn main() { let sum = 0u; uint::range(0u, 1000u) { |n| if n % 3u == 0u || n % 5u == 0u { sum += n; } } std::io::println(#fmt("%u", sum)); }
特に特筆事項は無い。
Problem 2
400万以下で偶数のフィボナッチ数の和を求める問題。
use std; pure fn fib(prev: uint, cur: uint) -> (uint, uint) { ret (cur, prev + cur); } fn main() { const MAX: uint = 4000000u; let (prev, cur) = (1u, 1u); let sum = 0u; while cur < MAX { if (cur % 2u == 0u) { sum += cur; } let (prev2, cur2) = fib(prev, cur); prev = prev2; cur = cur2; } std::io::println(#fmt("%u", sum)); }
これも普通ですね。本当は
(prev, cur) = fib(prev, cur);
って書きたかったんですが、少なくとも現時点では、この方法では分割代入はできないみたいです。
Problem 3
600851475143 の最大の素因数を求める問題。
use std; fn gen_prime(primes: [mutable u64]) -> [mutable u64] { let num = alt vec::last(primes) { none { ret [mutable 2u64] } some(2u64) { ret primes + [mutable 3u64] } some(x) { x + 2u64 } }; while true { for p in primes { if p * p > num { ret primes + [mutable num]; } if num % p == 0u64 { break; } } num += 2u64; } fail; } fn main() { let primes = gen_prime([mutable]); let num = 600851475143u64; while num != 1u64 { check vec::is_not_empty(primes); let p = vec::last_total(primes); while num % p == 0u64 { num /= p; std::io::println(#fmt("%u", p)); } primes = gen_prime(primes); } }
エラトステネスの篩で素数リストを作って、先頭から割っていっています。
二分探索がうまく動かなくて何度も書き直したのはここだけの秘密。境界条件はちゃんと考えてから書かないとだめですね。
とりあえず、最初のエントリはここまで。これからどんどんエントリ立てて行く予定。専用ブログ作ってもいいのかも。
