2018年01月16日

言語処理100本ノックでPython入門 #03 - 正規表現, リスト内包表記

   このエントリーをはてなブックマークに追加 Clip to Evernote

今日は、言語処理100本ノックの問題03です。

■ 問題

03. 円周率
"Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."

という文を単語に分解し,各単語の(アルファベットの)文字数を先頭から出現順に並べたリストを作成せよ.

■ 初めに書いたコード

import re
text = "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics." array = re.split(r'\s|,|\.', text) for s in filter(lambda w: len(w) > 0, array): print(len(s))

■ 次に書いたコード

import re
text = "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics." array = re.split(r'\s|,|\.', text) lens = [len(s) for s in filter(lambda w: len(w) > 0, array)] print(lens)

■ 最終版のコード

import re
text = "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics." array = re.split(r'\s|,|\.', text) lens = [len(x) for x in array if len(x) > 0] print(lens)

■ 最終版の実行結果

[3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9]

■ 今回学習したこと
 

正規表現の機能を使うには、
import re
と importします。

spliteメソッドで、分割できます。C#にも似たようなメソッドありますし、どの言語にもこういった機能は用意されてるんですね。
text = "Now I need a drink, alcoholic of course, after the heavy lectures involving quantum mechanics."
array = re.split(r'\s|,|\.', text)
r'\s|,|\.' が正規表現です。 'r' を前置した文字列リテラルではバックスラッシュを特別扱いしません。
C#の@”..."と同じです。

filter関数は、C#のWhereと同じですね。でもラムダ式書くのが面倒ですね。
for s in filter(lambda w: len(w) > 0, array):
    print(len(s))
これで、空文字を省いてくれます。

リスト内包表現使うと、さらに簡潔に書けます。
lens = [len(s) for s in filter(lambda w: len(w) > 0, array)]
でも、if を使うともっと簡単に書けました。
items = [x for x in array if len(x) > 0]
ちなみに、リスト内包表現のもっとも基本的な書き方は、
lens = [len(x) for x in items]
といった写像処理ですね。

以前、HaskellやF#をすこし勉強したので、リスト内包表現は意外と違和感なく使えました。

でもpythonのラムダ式、これはC#の方が良いですね。アロー式が使えればもっと簡単に書けるのにね。  

Posted by gushwell at 21:30Comments(0)Python

2018年01月14日

言語処理100本ノックでPython入門 #02 - for, zip, enumerate

   このエントリーをはてなブックマークに追加 Clip to Evernote

言語処理100本ノックの問題02をやりました。

■問題


第1章: 準備運動

02. 「パトカー」+「タクシー」=「パタトクカシーー」
「パトカー」+「タクシー」の文字を先頭から交互に連結して文字列「パタトクカシーー」を得よ.

■書いたコード

s1 = 'パトカー'
s2 = 'タクシー'
s3 = ""
for a, b in zip(s1, s2):
    s3 += a + b
print(s3)

■実行結果

パタトクカシーー

■今回学習したこと


