Hatena::Groupactionscript

nitoyon.dispatchEvent(null)

|

2010-04-11

Project Euler #31

| 02:45 | Project Euler #31 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #31 - nitoyon.dispatchEvent(null)

英国で200ペンスを払うのに支払う硬貨のパターンは何通りあるか、という問題。

このあたりからアルゴリズムに工夫をしないと解けない問題が増えてきてる。硬貨の種類を増やしつつ DP で計算した。

package{
import flash.display.Sprite;
import flash.text.TextField;

public class Problem31 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private var coins:Array = [1, 2, 5, 10, 20, 50, 100, 200];

    public function Problem31(){
        var a:Array = [];
        for (var i:int = 0; i <= 200; i++) { a[i] = 0; }
        a[0] = 1;

        for (var j:int = 0; j < coins.length; j++) {
            var coin:int = coins[j];
            for (var i:int = 1; i <= 200; i++) {
                if (i - coin >= 0) {
                    a[i] += a[i - coin];
                }
            }
        }
        t.text = a[200];
    }
}
}

2010-04-03

Project Euler #39

| 12:35 | Project Euler #39 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #39 - nitoyon.dispatchEvent(null)

p を直角三角形の3辺が整数となるもの周囲の長さとしたとき、たとえば p が 120 としたら取りうる値は {20,48,52}, {24,45,51}, {30,40,50} の3つである。p <= 1000 のとき、解の個数を最大化するような p はいくつか?

三辺 {a, b, c} のうちの2つを固定して三平方の定理で残り1つを求めて整数かどうか調べるだけ。a, b を固定するか a, c を固定するのが楽そうだが、ここでは a, b を固定する方法を選択した。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem39 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    
    public function Problem39(){
        var a:int = 1;
        var max:int = 0;
        var result:int = 0;
        var solutions:Array = [];
        setTimeout(function():void {
            for (var b:int = a; b <= (1000 - a) / 2; b++) {
                var cc:Number = Math.sqrt(a * a + b * b);
                if (cc == Math.floor(cc)) {
                    var p:int = a + b + cc;
                    if (p > 1000) continue;
                    solutions[p] = isNaN(solutions[p]) ? 1 : solutions[p] + 1;
                    if (max < solutions[p]) {
                        max = solutions[p];
                        result = p;
                    }
                }
            }

            t.text = "calculating... " + a + "\n" + result;

            if (a <= 333) {
                a++;
                setTimeout(arguments.callee, 10);
            } else {
                t.text = result.toString();
            }
        }, 10);
    }
}
}

Project Euler #42

| 13:17 | Project Euler #42 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #42 - nitoyon.dispatchEvent(null)

単語アルファベット順を足した数が、数列 t(n)=1/2*n*(n+1) に存在するかどうか。あらかじめ t(n) を求めておいてもいいのだけど、ちょっと工夫して数列に含まれるか求める関数を作った。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem42 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    
    public function Problem42(){
        var n:int = 0;
        var result:int = 0;
        setTimeout(function():void {
            for (var i:int = 0; i < 1000; i++) {
                if (n >= words.length) {
                    t.text = result.toString();
                    return;
                }
                if (isTriangleWord(words[n])) result++;
                n++;
            }
            t.text = "calculating " + n + "\n" + result;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function isTriangleWord(w:String):Boolean {
        var n:int = 0;
        for each (var c:String in w.split("")) {
            n += c.charCodeAt(0) - "A".charCodeAt(0) + 1;
        }
        return isTriangleNumber(n);
    }

    // t = 1/2*n*(n+1)
    // sqrt(t * 2) = sqrt(n*(n + 1)) > sqrt(n*n) = n
    private function isTriangleNumber(n:int):Boolean {
        var m:int = Math.floor(Math.sqrt(n * 2));
        return m * (m + 1) / 2 == n || (m - 1) * m / 2 == n;
    }

    private var words:Array = ["A","ABILITY" /* Embed words.txt here */];
}
}

Project Euler #45

| 13:42 | Project Euler #45 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #45 - nitoyon.dispatchEvent(null)

Triangle Number, Pentagonal Number, Hexagonal Number に共通する数字を探せ、という問題。3つの数の n を小さいものから増やしていく、という手法で解いた。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem45 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Problem45(){
        var n1:int = 286, n2:int = 166, n3:int = 144;
        setTimeout(function():void {
            for (var i:int = 0; i < 100; i++) {
                var tn:int = n1 * (n1 + 1) / 2;
                var pn:int = n2 * (3 * n2 - 1) / 2;
                var hn:int = n3 * (2 * n3 - 1);
                var min:int = Math.min(Math.min(tn, pn), hn);

                if (tn == pn && pn == hn) {
                    t.text = tn.toString();
                    return;
                } else if (tn == min) {
                    n1++;
                } else if (pn == min) {
                    n2++;
                } else {
                    n3++;
                }
            }

            t.text = "calculating\n" + n1 + "\n" + n2 + "\n" + n3;
            setTimeout(arguments.callee, 10);
        }, 10);
    }
}
}

2010-04-02

Project Euler #35

| 09:40 | Project Euler #35 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #35 - nitoyon.dispatchEvent(null)

197, 971, 719 のようにサイクルした全ての数が素数になるものは100万以下にいくつあるか、という問題。

素直に素数を列挙して、調べていけばよいだけ。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem35 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private var primes:Array = [];
    private var isPrime:Object;
    private var N:int = 1000000;
    
    public function Problem35(){
        enumPrime();
    }

    private function doit():void {
        var result:int = 0;
        for (var i:int = 0; i < primes.length; i++) {
            var n:int = primes[i];
            var s:String = n.toString();

            for (var j:int = 0; j < s.length - 1; j++) {
                s = s.substr(1) + s.charAt(0);
                if (!isPrime[parseInt(s, 10)]) break;
            }
            if (j == s.length - 1) result++;
        }

        t.text = result.toString();
    }

    private function enumPrime():void {
        var n:int = 5;
        var isNotPrime:Array = [];
        primes = [2, 3];
        isPrime = {2: true, 3: true};
        setTimeout(function():void {
            var c:int = 0;
            for (var j:int = 0; j < 2000; j++) {
                if (n % 2 != 0 && n % 3 != 0 && !isNotPrime[n]) {
                    primes.push(n);
                    isPrime[n] = true;
                    for (var i:int = n * 2; i < N; i += n) {
                        isNotPrime[i] = true;
                        c++;
                    }
                }
                n += 2;
                if (c > 10000 || n >= N) break;
            }

            if (n < N) {
                t.text = "check prime " + n + "...";
                setTimeout(arguments.callee, 10);
            } else {
                doit();
            }
        }, 10);
    }
}
}

Project Euler #40

| 01:44 | Project Euler #40 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #40 - nitoyon.dispatchEvent(null)

0.12345678910111213... のような1から順番に整数を並べていった無理数の1,10,100,...100,000番目の数をかけたらいくつになるか、という問題。

多少めんどくさいが、まじめに求めて行った。

package{
import flash.display.Sprite;
import flash.text.TextField;
import flash.utils.setTimeout;

public class Problem40 extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    
    public function Problem40(){
        var pos:int = 0;
        var result:int = 1;
        var n:int = 1;
        var d:int = 1;
        var nums:Array = [];
        setTimeout(function():void {
            for (var i:int = 0; i < 1000; i++) {
                var newpos:int = pos + n.toString().length;
                if (newpos >= d) {
                    var num:int = parseInt(n.toString().charAt(d - pos - 1), 10);
                    nums.push(num);
                    result *= num;
                    if (d == 1000000) {
                        t.text = result.toString() + "\n" + nums.join("\n");
                        return;
                    }
                    d *= 10;
                }

                pos = newpos;
                n++;
            }

            t.text = "calculating...\n" + n + "\n" + d;
            setTimeout(arguments.callee, 10);
        }, 10);
    }
}
}

2010-04-01

Project Euler #34

| 01:24 | Project Euler #34 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #34 - nitoyon.dispatchEvent(null)

145 以外の解が見つからずに困っていたが、0! = 1 であることを思い出して再計算させたらもう1つ見つかった。submit して正解。長かった。

package{
    import flash.display.Sprite;
    import flash.text.TextField;
    import flash.utils.setTimeout;
    
    public class Problem34 extends Sprite{
        private var t:TextField = TextField(addChild(new TextField()));
        
        public function Problem34(){
            var a:Array = [1, 1];
            for (var i:int = 2; i < 10; i++) {
                a[i] = a[i - 1] * i;
            }

            var n:int = 3;
            var result:Array = [];
            var total:int = 0;
            setTimeout(function():void {
                for (i = 0; i < 1000; i++) {
                    if (n > 1000000) { // 1000000 > 9!*6
                        t.text = total + "";
                        return;
                    }
                    
                    var tmp:int = n;
                    var sum:int = 0;
                    while (tmp > 0) {
                        sum += a[tmp % 10];
                        tmp /= 10;
                    }

                    if (sum == n) {
                        result.push(n);
                        total += n;
                    }

                    n++;
                }

                t.text = "calculating " + n + "\n" + result.join("\n");
                setTimeout(arguments.callee, 10);
            }, 10);
        }
    }
}

2010-03-27

Project Euler #30

| 17:42 | Project Euler #30 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #30 - nitoyon.dispatchEvent(null)

各桁を5乗して足した値が元の値が同じになる値を求めましょう、という問題。