文字列は、シングルクォートで括ってもOK.
実際に、ここ(https://docs.python.jp/3/reference/index.html)を見たら確かにそう書いてありました。

この問題は、C#だったらLINQのZipメソッド使う場面ですね。Zipと似たような機能がないかな〜と探したらありました。

zip関数をfor文とともに使えば、2つのシーケンスから同時に値を取り出すことができます。これ、めちゃくちゃ便利ですね。
pythonのfor文は、C#でいうとforeachにあたるんですね。

実は、初めに書いたのは、以下のようなコード
s1 = 'パトカー'
s2 = 'タクシー'
s3 = ""
for i, e in enumerate(s1):
    s3 += e + s2[i]
print(s3)

zip関数ではなく、enumerate関数使ってます。 こうすると、文字列を1文字ずつ列挙するとともに、インデックスもあわせて列挙できます。
これはこれで便利な機能ですね。どこかで使えそうです。

ちなみに、以下のように書けば、s1から1文字ずつ文字を取り出せます。
for e in s1:
    print(e)

これが、pythonのfor文の基本ですね。

じゃあ、C#でいう普通のfor文はどうやって書くのかなと思ったら、そのような構文は無いみたいです。
どうしても必要ならば、range関数でシーケンスを生成すればOK.
for i in range(10):
    print(i)

これで、0から9までを列挙できます。
次のように書けば、1から9までを列挙できます。

for i in range(1, 10): print(i)

次のような書き方もできます。これでも、s1の中の文字を1文字ずつ列挙できます。
for i in range(len(s1)):
    print(s1[i])

でもこのコードは、以下のように「enumerate使ってね」と警告がでます。pylint良くできてますね。
message: 'C0200:Consider using enumerate instead of iterating with range and len'

今回はいろんなことを学習できました。  
Posted by gushwell at 21:30Comments(0)Python

2018年01月10日

言語処理100本ノックでPython入門 #01 - スライス

   このエントリーをはてなブックマークに追加 Clip to Evernote

言語処理100本ノックのNo01の問題を解きます。

■問題

第1章: 準備運動
01. 「パタトクカシーー」
「パタトクカシーー」という文字列の1,3,5,7文字目を取り出して連結した文字列を得よ.

No00 でやったスライス機能使えばいいんですね。


■コード

s = "パタトクカシーー"
rev = s[::2]
print(rev)
上のコードのように、stepの指定を2にすれば、一つ置きに取り出せます。 デフォルトは1です。


■結果

パトカー

ちなみに、

rev = s[1::2]
print(rev)
とすれば、開始位置が0ではなく、1になるので、以下の結果が得られます。
タクシー


■今回学習したこと
 

特になし。No00で解いた時に学んだ内容で解けました。  
Posted by gushwell at 20:14Comments(0)Python

2018年01月07日

言語処理100本ノックでPython入門 #00 - スライス

   このエントリーをはてなブックマークに追加 Clip to Evernote

Pythonの勉強をしようと思い立ち、しばらく放置していたブログを再開したいと思います。 TypeScript、PythonとC#以外の話題が続いているので、ブログ名からC#とりました。

題材は、言語処理100本ノックの問題を一つずつ解いていこうというもの。 Visual Studio Codeを使いますが、環境設定方法はいろんな方が説明しているので省略します。

今回チャレンジするのは、第1章: 準備運動の第0問です。
第1章: 準備運動

00. 文字列の逆順
文字列"stressed"の文字を逆に(末尾から先頭に向かって)並べた文字列を得よ.


■書いたコード
s = "stressed"
rev = s[::-1]
print(rev)

■今回学習したこと

Pythonは、クラスやMainメソッドとか書かずにいきなりコードを書けます。
変数を宣言するのに型を指定する必要はありません。varや let も不要でいきなり変数を初期化すればOK。

s = "stressed"

C#と随分と違う感じ。

文字列を逆順にするには、Pythonのスライス機能を使います。

s = "stressed"
rev = s[::-1]

コンソールに出力するにはprint関数。

print(rev)

でも、これで実行しようとすると、pylint から以下のメッセージが出力されます。
C0103:Invalid module name "0"
C0111:Missing module docstring
C0103:Invalid constant name "s"
C0103:Invalid constant name "rev"
最初の1行が意味がよく分からないです。 2行目は、先頭に以下のようなdocstringが必要ということらしい。
"""
ここに説明文
"""
3行目、4行目は、定数は小文字で始めるなということのようです。英大文字で使ってね、ということらしいけど、多くのサイト見てみたけどほとんど小文字です。なので小文字のまま行こうと思います。 ということで、VSCodeの設定で、'C0103' を無視するように設定します。
"python.linting.pylintArgs": [
      "--disable=C0103"
],
以下のように複数指定することもできます。
"python.linting.pylintArgs": [
      "--disable=C0111,C0103"
],
今回は、両方指定しておくことにします。 この設定を入れたので、当たり前だけど、意味不明だった以下の警告も消えました。
C0103:Invalid module name "0"
その後、いろいろ試してみてわかったのは、module nameがファイル名と関係しているらしいということ。 

ファイル名を `p100.0.py` としていたんですよね。`.0` というのが良くなかったようです。 これを`p100.py` とすれば、消えました。 pythonは、ファイル名がモジュール名と密接に結びついているんですね。

でも、今回はこれを無視して、p100.0.py, p100.1.py, p100.2.py とファイル名を付けていこうと思います。 Visual Studio Codeのエクスプローラーでファイルをコピーすると、勝手にこのように連番を振ってくれるので楽なんですよね。

■スライス機能について

スライス機能は、一部分を取り出したり、逆順に取り出したり、一つおきに取り出したりといろんなことができます。
[開始位置:終了位置:ステップ]という指定をするのですが、マイナス値を指定できて、これが面白い動きをしれくれます。

試しにこんなコードを書いて見ました。

s = "0123456789"
print(s[1:4:1])
print(s[2:6])
print(s[2:12])
print(s[:6:])
print(s[0::2])
print(s[-1::1])
print(s[4::-1])
print(s[-3:])
print(s[-4:-1])
print(s[1:-1])
print(s[:-1])
print(s[:100])
print(s[-100:])

結果は、以下の通りです。     
123
2345
23456789
012345
02468
9
43210
789
678
12345678
012345678
0123456789
0123456789
  
Posted by gushwell at 21:30Comments(0)Python

2017年04月18日

TypeScriptでProject Euler #21 「友愛数」

   このエントリーをはてなブックマークに追加 Clip to Evernote


昨年の12月からTypeScriptでProjectEulerを解く記事を書き続けてきましたが、 当初の目標の10問をクリアし、その倍の問題を解いたので、そろそろ、このProjectEulerの挑戦も終わりにしたいと思います。 ということで、これが最後の問題です。

問題

d(n) を n の真の約数の和と定義する. (真の約数とは n 以外の約数のことである. ) もし, d(a) = b かつ d(b) = a (a ≠ b のとき) を満たすとき, a と b は友愛数(親和数)であるという.

例えば, 220 の約数は 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 なので d(220) = 284 である. また, 284 の約数は 1, 2, 4, 71, 142 なので d(284) = 220 である.

それでは10000未満の友愛数の和を求めよ.

   Project Euler日本語翻訳サイト から引用


約数を求めるDivisorsクラスを定義する

約数を求めるメソッドは、Divisorsクラスを作成し、その静的メソッドとして作成。 この手のメソッド書くときに迷うのが、TypeScriptの場合は、クラスではなく、単独の関数でも良いのかなということ。

名前空間に適切な名前を付ければ、そのほうが良いのかもしれないなーとは思いつつ、 C#erの僕は、クラスにすることを選択。

export class Divisors {
    // 約数を求める (自分自身は含めない)
    public static get(num: number): number[] {
        let ary = [];
        let m = Math.floor(num / 2);
        for (let n = 1; n <= m; n++) {
            if (num % n === 0) {
                ary.push(n);
            }
        }
        return ary;
    }
}


友愛数を求める

このメソッドができれば、友愛数を求めるのはそれほど難しくありませんね。

import * as Utils from './utils';
import { Divisors } from './math/divisors';


class Solver {
    exec(num: number): number {
        return this.amicableNumbers(num).map(x => x[0] + x[1]).reduce((x, y) => x + y,0);
    }

    // n 未満の友愛数のペアを列挙する
    private amicableNumbers(n: number): [number,number][] {
        var amicables = [];
        for (let a = 1; a < n; a++) {
            let temp = Divisors.get(a);
            let d = temp.reduce((x, y) => x + y,0);
            if (a >= d)
                continue;
            let y = Divisors.get(d).reduce((x, y) => x + y,0);
            if (a == y)
                amicables.push([a, d]);
        }
        return amicables;
    }
}


class Application {
    static run(): void {
        let sw = Utils.Stopwatch.startNew();
        try {
            let p = new Solver();
            let n = p.exec(10000);
            console.log(n);
        } finally {
            sw.stop();
            console.log(sw.toString());
        } 
    }
}

Application.run();
[number,number]

というのは、数値の要素を2つ持つオブジェクトという意味。 TypeScriptだと、これをタプルと言うらしいです。 まあ、実態は配列だけどね。

amicableNumbers メソッドでは、このタプルの配列を返しています。

なお、reduceの第2引数に 0 を与えていますが、これがないと例外が発生します。 JavaScriptのreduceは、第2引数が無いと、要素の数が 0 の時に例外が発生するんですね。 この第2引数は、reduceをする際の初期値を与えます。

最初は、第2引数与えななったので、例外が発生して、あれっなんで? ってちょっと悩んでしまいました。 よくよく考えると、「要素数ゼロの時は、何返したらいいかわからないよね、だから例外出すよ!」 ということで、至極当たり前の仕様ですね。

実行時間は、400ミリ秒でした。約数求めるところが効率悪いですから、まあ想定の範囲内です。


高速化する

Divisors.getメソッドをちょっと改良してみました。

export class Divisors {
    // 約数を求める (自分自身は含めない)
    public static get(num: number): number[] {
        let ary = [];
        if (num == 1)
            return ary;
        ary.push(1);
        let m = Math.floor(Math.sqrt(num));
        if (m * m === num) {
            ary.push(m);
            m--;
        }
        for (let i = 2; i <= m; i++) {
            if (num % i === 0) {
                ary.push(i);
                ary.push(Math.floor(num / i));
            }
        }
        return ary;
    }

}

かなりごちゃごちゃしたコードになりましたが、計算量が格段に減ってます。 これで、39ミリ秒まで速くすることができました。10倍の高速化です。

素因数分解から求めるという方法もあるのかもしれませんが、これで十分でしょう。


※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)TypeScript

2017年04月17日

TypeScriptでProject Euler #20 「各位の数字の和 2」

   このエントリーをはてなブックマークに追加 Clip to Evernote


問題

n × (n - 1) × ... × 3 × 2 × 1 を n! と表す.

例えば, 10! = 10 × 9 × ... × 3 × 2 × 1 = 3628800 となる. この数の各桁の合計は 3 + 6 + 2 + 8 + 8 + 0 + 0 = 27 である.

では, 100! の各位の数字の和を求めよ.

注: Problem 16 も各位の数字の和に関する問題です。解いていない方は解いてみてください。

   Project Euler日本語翻訳サイト から引用


BigUIntクラスを定義する

とうとう BigInt クラスを作る時が来たようです。 今回の問題では、BigInt * int が計算できれば良いのですが、 思い切って、BigInt * BigInt ができるクラスとしました。

なお、負の数は扱えないので、クラス名を BigUInt にしています。 加算と乗算だけの実装です。 減算、除算は実装していません。

const Fig: number = 10000000;
const Format: string = "000000";
const SliceNum: number = -7;

export class BigUInt {
    private list: number[] = [];
    constructor(n: number) {
        let i = 0;
        while (n > 0) {
            this.list[i] = n % Fig;
            n = Math.floor(n / Fig);
            i++;
        }
    }
    private create(src: number[]): BigUInt {
        var obj = new BigUInt(0);
        obj.list = src;
        return obj;
    }
    public clone(): BigUInt {
        var obj = new BigUInt(0);
        for (var i = 0; i < this.list.length; i++)
            obj.list[i] = this.list[i];
        return obj;
    }
    public add(num: BigUInt): BigUInt {
        let sum: number[] = [];
        let carry = 0;
        if (this.list.length > num.list.length) {
            var a = this.list;
            var b = num.list;
        } else {
            var a = num.list;
            var b = this.list;
        }
        for (var i = 0; i < a.length; i++) {
            if (i < b.length)
                var n = a[i] + b[i] + carry;
            else
                var n = a[i] + carry;
            sum[i] = n % Fig;
            carry = Math.floor(n / Fig);
        }
        if (carry > 0)
            sum[i] = carry;
        return this.create(sum);
    }
    public multiple(num: BigUInt): BigUInt {
        let ans = new BigUInt(0);
        let wrk: number[] = [];
        let a = this.list;
        let b = num.list;
        for (let ax = 0; ax < a.length; ax++) {
            for (let i = 0; i < ax; i++)
                wrk[i] = 0;
            let carry = 0;
            for (var bx = 0; bx < b.length; bx++) {
                var n = a[ax] * b[bx] + carry;
                wrk[bx + ax] = n % Fig;
                carry = Math.floor(n / Fig);
            }
            wrk[bx+ax] = carry;
            let w = this.create(wrk);
            ans = ans.add(w);
        }
        return ans;
    }
    public toString() {
        var s: string = "";
        for (var i = this.list.length - 1; i >= 0; i--) {
            var n = this.list[i];
            s += (Format + n).slice(SliceNum);
        }
        return s.replace(/^0+/g, '');
    }
}


BigUIntクラスを使って問題を解く

BigUInt クラスができれば、100! を求めるのは、ロジック的には、int での計算と変わらないですね。 このBigUIntを使って、以下のようなコードを書きました。 答えはあっているので、この BigUIntは、いちおう正しく動いているようです。

import * as Utils from './utils';
import { BigUInt } from './math/bigUInt';


class Solver {
    exec(maxnum: number): number {
        var a = new BigUInt(1);
        for (var i = 2; i <= maxnum; i++) {
            a = a.multiple(new BigUInt(i));
        }
        return a.toString().split("")
            .map(x => parseInt(x))
            .reduce((x, y) => x + y);
    }
}



class Application {
    static run(): void {
        let sw = Utils.Stopwatch.startNew();
        try {
            let p = new Solver();
            let n = p.exec(100);
            console.log(n);
        } finally {
            sw.stop();
            console.log(sw.toString());
        } 
    }
}

Application.run();

※Stopwatchクラスについては、「TypeScriptでProject Euler #0」 を見てください。

  
Posted by gushwell at 22:00Comments(0)TrackBack(0)TypeScript