解を満たすものが 1000000 までだと信じて列挙して、足し合わせて正解。

package{
import flash.display.Sprite;
import flash.text.*;
import flash.utils.setTimeout;

public class Eular extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Eular() {
        var result:int = 1;

        var n:int = 10;
        var digits:Array = [];
        setTimeout(function():void {
            for (var i:int = 0; i < 1000; i++) {
                if (n > 1000000) {
                    var a:int = 0;
                    for each (var i:int in digits) {
                        a += i;
                    }
                    t.text = a.toString();
                    return;
                }

                var sum:int = 0;
                var num:int = n;
                while (num != 0) {
                    sum += Math.pow(num % 10, 5);
                    num /= 10;
                }
                if (sum == n) {
                    digits.push(sum);
                    t.text = digits.join("\n");
                }

                n++;
            }

            t.text = "calclating: " + n + "\n" + digits.join("\n");
            setTimeout(arguments.callee, 10);
        }, 10);
    }
}
}

Project Euler #36

| 17:55 | Project Euler #36 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #36 - nitoyon.dispatchEvent(null)

10進数と2進数で左右対称な数字(100万以下)の和を求めよ、という問題。

ま、普通に求める。

package{
import flash.display.Sprite;
import flash.text.*;
import flash.utils.setTimeout;

public class Eular extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));

    public function Eular() {
        var result:int = 0;

        var n:int = 1;
        setTimeout(function():void {
            for (var i:int = 0; i < 1000; i++) {
                if (n > 1000000) {
                    t.text = result.toString();
                    return;
                }

                if (isPalindromic(n.toString()) && isPalindromic(n.toString(2))) {
                    result += n;
                }

                n++;
            }

            t.text = "calclating: " + n + "\n" + result;
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function isPalindromic(s:String):Boolean {
        return s.split("").reverse().join("") == s;
    }
}
}

Project Euler #37

| 21:22 | Project Euler #37 - nitoyon.dispatchEvent(null) を含むブックマーク はてなブックマーク - Project Euler #37 - nitoyon.dispatchEvent(null)

素数のうち左と右の両方から truncate したものも全て素数である数 11 個を求めよ、という問題。23 とか 3797 とか。

100万以上の素数を探索するように実装したが、解は全て100万以内だった。

package{
import flash.display.Sprite;
import flash.text.*;
import flash.utils.setTimeout;

public class Eular extends Sprite{
    private var t:TextField = TextField(addChild(new TextField()));
    private const N:int = 1000000;

    private var primes:Array = [];
    private var _isPrime:Object = {};

    public function Eular() {
        enumPrime();
    }

    private function enumPrime():void {
        var n:int = 5;
        var isNotPrime:Array = [];
        primes = [2, 3];
        _isPrime = {2: true, 3: true};
        setTimeout(function():void {
            var c:int = 0;
            for (var j:int = 0; j < 2000; j++) {
                if (n % 2 != 0 && n % 3 != 0 && !isNotPrime[n]) {
                    primes.push(n);
                    _isPrime[n] = true;
                    for (var i:int = n * 2; i < N; i += n) {
                        isNotPrime[i] = true;
                        c++;
                    }
                }
                n += 2;
                if (c > 10000 || n >= N) break;
            }

            if (n < N) {
                t.text = "check prime " + n + "...";
                setTimeout(arguments.callee, 10);
            } else {
                doit();
            }
        }, 10);
    }

    private function doit():void {
        var result:Array = [];
        var sum:int = 0;
        var index:int = 0;
        var num:int = primes[primes.length - 1] + 1;

        setTimeout(function():void {
            var n:int;
            for (var j:int = 0; j < 1000; j++){
                if (index >= primes.length) {
                    // solved
                    if (result.length >= 11) {
                        t.text = sum.toString() + "\n" + result.join("\n");
                        return;
                    }

                    // over N
                    n = num++;
                    if (!isPrime(n)) continue;
                } else {
                    n = primes[index];
                    index++;
                }

                if (n < 10) continue;

                var s:String = n.toString();
                for (var i:int = 1; i < s.length; i++) {
                    var s2:String = s.substr(0, i);
                    var n2:int = parseInt(s2, 10);
                    if (!isPrime(n2)) break;

                    s2 = s.substr(i);
                    n2 = parseInt(s2, 10);
                    if (!isPrime(n2)) break;
                }

                if (i == s.length) {
                    result.push(n);
                    sum += n;
                }
            }

            t.text = "checking " + n + "\n" + result.join("\n");
            setTimeout(arguments.callee, 10);
        }, 10);
    }

    private function isPrime(n:int):Boolean {
        if (n < N) return _isPrime[n] == true;

        for each (var prime:int in primes) {
            if (n % prime == 0) return false;
        }
        return true;
    }
}
}
|